在Python中维护一个大列表

Question

我需要维护一个大型的Python可拾取对象列表。该列表太大，无法全部存储在RAM中，因此需要一些数据库/分页机制。我需要该机制支持快速访问列表中的接近（附近）区域。

该列表应实现所有Python列表功能，但大多数情况下我将按顺序工作：扫描列表中的某个范围，并在扫描过程中决定是否要在扫描点插入/弹出某些节点。

该列表可以非常大（2-3 GB），不应一次全部包含在RAM中。节点很小（100-200字节），但可能包含各种类型的数据。

这个问题的一个好解决方案是使用BTree，在其中只加载最后访问的桶到RAM中。

使用SQL表不好，因为我需要实现复杂的索引键机制。我的数据不是表格，而是一个简单的Python列表，具有在特定索引中添加元素和从特定位置弹出元素的功能。

我尝试了ZODB和zc.blist，它们实现了一种基于BTree的列表，可以存储在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,)

打印结束:

扩展到5000000个节点花费了3.49秒
访问10000个节点花费了0.02秒
扩展到5050000个节点花费了3.98秒
访问10000个节点花费了0.01秒
扩展到5100000个节点花费了2.54秒
访问10000个节点花费了0.01秒
扩展到5150000个节点花费了2.19秒
访问10000个节点花费了0.11秒
扩展到5200000个节点花费了2.49秒
访问10000个节点花费了0.01秒
扩展到5250000个节点花费了3.13秒
访问10000个节点花费了0.05秒
被杀死（不是我干的）

- Oren

---

400MB有多大？你的电脑有多少RAM？ - user97370

假设它可以达到2GB。我不希望它浪费所有的内存资源。 - Oren

我第一次尝试将4,000,000个100字节对象放入字典中，结果导致Python进程消耗了900MB的内存。所花费的时间为几十秒钟，而对字典的访问时间基本上是即时的。 - Joe Koberg

我需要在我的程序中有大约10个这样的列表。 - Oren

Answer 1

使用zc.blist可以带来良好的结果，创建数据库时设置“cache_size”选项可控制保留在RAM中的数据大小。如果不经常执行“transaction.commit”，使用的RAM大小可能会增长。通过定义大的cache_size并经常执行transaction.commit，blist的最后访问的bucket将保留在RAM中，使您快速访问它们，并且使用的RAM数量不会增长太多。

尽管打包很昂贵，但如果您有大容量硬盘，则无需经常进行打包。

以下是一些代码供您尝试。在后台运行“top”并更改cache_size以查看它如何影响使用的RAM量。

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'])

- Oren

Answer 2

我认为ZODB是使用的工具。它可以存储大量任意项，并处理内存问题。

这里有一个可行的例子，在这种情况下，我包括了相互引用并按编号存储在BTree中的对象。

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 BTrees API documentation 中所述。

您可以通过将每个列表放在不同的键下来存储您的 10 个列表，这些键位于 ZODB 返回的 root 对象中。 root 对象充当 ZODB 对象存储的“网关”。

由于 ZODB，您还可以使用对象间引用以及 Btree 索引。例如：

tree = getTree()

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

- Joe Koberg

---

我承认这是一个非常低级的描述。我会修正问题，使其更加清晰明了。 - Oren

但是，当您在315和316之间插入一个节点时，索引将是多少？ 315.5？（也许可以，但如果有足够的项，您将遇到FP精度限制）。拥有一个仅引用彼此并遍历和插入/删除节点的双向链表很容易 - 但是，某些列表操作会变得昂贵（例如len（）除非您保持更新计数属性）...或通过索引进行随机访问。 - Joe Koberg

但是，ZODB保留了一个对象缓存，经常使用的内部节点应该留在缓存中。我不知道缓存逐出策略，所以不能确定回答。 - Joe Koberg

你必须提交才能告知系统何时开始进行写入操作。每当你修改某个属性时，都会产生一个IO。 - Joe Koberg

哦，关于ZODB FileStorage的另一件事是它是追加式存储...即使删除操作也会导致其增长，直到你"压缩"文件。但你可以免费获得原子性和历史记录功能。 - Joe Koberg

Answer 3

使用东京柜如何？非常快速和简单，就像列表一样，但是专为您想要的构建而设计。 http://1978th.net/tokyocabinet/

- John

---

可能存在以下问题：https://dev59.com/YXRB5IYBdhLWcg3wgXdV - Jon-Eric

我认为他会遇到与SQL提到的相同的“索引键”问题。 - Joe Koberg