큰 목록을 파이썬에서 유지하기

Question

나는 pickleable python 개체의 큰 목록을 유지 관리해야합니다. 목록이 너무 커서 RAM에 모두 저장되지 않으므로 일부 데이터베이스 \ 페이지 매커니즘이 필요합니다. 나는 그 메커니즘이 목록에있는 가까운 (가까운) 지역에 대한 빠른 액세스를 지원할 필요가있다.

리스트는 모든 파이썬 목록 기능을 구현해야하지만 대부분 순차적으로 작업 할 것입니다. 목록의 일부 범위를 스캔하고 스캐닝 중에 스캔 지점에 일부 노드를 삽입 할 것인지 결정하십시오.

목록이 매우 클 수 (2 - 3GB) 있으며 한 번에 모두 RAM에 포함되어서는 안됩니다. 노드는 작지만 (100-200 바이트) 다양한 유형의 데이터를 포함 할 수 있습니다.

좋은 해결책은 마지막으로 액세스 한 버킷 만 RAM에로드되는 BTree를 사용하는 것입니다.

복잡한 인덱스 키 메커니즘을 구현해야하므로 SQL 테이블을 사용하는 것은 좋지 않습니다. 내 데이터는 특정 인덱스에 요소를 추가하고 특정 위치에서 요소를 팝하는 기능이있는 테이블, 간단한 파이썬 목록이 아닙니다.

나는 ZODB 데이터베이스 파일에 저장할 수있는 BTree 기반 목록을 구현하는 ZODB과 zc.blist을 시도했지만 위의 기능이 적절한 시간에 실행되도록 구성하는 방법을 알지 못합니다. 모든 멀티 스레딩 \ 트랜잭션 기능이 필요하지 않습니다. 아무도 내 단일 스레드 프로그램을 제외하고 데이터베이스 파일을 건드릴 수 없습니다.

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가 사용하는 도구라고 생각합니다. 그것은 임의의 항목을 많이 저장할 것이고, 메모리 문제를 처리합니다.

다음은 작동 예제이며,이 경우에는 서로 참조하고 BTree에 번호로 저장되는 개체가 포함되어 있습니다. tree 변수는 기본적으로 사전처럼 작동과 키에 액세스 할 수있는이 시점에서

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 

. the ZODB BTrees API documentation에 설명 된대로 tree.keys(min, max)을 사용하여 범위의 키를 가져올 수도 있습니다.

ZODB에서 반환 한 root 개체에 서로 다른 키를 사용하여 10 개의 목록을 저장할 수 있습니다. root 개체는 ZODB 개체 저장소의 "게이트웨이"역할을합니다.

ZODB 덕분에 Btree 인덱스뿐만 아니라 개체 간 참조도 사용할 수 있습니다. 예 :

tree = getTree() 

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

Answer 3

도쿄 내각 사용은 어떻습니까? 매우 빠르고 간단하며 목록과 비슷하지만 원하는대로 만들었습니다. http://1978th.net/tokyocabinet/