在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/