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



Posted by Владимир Секретев (24.42.161.96) on June 07, 2002 at 22:12:24:

In Reply to: Снова о сортировке. Еще один подход. Я - против сортировки! posted by Аркадий Водяник on June 07, 2002 at 01:30:12:

Аркадий пишет:

в подавляющем большинстве случаев
"дотошная" сортировка с учетом всех знаков строк не нужна достаточно ограничиться несколькими первыми знаками


Действительно, именно этот "фокус", о котором я помалкивал, а теперь счел уместным рассказать, и позволяет моему алгоритму почти на равных бороться по скорости с "сортировкой с перекодированием".

Ведь для обеспечения надежной сортировки при перекодировании приходится перекодировать ВСЮ строку, так как не известно заранее, до какой глубины она будет просматриваться.

Мой алгоритм просматривает строку именно на ту глубину, на какую надо. Замеренная средняя глубина
просмотра (при 100% правильной сортировке) составила на тестовом массиве в 3000 строк всего 2.36 буквы!

Это значит, что если я, в своем алгоритме, ухудшу качество сортировки за счет уменьшения глубины просмотра, то заметный эффект по скорости получится только для глубины в 2 буквы!


Кстати о "6 знаках" в заметке Аркадия.

Моя статистика показывает, что 6 знаков это даже много. Похоже, что вполне достаточно 3-ёх.


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

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

Смею уверить, что правильная сортировка НУЖНА. Ибо, если ОПЕРАТОР вдруг заметит, что список отсортирован не правильно, то это может вызвать недоумение, сомнения в корректности работы программы. "А вдруг что-то пропало?". Значит разработчика - на ковер!

Кроме того, это может дать аргументы в руки недобросовестных конкурентов. "Ха, они сортировать не умеют!" Объясняй потом, что это было сделано намеренно, исходя из соображений разумной достаточности (я, кстати, за нее).

Мы же работаем с живыми людьми и, к сожалентю, не всегда доброжелательно настроенными. :(


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

Конечно, да! И он ТОЖЕ. Но сортировка - это традиция, от которой отойти не удасться именно потому, что она засела в генах с пеленок, с первого Букваря, где буквы алфавита отсортированы в алфавитном порядке. :)))


Так "Добро пожаловать в Клуб любителей быстрых поиска и сортировки!".

Подпись



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