Реферат: Максимальное ускорение алгоритма поиска
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-сравнения.
А теперь посмотрим, насколько превосходит алгоритм с контрольным кодом в "тяжелых" случаях сравнения. Допустим, мы сравниваем строку "Какие восхитительные цветы" со строкой "Какие восхитительные цвета". Обычный алгоритм обнаружит различие в строках, когда дойдет до сравнения последнего символа строк, в то время как алгоритм с контрольным кодом обнаружит различие уже в результате сравнения контрольных кодов строк. Выигрыш измеряется отсутствием значительного количества лишних операций.
Теряя минимум в своих кризисных ситуациях, алгоритм с контрольным кодом дает максимум производительности в кризисных местах алгоритма-соперника. Новый алгоритм поднимает производительность поиска на порядок. При обработке сверхвысоких объемов информации такой алгоритм может оказать неоценимую услугу, высвобождая из времени поиска весомую его долю.