Максимальное ускорение алгоритма поиска

Дмитрий Сахань

Временные затраты алгоритма поиска ощутимо чувствуются при обработке больших объемов информации. Если производится поиск DWORD-числа среди набора (массива) таких же значений, то самым оптимальным и скоростным будет последовательное сравнение заданного значения со всеми элементами массива до обнаружения совпадения. Однако для поиска строк или некоторых объектов, когда данные представлены в виде достаточно большого набора байт, дела обстоят иначе. Строка или содержимое объекта - это не DWORD-значение, и сравнивать приходится побайтно все содержимое до первого различия или полного совпадения. Как раз это и съедает основную часть затраченного на поиск времени.

Но программисты быстро вычислили, как усовершенствовать алгоритм поиска, чтобы он не тратил лишнее время. Суть заключалась в том, чтобы сначала сравнивать длины искомой и анализируемой строк (для объектов - размеры их содержимого). Различие в длинах/размерах точно свидетельствует о разнице содержимого строк/объектов, поэтому нет смысла тратить время на побайтное сравнение их содержимого. И только при совпадении длин выполняется "медлительный" код сравнения содержимого.

Вот как выглядит простой алгоритм сравнения. Есть глобальный массив M с некими строками, есть входная строковая переменная S с текстом искомой строки, и нужно найти такую же строку в массиве M. Пример утрированный и просто показывает, что на самом деле выполняется при сравнении строк (ведь программист просто написал бы код if s = m[i] then вместо указанных мной строк с if .... then).

var

m: array[1..1000] of AnsiString;

procedure Find(s: AnsiString);

var

i: Integer;

begin

for i = 1 to Length(m) do

if Длина(s) = Длина(m[i]) then

if Содержимое(s) = Содержимое(m[i]) then

нашли строку в m[i];

end;

Однако такое усовершенствование подразумевает ускорение только при разных длинах расположенных в массиве строк. Уже при расположении в массиве свыше 100 тысяч строк эффективность сравнения "длина-содержимое" начинает снижаться, так как массив заполняется большим количеством одинаковых по длинам строк. И чем больше располагать в массиве строк, тем менее эффективным становится данное усовершенствование.

Но самое неприятное для этого метода сравнения начинается, когда в силу каких-то обстоятельств или заранее заданных условий в массиве располагаются одинаковые по длинам строки/объекты. Тогда сравнение приходится вести только по содержимому, а сравнение длин оказывается лишней операцией. При огромных объемах информации падение производительности очень большое. Здесь нужно либо использовать производный (от данного) алгоритм поиска, либо написать более универсальный алгоритм. Программистам хорошо известно, что универсальность редко сочетается с производительностью. И все же хочу предложить свою идею, поскольку она хорошо сочетает универсальность с производительностью.

Для начала хочу упомянуть, что длинные строки (AnsiString) располагаются в памяти вместе с длиной строки. Получив адрес строки, затем отняв от него 4 байта, вы попадаете на адрес длины строки. Рассказываю это для системных программистов, так как программистов на Delphi, Visual Basic и C++ мало интересует, как там хранятся и сравниваются строки или массивы. Реализовав новый алгоритм на ассемблере, вы получите универсальную и быструю функцию поиска. Так вот, поле длины строки всегда задано типом DWord (4 байта). В общем случае то же относится и к байтовым массивам. Плохо, что в стандарт "длина-содержимое" сложно внедрить еще одно DWORD-поле, поэтому придется делать как-то иначе.

Суть моего предложения состоит в том, чтобы расположить перед длиной строки еще одно DWORD-поле. Для удобства назовем его "Контрольный код содержимого". Установка содержимого любой строки включает в себя: вычисление контрольного кода, установку длины строки и ее содержимого. Вычисление контрольного кода выполняется как побайтное сложение всех байт содержимого строки в DWORD-сумму.

Новый алгоритм поиска включает в себя дополнительное сравнение - сначала сравниваются контрольные коды содержимого двух строк, при их совпадении сравниваются длины строк, и при совпадении длин сравнивается содержимое строк. Формально алгоритм поиска принимает такой вид (для наглядности я вывел тип TNewString, чтобы вы видели, что работа ведется с измененным типом строки).

type TNewString = packed record

CRC: DWord;

Text: AnsiString;

end;

var

m: array[1..1000] of TNewString;

procedure Find(s: TNewString);

var

i: Integer;

begin

for i = 1 to Length(m) do

if s.CRC = m[i].CRC then

if Длина(s.Text) = Длина(m[i].Text) then

if Содержимое(s.Text) = Содержимое(m[i].Text) then

нашли строку в m[i];

end;

На первый взгляд кажется, что дополнительное сравнение прибавит к времени поиска еще лишнее время, но на деле это не так. Контрольный код позволяет с большой долей вероятности определять не равные строки, даже не прибегая к анализу их длин. Смысл в том, что одинаковые строки дадут одинаковый контрольный код. Но за любую универсальность приходится расплачиваться определенными исключениями, когда нововведение вместо пользы приносит лишние затраты. А любое нововведение хорошо только в том случае, если его "закономерные" затраты меньше затрат без него. И здесь новшество с контрольным кодом справляется самым лучшим образом. Дело в том, что контрольный код может быть одинаковым у заведомо разных строк. Объясню это на примере.

Допустим, мы сравниваем строку "вот так" со строкой "так вот". Контрольный код у них будет одинаковый, так как в обеих строках имеются те же самые символы. Алгоритм с контрольным кодом сравнит контрольные коды строк, затем длины строк, затем первый символ строк и найдет различие. Обычный алгоритм сравнит длины строк, а затем первый символ строк и также найдет различие. Выигрыш обычного алгоритма составит одно лишнее DWORD-сравнение алгоритма с контрольным кодом. В кризисных ситуациях (те самые исключения) алгоритм с контрольным кодом несет с собой самые минимальные затраты в виде лишнего DWORD-сравнения.

А теперь посмотрим, насколько превосходит алгоритм с контрольным кодом в "тяжелых" случаях сравнения. Допустим, мы сравниваем строку "Какие восхитительные цветы" со строкой "Какие восхитительные цвета". Обычный алгоритм обнаружит различие в строках, когда дойдет до сравнения последнего символа строк, в то время как алгоритм с контрольным кодом обнаружит различие уже в результате сравнения контрольных кодов строк. Выигрыш измеряется отсутствием значительного количества лишних операций.

Теряя минимум в своих кризисных ситуациях, алгоритм с контрольным кодом дает максимум производительности в кризисных местах алгоритма-соперника. Новый алгоритм поднимает производительность поиска на порядок. При обработке сверхвысоких объемов информации такой алгоритм может оказать неоценимую услугу, высвобождая из времени поиска весомую его долю.