Блог

У меня проблема и приемлемое решение. Я надеюсь, что есть лучшее решение.

Проблема

У меня есть массив, содержащий около 200 000 целых чисел. Учитывая два индекса, i1 и i2, мне нужно вычислить сумму всех элементов между i1 и i2. Каждое целое число в массиве находится в диапазоне от 1 до 4 включительно. Например:

 a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1   3   2)
  

Эта операция будет выполнена около 200 000 раз, поэтому должна быть довольно быстрой. Простой счетчик в цикле for равен O (n) и слишком медленный. Массив никогда не изменяется после построения, поэтому можно использовать относительно дорогостоящий этап предварительной обработки.

Мое лучшее решение на данный момент

Этот алгоритм работает за O (log n) время:

Сначала дополните исходный массив нулями, пока его длина не станет степенью двойки. Далее разделите массив на две равные части и сохраните сумму каждой. Затем разделите массив на четверти и сохраните сумму каждого. Затем восьмые. Продолжайте делать это, пока массив не будет разделен на секции длиной в 2 элемента. Для приведенного выше 8-элементного массива это занимает два шага:

 halves = [(a[0]   a[1]   a[2]   a[3]), (a[4]   a[5]   a[6]   a[7])]
quarters = [(a[0]   a[1]), (a[2]   a[3]), (a[4]   a[5]), (a[6]   a[7])]
  

Тогда, учитывая два индекса, теперь можно вычислить subsection_sum за O (log n) время. Например, subsection_sum(a, 2, 7) == четверти [1] половинки [1].

Введите вспомогательный массив, который содержит совокупную сумму. То есть элемент i вспомогательного массива имеет сумму элементов от 0 до i исходного массива. Тогда сумма подмассива — это просто разница двух элементов из вспомогательного массива. Это даст результат за постоянное время, O(1) .

Это зависит от инварианта в subsection_sum функции, указанной в вопросе,:

 subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1)   subsection_sum(a, i1, i2)
  

где я предполагаю i1 <= i2 . Переставляя, мы имеем:

 subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)
  

Обратите внимание, что суммы в правой части начинаются с 0 . Вспомогательный массив можно рассматривать как кэширование значений сумм от нуля, subsection_sum(a, 0, i) для всех i .

Если вы можете позволить себе O(n) дополнительное хранилище, вы можете создать таблицу поиска, i -й элемент которой является суммой элементов с индексами 0 через i (включительно) во входном массиве. В псевдокоде:

 def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i]   lookupTable[i-1]

    return lookupTable
  

Затем вы можете использовать эту таблицу для вычисления суммы всех элементов array между i1 и i2 , взяв разницу

 lookupTable[i2] - lookupTable[i1]
  

который требует постоянного времени.