Название: Максимальное ускорение алгоритма поиска
Вид работы: реферат
Рубрика: Информатика и программирование
Размер файла: 16 Kb
Скачать файл: referat.me-138900.docx
Краткое описание работы: Если производится поиск DWORD-числа среди набора (массива) таких же значений, то самым оптимальным и скоростным будет последовательное сравнение заданного значения со всеми элементами массива до обнаружения совпадения.
Максимальное ускорение алгоритма поиска
Дмитрий Сахань
Временные затраты алгоритма поиска ощутимо чувствуются при обработке больших объемов информации. Если производится поиск 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-сравнения.
А теперь посмотрим, насколько превосходит алгоритм с контрольным кодом в "тяжелых" случаях сравнения. Допустим, мы сравниваем строку "Какие восхитительные цветы" со строкой "Какие восхитительные цвета". Обычный алгоритм обнаружит различие в строках, когда дойдет до сравнения последнего символа строк, в то время как алгоритм с контрольным кодом обнаружит различие уже в результате сравнения контрольных кодов строк. Выигрыш измеряется отсутствием значительного количества лишних операций.
Теряя минимум в своих кризисных ситуациях, алгоритм с контрольным кодом дает максимум производительности в кризисных местах алгоритма-соперника. Новый алгоритм поднимает производительность поиска на порядок. При обработке сверхвысоких объемов информации такой алгоритм может оказать неоценимую услугу, высвобождая из времени поиска весомую его долю.
Похожие работы
-
Программное определение числовых массивов
Одномерные числовые массивы, образование элементами целочисленного массива невозрастающей последовательности. Программное нахождение суммы элементов каждой возможной строки матрицы и формирование массива из найденных сумм, вывод массива-результата.
-
Вызов Функции
Вызов функции, то есть запись выражение (список_выражений), можно проинтерпретировать как бинарную операцию, и операцию вызова можно перегружать так же, как и другие операции.
-
Массивы в языках Pascal и Basic
Министерство образования РФ Средняя школа № 4 РЕФЕРАТ по информатике Тема: «Массивы в языках Pascal и Basic» Выполнила: ученица 10 «А» класса Рудых Елена
-
Лабораторная работа №12
Цель работы: Изучение правил описания и вызова подпрограмм: процедур и функций. Получение навыков и овладение приемами работы над подпрограммами. Задание№ 17
-
Лабораторная работа №11
Цель работы: Изучение правил и получение навыков составления программ с использованием сложных типов данных массивов. Задание№ 17 . Из символов произвольного предложения сформировать массив целых чисел, соответствующих порядковому номеру литер в коде ASCII. Определить максимальный элемент этого порядка.
-
Обработка одномерных массивов и матриц
Заполнение массива из целых чисел с присвоением элементам разных значений. Варианты программы с использованием различных операторов организации циклов. Определение квадрата максимального из четных элементов массива и общего числа нулевых элементов.
-
Понятие и элементы массива
Массив - это коллекция переменных, которые имеют общее имя и базовый тип. Функциональные возможности, виды массивов и их характеристика. Основные требования к входным и выходным данным массива. Использование IF THEN для перехвата всех возможных ошибок.
-
Информатика и ВТ
Вычисление произведения элементов массива. Обсуждение алгоритма. Текст программы. Линейный, циклический и разветвляющийся вычислительные процессы.
-
Массивы в языках Pascal и Basic
Массив в Бейсике. Массив в Паскале. Действия над массивами.
-
Поиск подстроки в строке с помощью хеш-функции
Поиск подстроки в строке - часто возникающая на практике задача. Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный и вообще грустный.