Является ли этот алгоритм поиска оптимальным?

Question

У меня есть два списка, L и M, каждый из которых содержит тысячи 64-битных целых чисел без знака. Мне нужно выяснить, является ли сумма любых двух членов L членом М.

Можно ли улучшить производительность следующего алгоритма?

Sort(M)
for i = 0 to Length(L)
    for j = i + 1 to Length(L)
        BinarySearch(M, L[i] + L[j])

Answer 1

(я предполагаю, что ваша цель - найти все пары в L, которые суммируют что-то в M)

Забудьте хеш-таблицы!

Сортировка обоих списков.

Затем выполните внешний цикл вашего алгоритма: пройдитесь по каждому элементу i в L, затем по каждому большему элементу j в L. По ходу, сформируйте сумму и проверьте, находится ли он в M.

Но не смотрите с помощью бинарного поиска: просто выполните линейное сканирование с последнего места, где вы смотрели. Допустим, вы работаете с некоторым значением i, и у вас есть некоторое значение j, за которым следует некоторое значение j '. При поиске (i + j) вы попали бы в точку M, где найдено это значение, или в первое по величине значение. Вы сейчас ищете (я + J '); поскольку j '> j, вы знаете, что (i + j')> (i + j), и поэтому в M не может быть более раннего, чем последнее место, которое вы получили. Если и L, и M равномерно распределены, есть отличный шанс того, что точка в M, где вы найдете (i + j '), находится всего в нескольких шагах.

Если массивы распределены неравномерно, то лучше, чем линейное сканирование, быть сканированием скачка - смотрите N элементов за раз, вдвое меньше N, если переход идет слишком далеко.

Я полагаю, что это алгоритм O (n ^ 2), который так же быстр, как любой предложенный алгоритм хеширования (который имеет примитивную операцию O (1), но все же должен выполнять O (n ** 2) из ​​них). Это также означает, что вам не нужно беспокоиться об O (n log n) для сортировки. Он имеет гораздо лучшую локальность данных, чем хеш-алгоритмы - он в основном состоит из парных потоковых чтений по массивам, повторяемых n раз.

---

РЕДАКТИРОВАТЬ: Я написал реализации оригинального алгоритма Пола Бейкера, алгоритма хеширования Ника Ларсена и моего алгоритма, а также простую систему сравнения. Реализации просты (линейное зондирование в хеш-таблице, пропуски в моем линейном поиске отсутствуют), и мне пришлось угадывать различные параметры размеров. См. http://urchin.earth.li/~twic/Code/SumTest/ для кода. Я приветствую исправления или предложения, касающиеся любых реализаций, инфраструктуры и параметров.

Для L и M, содержащих 3438 элементов каждый, со значениями в диапазоне от 1 до 34380 и с хэш-таблицей Ларсена, имеющей коэффициент загрузки 0,75, медианные времена для запуска:

• Бейкер (бинарный поиск): 423 716 646 нс
• Larsen (hashtable): 733 479 121 нс
• Андерсон (линейный поиск): 62 077 597 нс

Разница намного больше, чем я ожидал (и, я признаю, не в том направлении, которое я ожидал). Я подозреваю, что я сделал одну или несколько серьезных ошибок в реализации. Если кто-нибудь заметит один, я действительно хотел бы услышать об этом!

Во-первых, я выделил хеш-таблицу Ларсена внутри метода timed. Таким образом, он оплачивает стоимость размещения и (некоторого) сбора мусора. Я думаю, что это справедливо, потому что это временная структура, которая нужна только алгоритму. Если вы думаете, что это то, что можно использовать повторно, было бы достаточно просто переместить его в поле экземпляра и выделить его только один раз (и Arrays. Заполнить его нулем внутри метода timed) и посмотреть, как это влияет на производительность. *

Answer 2

Сложность примера кода в вопросе O (m log m + l ² log m), где l = | L | и m = | M | поскольку он выполняет бинарный поиск (O (log m)) для каждой пары элементов в L (O (l ² )), а M сортируется первым.

Замена бинарного поиска хеш-таблицей снижает сложность до O (l ² ), предполагая, что вставка и поиск в хеш-таблице являются операциями O (1).

Это асимптотически оптимально, если вы предполагаете, что вам нужно обработать каждую пару чисел в списке L, поскольку существует O (l ² ) таких пар. Если на L есть пара тысяч чисел, и они являются случайными 64-битными целыми числами, то вам определенно необходимо обработать все пары.

Answer 3

Вместо сортировки M по стоимости n * log(n) вы можете создать хэш-набор по стоимости n.

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

Answer 4

В качестве альтернативы, добавьте все члены L в хэш-набор lSet, затем выполните итерацию по M, выполнив эти шаги для каждого m в M:

1. добавьте m в хэш-набор mSet - если m ужев mSet пропустите эту итерацию;если m находится в хэш-наборе dSet, также пропустите эту итерацию.
2. вычтите каждый член l из L меньше m из m, чтобы дать d, и проверьте, находится ли d также в lSet;
3. , если это так, добавить (l, d) к некоторой коллекции rSet;добавьте d в хэш-набор dSet.

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

Answer 5

Вы можете избежать бинарного поиска, используя хеш-таблицу, за исключением отсортированного массива M.