Gebrauch von __slots__ für set()

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

snafu hat geschrieben: [Datenbanken] wurde dem [Original Poster] ja bereits von mehreren Leuten vorgeschlagen. Bisher kam keine Begründung, warum dies offenbar keine Option für ihn ist.
... und zwar, weil es (für künftige Arbeiten) durchaus eine Option ist. Aber (falls jemand das nicht bemerkt hat), dieses eine Fussballspiel ist bereits abgepfiffen, das Ergebnis steht fest, und dieses hier sind die Kommentare, die daran nichts mehr ändern werden. (Nach "anderthalb Stunden" Laufzeit, das macht den Vergleich besonders lustig :D )


Dass mich die Kommentare sehr interessieren hat zwei Gründe:

(1)
Obwohl der Gebrauch einer Datenbank natürlich auch den Speichermangel umgeht, kann ich mir immer noch nicht vorstellen, dass so etwas mit dem direkten Abspeichern von Zahlen im Arbeitsspeicher geschwindigkeitsmäßig konkurrieren kann, und ich habe immer noch die Hoffnung, dass das zweite viel schneller ist. Ein Zugriff auf die Festplatte müsste deutlich langsamer sein als ein Zugriff auf den Arbeitsspeicher, oder ist diese Ansicht auch schon veraltet? Und (wie ich bereits erwähnte), auf welche Daten hier zugegriffen wird ist völlig unvorhersehbar.

(2)
Obwohl die meisten da anders denken als ich, bin ich immer noch der Ansicht, dass ein guter Programmierer wenigstens eine Ahnung haben sollte, wie sein Code vom Compiler umgesetzt wird. Profiling ist gut, sollte aber entweder dem Intuitionstraining dienen, oder um zu bestätigen, was der Codierer sich von Anfang an vorgestellt hat.
jerch
User
Beiträge: 1669
Registriert: Mittwoch 4. März 2009, 14:19

Goswin hat geschrieben:
snafu hat geschrieben: [Datenbanken] wurde dem [Original Poster] ja bereits von mehreren Leuten vorgeschlagen. Bisher kam keine Begründung, warum dies offenbar keine Option für ihn ist.
... und zwar, weil es (für künftige Arbeiten) durchaus eine Option ist. Aber (falls jemand das nicht bemerkt hat), dieses eine Fussballspiel ist bereits abgepfiffen, das Ergebnis steht fest, und dieses hier sind die Kommentare, die daran nichts mehr ändern werden. (Nach "anderthalb Stunden" Laufzeit, das macht den Vergleich besonders lustig :D )
Ich hoffe Dein Rechner hatte eine Halbzeitpause, sonst müssen wir das leider dem FIFA-Comitee melden ;)
Goswin hat geschrieben: (1)
Obwohl der Gebrauch einer Datenbank natürlich auch den Speichermangel umgeht, kann ich mir immer noch nicht vorstellen, dass so etwas mit dem direkten Abspeichern von Zahlen im Arbeitsspeicher geschwindigkeitsmäßig konkurrieren kann, und ich habe immer noch die Hoffnung, dass das zweite viel schneller ist. Ein Zugriff auf die Festplatte müsste deutlich langsamer sein als ein Zugriff auf den Arbeitsspeicher, oder ist diese Ansicht auch schon veraltet? Und (wie ich bereits erwähnte), auf welche Daten hier zugegriffen wird ist völlig unvorhersehbar.
Das ist schon noch so, wenn gleich moderne SSDs per PCI die "Festplatten" näher an RAM gerückt haben. Der random access klappt damit gut (ist ein Grund, warum SSDs als billige Alternative zu teuren Multilevel-RAID-Storage-Lösungen fürs DBs gesehen werden), von der Geschwindigkeit liegen aber noch Welten dazwischen.

Goswin hat geschrieben: (2)
Obwohl die meisten da anders denken als ich, bin ich immer noch der Ansicht, dass ein guter Programmierer wenigstens eine Ahnung haben sollte, wie sein Code vom Compiler umgesetzt wird. Profiling ist gut, sollte aber entweder dem Intuitionstraining dienen, oder um zu bestätigen, was der Codierer sich von Anfang an vorgestellt hat.
Mit der Intuition kommst Du bei so maschinenfernen Sprachen wie Python nicht weit, das ist einfach zu implementationsabhängig vom jeweiligen Interpreter (vgl. CPython, Jython, PyPy oder bei Javascript die verschiedenen Implementationen). In C klappt das noch ganz gut, wobei es auch da Überraschungen gibt (z.B. wird malloc der glibc vom gcc sehr anders umgesetzt als von clang auf dem x86).
Dav1d
User
Beiträge: 1437
Registriert: Donnerstag 30. Juli 2009, 12:03
Kontaktdaten:

Goswin hat geschrieben:(1)
Obwohl der Gebrauch einer Datenbank natürlich auch den Speichermangel umgeht, kann ich mir immer noch nicht vorstellen, dass so etwas mit dem direkten Abspeichern von Zahlen im Arbeitsspeicher geschwindigkeitsmäßig konkurrieren kann, und ich habe immer noch die Hoffnung, dass das zweite viel schneller ist. Ein Zugriff auf die Festplatte müsste deutlich langsamer sein als ein Zugriff auf den Arbeitsspeicher, oder ist diese Ansicht auch schon veraltet? Und (wie ich bereits erwähnte), auf welche Daten hier zugegriffen wird ist völlig unvorhersehbar.
Das interessante ist nicht unbedingt *wo* die Daten liegen sonder, *wie* so dort liegen. Es kommt auch darauf an *wie* du die Daten verwendest, willst du nur erstmal alle sammeln, dann einmal darüber iterieren oder machst du viele lookups? Dann kannst du auch eine Liste verwenden und es ist schneller als alles andere.

Nehmen wir mal an du machst viele lookups, dann hast du mit dem Set von Python Average O(1) lookups, worst case sieht das schonmal einiges schlechter aus O(n) (das ist verdammt viel bei 42 Millionen Einträgen). Dann kommt noch die Dauer des hashens dazu.
Vereinfacht angenommen unsere Datenbank ist ein B+-Tree ohne sonstige Optimierungen, das sind worst und average O(log(n)) lookups.
Jetzt kommt das Argument, aber meine Hashtable liegt doch im Arbeitsspeicher. Arbeitsspeicher ist ab dem Moment wo geswappt wird eh schonmal vorbei und es wird ziemlich langsam. Also wir nehmen an, kein Swapping. Naja, 42 Millionen Einträge sind ein dickes Ding für so eine Hashtable, wenn du Pech hast ist die ziemlich voll mit vielen Kollisionen, d.h. du hast nicht mehr nur O(1) lookups. Also für jeden Lookup der failt musst du weiter in der Table springen und jedes mal dein Element vergleichen (oder du hast eine Bucketlist an jeder Stelle hängen).
Nun zu unserem B+-Tree, er lädt immer ein paar Pages an Keys und vergleicht, maximal O(log(n)), log(42.000.000) ~= 17. Hast du jetzt Average mehr Kollisionen als log(n) hat der B+-Tree eh schon gewonnen. Wenn die Keys schlau liegen ist das Laden auch nur ein Bruchteil der dann letztendlichen Vergleiche (ah ja und SSDs gibts ja auch schon).

Wie du siehst hängt das von ein Paar Faktoren gewaltig ab, Befüllung der Table, Kollisionsresistenz des Sets (auch ja, was auch noch lustig ist, sets müssen resize'd werden falls sie zu klein werden, das heisst alles kopieren und ggf. rehashen), dann endgültige Kollisionen. Deine Anzahl der Lookups etc.
Sobald swapping ins Spiel kommt kannst du die Performance von Sets sowieso vergessen. Also generell lösen Datenbanken dein Memory-Problem, geben dir noch dazu nette Queries und sind (average) schneller.
the more they change the more they stay the same
Sirius3
User
Beiträge: 17747
Registriert: Sonntag 21. Oktober 2012, 17:20

@Goswin: bei einer Datenbank werden die meisten Operationen auch im Hauptspeicher stattfinden. Wenn man genug davon hätte, könnte man das auch komplett im Speicher behalten.

Das Aufbauen des Sets ist ein nicht zu vernachläßigender Zeitfresser. Python verdoppelt die Anzahl der Einträge, falls nicht genug Platz ist, das passiert bei 42 Millionen mindestens 26. Wenn das zum letzten Mal in der Nähe der 40 Millionen auftritt bedeutet das, dass gut 80 Millionen Einträge in eine Hashtabelle sortiert werden müssen und zudem doppelt so viel Speicher benötigt wird, als für das entgültige Set (im ungünstigen Fall ~3GB). Dagegen die Vorteile eines B+-Trees hat Dav1d ja schon beschrieben.
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

Goswin hat geschrieben: Ich habe inzwischen gemerkt, dass jede abgespeicherte Zahl bis zu 100 Dezimalziffern haben kann und ich immer noch 40_Millionen davon ohne MemoryError abspeichern kann. Dann kann ich ein Tripel wie ('abc','ad','befg') direkt durch eine Zahl wie 1020300104002050607 ohne Absturz abspeichern (jedes Zeichen ein positiver Integer, 0=Zeichentrenner, 00=Stringtrenner). Das ist trivial zu codieren, braucht allerdings auch ... [falsch:] fast anderthalb Stunden.
So peinlich das ist, hatte ich bisher eine Ungeschicklichkeit in meiner inneren Codeschleife übersehen, die sich dramatisch auf die Laufzeit ausgewirkt hat. Nach Bereinigung des Codes beträgt die Laufzeit beim Abspeichern von Zahlen nicht mehr anderthalb Stunden sondern nur noch 25_Minuten. Dazu kommt, dass die 10_Minuten beim Abspeichern von Tripeln mit Vorsicht zu genießen sind, da das Programm ja abgestürzt ist, und ich eine geschätzte zusätzliche Zeit hinzufügen müsste, die das Programm bei genügend Arbeitsspeicher noch gebraucht hätte. Zwar war rund 80% der Arbeit schon getan, aber auch so würde das Programm beim Abspeichern von Tripeln wohl mindestens 15_Minuten brauchen.

FAZIT: Durch Abspeichern von Zahlen anstelle von Tupeln lässt sich bei durchaus tragbarer Zeiteinbuße deutlich mehr Information im Arbeitsspeicher unterbringen. Das soll aber kein Einspruch gegen alternative Vorgehensweisen sein.
Antworten