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

Question

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

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

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

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

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

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

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

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

Answer 1

Некоторые измерения. Я взял 10 МБ бесплатного текста электронной книги и вычисленные частоты триграмм, получив файл размером 24 МБ. Хранение его в разных простых структурах данных Python заняло столько места в килобайтах, измеряемое как RSS от числа запущенных ps, где d - это dict, ключи и freqs - это списки, а a, b, c, freq - поля записи триграммы:

295760     S. Lott's answer
237984     S. Lott's with keys interned before passing in
203172 [*] d[(a,b,c)] = int(freq)
203156     d[a][b][c] = int(freq)
189132     keys.append((a,b,c)); freqs.append(int(freq))
146132     d[intern(a),intern(b)][intern(c)] = int(freq)
145408     d[intern(a)][intern(b)][intern(c)] = int(freq)
 83888 [*] d[a+' '+b+' '+c] = int(freq)
 82776 [*] d[(intern(a),intern(b),intern(c))] = int(freq)
 68756     keys.append((intern(a),intern(b),intern(c))); freqs.append(int(freq))
 60320     keys.append(a+' '+b+' '+c); freqs.append(int(freq))
 50556     pair array
 48320     squeezed pair array
 33024     squeezed single array

Записи, помеченные [*], не имеют эффективного способа поиска пары (a, b); они перечислены только потому, что другие предложили их (или их варианты). (Я был в некотором роде раздражен, когда делал это, потому что ответы с наибольшим количеством голосов не помогли, как показано в таблице.)

«Массив пар» - схема, приведенная ниже в моем исходном ответе («Я бы начал с массива с ключами». будучи первыми двумя словами ... "), где таблица значений для каждой пары представлены в виде одной строки. «Сжатый массив пар» - то же самое, опуская значения частоты, равные 1 (наиболее распространенные дело). «Squeezed single array» похож на массив сжатых пар, но объединяет ключ и значение в одну строку (с разделителем). Код сжатого одиночного массива:

import collections

def build(file):
    pairs = collections.defaultdict(list)
    for line in file:  # N.B. file assumed to be already sorted
        a, b, c, freq = line.split()
        key = ' '.join((a, b))
        pairs[key].append(c + ':' + freq if freq != '1' else c)
    out = open('squeezedsinglearrayfile', 'w')
    for key in sorted(pairs.keys()):
        out.write('%s|%s\n' % (key, ' '.join(pairs[key])))

def load():
    return open('squeezedsinglearrayfile').readlines()

if __name__ == '__main__':
    build(open('freqs'))

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

Оригинальный ответ: Простой отсортированный массив строк, каждая строка представляет собой разделенную пробелами конкатенацию слов, поиск которых выполняется с помощью модуля bisect, стоит попробовать для начала. Это экономит место на указателях и т. Д. Это по-прежнему тратит пространство из-за повторения слов; есть стандартный прием для удаления общих префиксов, с другим уровнем индекса для их возврата, но это довольно сложно и медленнее. (Идея состоит в том, чтобы хранить последовательные фрагменты массива в сжатой форме, которую необходимо сканировать последовательно, вместе с индексом произвольного доступа к каждому фрагменту. Блоки достаточно большие для сжатия, но достаточно малы для разумного времени доступа. Особое сжатие здесь применима следующая схема: если последовательные записи - «привет, георгий» и «привет, мир», вместо этого сделайте вторую запись «6world» (6 - это общая длина префикса.) Или, возможно, вы можете избежать использования zlib ? В любом случае, вы можете узнать больше в этом ключе, просматривая словарные структуры, используемые в полнотекстовом поиске.) Поэтому, в частности, я бы начал с массива с ключами, являющимися первыми двумя словами, с параллелью массив, в записях которого перечислены возможные третьи слова и их частоты. Это может все еще быть отстойным - я думаю, что вам может не повезти, если в комплект входят батарейки с эффективным энергопотреблением.

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

Я должен был упомянуть, как и кто-то другой, что отсортированный массив можно использовать только для списка слов, а не для биграмм или триграмм; затем для вашей «реальной» структуры данных, какой бы она ни была, вы используете целочисленные ключи вместо строк - индексы в списке слов. (Но это удерживает вас от использования общих префиксов, за исключением самого списка слов. Может быть, мне не стоит предлагать это в конце концов.)

Answer 2

Используйте кортежи.
Кортежи могут быть ключами к словарям, поэтому вам не нужно вкладывать словари.

d = {}
d[ word1, word2, word3 ] = 1

Также в качестве плюса вы можете использовать defaultdict

• так, чтобы элементы, у которых нет записей, всегда возвращали 0
• и чтобы вы могли сказать d[w1,w2,w3] += 1, не проверяя, существует ли ключ или нет

пример:

from collections import defaultdict
d = defaultdict(int)
d["first","word","tuple"] += 1

Если вам нужно найти все слова «word3», которые связаны с (word1, word2), найдите их в dictionary.keys (), используя понимание списка

если у вас есть кортеж, t, вы можете получить первые два элемента, используя ломтики:

>>> a = (1,2,3)
>>> a[:2]
(1, 2)

небольшой пример поиска кортежей со списком:

>>> b = [(1,2,3),(1,2,5),(3,4,6)]
>>> search = (1,2)
>>> [a[2] for a in b if a[:2] == search]
[3, 5]

Вы видите здесь, у нас есть список всех элементов, которые появляются как третий элемент в кортежах, начинающихся с (1,2)

Answer 3

В этом случае ZODB ¹Bree могут быть полезны, так как они намного меньше требуют памяти. Используйте BTrees.OOBtree (ключи объекта к значениям объекта) или BTrees.OIBTree (ключи объекта к значениям целых чисел) и используйте кортежи из 3 слов в качестве ключа.

Что-то вроде:

from BTrees.OOBTree import OOBTree as BTree

Интерфейс более или менее похож на диктовку, с дополнительным бонусом (для вас), что .keys, .items, .iterkeys и .iteritems имеют два min, max необязательных аргумента:

>>> t=BTree()
>>> t['a', 'b', 'c']= 10
>>> t['a', 'b', 'z']= 11
>>> t['a', 'a', 'z']= 12
>>> t['a', 'd', 'z']= 13
>>> print list(t.keys(('a', 'b'), ('a', 'c')))
[('a', 'b', 'c'), ('a', 'b', 'z')]

¹ Обратите внимание, что если вы работаете в Windows и работаете с Python> 2.4, я знаю, что есть пакеты для более поздних версий Python, но я не могу вспомнить, где.

PS Они существуют в CheeseShop ☺

Answer 4

Пара попыток:

Я полагаю, вы делаете что-то похожее на это:

from __future__ import with_statement

import time
from collections import deque, defaultdict

# Just used to generate some triples of words
def triplegen(words="/usr/share/dict/words"):
    d=deque()
    with open(words) as f:
        for i in range(3):
            d.append(f.readline().strip())

        while d[-1] != '':
            yield tuple(d)
            d.popleft()
            d.append(f.readline().strip())

if __name__ == '__main__':
    class D(dict):
        def __missing__(self, key):
            self[key] = D()
            return self[key]
    h=D()
    for a, b, c in triplegen():
        h[a][b][c] = 1
    time.sleep(60)

Это дает мне ~ 88 МБ.

Изменение хранилища на

h[a, b, c] = 1

занимает ~ 25 МБ

интернирование a, b и c занимает около 31 МБ. Мой случай немного особенный, потому что мои слова никогда не повторяются на входе. Вы можете сами попробовать некоторые варианты и посмотреть, поможет ли вам один из них.

Answer 5

Реализуете ли вы марковский текст?

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

Вот реализация с K-кортежем в качестве параметра:

import random

# can change these functions to use a dict-based histogram
# instead of a list with repeats
def default_histogram():          return []
def add_to_histogram(item, hist): hist.append(item)
def choose_from_histogram(hist):  return random.choice(hist)

K=2 # look 2 words back
words = ...
d = {}

# build histograms
for i in xrange(len(words)-K-1):
  key = words[i:i+K]
  word = words[i+K]

  d.setdefault(key, default_histogram())
  add_to_histogram(word, d[key])

# generate text
start = random.randrange(len(words)-K-1)
key = words[start:start+K]
for i in NUM_WORDS_TO_GENERATE:
  word = choose_from_histogram(d[key])
  print word,
  key = key[1:] + (word,)

Answer 6

У Сципи редкие матрицы, поэтому, если вы можете сделать первые два слова кортежем, вы можете сделать что-то вроде этого:

import numpy as N
from scipy import sparse

word_index = {}
count = sparse.lil_matrix((word_count*word_count, word_count), dtype=N.int)

for word1, word2, word3 in triple_list:
    w1 = word_index.setdefault(word1, len(word_index))
    w2 = word_index.setdefault(word2, len(word_index))
    w3 = word_index.setdefault(word3, len(word_index))
    w1_w2 = w1 * word_count + w2
    count[w1_w2,w3] += 1

Answer 7

Вот древовидная структура, которая использует библиотеку bisect, чтобы поддерживать отсортированный список слов. Каждый поиск в O (log2 (n)).

import bisect

class WordList( object ):
    """Leaf-level is list of words and counts."""
    def __init__( self ):
        self.words= [ ('\xff-None-',0) ]
    def count( self, wordTuple ):
        assert len(wordTuple)==1
        word= wordTuple[0]
        loc= bisect.bisect_left( self.words, word )
        if self.words[loc][0] != word:
            self.words.insert( loc, (word,0) )        
        self.words[loc]= ( word, self.words[loc][1]+1 )
    def getWords( self ):
        return self.words[:-1]

class WordTree( object ):
    """Above non-leaf nodes are words and either trees or lists."""
    def __init__( self ):
        self.words= [ ('\xff-None-',None)  ]
    def count( self, wordTuple ):
        head, tail = wordTuple[0], wordTuple[1:]
        loc= bisect.bisect_left( self.words, head )
        if self.words[loc][0] != head:
            if len(tail) == 1:
                newList= WordList()
            else:
                newList= WordTree()
            self.words.insert( loc, (head,newList) )
        self.words[loc][1].count( tail )
    def getWords( self ):
        return self.words[:-1]

t = WordTree()
for a in ( ('the','quick','brown'), ('the','quick','fox') ):
    t.count(a)

for w1,wt1 in t.getWords():
    print w1
    for w2,wt2 in wt1.getWords():
        print " ", w2
        for w3 in wt2.getWords():
            print "  ", w3

Для простоты здесь используется фиктивное значение в каждом дереве и списке. Это сохраняет бесконечные операторы if, чтобы определить, был ли список на самом деле пустым, прежде чем мы сделаем сравнение. Он только один раз пуст, поэтому операторы if теряются для всех n -1 других слов.

Answer 8

Хорошо, значит, вы пытаетесь сохранить разреженное трехмерное пространство. Типы шаблонов доступа, которые вы хотите в этом пространстве, имеют решающее значение для выбора алгоритма и структуры данных. Учитывая ваш источник данных, вы хотите передать это в сетку? Если вам не нужен доступ O (1):

Для повышения эффективности использования памяти вы хотите разделить это пространство на подпространства с одинаковым количеством записей. (как BTree). Итак, структура данных с:

• firstWordRange
• secondWordRange
• thirdWordRange
• numberOfEntries
• отсортированный блок записей.
• следующий и предыдущий блоки во всех трех измерениях

Answer 9

Вы можете попробовать использовать тот же словарь, только на один уровень глубины.

topDictionary[word1+delimiter+word2+delimiter+word3]

разделитель может быть простым "". (или используйте (слово1, слово2, слово3))

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

Answer 10

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

import numpy
w = {'word1':1, 'word2':2, 'word3':3, 'word4':4}
a = numpy.zeros( (4,4,4) )

Затем для индексации в вашем массиве вы должны сделать что-то вроде:

a[w[word1], w[word2], w[word3]] += 1

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