الحفاظ على قائمة كبيرة في بيثون

Question

أحتاج إلى الحفاظ على قائمة كبيرة من الكائنات القابلة للبيثون. القائمة كبيرة جدًا بحيث لا يتم تخزينها في ذاكرة الوصول العشوائي ، لذلك مطلوب بعض آلية قاعدة البيانات الترحيل. أحتاج إلى أن الآلية ستدعم الوصول السريع للمناطق القريبة (القريبة) في القائمة.

يجب أن تنفذ القائمة جميع ميزات قائمة Python ، لكن في معظم الأوقات سأعمل بشكل متتابع: مسح بعض النطاق في القائمة وأثناء المسح الضوئي ، حدد ما إذا كنت أرغب في إدراج بعض العقد في نقطة المسح.

يمكن أن تكون القائمة كبيرة جدًا (2-3 غيغابايت) ، ويجب ألا تكون موجودة في ذاكرة الوصول العشوائي في وقت واحد. العقد صغيرة (100-200 بايت) ولكن يمكن أن تحتوي على أنواع مختلفة من البيانات.

يمكن أن يكون الحل الجيد لهذا هو استخدام BTREE ، حيث يتم تحميل الدلاء الأخيرة التي تم الوصول إليها فقط في ذاكرة الوصول العشوائي.

استخدام جداول SQL ليس جيدًا ، لأنني سأحتاج إلى تنفيذ آلية مفتاح الفهرس المعقدة. لا تعد بياناتي جدولًا ، إنها قائمة بيثون بسيطة ، مع ميزة إضافة عناصر في فهارس محددة ، وعناصر تفرقع من مواقع محددة.

حاولت 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 كبير والقيام بالمعاملات. في كثير من الأحيان ، ستبقى آخر الدلاء التي تم الوصول إليها من بليست في ذاكرة الوصول العشوائي ، مما يتيح لك الوصول السريع إليها ، ولن تنمو كمية ذاكرة الوصول العشوائي المستخدمة كثيرًا.

التعبئة مكلفة للغاية ، ولكن إذا كان لديك صعبة كبيرة ، فلن تضطر إلى القيام بذلك في كثير من الأحيان على أي حال.

إليك بعض التعليمات البرمجية لتجربة نفسك. قم بتشغيل "أعلى" في الخلفية وقم بتغيير 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

ماذا عن استخدام خزانة طوكيو؟ سريع وبسيط للغاية ، مثل القوائم ولكن تم تصميمه لما تريد.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.

يمكنك تخزين قوائمك العشرة عن طريق وضع كل واحدة تحت مفتاح مختلف في root الكائن الذي تم إرجاعه بواسطة Zodb. ال root يعد الكائن بمثابة "بوابة" لتخزين كائن ZodB.

بفضل ZODB ، يمكنك أيضًا استخدام المراجع بين الكائنات وكذلك مؤشر BTREE. علي سبيل المثال:

tree = getTree()

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