Эффективные по памяти альтернативы словарям Python - PullRequest
Новая
       98

Эффективные по памяти альтернативы словарям Python

41 голосов
/ 29 ноября 2008

В одном из моих текущих побочных проектов я сканирую текст, просматривая частоту триплетов слов. Сначала я использовал словарь по умолчанию на три уровня глубиной. Другими словами, topDict[word1][word2][word3] возвращает количество раз, когда эти слова появляются в тексте, topDict[word1][word2] возвращает словарь со всеми словами, которые появились после слов 1 и 2 и т. Д.

Это работает правильно, но это очень интенсивно использует память. В моих первоначальных тестах он использовал примерно в 20 раз больше памяти, чем просто для хранения триплетов в текстовом файле, что выглядит как чрезмерно большой объем памяти.

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

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

Итак, у кого-нибудь есть предложения для меня?

Отредактировано, чтобы добавить:

Спасибо за ответы, пока. В некоторых ответах до сих пор предлагалось использовать кортежи, которые не очень-то мне помогли, когда я сжал первые два слова в кортеж. Я не решаюсь использовать все три в качестве ключа, так как хочу, чтобы было легко найти все третьи слова с учетом первых двух. (т.е. я хочу что-то вроде результата topDict[word1, word2].keys()).

Текущий набор данных, с которым я играю, - это самая последняя версия Wikipedia For Schools . Например, результаты синтаксического анализа первой тысячи страниц составляют примерно 11 МБ для текстового файла, где каждая строка представляет собой три слова, а количество всех табуляций разделено. Хранение текста в формате словаря, который я сейчас использую, занимает около 185 МБ. Я знаю, что будут дополнительные издержки для указателей и еще много чего, но разница кажется чрезмерной.

Ответы [ 12 ]

0 голосов
/ 29 ноября 2008

Если память просто недостаточно велика, pybsddb может помочь сохранить постоянную карту диска.

0 голосов
/ 29 ноября 2008

Вы можете поместить все слова в словарь. ключом будет слово, а значением является число (индекс).

Тогда вы используете это так: 

Word1=indexDict[word1]
Word2=indexDict[word2]
Word3=indexDict[word3]

topDictionary[Word1][Word2][Word3]

Вставить в indexDict с: 

if word not in indexDict:
    indexDict[word]=len(indexDict)
Страница:
...