在Python中维护大型列表

Question

我需要维护一个很大的可以用Python序列化的对象列表。这个列表太大了，不能全部放在内存里，所以需要一些数据库或分页机制。我希望这个机制能够快速访问列表中相邻的部分。

这个列表应该具备所有Python列表的功能，但大多数时候我会顺序操作：扫描列表中的某个范围，同时在扫描时决定是否要在当前点插入或删除一些节点。

这个列表可能会非常大（2-3 GB），不能一次性全部放在内存里。每个节点都很小（100-200字节），但可以包含各种类型的数据。

一个不错的解决方案是使用B树，这样只有最近访问的部分会被加载到内存中。

使用SQL表不太合适，因为我需要实现一个复杂的索引机制。我的数据不是表格，而是一个简单的Python列表，具备在特定索引添加元素和从特定位置删除元素的功能。

我尝试过ZODB和zc.blist，它们实现了一个基于B树的列表，可以存储在ZODB数据库文件中，但我不知道如何配置它，以便上述功能能够在合理的时间内运行。我不需要多线程或事务处理的功能，除了我自己的单线程程序，没有其他人会接触这个数据库文件。

有没有人能告诉我如何配置ZODB或zc.blist，以便上述功能运行得更快，或者给我展示一个不同的大列表实现？

我尝试过的一些简单代码：

import time
import random

NODE_JUMP = 50000
NODE_ACCESS = 10000

print 'STARTING'


random_bytes = open('/dev/urandom', 'rb')

my_list = list()

nodes_no = 0

while True:
    nodes_no += NODE_JUMP
    start = time.time()
    my_list.extend(random_bytes.read(100) for i in xrange(NODE_JUMP))
    print 'extending to %s nodes took %.2f seconds' % (nodes_no, time.time() - start)

    section_start = random.randint(0, nodes_no -NODE_ACCESS -1)
    start = time.time()
    for index in xrange(section_start, section_start + NODE_ACCESS):
        # rotate the string
        my_list[index] = my_list[index][1:] + my_list[index][0]

    print 'access to %s nodes took %.2f seconds' % (NODE_ACCESS, time.time() - start,)

打印结束于：

extending to 5000000 nodes took 3.49 seconds
access to 10000 nodes took 0.02 seconds
extending to 5050000 nodes took 3.98 seconds
access to 10000 nodes took 0.01 seconds
extending to 5100000 nodes took 2.54 seconds
access to 10000 nodes took 0.01 seconds
extending to 5150000 nodes took 2.19 seconds
access to 10000 nodes took 0.11 seconds
extending to 5200000 nodes took 2.49 seconds
access to 10000 nodes took 0.01 seconds
extending to 5250000 nodes took 3.13 seconds
access to 10000 nodes took 0.05 seconds
Killed (not by me)

Answer 1

我觉得ZODB是个不错的工具。它可以存储很多不同的东西，还能处理内存问题。

这里有一个可以运行的例子，这个例子里我放了一些互相引用的对象，并且这些对象是按数字存储在一个B树里的。

import random
from collections import deque

import ZODB
from ZODB.FileStorage import FileStorage
from ZODB.DB import DB
import transaction
import persistent
import BTrees

def random_string(n=100):
    return ''.join([chr(random.randint(0,95)+32) for i in xrange(n)]) 


class Node(persistent.Persistent):
   def __init__(self, value=None):
       if not value:
           self.value =  random_string()

   def setNeighbors(self, refs):
       self.p1 = refs[0]
       self.p2 = refs[1]
       self.p3 = refs[2]
       self.p4 = refs[3]


def getTree():
    storage = FileStorage('c:\\test.zdb')
    db = DB(storage)
    connection = db.open()
    root = connection.root()
    if root.has_key('tree'):
        tree = root['tree']
    else:
        tree = BTrees.OOBTree.OOBTree()
        root['tree'] = tree
        transaction.commit()
    return tree


def fillDB():
    tree = getTree()

    # start with some initial objects.
    nodes = deque([Node(), Node(), Node(), Node()])
    node = Node()

    for n in xrange(20000):
        tree[n] = node           # store the node based on a numeric ID
        node.setNeighbors(nodes) # Make the node refer to more nodes.
        node = nodes.popleft()   # maintain out list of 4 upcoming nodes.
        nodes.append(Node())
        if n % 1000 == 0:
            transaction.commit() # Must commit for data to make it to disk.
            print n
    transaction.commit()
    return tree

到这个时候，tree变量基本上就像一个字典，可以通过键来访问。你也可以使用tree.keys(min, max)来获取一个范围内的键，具体可以参考ZODB B树API文档。

你可以通过在ZODB返回的root对象下，把每个列表放在不同的键下，来存储你的10个列表。root对象就像是通往ZODB对象存储的“入口”。

得益于ZODB，你还可以使用对象之间的引用以及B树索引。例如：

tree = getTree()

node1 = tree[1]
print node1.p1.p1.p1.p1.p1.p1.p1.p1.p1.value

Answer 2

你觉得用东京柜（Tokyo Cabinet）怎么样？它非常快，而且简单，就像列表一样，但它是专门为你想要的功能设计的。

你可以在这里了解更多：http://1978th.net/tokyocabinet/

Answer 3

使用zc.blist可以带来不错的效果。在创建数据库时，设置“cache_size”选项可以控制保留在内存中的数据大小。如果你不经常执行“transaction.commit”，使用的内存可能会变得很大。通过定义一个较大的cache_size并且经常执行transaction.commit，最近访问的数据块会保留在内存中，这样你就能快速访问它们，而且使用的内存不会增长太多。

不过，打包数据是非常耗费资源的，但如果你的硬盘空间很大，其实也不需要太频繁地进行打包。

这里有一些代码可以自己试试。你可以在后台运行“top”命令，然后改变cache_size，看看它是如何影响内存使用量的。

import time
import os
import glob
from ZODB import DB
from ZODB.FileStorage import FileStorage
import transaction
from zc.blist import BList

print('STARTING')

random = open('/dev/urandom', 'rb')


def test_list(my_list, loops = 1000, element_size = 100):
    print('testing list')
    start = time.time()
    for loop in xrange(loops):
        my_list.append(random.read(element_size))
    print('appending %s elements took %.4f seconds' % (loops, time.time() - start))

    start = time.time()
    length = len(my_list)
    print('length calculated in %.4f seconds' % (time.time() - start,))

    start = time.time()
    for loop in xrange(loops):
        my_list.insert(length / 2, random.read(element_size))
    print('inserting %s elements took %.4f seconds' % (loops, time.time() - start))

    start = time.time()
    for loop in xrange(loops):
        my_list[loop] = my_list[loop][1:] + my_list[loop][0]
    print('modifying %s elements took %.4f seconds' % (loops, time.time() - start))

    start = time.time()
    for loop in xrange(loops):
        del my_list[0]
    print('removing %s elements took %.4f seconds' % (loops, time.time() - start))

    start = time.time()
    transaction.commit()
    print('committing all above took %.4f seconds' % (time.time() - start,))

    del my_list[:loops]
    transaction.commit()

    start = time.time()
    pack()
    print('packing after removing %s elements took %.4f seconds' % (loops, time.time() - start))

for filename in glob.glob('database.db*'):    
    try:
        os.unlink(filename)
    except OSError:
        pass

db = DB(FileStorage('database.db'),
        cache_size = 2000)

def pack():
    db.pack()

root = db.open().root()

root['my_list'] = BList()

print('inserting initial data to blist')

for loop in xrange(10):
    root['my_list'].extend(random.read(100) for x in xrange(100000))
    transaction.commit()

transaction.commit()

test_list(root['my_list'])