如何并行执行自定义函数公式，同时保持 Google Sheet 可共享且无需许可？
How to parallelize execution of a custom function formula while keeping the Google Sheet shareable and permissionless?
我有一个带有自定义函数公式的 Google Sheet：从电子表格中获取一个矩阵和两个向量，进行一些冗长的 matrix-vector 计算（>30 秒，所以超出配额)，然后将结果输出为一堆行。它是 single-threaded，因为那是 Google Apps 脚本 (GAS) 的本机，但我想使用 multi-threading 解决方法并行计算，因此它大大加快了速度。
要求（1-3）：
UX：它应该 运行 自动和反应地计算作为自定义函数公式，这意味着用户不必通过单击 运行 按钮或类似按钮手动启动它。就像我目前的 single-threaded 版本一样。
Parallelizable：理想情况下，它应该产生 ~30 threads/processes，这样就不会像现在那样花费 >30 秒（这使得它由于 Google 的 quota limit) 而超时，应该需要 ~1 秒。 （我知道 GAS 是 single-threaded，但有一些变通方法，参考如下）。
可共享性：理想情况下，我应该能够与其他人共享 Sheet，这样他们就可以“复制”它，并且脚本仍将 运行 为它们进行计算：
- 3.1 Permissionless：无需我手动向用户分发个人权限（无许可）。例如，每当有人“复制”和 "Execute the app as user accessing the web app"。我的初步测试表明这是可能的。
- 3.2 Non-intrusive：电子表格的用户无需给予 侵入性 授权，例如“给予此 spreadsheet/script/app 访问您的整个 Google 云端硬盘或 Gmail 帐户？”。用户必须向 script/webapp 授予 non-intrusive 授权是可以接受的，只要仍然保持要求 3.1。
- 3.3 UX：不强制用户查看电子表格中的 HTML 边栏。
我已经阅读了@TheMaster 的，其中概述了在Google Apps 脚本中解决并行化的一些潜在方法。解决方法 #3 google.script.run 和解决方法 #4 UrlFetchApp.fetchAll（均使用 Google Web 应用程序）看起来最有希望。但是有些细节我不知道，比如他们是否可以通过 sub-requirements.
来满足要求 1 和 3
我可以想到另一个潜在的简单解决方法，即将函数拆分为几个自定义函数公式，并在电子表格本身（存储中间结果）中进行并行化（通过某种 Map/Reduce）回到电子表格，并让自定义函数公式作为缩减器工作）。但就我而言，这是不希望的，而且可能不可行。
我非常有信心我的函数可以使用某种 Map/Reduce 进程并行化。该函数目前通过执行所有计算 in-memory 进行了优化，而无需触及电子表格 in-between 步骤，然后最终将结果输出到电子表格。它的细节非常复杂，超过 100 行，所以我不想让您负担更多（并且可能令人困惑）的信息，这些信息不会真正影响本案例的一般适用性。对于这个问题的上下文，您可以假设我的函数是可并行化的（并且 map-reduce'able），或者考虑您已经知道的任何函数。有趣的是，通常可以通过 Google Apps 脚本中的并行化来实现，同时还保持最高级别的可共享性和 UX。如果需要，我会用更多细节更新这个问题。
2020-06-19 更新：
更清楚地说，我不完全排除 Google Web 应用程序的变通办法，因为我没有了解它们的实际限制的经验，无法确定它们是否可以在要求范围内解决问题。我已经更新了 sub-requirements 3.1 和 3.2 以反映这一点。我还添加了 sub-req 3.3，以更清楚地说明意图。我还删除了请求 4，因为它与请求 1 大部分重叠。
我也编辑了问题并删除了相关的sub-questions，所以它更侧重于标题中的单一主要HOWTO-question。我的问题中的要求应该提供一个明确的 objective 标准，哪些答案将被认为是最好的。
我意识到这个问题可能需要寻找 Google Sheet 多线程解决方法的圣杯，正如@TheMaster 私下指出的那样。理想情况下，Google 将提供一项或多项功能来支持多线程、map-reduce 或更多无权限共享。但在那之前，我真的很想知道在我们当前的限制条件下，最佳解决方法是什么。我希望这个问题也与其他人相关，即使考虑到严格的要求。
如果您使用“任何人，甚至匿名”发布网络应用程序，以“我”身份执行，则自定义函数可以使用 UrlFetchApp.fetchAllAuthorization not needed to post to that web-app. This will run in parallelproof。这解决了所有三个要求。
这里要注意的是：如果多个人使用 sheet，自定义函数将不得不 post 到“相同的”webapp（你发布的和你一样执行的）进行处理， Google 将限制同时执行quota limit:30.
要解决此问题，您可以要求使用您 sheet 的人发布他们自己的网络应用程序。他们必须在开始时执行一次，并且不需要授权。
如果没有，您将需要为负载托管一个自定义服务器，或者 google-cloud-functions 之类的东西可能会有所帮助
我最终使用了我在post中提到的天真的解决方法：
I can conceive of an other potential naïve workaround which would be
to split the function up into several custom functions formulas and do
the parallelization (by some kind of Map/Reduce) inside the
spreadsheet itself (storing intermediary results back into the
spreadsheet, and having custom function formulas work on that as
reducers). But that's undesired, and probably unfeasible, in my case.
我最初忽略了它，因为它涉及到一个额外的 sheet 选项卡，其中包含不理想的计算。但是当我在调查替代解决方案后反思时，它实际上以最非侵入性的方式解决了所有规定的要求。由于它不需要用户提供任何额外的东西，因此 spreadsheet 被共享。它还尽可能保持 'within' Google Sheets（不需要半或完全外部 Web 应用程序），通过依赖并发执行 spread[= 的本机并行化来进行并行化89=] 单元格，结果可以在其中链接，并且在用户看来就像使用常规公式一样（不需要额外的菜单项或 运行-this-script-buttons 必要）。
所以我在 Google Sheet 秒内使用自定义函数实现了 MapReduce，每个函数都在我想要计算的时间间隔的一部分上运行。在我的例子中，我能够做到这一点的原因是 我计算的输入可分为间隔，每个间隔都可以单独计算，然后稍后加入。**
然后每个并行自定义函数接受一个间隔，计算，并将结果输出回sheet（我建议输出为行而不是列，因为列的上限为 18 278 列。在 Google Spreadsheet limitations 上看到这个优秀的 post。）我在 only 40,000 new rows at a time 限制中做了 运行，但能够执行一些减少在每个间隔上，这样他们只输出非常有限的行到 spreadsheet。那就是并行化； MapReduce 的地图部分。然后我有一个单独的自定义函数来完成 Reduce 部分，即：动态定位***单独计算的自定义函数的 spreadsheet 输出区域，并在它们的结果可用时将它们连接在一起进一步减少它们（以找到性能最好的结果），达到 return 最终结果。
有趣的部分 是我认为我会击中 Google Sheet 的 only 30 simultaneous execution quota limit。但我能够并行处理多达 64 个独立且看似同时执行的自定义函数。 可能是Google如果它们超过30个并发执行就将它们放入队列，并且在任何给定时间实际只处理其中的30个（如果知道请评论）。但无论如何，并行化 benefit/speedup 是巨大的，而且似乎几乎可以无限扩展。但有一些警告：
您必须预先手动定义并行自定义函数的数量。所以并行化不会根据需求无限地自动缩放****。这一点很重要，因为违反直觉的结果是 在某些情况下使用较少的并行化实际上执行得更快 。在我的例子中，一个非常小的间隔的结果集可能非常大，而如果间隔更大，那么很多结果将被排除在该并行自定义函数的算法中（即 Map 也没有一些减少）。
在极少数情况下（大量输入），Reducer 函数会在所有并行 (Map) 函数完成之前输出结果（因为其中一些似乎花费的时间太长）。所以你似乎有一个完整的结果集，但几秒钟后它会在最后一个并行函数 return 的结果时重新更新。这并不理想，所以为了得到通知，我实现了一个函数来告诉我结果是否有效。我将它放在 Reduce 函数上方的单元格中（并将文本涂成红色）。 B6 是间隔数（此处为 4），其他单元格引用转到具有每个间隔的自定义函数的单元格：=didAnyExecutedIntervalFail($B,S13,AB13,AK13,AT13)
function didAnyExecutedIntervalFail(intervalsExecuted, ...intervalOutputs) {
const errorValues = new Set(["#NULL!", "#DIV/0!", "#VALUE!", "#REF!", "#NAME?", "#NUM!", "#N/A","#ERROR!", "#"]);
// We go through only the outputs for intervals which were included in the parallel execution.
for(let i=0; i < intervalsExecuted; i++) {
if (errorValues.has(intervalOutputs[i]))
return "Result below is not valid (due to errors in one or more of the intervals), even though it looks like a proper result!";
}
}
并行自定义函数受任何自定义函数的 Google 配额限制 max 30 sec execution time。所以如果他们计算的时间太长，他们仍然可能会超时（导致上一点提到的问题）。缓解这个超时的方法是更多的并行化，分成更多的间隔，让每个并行的自定义函数运行s低于30秒。
这一切的输出都受到GoogleSheet的限制。具体来说 max 5M cells in a spreadsheet. So you may need to perform some reduction on the size of the results calculated in each parallel custom function, before returning its result to the spreadsheet. So that they each are below 40 000 rows, otherwise you'll receive the dreaded "Results too large" error). Furthermore, depending on the size the result of each parallel custom function, it would also limit how many custom functions you could have at the same time, as they and their result cells take space in the spreadsheet. But if each of them take in total, say 50 cells (including a very small output), then you could still parallelize pretty much (5M / 50 = 100 000 parallel functions) within a single sheet. But you also need some space for whatever you want to do with those results. And the 5M cells limit is for the whole Spreadsheet in total, not just for one of its sheet tabs，显然。
** 对于那些感兴趣的人：我基本上想计算一个位序列的所有组合（通过蛮力），所以函数是 2^n 其中 n 是位数。初始的组合范围是从1 to 2^n开始，所以可以分成组合的区间，比如分成两个区间，就是一个从1 to X，一个从X+1 to 2^n ].
*** 对于那些感兴趣的人：我使用了一个单独的 sheet 公式，根据包含内容的行的存在动态确定其中一个间隔的输出范围。它在每个间隔的单独单元格中。对于第一个间隔，它位于单元格 S11 中，公式如下所示：
=ADDRESS(ROW(S13),COLUMN(S13),4)&":"&ADDRESS(COUNTA(S13:S)+ROWS(S1:S12),COLUMN(Z13),4) 并且它会输出 S13:Z15 这是动态计算的输出范围，它只计算那些有内容的行（使用 COUNTA(S13:S)），从而避免有一个静态确定的范围。因为对于正常的静态范围，输出的大小必须事先知道，但事实并非如此，或者它可能不包括所有输出，或者有很多空行（而且你不希望Reducer 遍历大量本质上为空的数据结构）。然后我会使用 INDIRECT(S) 将该范围输入到 Reduce 函数中。这就是您如何将结果从并行自定义函数处理的间隔之一获取到主 Reducer 函数中。
**** 尽管您可以使其自动扩展到一些预定义数量的并行自定义函数。您可以使用一些预配置的阈值，并在某些情况下划分为 16 个区间，但在其他情况下会自动划分为 64 个区间（根据经验预配置）。然后，您只需停止/短路不应参与的自定义函数，具体取决于该并行化自定义函数的数量是否超过您想要划分和处理的间隔数。在并行自定义函数的第一行：if (calcIntervalNr > intervals) return;。虽然您必须提前设置所有并行自定义函数，这可能很乏味（请记住您必须考虑每个输出区域，并且受到 Google 中的 max cell limit of 5M cells Sheets).
我有一个带有自定义函数公式的 Google Sheet：从电子表格中获取一个矩阵和两个向量，进行一些冗长的 matrix-vector 计算（>30 秒，所以超出配额)，然后将结果输出为一堆行。它是 single-threaded，因为那是 Google Apps 脚本 (GAS) 的本机，但我想使用 multi-threading 解决方法并行计算，因此它大大加快了速度。
要求（1-3）：
UX：它应该 运行 自动和反应地计算作为自定义函数公式，这意味着用户不必通过单击 运行 按钮或类似按钮手动启动它。就像我目前的 single-threaded 版本一样。
Parallelizable：理想情况下，它应该产生 ~30 threads/processes，这样就不会像现在那样花费 >30 秒（这使得它由于 Google 的 quota limit) 而超时，应该需要 ~1 秒。 （我知道 GAS 是 single-threaded，但有一些变通方法，参考如下）。
可共享性：理想情况下，我应该能够与其他人共享 Sheet，这样他们就可以“复制”它，并且脚本仍将 运行 为它们进行计算：
- 3.1 Permissionless：无需我手动向用户分发个人权限（无许可）。例如，每当有人“复制”和 "Execute the app as user accessing the web app"。我的初步测试表明这是可能的。
- 3.2 Non-intrusive：电子表格的用户无需给予 侵入性 授权，例如“给予此 spreadsheet/script/app 访问您的整个 Google 云端硬盘或 Gmail 帐户？”。用户必须向 script/webapp 授予 non-intrusive 授权是可以接受的，只要仍然保持要求 3.1。
- 3.3 UX：不强制用户查看电子表格中的 HTML 边栏。
我已经阅读了@TheMaster 的google.script.run 和解决方法 #4 UrlFetchApp.fetchAll（均使用 Google Web 应用程序）看起来最有希望。但是有些细节我不知道，比如他们是否可以通过 sub-requirements.
我可以想到另一个潜在的简单解决方法，即将函数拆分为几个自定义函数公式，并在电子表格本身（存储中间结果）中进行并行化（通过某种 Map/Reduce）回到电子表格，并让自定义函数公式作为缩减器工作）。但就我而言，这是不希望的，而且可能不可行。
我非常有信心我的函数可以使用某种 Map/Reduce 进程并行化。该函数目前通过执行所有计算 in-memory 进行了优化，而无需触及电子表格 in-between 步骤，然后最终将结果输出到电子表格。它的细节非常复杂，超过 100 行，所以我不想让您负担更多（并且可能令人困惑）的信息，这些信息不会真正影响本案例的一般适用性。对于这个问题的上下文，您可以假设我的函数是可并行化的（并且 map-reduce'able），或者考虑您已经知道的任何函数。有趣的是，通常可以通过 Google Apps 脚本中的并行化来实现，同时还保持最高级别的可共享性和 UX。如果需要，我会用更多细节更新这个问题。
2020-06-19 更新：
更清楚地说，我不完全排除 Google Web 应用程序的变通办法，因为我没有了解它们的实际限制的经验，无法确定它们是否可以在要求范围内解决问题。我已经更新了 sub-requirements 3.1 和 3.2 以反映这一点。我还添加了 sub-req 3.3，以更清楚地说明意图。我还删除了请求 4，因为它与请求 1 大部分重叠。
我也编辑了问题并删除了相关的sub-questions，所以它更侧重于标题中的单一主要HOWTO-question。我的问题中的要求应该提供一个明确的 objective 标准，哪些答案将被认为是最好的。
我意识到这个问题可能需要寻找 Google Sheet 多线程解决方法的圣杯，正如@TheMaster 私下指出的那样。理想情况下，Google 将提供一项或多项功能来支持多线程、map-reduce 或更多无权限共享。但在那之前，我真的很想知道在我们当前的限制条件下，最佳解决方法是什么。我希望这个问题也与其他人相关，即使考虑到严格的要求。
如果您使用“任何人，甚至匿名”发布网络应用程序，以“我”身份执行，则自定义函数可以使用 UrlFetchApp.fetchAllAuthorization not needed to post to that web-app. This will run in parallelproof。这解决了所有三个要求。
这里要注意的是：如果多个人使用 sheet，自定义函数将不得不 post 到“相同的”webapp（你发布的和你一样执行的）进行处理， Google 将限制同时执行quota limit:30.
要解决此问题，您可以要求使用您 sheet 的人发布他们自己的网络应用程序。他们必须在开始时执行一次，并且不需要授权。
如果没有，您将需要为负载托管一个自定义服务器，或者 google-cloud-functions 之类的东西可能会有所帮助
我最终使用了我在post中提到的天真的解决方法：
I can conceive of an other potential naïve workaround which would be to split the function up into several custom functions formulas and do the parallelization (by some kind of Map/Reduce) inside the spreadsheet itself (storing intermediary results back into the spreadsheet, and having custom function formulas work on that as reducers). But that's undesired, and probably unfeasible, in my case.
我最初忽略了它，因为它涉及到一个额外的 sheet 选项卡，其中包含不理想的计算。但是当我在调查替代解决方案后反思时，它实际上以最非侵入性的方式解决了所有规定的要求。由于它不需要用户提供任何额外的东西，因此 spreadsheet 被共享。它还尽可能保持 'within' Google Sheets（不需要半或完全外部 Web 应用程序），通过依赖并发执行 spread[= 的本机并行化来进行并行化89=] 单元格，结果可以在其中链接，并且在用户看来就像使用常规公式一样（不需要额外的菜单项或 运行-this-script-buttons 必要）。
所以我在 Google Sheet 秒内使用自定义函数实现了 MapReduce，每个函数都在我想要计算的时间间隔的一部分上运行。在我的例子中，我能够做到这一点的原因是 我计算的输入可分为间隔，每个间隔都可以单独计算，然后稍后加入。**
然后每个并行自定义函数接受一个间隔，计算，并将结果输出回sheet（我建议输出为行而不是列，因为列的上限为 18 278 列。在 Google Spreadsheet limitations 上看到这个优秀的 post。）我在 only 40,000 new rows at a time 限制中做了 运行，但能够执行一些减少在每个间隔上，这样他们只输出非常有限的行到 spreadsheet。那就是并行化； MapReduce 的地图部分。然后我有一个单独的自定义函数来完成 Reduce 部分，即：动态定位***单独计算的自定义函数的 spreadsheet 输出区域，并在它们的结果可用时将它们连接在一起进一步减少它们（以找到性能最好的结果），达到 return 最终结果。
有趣的部分 是我认为我会击中 Google Sheet 的 only 30 simultaneous execution quota limit。但我能够并行处理多达 64 个独立且看似同时执行的自定义函数。 可能是Google如果它们超过30个并发执行就将它们放入队列，并且在任何给定时间实际只处理其中的30个（如果知道请评论）。但无论如何，并行化 benefit/speedup 是巨大的，而且似乎几乎可以无限扩展。但有一些警告：
您必须预先手动定义并行自定义函数的数量。所以并行化不会根据需求无限地自动缩放****。这一点很重要，因为违反直觉的结果是 在某些情况下使用较少的并行化实际上执行得更快 。在我的例子中，一个非常小的间隔的结果集可能非常大，而如果间隔更大，那么很多结果将被排除在该并行自定义函数的算法中（即 Map 也没有一些减少）。
在极少数情况下（大量输入），Reducer 函数会在所有并行 (Map) 函数完成之前输出结果（因为其中一些似乎花费的时间太长）。所以你似乎有一个完整的结果集，但几秒钟后它会在最后一个并行函数 return 的结果时重新更新。这并不理想，所以为了得到通知，我实现了一个函数来告诉我结果是否有效。我将它放在 Reduce 函数上方的单元格中（并将文本涂成红色）。 B6 是间隔数（此处为 4），其他单元格引用转到具有每个间隔的自定义函数的单元格：
=didAnyExecutedIntervalFail($B,S13,AB13,AK13,AT13)
function didAnyExecutedIntervalFail(intervalsExecuted, ...intervalOutputs) {
const errorValues = new Set(["#NULL!", "#DIV/0!", "#VALUE!", "#REF!", "#NAME?", "#NUM!", "#N/A","#ERROR!", "#"]);
// We go through only the outputs for intervals which were included in the parallel execution.
for(let i=0; i < intervalsExecuted; i++) {
if (errorValues.has(intervalOutputs[i]))
return "Result below is not valid (due to errors in one or more of the intervals), even though it looks like a proper result!";
}
}
并行自定义函数受任何自定义函数的 Google 配额限制 max 30 sec execution time。所以如果他们计算的时间太长，他们仍然可能会超时（导致上一点提到的问题）。缓解这个超时的方法是更多的并行化，分成更多的间隔，让每个并行的自定义函数运行s低于30秒。
这一切的输出都受到GoogleSheet的限制。具体来说 max 5M cells in a spreadsheet. So you may need to perform some reduction on the size of the results calculated in each parallel custom function, before returning its result to the spreadsheet. So that they each are below 40 000 rows, otherwise you'll receive the dreaded "Results too large" error). Furthermore, depending on the size the result of each parallel custom function, it would also limit how many custom functions you could have at the same time, as they and their result cells take space in the spreadsheet. But if each of them take in total, say 50 cells (including a very small output), then you could still parallelize pretty much (5M / 50 = 100 000 parallel functions) within a single sheet. But you also need some space for whatever you want to do with those results. And the 5M cells limit is for the whole Spreadsheet in total, not just for one of its sheet tabs，显然。
** 对于那些感兴趣的人：我基本上想计算一个位序列的所有组合（通过蛮力），所以函数是 2^n 其中 n 是位数。初始的组合范围是从1 to 2^n开始，所以可以分成组合的区间，比如分成两个区间，就是一个从1 to X，一个从X+1 to 2^n ].
*** 对于那些感兴趣的人：我使用了一个单独的 sheet 公式，根据包含内容的行的存在动态确定其中一个间隔的输出范围。它在每个间隔的单独单元格中。对于第一个间隔，它位于单元格 S11 中，公式如下所示：
=ADDRESS(ROW(S13),COLUMN(S13),4)&":"&ADDRESS(COUNTA(S13:S)+ROWS(S1:S12),COLUMN(Z13),4) 并且它会输出 S13:Z15 这是动态计算的输出范围，它只计算那些有内容的行（使用 COUNTA(S13:S)），从而避免有一个静态确定的范围。因为对于正常的静态范围，输出的大小必须事先知道，但事实并非如此，或者它可能不包括所有输出，或者有很多空行（而且你不希望Reducer 遍历大量本质上为空的数据结构）。然后我会使用 INDIRECT(S) 将该范围输入到 Reduce 函数中。这就是您如何将结果从并行自定义函数处理的间隔之一获取到主 Reducer 函数中。
**** 尽管您可以使其自动扩展到一些预定义数量的并行自定义函数。您可以使用一些预配置的阈值，并在某些情况下划分为 16 个区间，但在其他情况下会自动划分为 64 个区间（根据经验预配置）。然后，您只需停止/短路不应参与的自定义函数，具体取决于该并行化自定义函数的数量是否超过您想要划分和处理的间隔数。在并行自定义函数的第一行：if (calcIntervalNr > intervals) return;。虽然您必须提前设置所有并行自定义函数，这可能很乏味（请记住您必须考虑每个输出区域，并且受到 Google 中的 max cell limit of 5M cells Sheets).