在python中维护大型列表

Question

我需要维护大量的python pickleable对象。该列表太大而无法全部存储在RAM中，因此需要一些数据库\分页机制。我需要该机制支持快速访问列表中的近距离（附近）区域。

该列表应该实现所有python-list功能，但大多数时候我将按顺序工作：扫描列表中的某个范围，并在扫描时决定是否要在扫描点中插入\弹出一些节点。

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

对此的很好的解决方案，可以使用B树，其中只有最后访问桶在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,) 

打印止带：

 
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

使用ZC。blist可以带来好的结果，并且在创建DB时设置“cache_size”选项控制将保留在RAM中的数据的大小。如果您不经常执行“transaction.commit”，则使用的RAM的大小会变得更大。通过定义一个大的cache_size并且经常执行transaction.commit，最后访问的blist存储区会留在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']) 

Answer 2

我觉得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变量基本上就像一本字典，并且可以通过按键来访问。如the ZODB BTrees API documentation所述，您也可以使用tree.keys(min, max)来获取范围内的密钥。

您可以通过将每一个下由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 3

如何使用东京内阁？非常快速和简单，就像列表，但为您想要的内容而构建。 http://1978th.net/tokyocabinet/