Разработайте алгоритм, найдите наиболее часто используемое слово в книге

Question

Вопрос для интервью:

Найдите наиболее часто используемое слово в книге.

Моя идея:

Используйте хеш-таблицу, пройдите и отметьте хеш-таблицу.

Если размер книги известен, и если найдено, что какое-либо слово используется> 50%, пропустите все новые слова в следующем обходе и считайте только старые слова. Что если размер книги неизвестен?

Это O (n) и O (n) время и пространство.

Есть идеи получше?

Спасибо

Answer 1

Это на самом деле классический пример уменьшения карты .

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

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

Answer 2

Чтобы определить сложность, я думаю, вам нужно учитывать две переменные: n = общее количество слов, m = количество уникальных слов. Я полагаю, что сложность наилучшего случая будет близка к O (n log (m)) по скорости и O (m) по памяти, при условии, что каждый раз вы выполняете итерацию по каждому из n слов, а также строите и ищете на основе хеш-таблицы или другая такая структура, которая в конечном итоге содержит m элементов.

Answer 3

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

Четный Python; Counter.nlargest s , который используется для этих целей, реализуется через структуру данных кучи.

Структура данных двоичной кучи имеет следующую сложность

CreateHeap - O(1)
FindMin - O(1)
deleteMin - O(logn)
Insert - O(logn)

Я запустил сравнение для Hash (используя словарь по умолчанию в Python) и Heap (используя Collections.Counter.nlargest в Python), и Hash справляется немного лучше, чем Heap.

>>> stmt1="""
import collections, random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
somehash=collections.defaultdict(int)
for d in somedata:
    somehash[d]+=1
maxkey=0
for k,v in somehash.items():
    if somehash[maxkey] > v:
        maxkey=k
"""
>>> stmt2="""
import collections,random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
collections.Counter(somedata).most_common(1)
"""
>>> t1=timeit.Timer(stmt=stmt1)
>>> t2=timeit.Timer(stmt=stmt2)
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10)
38168.96 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10)
33600.80 usec/pass

Answer 4

Ваше решение правильное, быстрое и, вероятно, лучшее / простое с практической точки зрения.

Решения других авторов имеют более сложную временную сложность, чем ваше решение. Для хэша, который вы используете, сложность времени действительно равна O (n). Каждая вставка - это O (1), и есть n слов, поэтому фаза вставки стоит O (n). Итерация и поиск максимума - это O (n). Пробел также O (n), как вы упомянули.

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

Куча будет стоить дороже по времени, потому что вам нужно поддерживать кучу во время каждой вставки. Куча вставки равна O (log (n)) и, следовательно, общая стоимость вставки будет O (nlog (n)).

Answer 5

Существует обобщение вашей оптимизации - если размер книги известен, и любое слово, которое вы видели, имеет счет> оставшееся количество слов + следующий наибольший счет, ваше текущее слово с наибольшим счетом является ответом.

Answer 6

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

Для точного ответа я бы использовал идеальную хеш-функцию из k наиболее распространенных слов. Идеальная хеш-функция требует O (k) памяти и гарантирует быстрый поиск O (1) в худшем случае.

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