Снова о сортировке. Еще один подход. Я - против сортировки!



Posted by Аркадий Водяник (195.58.229.59) on June 07, 2002 at 01:30:12:

In Reply to: Версия 1.4 - turbo posted by Владимир Секретёв on June 06, 2002 at 16:28:39:

В своем сообщении 4371 я выступил за предварительную
подготовку сортируемого материала в соответствии с заданным
алфавитом и использование оператора sort array.
На 1000 строк (машине P233) предварительная подготовка
длилась 424 мс.

Вспомним, однако, что в подавляющем большинстве случаев
"дотошная" сортировка с учетом всех знаков строк не нужна:
достаточно ограничиться несколькими первыми знаками. Ниже
показан пример подготовки к сортировке по первым 6 знакам.
Как видно, время подготовки удалось уменьшить в 3.7 раза.
Надо отметить, что здесь все подготовлено для сортировки
не строкового, а числового массива. Сортировка же
числовых массивов выполняется в общем случае существенно
быстрее строковых (в этом сообщении не показано).
Дальнейшие манипуляции с сортировкой должны быть такими же,
как показано в 4371.


Вpеменной пpофиль фоpмы M

Количество выполнений: 1 (машина та же - P233)
На это количество выполнений потpебовалось 115 мс = 100%
Распpеделение вpемени по стpокам исходного текста в относительных %, и мс:

~ ~¦0001 *
~ ~¦0002 W=256
~ ~¦0003 w1=W * W * W * W * W
~ ~¦0004 w2=W * W * W * W
~ ~¦0005 w3=W * W * W
~ ~¦0006 w4=W * W
~ ~¦0007 w5=W
~ ~¦0008 w6=1
~ 2¦0009 [w 1,w1,w2,w3,w4,w5,w6]
~ ~¦0010 *
~ ~¦0011 * Пусть необычный алфавит для сортировки задан массивом а.
~ 3¦0012 for i=1 to 256 [a i,256-i];endfor
~ ~¦0013 *
~ ~¦0014 * Пусть p - подлежащий сортировке массив.
~ ~¦0015 * Для наших целей достаточно иметь только один элемент массива,
~ ~¦0016 * так как в этом примере мы не будем вызывать собственно SORT,
~ ~¦0017 * а сколько бы элементов массива не было на самом деле, на замерах
~ ~¦0018 * времени перекодирования это не скажется.
~ ~¦0019 *
~ 2¦0020 [p 1,'qwerty-'] строка длиннее, чем 6
~ ~¦0021 * Пусть нам требуется перекодировать 1000 элементов массива:
~ ~¦0022 *
~ 1¦0023 for j=1 to 1000
~ ~¦0024 t=0
~ 3¦0025 s=[p 1]
~ 4¦0026 L=[length s]
~ 3¦0027 if L > 6 L=6; endif
## 11.3% 13¦0028 for i=1 to L
############# 66.1% 76¦0029 t=t + [a [hc s,i]]*[w i]
~ 1¦0030 endfor
~ 5¦0031 [q 1,t]
~ 2¦0032 endfor

В этом примере первые 6 знаков строки рассматриваются как число
в 256-ричной системе счисления. В переменных w1..w6 подсчитаны
весовые коэффициенты каждой позиции для такой системы счисления.

Расширим такой подход для сортировки по первым 8 знакам.
Сузим алфавит: пусть он состоит из 26 строчных латинских,
26 прописных латинских, 32 строчных русских, 32 прописных
русских, 10 цифр и еще пробел зарезервируем (все остальное
считаем пробелом). Получим: 26+26+32+32+10+1=127.
Вот весовые коэффициенты:


w1=127*127*127*127*127*127*127
w2=127*127*127*127*127*127
w3=127*127*127*127*127
w4=127*127*127*127
w5=127*127*127
w6=127*127
w7=127
w8=1

Почему такой подход ограничен то 6-ю, то 8-ю литерами?
Из-за длины мантиссы чисел double (до 15 десятичных цифр).

* * *

Небольшое отступление:

Я считаю, что в наши дни сортировка это уже далеко не такое
базовое понятие и не такое уж необходимое и полезное дело.

Быстрый поиск - вот что нам нужно на самом деле.

Сортировка ускоряет поиск в бумажных словарях, на машинах
с предельно малой памятью, где поиск в сортированном массиве
быстр и не требует индексирования (например, применяют метод
деления пополам).

Дело построено далеко не оптимальным образом, если человеку
дают список каких-либо наименований длиной в несколько
тысяч позиций (отсортированных) и, по сути дела, предлагают
найти в нем что-либо глазами. Хотя для списка из сотни
элементов это еще неплохо, а иногда и единственно возможно -
если человек не знает, что он хочет.

Я дополнил бы предложенное Владимиром название
: Добро пожаловать в Клуб любителей быстрой сортировки!.
так:
Добро пожаловать в Клуб любителей быстрых поиска и сортировки!.



Пpишедшие ответы: