maintenir une grande liste en python

Question

J'ai besoin de maintenir une grande liste d'objets python pickleable. La liste est trop grande pour être stockée dans la mémoire RAM, donc un mécanisme de base de données \ paging est requis. J'ai besoin que le mécanisme permette un accès rapide pour les zones proches (proches) de la liste.

La liste devrait implémenter toutes les fonctionnalités de python-list, mais la plupart du temps je vais travailler séquentiellement: balayer une partie de la liste et pendant l'analyse décider si je veux insérer \ pop quelques noeuds dans le point de scan.

La liste peut être très volumineuse (2-3 Go) et ne devrait pas être contenue dans la RAM à la fois. Les nœuds sont petits (100-200 octets) mais peuvent contenir différents types de données.

Une bonne solution pour cela pourrait être d'utiliser un BTree, où seuls les derniers buckets accédés sont chargés dans la RAM.

L'utilisation de tables SQL n'est pas bonne, car j'aurai besoin d'implémenter un mécanisme de clé d'index complexe. Mes données ne sont pas une table, c'est une simple liste python, avec la fonction d'ajouter des éléments dans des index spécifiques, et de faire sauter des éléments à partir de positions spécifiques.

J'ai essayé ZODB et zc.blist, qui implémentent une liste basée sur BTree qui peut être stockée dans un fichier de base de données ZODB, mais je ne sais pas comment le configurer pour que les fonctionnalités ci-dessus s'exécutent dans un délai raisonnable. Je n'ai pas besoin de toutes les fonctionnalités multi-threading \ transactioning. Personne d'autre ne touchera le fichier de base de données sauf pour mon programme monothread. Est-ce que quelqu'un peut m'expliquer comment configurer le ZODB \ zc.blist afin que les fonctionnalités ci-dessus puissent s'exécuter rapidement, ou me montrer une autre implémentation de grandes listes?

Une partie du code & rapide sale que j'ai essayé:

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,) 

Imprimer terminée par:

 
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

Utilisation de zc.blist peut apporter de bons résultats après tout, et définir l'option "cache_size" lors de la création du DB contrôle la taille des données qui resteront dans la RAM. La taille de la RAM utilisée peut grossir si vous ne faites pas "transaction.commit" assez souvent. En définissant un grand cache_size et en faisant transaction.commit souvent, les derniers buckets accédés de la blist resteront dans la RAM, vous donnant un accès rapide à ceux-ci, et la quantité de RAM utilisée ne grossira pas trop.

L'emballage est très cher, mais si vous avez un gros disque dur, vous n'avez pas besoin de le faire aussi souvent.

Voici un code pour vous essayer. Exécutez "top" en arrière-plan et modifiez cache_size pour voir comment cela affecte la quantité de RAM utilisée.

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

Je pense que la ZODB est l'outil à utiliser. Il va stocker beaucoup d'éléments arbitraires, il gère les problèmes de mémoire.

Voici un exemple de travail, et dans ce cas, j'ai inclus des objets qui se réfèrent les uns aux autres et qui sont stockés dans un BTree par numéro.

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 

A ce stade, la variable tree fonctionne essentiellement comme un dictionnaire et est accessible par la clé. Vous pouvez également obtenir les clés dans une plage en utilisant tree.keys(min, max) comme décrit par the ZODB BTrees API documentation.

Vous pouvez stocker vos 10 listes en plaçant chacune d'elles sous une clé différente dans l'objet root retourné par le ZODB. L'objet root sert de «passerelle» au stockage d'objets ZODB.

Grâce au ZODB, vous pouvez également utiliser les références inter-objets ainsi que l'index Btree. Par exemple:

tree = getTree() 

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

Answer 3

Comment utiliser Tokyo Cabinet? Très rapide et simple, comme des listes mais construit pour ce que vous voulez. http://1978th.net/tokyocabinet/