Я закончил тем, что использовал наивный обходной путь, который я упомянул в своем сообщении:
Я могу придумать другой потенциальный наивный обходной путь, который заключался бы в том, чтобы разделить функцию на несколько формул пользовательских функций и выполнить распараллеливание (с помощью некоторого вида Map / Reduce) внутри самой электронной таблицы (сохранение промежуточных результатов обратно в электронную таблицу и использование пользовательских формул функций в качестве редукторов). Но в моем случае это нежелательно и, вероятно, невыполнимо.
Я сначала проигнорировал это, потому что это связано с наличием дополнительной вкладки листа с вычислениями, что было не идеально. Но когда я задумался над этим после исследования альтернативных решений, он фактически решает все заявленные требования самым ненавязчивым образом. Поскольку для этого не требуется ничего лишнего от пользователей, к таблице открыт доступ. Он также остается `` внутри '' Google Таблиц, насколько это возможно (не требуется полу- или полностью внешнее веб-приложение), выполняя распараллеливание, полагаясь на собственное распараллеливание одновременно выполняющихся ячеек электронной таблицы, где результаты могут быть объединены в цепочку и видны пользователю. например, с использованием обычных формул (без дополнительных пунктов меню или кнопок запуска этого сценария).
Итак, я реализовал MapReduce в Google Таблицах, используя пользовательские функции, каждая из которых работает с частью интервала, который я хотел вычислить. Причина, по которой я смог это сделать в моем случае, заключалась в том, что входные данные для моих вычислений были разделены на интервалы, каждый из которых можно было вычислить отдельно , а затем присоединить позже. **
Каждая параллельная настраиваемая функция затем берет один интервал , вычисляет его и выводит результаты обратно на лист (я рекомендую выводить в виде строк, а не столбцов, поскольку столбцы ограничены максимумом 18 278 столбцов. См. Это отличное сообщение об ограничениях Google Spreadsheet .) Я столкнулся с ограничением only 40,000 new rows at a time, но смог выполнить некоторое сокращение на каждом интервале, так что они выводят в электронную таблицу только очень ограниченное количество строк. Это было распараллеливание; Часть Map в MapReduce. Затем у меня была отдельная настраиваемая функция, которая выполняла часть «Уменьшение», а именно: динамически нацеливать *** на область вывода электронной таблицы отдельно рассчитанных настраиваемых функций и принимать их результаты, когда они доступны, и объединять их вместе, дополнительно уменьшая их (до найти наиболее эффективные результаты), чтобы получить окончательный результат.
Интересная часть заключалась в том, что я думал, что достигну only 30 simultaneous execution предела квоты Google Таблиц . Но я смог распараллелить до 64 независимо и, казалось бы, одновременно выполняя пользовательские функции. Может случиться так, что Google помещает их в очередь, если они превышают 30 одновременных выполнений, и фактически обрабатывают только 30 из них в любой момент времени (прокомментируйте, если вы знаете). Но в любом случае выгода / ускорение распараллеливания были огромными и, казалось, почти бесконечно масштабируемыми. Но с некоторыми оговорками:
Вы должны определить количество параллельных пользовательских функций заранее вручную. Таким образом, распараллеливание не может бесконечно автоматически масштабироваться в соответствии с требованиями ****. Это важно из-за противоречащего интуиции результата, что в некоторых случаях с меньшим распараллеливанием на самом деле выполняется быстрее . В моем случае набор результатов из очень небольшого интервала может быть чрезвычайно большим, в то время как если бы интервал был больше, то многие результаты были бы исключены в алгоритме в этой распараллеленной пользовательской функции (т.е. некоторое сокращение).
В редких случаях (с огромными входными данными) функция Reducer будет выводить результат до того, как будут выполнены все параллельные функции (Map) (поскольку некоторые из них, по-видимому, принимают слишком долго). Таким образом, у вас, по-видимому, есть полный набор результатов, но через несколько секунд он обновится, когда последняя параллельная функция вернет свой результат. Это не идеально, поэтому, чтобы получить уведомление об этом, я реализовал функцию, которая сообщает мне, был ли результат верным. Я поместил его в ячейку над функцией «Уменьшить» (и покрасил текст в красный цвет). B6 - это количество интервалов (здесь 4), а другая ячейка ссылается на go на ячейку с пользовательской функцией для каждого интервала: =didAnyExecutedIntervalFail($B$6,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 максимум 30 секунд c время выполнения для любой пользовательской функции. Поэтому, если на их вычисление уходит слишком много времени, они все равно могут истечь (что вызывает проблему, упомянутую в предыдущем пункте). Способ уменьшить этот тайм-аут состоит в большем распараллеливании, разделении на большее количество интервалов, чтобы каждая параллельная пользовательская функция работала менее 30 секунд.
Вывод всего этого ограничен ограничениями Google Sheet . А именно максимум 5M ячеек в электронной таблице. Таким образом, вам может потребоваться некоторое уменьшение размера результатов, вычисляемых в каждой параллельной пользовательской функции, прежде чем возвращать результат в электронную таблицу. Чтобы каждая из них была меньше 40 000 строк, иначе вы получите ужасную ошибку «Результаты слишком велики»). Кроме того, в зависимости от размера результата каждой параллельной настраиваемой функции, это также ограничит количество настраиваемых функций, которые вы можете использовать одновременно, поскольку они и их ячейки результатов занимают место в электронной таблице. Но если каждая из них займет всего, скажем, 50 ячеек (включая очень небольшой вывод), то вы все равно сможете распараллелить довольно много (5M / 50 = 100 000 параллельных функций) на одном листе. Но вам также нужно место для того, что вы хотите сделать с этими результатами. И ограничение 5M ячеек предназначено для всей электронной таблицы в целом, а не только для одной из ее вкладок , по-видимому.
** Для тех, кому интересно: я в основном хотел вычислить все комбинации последовательности битов (методом перебора), поэтому функция была 2^n, где n - количество битов. Первоначальный диапазон комбинаций был от 1 to 2^n, поэтому его можно было разделить на интервалы комбинаций, например, при разделении на два интервала это будет один из 1 to X, а затем один из X+1 to 2^n.
*** Для интересующихся: я использовал формулу отдельного листа для динамического определения диапазона вывода одного из интервалов на основе наличия строк с содержимым. Он находился в отдельной ячейке для каждого интервала. Для первого интервала он находился в ячейке S11, и формула выглядела следующим образом: =ADDRESS(ROW(S13),COLUMN(S13),4)&":"&ADDRESS(COUNTA(S13:S)+ROWS(S1:S12),COLUMN(Z13),4), и он выводил S13:Z15, который является динамически вычисляемым диапазоном вывода, который учитывает только те строки с содержимым (с использованием COUNTA(S13:S)), таким образом избегая статического определения диапазона. Поскольку при нормальном диапазоне stati c размер вывода должен быть известен заранее, а это не так, иначе он, возможно, не будет включать весь вывод или много пустых строк (а вы не не хочу, чтобы Reducer перебирал множество по существу пустых структур данных). Затем я бы ввел этот диапазон в функцию Reduce, используя INDIRECT(S$11). Вот как вы получаете результаты из одного из интервалов, обработанных параллельной пользовательской функцией, в основную функцию Reducer.
**** Хотя вы могли бы сделать его автоматическим масштабированием до некоторого заранее определенного количество параллельных пользовательских функций. Вы можете использовать некоторые предварительно сконфигурированные пороги и в некоторых случаях разделить, скажем, на 16 интервалов, но в других случаях автоматически разделить на 64 интервала (предварительно сконфигурированных, исходя из опыта). Затем вы просто останавливаете / закорачиваете пользовательские функции, которые не должны участвовать, в зависимости от того, превышает ли количество этой параллельной пользовательской функции количество интервалов, на которые вы хотите разделить и обработать. В первой строке распараллеленной пользовательской функции: if (calcIntervalNr > intervals) return;. Хотя вам придется заранее настроить все параллельные пользовательские функции, что может быть утомительным (помните, что вы должны учитывать область вывода каждой, и ограничены максимальным пределом ячеек в 5 миллионов ячеек в Google Таблицы).