Что может быть быстрее бинарного поиска? Другой бинарный поиск.
function Search4b(Val: integer; const Arr: IntegerArray; Right: integer): integer; var Left: integer; begin; Result:=Right shr 1; Left:=0; if Right>=0 then while true do begin; if Val>Arr[Result] then begin; Left:=Result+1; Result:=(Left + Right) shr 1; if Left<=Right then continue else break; end else if Val<Arr[Result] then begin; Right:=Result+(-1); Result:=(Left + Right) shr 1; if Left<=Right then continue else break; end else exit; end; Result:=-1; end;
Особенности этого шедевра человеческой мысли:
1. Левая и правая граница поиска включают первый и последний элементы массива, которые могут содержать искомое значение. Кто-то думал, что может быть иначе?
2. Как обычно, наш двоичный поиск содержит три ветки – так алгоритм выглядит проще. Второй переход все равно не предсказывается и на скорость практически не влияет.
3. Мы даже не пытаемся предварительно считать сравниваемый элемент из массива во временную переменную – пусть это сделает компилятор, если сможет.
4. При вычислении новой правой границы используется сложение, а не вычитание, чтобы лишний раз намекнуть компилятору на возможность использования инструкции LEA.
5. Индекс среднего элемента округляется, как принято, влево – в данном случае так проще и быстрее.
6. Вычисление очередного индекса среднего элемента начинается как можно раньше, еще до проверки окончания цикла.
7. Проверка окончания цикла выполняется отдельно для левой и правой ветки, чтобы уменьшить количество переходов.
Comments (2)
Автоматизированый быстрый поиск
Здравствуйте, сможете помочь с кодом для такой задачи:
Есть три txt файла на SSD диске
Файл Word1 - основной отсортированный список неповторяющихся слов (около 100млн строк) - 10гб
Файл Test1 - список слов которые надо проверить на совпадение с файлом Base1 (по 10 млн строк) - 1гб
Файл Check1 - построчный список слов совпавших при сравнении файлов Word1 и Test1
Смысл в том что б выявить дубляжи слов которые есть в Test1 при сравнении с основным словарем - Word1. И показать только эти дубляжи в файле Check1.
Я уже находил несколько реализаций, но все работает ужасно медленно, а надо что б не жрало память и был максимально быстрый поиск. На что то более серьезное у меня просто не хватит знаний Делфи.
Тут основная проблема - большой объем данных
1. На 64-битной Delphi и большом объеме памяти имеет смысл загрузить в память файл Test1 и отсортировать. Затем в цикле последовательно читая слова из файла Word1 сравнивать очередное слово из файла с очередным словом в памяти и совпадающие выводить в файл Check1. Будьте внимательны при написании цикла - индекс слова в памяти не всегда нужно увеличивать.
2. На 32-битной Delphi или малом объеме памяти можно обрабатывать данные файла Test1 порциями по 2..5 млн строк.