Самый эффективный алгоритм сортировки для большого набора чисел
В случае Windows, путь использует путь в стиле UNIX, поэтому сделайте обратную косую черту в прямую косую черту.
webbrowser.get("C:/Program Files (x86)/Google/Chrome/Application/chrome.exe %s").open("http://google.com")
См .: Python: универсальный webbrowser.get (). Open () для chrome.exe не работает
8 ответов
First, you will need a map of word -> count. 50 000 слов - это не много - легко поместится в памяти, так что волноваться не о чем. В C ++ вы можете использовать стандартный STL std :: map.
Затем, когда у вас есть карта, вы можете скопировать все ключи карты в вектор.
Затем отсортируйте этот вектор с помощью специального оператора сравнения: вместо сравнения слов сравните счетчики с карты. (Не беспокойтесь о конкретном алгоритме сортировки - ваш массив не такой большой, поэтому вам подойдет любая стандартная сортировка библиотеки.)
Я бы начал с быстрой сортировки и пошел бы оттуда.
Посетите вики-страницу об алгоритмах сортировки , чтобы узнать различия.
Вам следует попробовать сортировку MSD radix . Он отсортирует ваши записи в лексикографическом порядке . Вот проект кода Google , который может вас заинтересовать.
Посмотрите ссылку. Наглядное представление о том, как работает другой алгоритм. Это даст вам подсказку!
Вы можете получить лучшую производительность, чем быстрая сортировка, с этой конкретной проблемой, предполагая, что если два слова встречаются одинаковое количество раз, то не имеет значения, в каком порядке вы их выводите.
Сначала step: Создайте хэш-карту со словами в качестве ключевых значений и частотой в качестве связанных значений. Вы заполните эту хеш-карту, когда будете разбирать файл. При этом следите за самой высокой встречающейся частотой. Этот шаг имеет сложность O (n).
Второй шаг: Создайте список с количеством записей, равным наивысшей частоте из первого шага. Индекс каждого слота в этом списке будет содержать список слов с частотой, равной индексу. Таким образом, слова, которые встречаются в документе 3 раза, например, войдут в список [3]. Просмотрите хеш-карту и вставьте слова в соответствующие места в списке. Этот шаг имеет сложность O (n).
Третий шаг: Проходить по списку в обратном порядке и выводить все слова. Этот шаг имеет сложность O (n).
В целом этот алгоритм выполнит вашу задачу за O (n) времени , а не за O (nlogn), требуемую быстрой сортировкой.
Практически в каждом случае, который я когда-либо тестировал, Quicksort работал лучше всего. Однако у меня было два случая, когда Combsort был лучшим. Могло быть так, что комбинированная сортировка была лучше в тех случаях, потому что код был слишком маленьким, или из-за какой-то причуды в том, как были упорядочены данные.
Каждый раз, когда сортировка появляется в моем профиле, я пробую основные сортировки. У меня никогда не было ничего, что превосходило бы Quicksort и Combsort.
Я думаю, вы хотите сделать что-то, как описано в сообщении ниже:
http://karephul.blogspot.com/2008/12/groovy-closures.html
Языки которые поддерживают закрытие, делают решение намного проще, как и LINQ, как сказал Эрик.
Для больших наборов вы можете использовать так называемое «индексирование на основе сортировки» при поиске информации, но для 50 000 слов вы можете использовать следующее:
- прочитать весь файл в буфер .
- проанализировать буфер и построить вектор лексемы с struct token {char * term, int termlen; } термин - указатель на слово в буфере.
- отсортировать таблицу по термину (лексикографический порядок).
- установить номер записи = 0, выполнить итерацию по вектору терминов, когда термин новый, сохраните его в векторе: struct {char * term; int частота; } в index entrynum установите частоту равной 1 и увеличьте номер записи, в противном случае увеличьте частоту.
- отсортируйте вектор по частоте в порядке убывания.