 |
Сортировка строк по словам.
|
|
|
|
Сортировка слов является более полезной, нежели по символам. Однако типичные задачи требуют более быстрой методики сортировки, нежели описанные в главе 4. Здесь будет описываться
Существуют довольно мало причин, когда может потребоваться сортировка по символам. Гораздо больше причин для сортировки слов. Например, алфавитный указатель в книге – это список слов, найденных в книге с номерами страниц, на которых они встречаются. Слова в таком указателе должны быть отсортированы в алфавитном порядке. Однако даже создание такого списка – нелегкая работа, в котором сортировка играет ключевую роль.
Рассмотрим 400-страничную книгу с 500 словами на странице – книгу из 200 000 слов. Предположим, что в ней есть 3 000 уникальных слов. Каким образом они могут быть найдены? Самым простым способом было бы отсортировать всю книгу целиком, а затем пройтись по отсортированным строкам, выкинуть дубликаты, которые будут собраны вместе после сортировки. На самом деле, это не такая уж элементарная задача.
SelectSort требует n2 операций чтения-записи файла длиной n символов. Предположим, что длина слова, в среднем, 5 символов, а также пробел между каждой парой слов. SelectSort потребует 200000* 200000=4*1010 операций чтения-записи слов и 24*1010 операций чтения-записи символов. Поскольку в году всего лишь 313 360 секунд в году, даже при миллионе операций чтения / записи в секунду эта задача потребует 9 месяцев выполнения, что на практике вовсе не подходит.
Другим способом создания списка слов, могло бы быть сортировка слов на первой странице, удаление дубликатов, затем на второй и т.д. На первой странице будет меньше 500 слов, но большинство из 3000 уникальных слов могут появиться на нескольких первых страницах. Как только это произойдет, на каждой странице необходимо будет отсортировать 3500 слов. В самом худшем случае нам придется сортировать 400 раз по 3500 слов. Количество операций чтения / записи на каждой странице будет равно 3500 * 3500 = 1.225 * 107, а для всей книги – 3500 * 3500 * 400 = 4.9 * 109 или 2.94 * 1010 операций чтения-записи символов. Что ж, раз в 8 лучше, однако все равно потребует больше месяца выполнения.
|
|
|
Стратегия сортировки, которую мы разработаем в дальнейшем, требует только n * k операций чтения для сортировки файла длиной n символов, где k – наименьшее целое, такое, что
2k >= n
Для n = 200 000, количества слов в книге, количество операций чтения требуемое при такой сортировке будет:
n * k = 200000 * 18 = 3 600 000 (поскольку 218 = 262144 > 200000)/
Опять таки, предположив, что слова у нас в среднем имеют длину 5 символов и должны быть разделены пробелом, сортировка слов потребует 21 600 000 операций считывания символов (немногим больше 21 секунды). Для простоты и сравнения с SelectSort эта новая стратегия сортировки будет разработана для сортировки символов.
10.2.1 Сортировка при помощи разделения и слияния.
Две отсортированные строки могут быть объединены в одну отсортированную строку при помощи циклического сравнивания их первых символов и перемещения символа, который должен быть первым в конец новой строки.
Например, рассмотрим две отсортированные строки:
Cow
Art
Сначала сравниваются a и c, и a выбирается в качестве начала новой строки, сравнивая c и r, мы добавляем символ c в конец строки. Выполнение пошагового слияния строк показано в следующей таблице:
| После выполнения шага | Старые строки | Новая строка | |
| cow | art | ||
| cow | rt | a | |
| ow | rt | ac | |
| w | rt | aco | |
| w | t | acor | |
| w | acort | ||
| acortw |
Таким образом, если файл может быть разделен на отсортированные части, называемые сериями (runs), то он может быть отсортирован путем объединения этих серий. Произвольная строка не может быть просто разделена на две серии за один проход, но она может быть разделена на две строки, каждая из которых содержит несколько серий. Путем повторяющихся операций разделения и слияния может быть получена отсортированная строка. Покажем это на примере. Рассмотрим строку
|
|
|
Character,
которая содержит 4 серии: ch, ar, act, er. Разделив символы на 2 новые строки и переключаясь между строками после обработки каждой серии, будут созданы строки:
ch·act
ar·er
(точка не является частью строки, а лишь показывает разрыв между сериями).
Объединяя эти строки символ за символом, получим в результате:
| После выполнения шага | Старые строки | Новая строка | |
| chact | arer | ||
| chact | rer | a | |
| hact | rer | ac | |
| act | rer | ach | |
| ct | rer | acha | |
| t | rer | achac | |
| t | er | achacr | |
| t | r | achacre | |
| t | achacrer | ||
| achacrert |
Склеенная строка теперь содержит 3 серии: ach, acr, ert. Снова разделяем ее на две строки по сериям:
ach·ert
Acr
после объединения получим:
aacch·errt
Разделение строк дает:
Aacch
Errt
И третья операция слияния дает нам сортированную строку:
Aaccehrrt
Другой способ слияния – слежение за границами серий и перемещение всех символов в паре серий до рассмотрения следующее пары серий. Для выше упомянутого примера, разделив строку на:
ch·act
ar·er
после слияния мы получим:
aacch·errt
а после второго разделения/слияния мы получим отсортированную строку гораздо быстрее, чем при посимвольном слиянии.
Разница между слиянием по символам и слиянием по сериям огромная. Слияние по сериям гарантирует нам уменьшение количества серий наполовину, поскольку каждая пара серий будет превращена в одну серию. Слияние по символам не обладает таким свойством.
Сортируемый файл может уже содержать длинные серии, но может и не содержать. В общем случае нам могут быть гарантированы только серии единичной длины – отдельные символы. Если файл будет разделен на чередующиеся символы, то каждый кусочек будет содержать серии единичной длины. Затем они могут быть объединены для получения серий длиной в 2 символа. Разделяя файл на чередующиеся серии длины 2 и, объединяя их, мы получим серии длиной 4 символа и т.д. При этом, случайно возможные серии большей длины игнорируются, однако эта процедура стабильно приближает нас к конечному результату. Мы сможем избежать подсчета длины серий, если обозначим символом # искусственные границы серий. Пример данного процесса показан ниже для строки wrcaot:
|
|
|
| Шаг | Разделенные строки | Склеенная строка | |
| w#r#c#a#o#t# | |||
| Разделение | w#c#o# | r#a#t# | |
| Слияние | rw#ac#ot# | ||
| Разделение | rw#ot# | ac# | |
| Слияние | acrw#ot | ||
| Разделение | acrw# | ot# | |
| Слияние | acortw# |
Этот процесс прекращается, когда текст содержит одну-единственную серию. Процедура MergeSort1 будет спроектирована с использованием этих идей.
Design part 2
ROCEDURE MergeSort1 (VAR Txt: TEXT);
VAR
Temp1, Temp2: TEXT;
Sorted, Ch: CHAR;
{включает в себя процедуру CopyOpen(VAR F1, F2: TEXT)
Копирует строку из F1 в F2 без выполнения RESET и REWRITE;
поэтому F1 должен быть открыт для чтения, а F2 для записи,
а строки прошлого в этих файлах могут не быть пустыми}
BEGIN {MergeSort1}
{присвоить переменной Sorted значение ‘Y’ если Txt отсортирован, иначе - ‘N’ };
{разделить n символов в Txt на n серий единичной длины, разделенные символом ‘ #’ };
WHILE Sorted = ‘N’
DO
BEGIN
{разделить n/k серий длины k из Txt в n/2k серий в файлах Temp1 и Temp2};
{соединить n/2k серий длины k из файлов Temp1 и Temp2 в n/2k серий длины 2k в файл Txt};
{присвоить переменной Sorted значение ‘Y’ если файл Txt отсортирован, иначе присвоить ‘N’};
END
END {MergeSort1}
10.2.2 Слияние серий.
Когда количество серий нечетно, он не могут быть просто разделен на 2 файла, например, rw#ac#ot# разделяется на rw#ot# и ac#. Таким образом, во время слияния после того, как один разделенный файл буд полностью считан, другой еще может содержать одну серию, которая должна быть скопирована в в объединенный файл без каких-либо сравнений.
Раздел проекта
{соединить n/2k серий длины k из файлов Temp1 и Temp2 в n/2k серий длины 2k в файл Txt};
будет спроектирован как вызов процедуры
MergeRuns(Temp1, Temp2, Txt)
объявленной как:
Design Part 2.1
PROCEDURE MergeRuns(VAR In1, In2, Result: TEXT);
{склеивает серии из In1 и In2 в Result }
VAR
|
|
|
Ch1, Ch2: CHAR;
BEGIN {MergeRuns}
{инициализируем параметры файлов}
WHILE NOT EOLN(In1) AND NOT EOLN(In2)
DO
BEGIN
{склеиваем серии из In1 и In2 в Result}
END
{копируем последнюю серию из In1 или In2 (если такая имеется) в Result};
{сбрасываем параметры файлов}
END{MergeRuns}
Во время слияния, символы, содержащиеся в одной из двух серий, будут потрачены первыми. Таким образом, остаток из первой или второй серии необходимо будет скопировать в результирующий файл.
Design Part 2.1.1
BEGIN {копируем серии из In1 и In2 в Result}
READ(In1, Ch1);
READ(In2, Ch2);
WHILE (Ch1 <> ‘#’) AND (Ch2 <> ‘#’)
DO
{копируем меньший символ из Ch1 и Сh2 в Result и считываем
следующий символ из соответствующего файла};
{копируем остаток серии In1};
{копируем остаток серии In2};
WRITE(Result, ‘#’)
END
Design Part 2.1.2
BEGIN {копируем последнюю серию из In1 или In2 (если такая имеется) в Result}
IF EOLN(In1) AND EOLN(In2)
THEN
WRITELN(In1);
ELSE
IF NOT EOLN(In1)
THEN {копируем оставшуюся серию из In1 (если такая имеется) в Result}
CopyOpen(In1, Result)
ELSE {копируем оставшуюся серию из In2 (если такая имеется) в Result}
CopyOpen(In2, Result)
END
10.2.3 Разделение серий.
Процедура также скрывает детали разделения одного файла на два. Часть
{разделить n/k серий длины k из Txt в n/2k серий в файлах Temp1 и Temp2}
будет спроектирована как оператор вызова процедуры
SplitIntoRuns(Txt, Temp1, Temp2)
Design Part 2.2
PROCEDURE SplitIntoRuns(VAR FileIn, Result1, Result2: TEXT)
{разделяем серии из FileIn в серии в каждом из файлов Result1 и Result2}
VAR
Switch, Ch: CHAR;
BEGIN {SplitIntoRuns}
RESET(FileIn);
REWRITE(Result1);
REWRITE(Result2);
{копируем серии попеременно в Result1 и Result2}
WRITELN(Result1);
RESET(Result1);
WRITELN(Result2);
RESET(Result2)
END {SplitIntoRuns}
Процедура SplitIntoRuns требует 2 символьные переменные: Ch для копирования символов и Switch для запоминания файла, в который происходит копирование в настоящий момент.
Design Part 2.2.1
BEGIN {копируем серии попеременно в Result1 и Result2}
Switch:= ‘1’;
WHILE NOT EOLN(FileIn)
DO
BEGIN
Read(FileIn, Ch);
{копируем Ch в Result1, если Switch=’1’, иначе – в Result2}
{Если встречен конец серии (Ch = ‘#’), то переключаем Switch на другой файл}
END
END
Завершение MergeSort1
Склеенный файл проверяется в двух местах программы, для того, чтобы определить, является он отсортированным или нет, поэтому эта проверка является естественным кандидатом для оформления в виде оператора процедуры:
{присвоить переменной Sorted значение ‘Y’ если Txt отсортирован, иначе - ‘N’ }
будет оформлено в
|
|
|
