Mag*_*gne 6 multithreading mapreduce google-sheets google-apps-script custom-function
我有一个带有自定义函数公式的 Google 表格：从电子表格中获取一个矩阵和两个向量，进行一些冗长的矩阵向量计算（>30 秒，因此超出配额），然后将结果输出为一堆行。它是单线程的，因为这就是 Google Apps 脚本 (GAS) 本身的本质，但我想使用多线程解决方法并行化计算，因此它可以大大加快计算速度。
\n要求（1-3）：
\n用户体验：它应该作为自定义函数公式自动且反应性地运行计算，这意味着用户不必通过单击运行按钮或类似按钮来手动启动它。就像我目前的单线程版本一样。
\n可并行化：理想情况下，它应该生成约 30 个线程/进程，这样就不会像现在那样花费 >30 秒（这会导致由于 Google 的配额限制而超时），而应该花费约 1 秒。（我知道 GAS 是单线程的，但有一些解决方法，如下所述）。
\n可共享性：理想情况下，我应该能够与其他人共享工作表，以便他们可以“制作副本”，并且脚本仍将为他们运行计算：
\n我已经阅读了@TheMaster 的这篇优秀的相关答案，其中概述了解决 Google Apps 脚本中并行化问题的一些潜在方法。解决方法 #3google.script.run和解决方法 #4 UrlFetchApp.fetchAll（均使用 Google Web App）看起来最有希望。但有些细节我不知道，比如他们是否可以遵守要求 1 和 3 及其子要求。
我可以设想另一种潜在的 na\xc3\xafve 解决方法，它将函数拆分为几个自定义函数公式，并在电子表格本身内部进行并行化（通过某种 Map/Reduce）（将中间结果存储回电子表格，并使用自定义函数公式作为化简器对其进行处理）。但就我而言，这是不受欢迎的，而且可能是不可行的。
\n我非常有信心我的函数可以使用某种 Map/Reduce 过程进行并行化。目前，该函数通过在内存中进行所有计算进行优化，在最终将结果输出到电子表格之前，无需在步骤之间接触电子表格。它的细节非常复杂，超过 100 行，所以我不想让您负担更多（并且可能令人困惑的）信息，这些信息不会真正影响此案例的一般适用性。对于这个问题的上下文，您可以假设我的函数是可并行的（并且可以进行映射减少），或者考虑您已经知道的任何函数。有趣的是，通常可以通过 Google Apps 脚本中的并行化来实现，同时还保持最高水平的可共享性和用户体验。如果需要，我将用更多详细信息更新此问题。
\n2020年6月19日更新：
\n更明确地说，我并不完全排除 Google Web App 变通办法，因为我还没有了解它们的实际限制的经验，无法确定它们是否可以在要求范围内解决问题。我更新了子要求 3.1 和 3.2 以反映这一点。我还添加了子要求 3.3，以更清楚地表达意图。我还删除了请求 4，因为它与请求 1 大部分重叠。
\n我还编辑了该问题并删除了相关的子问题，因此它更侧重于标题中的单个主要 HOWTO 问题。我的问题中的要求应该提供一个明确的客观标准，根据该标准，答案将被认为是最佳的。
\n我意识到这个问题可能需要寻找 Google Sheet 多线程解决方法的圣杯，正如 @TheMaster 私下指出的那样。理想情况下，Google 会提供一项或多项功能来支持多线程、map-reduce 或更多无需许可的共享。但在那之前我真的很想知道在我们当前的限制下最佳的解决方法是什么。我希望这个问题也与其他人相关，即使考虑到严格的要求。
\n我最终使用了我在帖子中提到的 na\xc3\xafve 解决方法：
\n\n\n我可以设想另一种潜在的 na\xc3\xafve 解决方法，该解决方法是将函数拆分为几个自定义函数公式，并在电子表格本身内部进行并行化（通过某种 Map/Reduce）（存储中间结果）返回\n电子表格，并让自定义函数公式作为\nreducer 对其进行处理）。但就我而言，这是不受欢迎的，而且可能是不可行的。
\n
我最初忽略了它，因为它涉及到一个额外的工作表选项卡，其中的计算并不理想。但当我在研究替代解决方案后反思它时，它实际上以最非侵入性的方式解决了所有规定的要求。由于它不需要用户提供任何额外的信息，因此可以与其共享电子表格。它还尽可能保留在 Google Sheets 中（不需要半或完全外部 Web 应用程序），通过依赖并发执行的电子表格单元格的本机并行化来进行并行化，其中结果可以链接起来，并且看起来用户喜欢使用常规公式（不需要额外的菜单项或运行此脚本按钮）。
\n因此，我使用自定义函数在 Google Sheets 中实现了 MapReduce，每个函数都对我想要计算的间隔的一部分进行操作。在我的例子中，我能够做到这一点的原因是，我的计算的输入可分为多个间隔，每个间隔可以单独计算，然后再加入。**
\n然后，每个并行自定义函数接受一个时间间隔，计算结果，并将结果输出回工作表（我建议输出为行而不是列，因为列的上限为最多 18 278 列。请参阅这篇有关Google 电子表格限制的优秀文章。）我确实遇到了only 40,000 new rows at a time限制，但能够在每个间隔上执行一些减少操作，以便它们仅向电子表格输出非常有限的行数。这就是并行化；MapReduce 的 Map 部分。然后，我有一个单独的自定义函数，它执行减少部分，即：动态定位***单独计算的自定义函数的电子表格输出区域，并获取它们的结果（一旦可用），并将它们连接在一起，同时进一步减少它们（以找到表现最好的结果），返回最终结果。
有趣的是，我认为我会达到Google Sheets 的only 30 simultaneous execution 配额限制。但我能够并行化多达 64 个独立且看似同时执行的自定义函数。如果并发执行超过 30 个，Google 可能会将它们放入队列，并且在任何给定时间实际上只处理其中的 30 个（如果您知道，请发表评论）。但无论如何，并行化的好处/加速是巨大的，而且似乎几乎可以无限扩展。但有一些警告：
您必须预先手动定义并行自定义函数的数量。因此并行化不会根据需求无限自动扩展****。这很重要，因为与直觉相反的结果是，在某些情况下，使用较少的并行化实际上执行得更快。就我而言，非常小的间隔的结果集可能会非常大，而如果间隔较大，那么在该并行自定义函数的算法中，很多结果将被排除（即 Map 也这样做了）有所减少）。
\n在极少数情况下（输入巨大），Reducer 函数将在所有并行 (Map) 函数完成之前输出结果（因为其中一些函数似乎花费太长时间）。因此，您似乎拥有完整的结果集，但几秒钟后，当最后一个并行函数返回其结果时，它将重新更新。这并不理想，因此为了得到通知，我实现了一个函数来告诉我结果是否有效。我将其放在“Reduce”函数上方的单元格中（并将文本涂成红色）。B6 是间隔数（此处为 4），其他单元格引用转到具有每个间隔的自定义函数的单元格：=didAnyExecutedIntervalFail($B$6,S13,AB13,AK13,AT13)
function didAnyExecutedIntervalFail(intervalsExecuted, ...intervalOutputs) {\n const errorValues = new Set(["#NULL!", "#DIV/0!", "#VALUE!", "#REF!", "#NAME?", "#NUM!", "#N/A","#ERROR!", "#"]);\n // We go through only the outputs for intervals which were included in the parallel execution.\n for(let i=0; i < intervalsExecuted; i++) {\n if (errorValues.has(intervalOutputs[i]))\n return "Result below is not valid (due to errors in one or more of the intervals), even though it looks like a proper result!";\n }\n }\n并行自定义函数受到 Google 配额的限制，任何自定义函数的执行时间最长为 30 秒。因此，如果它们计算时间太长，它们仍然可能会超时（导致上一点提到的问题）。缓解这种超时的方法是更多地并行化，划分更多的间隔，使每个并行自定义函数的运行时间低于 30 秒。
\n这一切的输出都受到 Google Sheet 限制的限制。具体来说，电子表格中最多有 500 万个单元格。因此，在将结果返回到电子表格之前，您可能需要对每个并行自定义函数中计算的结果的大小进行一些减小。这样它们每个都低于 40 000 行，否则您将收到可怕的“结果太大”错误）。此外，根据每个并行自定义函数结果的大小，它还会限制您可以同时拥有的自定义函数数量，因为它们及其结果单元格会占用电子表格中的空间。但是，如果每个函数总共包含 50 个单元（包括非常小的输出），那么您仍然可以在单个工作表中实现相当多的并行化（5M / 50 = 100 000 个并行函数）。但您还需要一些空间来放置您想要对这些结果执行的任何操作。显然，5M 单元格限制是针对整个电子表格的，而不仅仅是针对其工作表选项卡之一。
\n** 对于那些感兴趣的人：我基本上想计算位序列的所有组合（通过强力），所以函数就是2^n位数n。初始组合范围是从1 to 2^n，因此可以将其分为组合区间，例如，如果分为两个区间，则为 1 from 1 to X，然后为 1 from X+1 to 2^n。
*** 对于那些感兴趣的人：我使用了一个单独的工作表公式，根据包含内容的行的存在来动态确定其中一个间隔的输出范围。每个时间间隔都在一个单独的单元格中。对于第一个间隔，它位于单元格中S11，公式如下所示：\n=ADDRESS(ROW(S13),COLUMN(S13),4)&":"&ADDRESS(COUNTA(S13:S)+ROWS(S1:S12),COLUMN(Z13),4)并且它将输出S13:Z15动态计算的输出范围，该范围仅对具有内容的行进行计数（使用COUNTA(S13:S)），从而避免静态确定范围。由于使用正常的静态范围，输出的大小必须提前知道，但事实并非如此，否则它可能不包含所有输出，或者包含很多空行（而你不知道）不希望Reducer 迭代大量本质上为空的数据结构）。然后我会使用 将该范围输入到Reduce 函数中INDIRECT(S$11)。这就是您如何将结果从并行自定义函数处理的间隔之一获取到主Reducer 函数中。
**** 虽然您可以使其自动扩展至一些预定义数量的并行自定义函数。您可以使用一些预先配置的阈值，并在某些情况下划分为 16 个间隔，但在其他情况下自动划分为 64 个间隔（根据经验预先配置）。然后，您只需停止/短路不应参与的自定义函数，具体取决于该并行自定义函数的数量是否超过您想要划分和处理的间隔数。在并行化自定义函数的第一行：if (calcIntervalNr > intervals) return;。尽管您必须提前设置所有并行自定义函数，但这可能很乏味（请记住，您必须考虑每个函数的输出区域，并且受到Google 表格中5M 单元格最大单元格限制的限制）。