使用flas减少python对象trie的内存使用

Question

我正在寻找一些关于如何减少python内存使用的技巧。我使用这段代码作为保存数据的主要结构：

http://stevehanov.ca/blog/index.php?id=114

我需要它来服务于使用烧瓶服务器的邻近词匹配。我需要投入超过两千万条不同的弦（而且还会增加）。现在我想把一千四百万放进银行的时候会记忆犹新。在

我只是添加了一个字典来保存一些快速访问的值（我需要它，但它可以看作是一种外观标识，它与单词没有直接关系）

  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优化，有没有办法让“letter”对象变小以节省一些内存？在

请注意，我的困难来自于这样一个事实：这个字母不仅是[a-z]，而且需要处理所有的“unicode范围”（比如重音字符，但不仅如此）。顺便说一句，它是一个单个字符，所以从内存指纹来看应该很轻。如何使用codepoint而不是string对象（它会更节省内存吗）？在

编辑：在@juanpa arrivillaga回复后添加一些其他信息

所以，首先，我发现在我的计算机上使用slot结构没有什么区别，有没有__slot__我看到了相同的内存使用情况。在

使用__slot__：

^{pr2}$

{cd1>没有^：

>>> 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”的字符串（因此与unicode无关，不像字母）：

顺便说一句，我的目标是拥有with values和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)))

添加： 最后，我应该确定我使用的是python2.7.x家族。在

我想知道是否有像numpy这样的库中的固定len数据类型可以帮助我节省一些内存，同样是新的，我不知道该在哪里查找。顺便说一句，“词”不是真正的“自然语言词”，而是“任意长度的字符序列”，它们也可以很长。在

从您的回复中，我同意避免在每个节点中存储单词是有效的，但是您需要查看链接的文章/代码片段。主要目标不是重建这个单词，而是能够使用这个单词进行高效/非常快速的近似字符串匹配，然后获得与每个最接近的匹配项相关的“值”，我不确定我是否理解向下到树的路径的目标是什么。（没有到达完整的树？），当匹配时，我们只需要匹配原始单词（但我的理解可能在这一点上是错误的）。在

所以我需要在某个地方有一个巨大的dict，我想封装在类中以方便使用。但从内存“重量”的角度来看，这可能是太贵了吗？在

我还注意到，我得到的内存使用量已经低于您的示例（我现在不知道为什么），但是这里有一个包含在结构中的“letter”的示例值。在

>>> s = u"\u266f"
>>> ord(s)
9839
>>> sys.getsizeof(s)
28
>>> sys.getsizeof(ord(s))
12
>>> print s
♯
>>> repr(s)
"u'\\u266f'"

Answer 1

低挂水果：use ^{} in your node class，否则，每个TrieNode对象都携带一个dict。在

class TrieNode:
    __slots__ = "word", "children"
    def __init__(self):
        self.word = None
        self.children = {}

现在，每个trinode对象将不携带属性dict。比较大小：

^{pr2}$

对比：

>>> 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对象被缓存，很可能大多数字符都在该范围内，但是即使它们不是，在Python中仍然强大的int甚至比单个字符串都小：

>>> 'ñ'
'ñ'
>>> 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，它的增长速度非常快，但是这个信息是多余的。你说：

I just add a dictionary to hold some value with quick access (I need it)

您可以从路径重建单词。它应该是比较快的，我会认真考虑不要有这个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