Python链表中的错误内存分配

Question

我有一个关于Python简单链表及其内存消耗的问题。

以下是代码：

import sys

class Record:
    def __init__(self,elem):
        self.elem=elem
        self.next=None

    def size(self):
        print 'elem.size = ', sys.getsizeof(self.elem)
        print 'next.size = ', sys.getsizeof(self.next)


class LinkedList:
    def __init__(self):
        self.first=None
        self.last=None

    def addAsLast(self,elem):
        rec=Record(elem)
        if self.first==None:
            self.first=self.last=rec
        else:
            self.last.next=rec
            self.last=rec

if __name__=="__main__":
    l=LinkedList()
    r = Record(1)
    r.size()

    maxx = 10000000
    r = range(1, maxx)
    print 'size of r: ', sys.getsizeof(r)
    print 'size of r[n-1]: ', sys.getsizeof(r[maxx-2])

    for i in r:
        if(i% (maxx/10) == 0): print '.'
        l.addAsLast(i)
    print "The End"

我的问题是：运行这个脚本会消耗1.7 GB的内存。

输出如下：

elem.size =  12 
next.size =  8 
size of r:  40000028
size of r[n-1]:  12

那么，让我们进行一些快速的数学计算：

1000万个记录。

每个记录有12个字节（元素）+ 8个字节（指向下一个记录的指针）= 20字节

20字节 * 1000万 = 2亿字节 = 190.7 MB

即使我必须考虑由range()函数分配的列表（约30 MB），我如何管理这样巨大的内存消耗？我在这段代码中犯了什么愚蠢的错误吗？我希望答案会让我感到惭愧和抱歉，但是到目前为止，我只是在想究竟发生了什么！

非常感谢您的帮助。

- Cob013

---

虽然这并不能填补巨大的差距，但你应该修改Record类的size方法，并将其打印为sys.sizeof(self)而不是两个组件元素。它是32字节，而不是20字节，因为类结构中有开销。 - Aaron D

分段可能会添加一些东西，我猜。我会尝试像recpool=[None]*10000000; ... rec=recpool[j]; j+=1 这样的方法，然后看看会发生什么。 - Elazar

另外，尝试使用 gc.disable()。 - Elazar

如果你使用__slots__，你将会严重减少数据结构的大小，因为__dict__将被消除。此外，链表是一种非常浪费内存的结构，除非你的有效载荷很大。除非你需要从一个非常长的列表中快速删除，否则请避免使用它，即使这样也要考虑跳表等其他结构。 - 9000

@Elazar：我已经使用了gc.disable()，但结果总是大约+2.0 GB。我会尽快尝试使用__slots__，以前从未听说过，所以我会去阅读一些资料。欢迎提供任何示例。不幸的是，这次我相当被迫使用这种LinkedList，我只需要尽可能地节省内存。 - Cob013

考虑转向 C :) - Elazar

Answer 1

如下所示的修改后的打印：

class Record:
    def __init__(self,elem):
        self.elem=elem
        self.next=None

    def size(self):
        print 'Record size = ', sys.getsizeof(self)
        print 'elem.size = ', sys.getsizeof(self.elem)
        print 'next.size = ', sys.getsizeof(self.next)

输出：

Record size =  72
elem.size =  24
next.size =  16

所以，我的每个链表节点是72字节x 10M应该是720MB，.72GB

我运行了程序，并使用top命令查看内存开销为3.6G。 我的元素大小是您的两倍，我注意到总内存消耗是您的两倍（3.6G，而不是1.7G）。

这一定是由于额外的Python内存开销，例如垃圾回收。

- vfxdrummer

Answer 2

>>> class Record:
...     def __init__(self, elem):
...             self.elem = elem
...             self.next = None   
... 
>>> r = Record(1)
>>> sys.getsizeof(r)
72

还有什么我没注意到吗？

此外，在我的系统上：

>>> sys.getsizeof(1)
24
>>> sys.getsizeof(None)
16

- 2rs2ts

---

现在想想：56或72字节，仍然不应该加起来达到1.7GB。以56字节为例，这个计算会让你达到约600MB。我会继续思考的 :) - 2rs2ts

56+28=84。四舍五入为88。88*10000000~=0.88GB。加上碎片化和GC开销，你就得到了一个接近的结果。 - Elazar

请记住，垃圾回收可能会消耗原始资源的大约150％，具体取决于其工作方式。 - Elazar

幼稚，但是...你从哪里得到那个28的？ - 2rs2ts

在我的机器上，sizeof(1) 的结果是多少？ - Elazar

我通常不太担心Python的内存使用，但我相信每个类的实例都是作为哈希表实现的，而哈希表有一些开销。您可以使用“slots”机制来解决这个问题。 - dstromberg