Скорый поиск

Январь 13, 2012 — Шарахов А.П.

Что может быть быстрее бинарного поиска? Другой бинарный поиск.

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 млн строк.