بيثون: Zope's BTREE OOSET، IISET، إلخ ... فعالة لهذا الشرط؟

Question

سألت سؤال آخر:https://stackoverflow.com/Questions/1180240/best-way-we-sort-1m-records-in-phenthon. حيث كنت أحاول تحديد أفضل نهج لفرز 1 مليون سجل. في حالتي، أحتاج إلى أن أكون قادرا على إضافة عناصر إضافية إلى المجموعة وجعلها لجأت. اقترح أن أحاول استخدام BTRES Zope لهذه المهمة. بعد القيام ببعض القراءة، أنا جذاب قليلا فيما يتعلق بالبيانات التي أضعها في مجموعة.

أساسا، لكل سجل لدي قطعتين من البيانات. 1. معرف فريد يدري للمستخدم و 2. قيمة الفائدة للفرز.

أرى أنه يمكنني إضافة العناصر إلى Ooset كما tuples، حيث تكون القيمة للفرز في الفهرس 0. لذلك، (200, 'id1'),(120, 'id2'),(400, 'id3') وسيتم فرز المجموعة الناتجة مع id2, id1 and id3 مرتب.

ومع ذلك، جزء من متطلبات هذا هو أن كل معرف يظهر مرة واحدة فقط في المجموعة. سأضيف بيانات إضافية إلى المجموعة بشكل دوري وقد تتضمن البيانات الجديدة أو لا تشمل "معرفات" مكررة. إذا تم تكرارها، فأنا أرغب في تحديث القيمة وعدم إضافة إدخال إضافي. لذلك، بناء على TUPLES أعلاه، قد أضيف (405, 'id1'),(10, 'id4') إلى المجموعة ويريد أن يكون الإخراج id4, id2, id3, id1 مرتب.

أي اقتراحات بشأن كيفية تحقيق ذلك. آسف على الجديد في هذا الموضوع.

* تحرير - معلومات إضافية *

فيما يلي بعض الكود الفعلي من المشروع:

for field in lb_fields:
        t = time.time()
        self.data[field] = [ (v[field], k) for k, v in self.foreign_keys.iteritems() ]
        self.data[field].sort(reverse=True)
        print "Added %s: %03.5f seconds" %(field, (time.time() - t))

Ogine_Keys هي البيانات الأصلية في القاموس مع كل معرف كمفتاح وقاموس البيانات الإضافية كقيمة. البيانات هي القاموس الذي يحتوي على قوائم البيانات الفرز.

كملاحظة جانبية، نظرا لأن كل استثثال للحقل في LB_Fields يعمل، فإن الوقت المناسب للفرز - ليس كثيرا ... ولكنه ملحوظ. بعد فرز 1 مليون سجل لكل من الحقول 16، يستخدم حوالي 4 العربات أو ذاكرة الوصول العشوائي. في نهاية المطاف سوف يعمل هذا على جهاز مع 48 العربات.

Answer 1

لا أعتقد أن BTRES أو غيرها من هياكل البيانات المرتبة التقليدية (الأشجار السوداء الحمراء، إلخ) ستساعدك، لأنها تحتفظ بالترتيب حسب المفتاح، وليس عن طريق القيمة المقابلة - بمعنى آخر، الحقل الذي يضمنانه هو نفسه واحد يطلبونها من قبل. متطلباتك مختلفة، لأنك تريد التفرد على طول حقل واحد، ولكن Sandedness من جانب الآخر.

ما هي متطلبات أداءك؟ بتنفيذ Python النقي البسيط إلى حد ما يعتمد على Dicts Python من أجل التفرد ونشرات Python، على جهاز كمبيوتر محمول سريعا سريعا، أحصل على 5 ثوان بالنسبة للبناء الأصلي (أساسا فرز أكثر من مليون عنصر، بدءا مني كإخبز) ، وحوالي 9 ثوان ل "التحديث" مع 20،000 أزواج معرف / قيمة جديدة تضم نصف "تتداخل" (وبالتالي الكتابة فوق) معرف موجود ونصف جديد (يمكنني تطبيق التحديث بطريقة أسرع، ولكن حوالي 6.5 ثانية، ولكن هذا التنفيذ له شذوذ: إذا كان أحد أزواج "جديدة" متطابقة تماما لأحد "القديم"، فإن معرف وقيم كل من كلا من المعرف والقيمة، فهو تكرار - تجمع ضد هذا "ازدواجية متطابقة" هو ما يدفعني من 6.5 ثانية إلى 9، وأتخيل أنك ستحتاج إلى نفس النوع من الاحتياطات).

إلى أي مدى هي هذه الأوقات 5 و 9 ثوان من متطلباتك (مع مراعاة السرعة الفعلية للآلة التي ستشغيلها على VS 2.4 GHz Core Duo، 2GB من ذاكرة الوصول العشوائي، وقضايا أداء الكمبيوتر المحمول النموذجي من هذا الكمبيوتر المحمول 'تأمل)؟ Iow، هل هو قريب بما فيه الكفاية ل "المسافة المذهلة" لتكون تستحق العبث ومحاولة الضغط على الدورات القليلة الأخيرة من، أو هل تحتاج إلى أوامر ذات قيمة أسرع بكثير؟

لقد جربت العديد من الأساليب الأخرى (مع SQL DB، مع C ++ و STD :: Trans & C، ... لكنهم جميعا أبطأ، لذلك إذا كنت بحاجة إلى أداء أعلى بكثير، فأنا لست متأكدا مما يمكنك القيام به وبعد

يحرر: نظرا لأن المرجع يقول إن هذا الأداء سيكون على ما يرام، لكنه لا يستطيع تحقيق أي مكان بالقرب من ذلك، أعتقد أنني أفضل عرض البرنامج النصي الذي اعتدت فيه قياس هذه الأوقات ...:

import gc
import operator
import random
import time


nk = 1000

def popcon(d):
  for x in xrange(nk*1000):
    d['id%s' % x] = random.randrange(100*1000)

def sorted_container():
  ctr = dict()
  popcon(ctr)
  start = time.time()
  ctr_sorted = ctr.items()
  ctr_sorted.sort(key=operator.itemgetter(1))
  stend = time.time()
  return stend-start, ctr_sorted

def do_update(ctr, newones):
  start = time.time()
  dicol = dict(ctr)
  ctr.extend((k,v) for (k,v) in newones if v!=dicol.get(k,None))
  dicnu = dict(newones)
  ctr.sort(key=operator.itemgetter(1))
  newctr = [(k,v) for (k,v) in ctr if v==dicnu.get(k,v)]
  stend = time.time()
  return stend-start, newctr

def main():
  random.seed(12345)
  for x in range(3):
    duration, ctr = sorted_container()
    print 'dict-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
    newones = [('id%s' % y, random.randrange(nk*100))
                for y in xrange(nk*990,nk*1010)]
    duration, ctr = do_update(ctr, newones)
    print 'updt-to-sorted, %d: %.2f sec, len=%d' % (x, duration, len(ctr))
    del ctr
    gc.collect()

main()

وهذا هو المدى النموذجي:

$ time python som.py
dict-to-sorted, 0: 5.01 sec, len=1000000
updt-to-sorted, 0: 9.78 sec, len=1010000
dict-to-sorted, 1: 5.02 sec, len=1000000
updt-to-sorted, 1: 9.12 sec, len=1010000
dict-to-sorted, 2: 5.03 sec, len=1000000
updt-to-sorted, 2: 9.12 sec, len=1010000

real    0m54.073s
user    0m52.464s
sys 0m1.258s

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

هذا هو مع Python 2.5.2 المزود بالنظام على جهاز MacBook باستخدام Mac OS X 10.5.7 و 2.4 جيجا هرتز Intel Core Duo، و 2 جيجابايت من ذاكرة الوصول العشوائي (مرات لا تتغير كثيرا عندما استخدم إصدارات مختلفة من Python).

Answer 2

من الممكن تماما حل مشكلتك. لهذا يجب عليك فقط ملاحظة أن أنواع الحاويات في بيثون دائما مقارنة الكائنات عن طريق الاتصال بطرقهم. لذلك يجب أن تفعل شيئا مثل:

class Record:
    'Combination of unique part and sort part.'
    def __init__(self, unique, sort):
        self.unique = unique
        self.sort = sort

    def __hash__(self):
        # Hash should be implemented if __eq__ is implemented.
        return hash(self.unique)

    def __eq__(self, other):
        return self.unique == other.unique

    def __lt__(self, other):
        return self.sort < other.sort

 records = btree((Record(u, s) for u, s in zip(unique_data, sort_data)))

 print(records.pop())

ملاحظات:

• اعتمادا على كيفية تطبيق نوع الحاويات المفضل لديك، قد تحتاج إلى إضافة طرق ل! =، <=،>،> كذلك
• هذا لن يكسر العلاقة بين == و <= طالما x.unique == y.unique ==> x.sort == y.sort