Уменьшение использования памяти с помощью объектов Python, которые используются с помощью колбы
Я ищу несколько советов о том, как уменьшить использование памяти для Python. Я использую этот фрагмент кода в качестве основной структуры для хранения моих данных:
http://stevehanov.ca/blog/index.php?id=114
Мне нужно, чтобы он служил для сопоставления слов близости с помощью фляги сервера. Мне нужно поставить гораздо больше 20 миллионов разных строк (и это будет увеличиваться). Теперь я получаю MemoryError при попытке положить около 14 миллионов в Trie.
Я просто добавляю словарь для хранения некоторого значения с быстрым доступом (он мне нужен, но его можно рассматривать как некий идентификатор внешнего вида, он не имеет прямого отношения к слову)
class TrieNode:
values = {}
def __init__(self):
self.word = None
self.children = {}
global NodeCount
NodeCount += 1
def insert( self, word, value):
node = self
for letter in word:
if letter not in node.children:
node.children[letter] = TrieNode()
node = node.children[letter]
TrieNode.values[word] = value
node.word = word
Я не знаком с оптимизацией Python, есть ли способ сделать объект "письмо" менее большим, чтобы сэкономить память?
Пожалуйста, обратите внимание, что мои трудности связаны с тем, что это письмо не только [az], но и должно обрабатывать весь "диапазон Юникода" (например, акцентированные символы, но не только). Кстати, это один символ, поэтому он должен быть достаточно легким по отпечатку памяти. Как я могу использовать кодовую точку вместо строкового объекта (это будет более эффективно использовать память)?
РЕДАКТИРОВАТЬ: добавить некоторую другую информацию после ответа от @juanpa-Arrivillaga
Итак, во-первых, я не вижу разницы, используя конструкцию слота, на моем компьютере, с или без __slot__ Я вижу то же самое использование памяти.
с __slot__:
>>> class TrieNode:
NodeCount = 0
__slots__ = "word", "children"
def __init__(self):
self.word = None
self.children = {}
#global NodeCount # my goal is to encapsulated the NodeCount in the class itself
TrieNode.NodeCount += 1
>>> tn = TrieNode()
>>> sys.getsizeof(tn) + sys.getsizeof(tn.__dict__)
176
без __slot__:
>>> class TrieNode:
NodeCount = 0
def __init__(self):
self.word = None
self.children = {}
#global NodeCount
TrieNode.NodeCount += 1
>>> tn = TrieNode()
>>> sys.getsizeof(tn) + sys.getsizeof(tn.__dict__)
176
поэтому я не понимаю, почему. Где я не прав?
вот еще кое-что, что я тоже попробовал, используя ключевое слово intern, потому что это значение является строкой, обрабатывающей "id" (и поэтому не относится к юникоду, а не к букве):
Кстати, моя цель состояла в том, чтобы иметь со значениями и NodeCount, эквивалентную концепцию для класса / статических переменных, чтобы каждая из них использовалась всеми экземплярами небольших созданных объектов, я думал, что это сохранит память и позволит избежать дублирования, но я могу неправильно из моего понимания "статоподобной" концепции в Python)
class TrieNode:
values = {} # shared amon all instances so only one structure?
NodeCount = 0
__slots__ = "word", "children"
def __init__(self):
self.word = None
self.children = {}
#global NodeCount
TrieNode.NodeCount += 1
def insert( self, word, value = None):
# value is a string id like "XYZ999999999"
node = self
for letter in word:
codepoint = ord(letter)
if codepoint not in node.children:
node.children[codepoint] = TrieNode()
node = node.children[codepoint]
node.word = word
if value is not None:
lost = TrieNode.values.setdefault(word, [])
TrieNode.values[word].append(intern(str(value)))
ДОБАВЛЕНО: Наконец, я должен был уточнить, что я использую семейство Python 2.7.x.
Мне было интересно, есть ли какие-либо фиксированные типы данных len из библиотеки, такие как numpy, может помочь мне сэкономить память, опять же, как новую, я не знаю, где искать. Кстати, "слово" - это не реальное "слово на естественном языке", а "последовательность символов произвольной длины", и они также могут быть очень длинными.
Исходя из вашего ответа, я согласен с тем, что избегать сохранения слова в каждом узле было бы эффективно, но вам нужно взглянуть на связанную статью / фрагмент кода. Основная цель не в том, чтобы восстановить это слово, а в том, чтобы сделать эффективное / очень быстрое приблизительное сопоставление строк, используя это слово, а затем получить "значение", связанное с каждым из самых близких совпадений, я не уверен, что понял цель пути вниз к дереву. (не доходя до полного дерева?), и при сопоставлении нам просто нужно подобрать оригинальное слово (но мое понимание может быть неверным в этой точке).
поэтому мне нужно, чтобы где-то был этот огромный дикт, и я хотел, чтобы в классе было удобно. Но может быть, это слишком дорого с точки зрения "веса" памяти?
Также я заметил, что я получаю уже меньше памяти, чем ваш образец (пока не знаю, почему), но вот пример значения "буквы", содержащегося в структуре.
>>> s = u"\u266f"
>>> ord(s)
9839
>>> sys.getsizeof(s)
28
>>> sys.getsizeof(ord(s))
12
>>> print s
♯
>>> repr(s)
"u'\\u266f'"
1 ответ
Низко висящие фрукты: используйте __slots__ в вашем классе узла, в противном случае, каждый TrieNode объект носит вокруг dict,
class TrieNode:
__slots__ = "word", "children"
def __init__(self):
self.word = None
self.children = {}
Теперь каждый объект TrieNode не будет содержать атрибут dict, Сравните размеры:
>>> class TrieNode:
... def __init__(self):
... self.word = None
... self.children = {}
...
>>> tn = TrieNode()
>>> sys.getsizeof(tn) + sys.getsizeof(tn.__dict__)
168
Vs:
>>> class TrieNode:
... __slots__ = "word", "children"
... def __init__(self):
... self.is_word = False
... self.children = {}
...
>>> sys.getsizeof(tn)
56
>>> tn.__dict__
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'TrieNode' object has no attribute '__dict__'
Еще одна оптимизация, использовать int объекты. Маленький int объекты кэшируются, вероятно, большинство ваших персонажей все равно будут находиться в этом диапазоне, но даже если это не так, int хотя в Python все еще громоздкий, он меньше, чем даже одна строка символов:
>>> 'ñ'
'ñ'
>>> ord('ñ')
241
>>> sys.getsizeof('ñ')
74
>>> sys.getsizeof(ord('ñ'))
28
Так что вы можете сделать что-то вроде:
def insert( self, word, value):
node = self
for letter in word:
code_point = ord(letter)
if code_point not in node.children:
node.children[code_point] = TrieNode()
node = node.children[code_point]
node.is_word = True #Don't save the word, simply a reference to a singleton
Кроме того, вы держите вокруг переменной класса valuesdict это чрезвычайно растет, но эта информация избыточна. Ты говоришь:
Я просто добавляю словарь для хранения некоторого значения с быстрым доступом (он мне нужен)
Вы можете восстановить слова с пути. Это должно быть относительно быстро, я бы серьезно подумал против этого dict, Посмотрите, сколько памяти требуется для хранения миллиона односимвольных строк:
>>> d = {str(i):i for i in range(1000000)}
>>> (sum(sizeof(k)+sizeof(v) for k,v in d.items()) + sizeof(d)) * 1e-9
0.12483203000000001
Вы могли бы сделать что-то вроде:
class TrieNode:
__slots__ = "value", "children"
def __init__(self):
self.value = None
self.children = {}
def insert( self, word, value):
node = self
for letter in word:
code_point = ord(letter)
if code_point not in node.children:
node.children[code_point] = TrieNode()
node = node.children[code_point]
node.value = value #this serves as a signal that it is a word
def get(word, default=None):
val = self._get_value(word)
if val is None:
return default
else:
return val
def _get_value(self, word):
node = self
for letter in word:
code_point = ord(letter)
try:
node = node.children[code_point]
except KeyError:
return None
return node.value