Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Максимальное ускорение алгоритма поиска
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 16:47:34 05 апреля 2006 Похожие работы
Просмотров: 43 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

Временные затраты алгоритма поиска ощутимо чувствуются при обработке больших объемов информации. Если производится поиск 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-сравнения.

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

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:15:31 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:33:44 24 ноября 2015

Работы, похожие на Реферат: Максимальное ускорение алгоритма поиска

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151310)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru