Лекции по информатике (984119), страница 16
Текст из файла (страница 16)
Без ограничения общности предположим, что алфавит последовательности и образца цифровой и строки име>от простую числовую интерпретаци>о. Если р[0... ЛХ вЂ” 1) образец, то через Р обозначим число, десяти шой записью которого он является. В последова,тельности в[0... Л> — 1) >71 = 0,1,..., Л> — Л| — 1 обозначим через Я число, десятичным изображением которого является подстрока я[1, .. Х + ЛХ вЂ” 1).
Очевидно, 1 является допус:тимым сдвигом при ускоренном поиске тогда и только тогда. когда соотвстствук>- щая подстрока в совпадает с образцом р. Если бы мы могли вычислить Р за время 0(М), и все Я; за время 0(ЛС), то мы смогли бы за это же время найти все допустимые сдвиги, сравнивая Р со всеми Я . Однако для длинных образцов это может привести к слишком большим числам даже лля 64-битной целочисленной и адресной арифметики, которая до сих пор остается уделом профессиональных вычислений. Вычислить Р за линейное время 0(ЛХ) можно по схеме Горнера: Р = рм д+ 10(рм 2 1-... + 10(Х»+ 10ро)...) Точно также за время 0(ЛХ) можно вычислить Яш Чтобы вычислить >>, >2...., Яь,>г > за время О('У вЂ” ЛХ) заметим, что при известном Я можно вычислить Я „> за постоянное [а, значит, очень малое) время: Я,:., = 10(Я> — 10м-'з,) + з„м Чтобы получить строку в[у 1-1...
1-1 ЛХ) из а [1... 1 1- ЛХ вЂ” 1) надо удалить первую цифру старой строки (это аналогично вычитанию 10м ' в ) и приписать к ней справа следующую цифру из последовательности [текстовый аналог сложения с цифрой в и). Заметим, что константу 10м " можно вычислить заранее, причем за время, пропорциональное 011о~ М) (этот способ основан на двоичном разложении числа М )36[).
Таким образом, все числа Р, 5о, 5„..., 5р; м > могут бьгп найдены за время 0(Л> 1 М), за это же время могут бьггь найдены вес вхождения образца р в последовательность а. До сих пор мы не касались вопроса о величине чисел Р и Я . При достаточно длинном образце эта характеристика может оказать существенное влияние на время работы алгоритма,, поскольку затраты на непосредственное вычисление и хранение чисел, длиннее машинного слова,,линейны, а не постоянны, как в случае аппаратной реализации. К счастью, эту трудность можно обойти таким образом: надо проводить вычисления Р и > по модулю д. Тогда все числа не будут превосходить сХ и можно считать, что каждое из чисел Р и о действительно будет вычислено за постоянное время. В общем случае лля алфавита (О, 1,..., а>) выбирают такое простое число >1, что дд помещается в машинное слово.
Бессмысленно выбирать не простые числа, поскольку вероятность холостс>го срабатывания возрастает пропорционально квадрату НОД(сХ, .Я , .Р). Соотношение для вычисления Я .» принимает вид: о,. > = (сХ(Я, — к,1>) 1- э, и) пн>с1о, 6 = с1 (>пос1 >Х). Вычисления по модулю д всем хороши, кроме одного: из 8 = 'Р (шос1 с7) еще не слс; дует 8 = 'Р. Из неравенства Я, ф Р (шос1 т1) следует.
что образец нс входттт в последовательность, начиная с позиции у, а вот в случае Я. = Р (пюс1 с() необходимо проверить, совпадают ли строки р[0... М вЂ” 11 и з[1... у + М вЂ” 1]. Если они совпадатот. то вхождение найдено, в противном случае имест место хо.ластов срабатывание этого опс"ночного поискового алгоритма,.
Если простое число Ч достаточно велико, то вероятность холостых срабатываний будет очень мала. Оценим максимальную ллину. образца, гарантированно отыскиваемого без холостых срабатываний для аппаратно реализованной 64-битной арифметики при использовании вполне достаточного для практики 8-битного алфавита из 256 знаков. Как было отмечено выше, в качестве множителя с7 необходимо выбрать простое число, такое что сЩ < 2е~. Отсюда следУет, что т7 < 2зе, и сУществУют два таких обРазца Рт и Рг длиной по 7 знаков каждый, что рт = рг (шос1 т7). Поскольку длина образца измеряется сугубо целым числом байтов, то придется уступить еще один байт и перейти в следующий логарифмический поддтлапазон [2~г,2'в), в котором найдется простое число т1: 2лг < т7 < 2ьв, и чем ближе к правой границе, тем лучше.
Это уменьшит вероятность холостых срабатываний. ргоигаш 11К((прп(,оп(рпС); сопвС Мтпах -- 100; (' Максттмальная длина образца ) Хтпах — 10000; (' Максимальная, длина текста ( с( 256; (' Основание системы счис.ленив для, интерпретации образца, и подтттрок последовательности — достолпочтто для, 8 — битттьтх кодировок, ) с1 -- 27021597764222939; (' Наибольтаее простое (тр) число оттт 2 до МахуиС для бл— бтлтттой арифмепт ики ) ('т7 = 8388598); (' Для.
кухоттттых и бытовых (38 бити) процессоров ) ттаг Х, М: шСеиег; (' Фактттческая длина птекста и образца ) р: аггау [О..Мшах — 1[ оС'сЬаг; (' Образец 3 з: аггау [О..Хшах — 1[ оГсЬаг:, (' Текст 3 рО, зО: шСеиег; (' Значения характеристпических чисел образца и фрагмента носледовательпосттит (так называемая бегущая сумма) ) (т: шСеиег; (' Множитель для вьтчис.ления бегущей суммы равен значенито функции тт = дд' т (тпос1 т7) ) 1, 1с: шСеиег; Ьеиш лчпСе1п; (т Считпътвание тпекста ) Х:-- 0; Мп1е поС ео1п с1о Ьеиш геас1 (з [Х[); Х: — Х вЂ”:1; епс1; геас11п; гереаС ллччСе1п; ллт1Се('> '); М:-- 0; (' С аштыватате образца, ) Мп1е поС ео1п с1о Ьеиш геас1[р[М]):, М:-М -1; епс1; геасПп; глггйе1п; 1Г М ~> О СЬеп Ьеи1п 1г: 1; Гог г: 1 $о М вЂ” 1 с1о 1г: Ь * <1 пюс1 <1; ( сг = <ггг ' [<по<1 <г) у рО: О, ао: — — О; Хог г: - 0 $о ш — 1 с1о Ьея1п ( Вычисление характерггсгпггческггх чисел гг ро:-- [с1 * ро '- ог<Цр[1]) ) гпос1 с1:, ао ь- [<1 * во — оЫ[а[г ]) ) пюс1 с1; епс1; Гог г:== 0 Фо Х вЂ” М вЂ” 1 с1о Ьеи1п 11' ро = го ФЬеп Ьеи1п ( Если характеристическгге числа совпали гг 1<: =- 0; ( Прямое сравнение ггодстрокгг с образи,ом, гг Мп1е [1«-= М) апс1 [р[1<] =- в[г — ' 1с]) с1о 1< г-- 1< — 1; 1Г 1< >-- М СЬеп ( Совпадение с образцом г глтйе1п[г); епс1; ( Несовпадение, вьгчисление следующего хараклперистического числа 5 во:-- Иго — [1г л ос<1[а[1]) )) л с1 + ос<1[а[г + М])) гпос1 с1; ( пр<гд<гиогсегггге по образцу — позггг1ггогггг<ге вычитангге старой, буквьч из конца 'гггала (стариппЪ 1нгзряд) и доб<г<слгегггге новой в начало числа (младигггг1 р<гзряд) К ао г О ФЬеп во: — во+ ц епс1 епс1 шй11 ш -- 0; ( Вот зачем нам поиадоби.лось 256 — ричная, сггстема счис.лег<из из 1 семестра! гг епс1.
6.2 Алгоритмы сортировки 6.2. 1 Введение Сортировка, представляет собой хороший прилг<гр задачи, для решения которой суп«гствует множество различных алгоритмов. Каждый из них имеет свои достоинства и свои недостатки, и выбор нужного алгоритма зависит от многих конкретных условий [52, 65].
Сортировку следует понимать как процесс перестановки заданного множества объектов в некотором порядке. Цель сортировки — облегчить последующий поиск элементов В такОм Отсорти1эол>ане!оъл мнОжестВе. С(>р'1'ирОВка этО Одие1 из уе1иВерсальн1ях ОснОВОНО- лагающих видов обработки данных. Телефонные книги, словари, оглавлеллия библиотек, прайс-листы вот примеры отсортированных „:Гля поиска множеств хранимых обьек~ц Сортировка, является непреъленным разделом любого фундаментального курса обучения программированик> ~36~. При построении алгоритмов сортировки используется множество классических универсальных приемов.
Трудно найти какую-либо другун> задачу, для которой было бы изобретено такое огромное разноооразие алгоритмов. Алгоритмы сортировки идеально подходят для сложностного ан<;лиза. С другой сторс>ны, сортировки„ как и поиск, показывают, что за быстроту работы и экономию памяти приходится расплачиваться существенным усложнением алгоритмов и структур данных. Выбор алгоритма всегда зависит от структуры обрабатываемых данных. В случае сортировки эта зависимость столь глубока, что соответствующие методы распадаются на два почти непересекающихся класса - сортировку ллассиво<л и сортировку файлов (посггедовагпельносгпей).
Иногда их называют внутренними и внешними сортировками, поскольку массивы хранятся в основной (оперативной, внутренней) памяти машины с произвольным доступом, а файлы обычно размещаются в медленной, но более емкой, дешевой и долговременной внешней памяти, на электромеханических устройствах, основанных на поступательноъл или вращательном движении носителя. Уже на примере сортировки колоды игральных карт для пасьянсов или фокусов ясно, что удобнее разложить все карты на большом столе в прямом доступе так, чтобы все они были одновремешю видны.
Если же сортируемые карты по каким-.либо Глричинам должны оставаться в колоде, то сортировка идет вс><епуло, Гюскольку видна только одна карта. Так же приходится сортировать и очень большие колоды, для которых не хватит никакого стола. Заметим, что раскладка пасьянса является своеобразным недетерминированным процессом сортировки, в то время как гадание скорс'е являетс:я поисколл с сулцественно нслформальной сеълантической интерпретацией. Для постановки задачи сортировки введем некоторые понятия и обозначения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
