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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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()) 

Answer 4

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

Использование Python!

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

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

Answer 9

В значительной степени это зависит от того, что вы хотите делать с данными, как только вы его захватили. См. Why Use a Hash Table over a Trie (Prefix Tree)?