Python:Zope ist BTree OOSet, IISet, etc... Effektive für diese Anforderung?

Question

Ich fragte eine andere Frage:https://stackoverflow.com/questions/1180240/best-way-to-sort-1m-records-in-python wo war ich versucht zu ermitteln, den besten Ansatz für die Sortierung von 1 million Datensätze.In meinem Fall habe ich werden müssen in der Lage, weitere Elemente hinzufügen, um die Sammlung und haben Sie gegriffen.Es wurde vorgeschlagen, dass ich versuche, mit Zope ist BTrees für diese Aufgabe.Nach etwas Lesen bin ich ein wenig ratlos, welche Daten ich möchte in einem Satz.

Im Grunde, für jede Platte, die ich haben zwei Stücke von Daten.1.Eine einzigartige ID, die eine Zuordnung zu einem Nutzer und über 2.ein Wert von Interesse für die Sortierung an.

Ich sehe, dass ich die Elemente hinzu, um eine OOSet als Tupel, bei denen der Wert für die Sortierung ist mit dem index 0.So, (200, 'id1'),(120, 'id2'),(400, 'id3') und die Ergebnismenge sortiert sein würde id2, id1 and id3 in Ordnung.

Allerdings ist ein Teil der Voraussetzung für diese ist, dass jede id nur einmal erscheinen in der Gruppe.Ich werde hinzufügen, die zusätzliche Daten zu dem Satz, in regelmäßigen Abständen und die neuen Daten kann oder auch nicht dupliziert, 'ids'.Wenn Sie dupliziert möchte ich den Wert aktualisieren und nicht einen weiteren Eintrag hinzufügen.So, basierend auf den Tupeln oben, könnte ich hinzufügen (405, 'id1'),(10, 'id4') zu dem set und möchte die Ausgabe zu haben id4, id2, id3, id1 in Ordnung.

Irgendwelche Vorschläge, wie dies zu erreichen.Sorry für meine newbness auf das Thema.

* BEARBEITEN - zusätzliche info *

Hier ist der aktuelle code aus dem Projekt:

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

foreign_keys die ursprünglichen Daten in ein dictionary mit jeder id als Schlüssel und ein Wörterbuch mit den zusätzlichen Daten, wie der Wert.Daten ist ein Wörterbuch mit Listen von sortierten Daten.

Als eine Seite beachten Sie, wie jedes itereation der für das Feld in lb_fields läuft, die Zeit zu Sortieren erhöht - nicht viel...aber es ist spürbar.Nach 1 Millionen Datensätze sortiert wurden für jedes der 16 Felder ist es mit über 4 Gigs RAM.Letztendlich wird dies führen Sie auf einem Computer mit 48 Gigs.

Answer 1

Ich glaube nicht, dass BTrees oder andere traditionelle sortiert Datenstrukturen (rot-schwarz-Bäume, etc) wird Ihnen helfen, weil Sie halten, um durch die Taste, nicht durch entsprechende Wert-in anderen Worten, der Bereich, für den Sie garantiert so einzigartig ist die gleiche, die Sie Reihenfolge durch.Ihre Anforderungen sind unterschiedlich, weil Sie wollen, Einzigartigkeit, zusammen ein Feld, aber sortedness von den anderen.

Was sind Ihre performance-Anforderungen?Mit einer eher einfachen reinen Python-Implementierung auf Basis von Python-dicts für Einzigartigkeit und Python-Arten, auf eine nicht-blazingly-fast laptop, bekomme ich 5 Sekunden für den ursprünglichen Bau (im wesentlichen eine Art über die Millionen-Elemente, beginnend mit der Sie als dict), und etwa 9 Sekunden für das "update" mit 20.000 neue id/Wert-Paaren, von denen die Hälfte "überschneidung" (also überschrieben) werden eine vorhandene id und die Hälfte neuen (kann ich implementieren die update-ein schneller Weg, etwa 6,5 Sekunden aber die Umsetzung ist eine Anomalie:wenn man die "neue" Paare ist genau identisch zu einem von der "alten", die beide id und Wert, vervielfältigt -- Abwehr gegen solche "Vervielfältigung identicals" ist, was treibt mich von 6,5 Sekunden bis 9, und Stelle mir vor, Sie müssten die gleiche Art von vorsorge).

Wie weit sind die beiden 5-und 9 Sekunden mal von Ihren Anforderungen (unter Berücksichtigung der tatsächlichen Geschwindigkeit der Maschine, Sie werde laufen auf vs 2.4 GHz Core Duo, 2 GB RAM und der typischen laptop-performance-Probleme der laptop, den ich verwende)?IOW, ist es nahe genug, um "Schlagdistanz" zu sein lohnt sich, basteln und versuchen, squeeze-einen letzten Zyklen aus, oder tun Sie benötigen Größenordnungen schneller Leistung?

Ich habe versucht, mehrere andere Ansätze (mit einer SQL-DB mit C++ und Ihre std::sort &c, ...), aber Sie sind langsamer, also, wenn Sie brauchen sehr viel höhere Leistung ich bin mir nicht sicher, was Sie tun können.

Bearbeiten:seit der OP sagt, diese Leistung wäre in Ordnung, aber er kann nicht erreichen, die irgendwo in der Nähe es, ich denke, ich würde am besten zeigen Sie das Skript, das ich verwendet, um zu Messen, diese Zeiten...:

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

und dies ist eine typische Ausführung:

$ 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

die insgesamt verstrichene Zeit, ein paar Sekunden mehr als das Summen bin ich Messen, offensichtlich, weil es die Zeit erforderlich zu füllen Sie den Behälter mit Zufallszahlen, generieren die "neue Daten", auch zufällig, zu zerstören und Müll-sammeln Sie die Dinge am Ende jedes Laufs, und so weiter.

Dies ist mit dem system gelieferte Python 2.5.2 auf einem Macbook mit Mac OS X 10.5.7, 2.4 GHz Intel Core Duo und 2GB RAM (mal nicht viel ändern, wenn ich verschiedene Versionen von Python).

Answer 2

Es ist durchaus möglich, Ihr Problem zu lösen. Hierzu sollte man einfach beachten Sie, dass die Containertypen in Python immer vergleichen Objekte durch ihre Methoden aufrufen. Daher sollten Sie so etwas wie:

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

Weitere Informationen:

• je nachdem, wie Sie Ihr Lieblingscontainertyp implementiert ist, müssen Sie möglicherweise Methoden hinzufügen für! =, <=,>,> = Und
• das wird nicht bricht die Beziehung zwischen == und <= solange x.unique == y.unique ==> x.sort == y.sort