Самый эффективный алгоритм сортировки для большого набора чисел

Question

Я работаю над большим проектом, я не буду суммировать его здесь, но этот раздел проекта должен взять очень большой текстовый документ (минимум около 50 000 слов (не уникальный)) выводите каждое уникальное слово в порядке от наиболее употребляемого до наименее используемого (вероятно, верхние три будут "a" "an" и "the").

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

Есть предложения?

Answer 1

Для начала вам понадобится карта слова -> кол. 50000 слов - это не много - он легко уместится в памяти, поэтому не о чем беспокоиться. В C ++ вы можете использовать стандартную STL std :: map.

Затем, получив карту, вы можете скопировать все ключи карты в вектор.

Затем отсортируйте этот вектор, используя пользовательский оператор сравнения: вместо сравнения слов сравните счетчики с карты. (Не беспокойтесь об определенном алгоритме сортировки - ваш массив не такой большой, поэтому любая стандартная сортировка библиотеки подойдет вам.)

Answer 2

Я бы начал с быстрой сортировки и пошел бы оттуда.

Посетите вики-страницу по алгоритмам сортировки , чтобы узнать различия.

Answer 3

Вы должны попробовать сортировку MSD radix . Он отсортирует ваши записи в лексикографическом порядке . Вот проект Google Code , который может вас заинтересовать.

Answer 4

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

Каждый раз, когда сортировка появляется в моем профиле, я пробую основные виды. У меня никогда не было ничего, что могло бы превзойти Quicksort и Combsort.

Answer 5

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

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

Второй шаг: Создайте список с количеством записей, равным наибольшей частоте с первого шага. Индекс каждого слота в этом списке будет содержать список слов с частотой, равной индексу. Так слова, которые встречаются в документе 3 раза, попадут, например, в список [3]. Выполните итерацию по хэш-карте и вставьте слова в соответствующие места в списке. Этот шаг - сложность O (n).

Третий шаг: Перебирать список в обратном порядке и выводить все слова. Этот шаг - сложность O (n).

В целом, этот алгоритм выполнит вашу задачу за O (n) времени , а не O (nlogn), требуемый быстрой сортировкой.

Answer 6

Посмотрите на ссылку. Наглядное представление о том, как работает другой алгоритм. Это даст вам подсказку!

Алгоритмы сортировки

Answer 7

Вы также можете попробовать реализовать цифровые деревья, также известные как Trie. Вот ссылка

Answer 8

Для больших наборов вы можете использовать так называемую «индексацию на основе сортировки» при поиске информации, но для 50 000 слов вы можете использовать следующее:

• прочитать весь файл в буфер.
• проанализировать буфер и построить вектор токена struct token {char * term, int termlen; } term - указатель на слово в буфере.
• сортировка таблицы по термину (лексикографический порядок).
• установить entrynum = 0, перебрать термин вектор, когда термин новый, сохраните его в векторе: struct {char * term; Int частота; } в index entrynum установите частоту в 1 и увеличьте номер записи, в противном случае увеличьте частоту.
• сортировка вектора по частоте в порядке убывания.

Answer 9

Я думаю, что вы хотите сделать что-то, как описано в посте ниже:

http://karephul.blogspot.com/2008/12/groovy-closures.html

Языки, которые поддерживают закрытие, делают решение намного проще, как LINQ, как упоминал Эрик.