Разбиение массива нахождение минимальной разницы между суммой двух подмассивов в распределенной среде

Question

Эту проблему мне задали вчера.Мне пришлось написать код, чтобы разбить массив на две части так, чтобы разница между суммой этих двух частей была минимальной.

Вот код, который я написал со сложностью O (n)

function solution(a) {
  let leftSum = 0;
  let rightSum = a.reduce((acc, value) => acc + value ,0);
  let min = Math.abs(rightSum - leftSum);
  a.forEach((item, i) => {
   leftSum += a[i];
   rightSum -= a[i]; 
   const tempMin = Math.abs(rightSum - leftSum);
   if(tempMin < min) min = tempMin;
  })
  return min;
}

Но затем меня спросили, имеет ли длина входного массива 10 миллионов, как бы я решил эту проблему в распределенной среде?

Я новичок в распределенном программированииНужна помощь в этом.

Answer 1

Если у вас есть N узел, s затем разбейте массив на N последовательные подмассивы; это даст вам N последовательных сумм. Сделайте проход, чтобы определить, какой подмассив содержит нужную точку разделения Разница между суммами «до» и «после» - ваша цель смещения для следующей фазы ...

Теперь разделите этот "средний" массив на N частей. Опять же, вы ищите подходящую точку разделения, за исключением того, что теперь вы знаете точный результат, который вам нужен (поскольку у вас есть сумма массива и пропущенная разница).

Повторяйте этот второй абзац, пока вы не поместите весь подмассив в один узел и , это самый быстрый способ завершить вычисления для вашего проекта.

---

Вы можете несколько ускорить это, сохраняя кумулятивную сумму для каждого значения; это позволит вам находить подходящую точку разделения несколько быстрее на каждом этапе, так как вы можете использовать бинарный или интерполяционный поиск для каждого этапа после первого.

Answer 2

Учитывая массив длины N и предоставленные M доступных узлов, разделите массив на куски размера N / M. Каждый узел вычисляет сумму своего чанка и отчитывается. Общая сумма рассчитывается путем сложения частичных сумм. Затем общая и частичная суммы распределяются по каждому из узлов. Каждый узел определяет лучшую точку разделения в пределах своего фрагмента (локальный минимум) и отчитывается. Глобальный минимум вычисляется из локальных минимумов.

Например, если в массиве 10 миллионов записей и доступно 200 узлов, размер чанка равен 50000. Таким образом, каждый узел получает 50000 чисел и сообщает сумму. Общая сумма массива вычисляется путем сложения 200 частичных сумм. Затем каждому узлу присваивается сумма вместе с 200 частичными суммами. Информация на каждом узле теперь состоит из

• номер чанка
• 50000 записей массива для этого чанка
• массив всего
• 200 частичных сумм

Из этой информации каждый узел может вычислить свой локальный минимум. Глобальный минимум вычисляется из 200 локальных минимумов.

В идеальном случае, когда пропускная способность сети бесконечна, задержка сети равна нулю и может использоваться любое количество узлов, размер порции должен составлять sqrt(N). Таким образом, каждый узел получает sqrt(N) элементов массива, а затем получает sqrt(N) частичных сумм. В этих идеальных условиях время работы составляет O(sqrt(N)) вместо O(N).

Конечно, в реальном мире нет смысла пытаться распространять подобные проблемы. Количество времени (на элемент массива) для отправки элементов массива по сети является значительным. Гораздо больше, чем количество времени (на элемент массива), необходимое для решения проблемы на одном компьютере.

Answer 3

Предположим, что массив хранится последовательно на нескольких узлах N_1, ..., N_k.Простая распределенная версия вашего исходного алгоритма может быть следующей:

1. В каждом N_i вычислите сумму s_i подмассива, хранящегося в N_i, и отправьте ее на управляющий узел M
2. На узле M, используя s_1, ..., s_k, вычислите leftSum_i и rightSum_i для левой границы подмассива каждого N_i и отправьте их обратно в N_i
3. На каждом N_i, используя leftSum_i и rightSum_i, выполните поиск, чтобы найти минимум min_i и отправьте его обратно в M
4. . На узле M вычислите глобальный минимум min из min_i, ...min_k

Примечание: ваш исходный алгоритм может быть оптимизирован для сохранения только значения rightSum - leftSum, а не двух отдельных значений leftSum и rightSum.Распределенная версия также может быть оптимизирована соответственно.