Есть ли причина для реализации моего собственного алгоритма сортировки?

Question

Сортировка изучалась десятилетиями, поэтому, конечно, алгоритмы сортировки, предоставляемые любой платформой программирования (java, .NET и т. Д.), Должны быть хорошими, верно? Есть ли причина переопределять что-то вроде System.Collections.SortedList?

Answer 1

Бывают моменты, когда ваше глубокое понимание ваших данных может привести к гораздо более эффективным алгоритмам сортировки, чем любой доступный алгоритм общего назначения. Я поделился примером такой ситуации в другом посте в SO, но я поделюсь им, чтобы привести конкретный пример:

Еще во времена COBOL, FORTRAN и т. Д. Разработчик, работавший на телефонную компанию, должен был взять относительно большой кусок данных, состоящий из активных телефонных номеров (я полагаю, это было в районе Нью-Йорка) и отсортировать этот список. В первоначальной реализации использовалась сортировка кучи (это были 7-значные телефонные номера, и во время сортировки происходила большая замена диска, поэтому сортировка кучи имела смысл).

В конце концов, разработчик наткнулся на другой подход: осознав, что в его наборе данных может существовать один и только один из каждого телефонного номера, он понял, что ему не нужно хранить сами номера телефонов в памяти. Вместо этого он рассматривал все 7-значное пространство телефонных номеров как очень длинный битовый массив (при 8 телефонных номерах на байт для 10 миллионов телефонных номеров требуется чуть более одного мегабайта для захвата всего пространства). Затем он сделал один проход через свои исходные данные и установил бит для каждого найденного им телефонного номера равным 1. Затем он сделал последний проход через битовый массив в поисках старших бит и вывел отсортированный список телефонных номеров.

Этот новый алгоритм был намного, намного быстрее (по крайней мере, в 1000 раз быстрее), чем алгоритм сортировки кучи, и занимал примерно столько же памяти.

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

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

Однако, если сортировка является вспомогательной частью вашего приложения, или вы просто реализуете алгоритм общего назначения, очень велики шансы, что некоторые чрезвычайно умные типы университетов уже предоставили алгоритм, который лучше, чем вы будете в состоянии придумать. Быструю сортировку действительно сложно превзойти, если вы можете хранить вещи в памяти, а сортировка кучи довольно эффективна для упорядочения массивных данных (хотя я лично предпочитаю использовать реализации типа B + Tree для кучи, поскольку они настроены на разбиение на страницы диска производительность).

Answer 2

Обычно нет.

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

Answer 3

Внедрение собственного алгоритма сортировки сродни оптимизации, и, как сказал сэр Чарльз Энтони Ричард Хоар , «мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация является корнем всех». зло».

Answer 4

В некоторых библиотеках (например, в самой собственной Коллекции Java) сортировка осуществляется на основе критериев, которые могут или не могут применяться к вам. Например, Collections.sort использует сортировку слиянием для эффективности O (n log (n)), а также для фактической сортировки на месте. Если два разных элемента имеют одинаковое значение, первый элемент в исходной коллекции остается впереди (хорошо для многопроходной сортировки по разным критериям (сначала сканирование по дате, затем по имени, коллекция остается по названию (затем по дате), отсортированной)) Однако, если вам нужны немного лучшие константы или у вас есть специальный набор данных, возможно, имеет смысл реализовать собственную быструю или радикальную сортировку, точно соответствующую тому, что вы хотите сделать.

Тем не менее, все операции выполняются быстро при достаточно малых n

Answer 5

• Возможно, вы захотите многопоточную реализацию сортировки.
• Вам могут потребоваться более высокие характеристики производительности, чем в Quicksorts O (n log n), например, bucketsort.
• Возможно, вам потребуется стабильная сортировка, в то время как алгоритм по умолчанию использует быструю сортировку. Специально для пользовательских интерфейсов вы хотите, чтобы порядок сортировки был согласованным.
• Для используемых структур данных могут быть доступны более эффективные алгоритмы.
• Вам может потребоваться итеративная реализация алгоритма сортировки по умолчанию из-за переполнения стека (например, вы сортируете большие наборы данных).

до бесконечности.

Answer 6

краткий ответ; нет, за исключением академического интереса.

Answer 7

Если у вас есть опыт внедрения алгоритмов сортировки и вы понимаете, как характеристики данных влияют на их производительность, то вы уже знаете ответ на свой вопрос. Другими словами, вы уже знаете, что у QuickSort есть пешеходная производительность по сравнению с почти отсортированным списком. :-) И что, если у вас есть данные в определенных структурах, некоторые виды сортировки (почти) бесплатны. И т.д.

В противном случае, нет.

Answer 8

Проблема сортировки общего назначения была исследована в аду и обратно, поэтому беспокоиться об этом вне академического интереса бессмысленно. Однако большая часть сортировки не выполняется для обобщенного ввода, и часто вы можете использовать свойства данных для увеличения скорости сортировки.

Типичным примером является сортировка подсчета. Доказано, что для сортировки сравнения общего назначения O (n lg n) - лучшее, что мы можем когда-либо надеяться сделать.

Однако предположим, что мы знаем диапазон, в котором сортируемые значения находятся в фиксированном диапазоне, скажем, [a, b]. Если мы создадим массив размером b - a + 1 (по умолчанию все равно нулю), мы можем линейно сканировать массив, используя этот массив для хранения счетчика каждого элемента, что приведет к линейной сортировке по времени (по диапазону данных ) - нарушение границы, но только потому, что мы используем специальное свойство наших данных. Подробнее см. здесь .

Так что да, полезно написать собственные алгоритмы сортировки. Обратите внимание на то, что вы сортируете, и иногда вы сможете придумать замечательные улучшения.

Answer 9

Несколько месяцев назад блог Coding Horror сообщил о какой-то платформе с ужасающе плохим алгоритмом сортировки. Если вам нужно использовать эту платформу, вы наверняка захотите реализовать свою собственную.