ведение большого списка в python

Question

Мне нужно вести большой список объектов, выбираемых Python. Список слишком велик, чтобы его можно было хранить в ОЗУ, поэтому требуется какой-то механизм базы данных \ подкачки. Мне нужно, чтобы механизм поддерживал быстрый доступ для близких (близлежащих) областей в списке.

В списке должны быть реализованы все функции списка python, но большую часть времени я буду работать последовательно: сканировать некоторый диапазон в списке и во время сканирования решить, хочу ли я вставить \ вытолкнуть некоторые узлы в точке сканирования.

Список может быть очень большим (2–3 ГБ), и не должен все одновременно содержаться в ОЗУ. Узлы маленькие (100-200 байт), но могут содержать различные типы данных.

Хорошим решением для этого может быть использование BTree, где в ОЗУ загружаются только последние использованные сегменты.

Использование таблиц 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 может принести хорошие результаты, а установка опции «cache_size» при создании БД контролирует размер данных, которые останутся в ОЗУ.Размер используемой оперативной памяти может увеличиться, если вы не будете часто выполнять транзакции.Определяя большой размер cache_size и часто проводя транзакции с помощьюmit.commit, последние открытые сегменты блиста останутся в оперативной памяти, что обеспечит вам быстрый доступ к ним, а объем используемой оперативной памяти не увеличится слишком сильно.* Упаковка очень дорогая, но если у вас большой жесткий диск, вам не обязательно делать это так часто.

Вот код, который вы можете попробовать сами.Запустите «top» в фоновом режиме и измените cache_size, чтобы увидеть, как он влияет на объем используемой оперативной памяти.

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

Как насчет использования Tokyo Cabinet? Очень быстро и просто, как списки, но построен для того, что вы хотите. http://1978th.net/tokyocabinet/

Answer 3

Я думаю, что 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 .

Вы можете сохранить свои 10 списков, поместив каждый из них под свой ключ в объекте root, возвращаемом ZODB. Объект root служит «шлюзом» для хранилища объектов ZODB.

Благодаря ZODB вы также можете использовать ссылки между объектами, а также индекс Btree. Например:

tree = getTree()

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