Оптимизация количества слов

Question

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

У меня плоский набор случайных (английских) слов, по одному в каждой строке. Мне нужно написать эффективную программу для подсчета количества вхождений каждого слова. Файл большой (около 1 ГБ), но у меня достаточно оперативной памяти для всего. Они хранятся на постоянном носителе, поэтому скорость чтения низкая, поэтому мне нужно просто прочитать их один раз линейно.

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

Какой подход будет лучше?

Answer 1

Хеш-таблица (если все сделано правильно, и вы сказали, что у вас много ОЗУ) O (1) для подсчета определенного слова, в то время как три будет O (n), где n - длина слова ,

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

Answer 2

Я думаю, что три с количеством в качестве листьев может быть быстрее.

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

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

Например, если вы прочитали символы «torto», три будет знать, что единственное возможное слово, начинающееся таким образом, это черепаха.

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

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

Answer 3

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

Answer 4

Я бы использовал объект Dictionary, где ключ - это слово, преобразованное в нижний регистр, а значение - это число. Если в словаре нет слова, добавьте его со значением 1. Если в нем есть слово, увеличьте значение.

Answer 5

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

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

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

Answer 6

Я думаю, что для вашего случая использования Trie является излишним. Хэш word => # вхождений - это именно то, что я бы использовал. Даже используя медленный интерпретируемый язык, такой как Perl, вы можете за один раз взломать файл объемом 1 ГБ. (Я делал это раньше.)

Answer 7

В значительной степени это зависит от того, что вы хотите сделать с данными после их захвата. См. Зачем использовать хеш-таблицу над Trie (деревом префиксов)?

Answer 8

Используйте Python!

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

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

Answer 9

простой скрипт на python:

import collections
f = file('words.txt')
counts = collections.defaultdict(int)
for line in f:
    counts[line.strip()] +=1

print "\n".join("%s: %d" % (word, count) for (word, count) in counts.iteritems())