Gebrauch von __slots__ für set()

[snafu]

Edit: Wobei das aber auch nach hinten losgehen kann, je nachdem wie viele verschiedene Zeichenketten es gibt und ob das jeweils eigene Objekte sind oder ob für die gleiche Zeichenkette die selbe verwendet wird oder nicht.

Du meinst, weil Python Optimierungen nutzt, wenn mehrfach der gleiche String verwendet wird? Stimmt schon. Aber da müsste man wohl einfach ausprobieren, was weniger Speicherplatz frisst.

[BlackJack]

@snafu: Ich denke die Antwort ist: Datenbank verwenden anstatt da irgendwelche komischen Sachen zu machen die an Voodoo grenzen. Man sollte bei den 3 Stunden beispielsweise erst einmal klären woher die kommen. Wenn das System die Datenmenge an sich zwar schafft, aber so lange braucht weil's heftig am swappen ist, kann man an der verwendeten Funktion Geschwindigkeitsmässig sicher kaum etwas machen wenn sie nicht total ungünstig programmiert ist.

[Goswin]

@Goswin: Magst du zeigen, was du da gebastelt hast? Der Performance-Verlust ist schon ziemlich krass.

Gerne (inzwischen schaffe ich es in bereits anderthalb Stunden).

(1)
Jedem Tripel kann ich auf eindeutige Art eine Permutation der Zahlen 0,...,10 zuordnen (das ist möglich, weil keines der Zeichen sich wiederholen darf). Dieser Schritt geht schnell vonstatten. Es gibt 11!_=_39916800 solche Permutationen, daher die zig-Millionen Tripel.

(2)
Jeder Permutation muss nun auf eindeutige Art eine ganze Zahl zugeordnet werden, und das ist der aufwändige Schritt. Gestern hatte ich mir dafür aus dem Internet einen Algoritmus von Myrvold & Ruskey geholt und in Python3 übersetzt; heute früh habe ich ebenfalls aus dem Internet einen Algorithmus von Blai Bonet geholt (https://www.aaai.org/Papers/Workshops/2 ... 10-004.pdf), wodurch das Ganze etwas schneller wurde. Meine Umsetzung von Bonets Algorithmus ist:

Code: Alles auswählen

from math import log, ceil
from itertools import permutations

def ort_perm(perm):
   """
   perm: Permutation der Zahlen (0,1,2,...,n)
   #
   berechnet das lexikografische Ranking der Permutation nach Blai Bonet
   https://www.aaai.org/Papers/Workshops/2008/WS-08-10/WS08-10-004.pdf
   Laufzeit ist O(n*log(n))
   """
   #assert sorted(perm)==list(range(len(perm)))

   nn = len(perm)
   pot = 1<<ceil(log(nn,2))
   baum_lst = 2*pot*[0]
   ort = 0
   for ii in range(nn):
      knoten = pot + perm[ii]
      while knoten%2==0:
         baum_lst[knoten] += 1
         knoten >>= 1
      ctr = perm[ii] - baum_lst[(knoten>>1)<<1]
      baum_lst[knoten] += 1
      knoten >>= 1
      baum_lst[knoten] += 1
      ort = ort*(nn-ii) + ctr
   return  ort


nn = 4
for perm in permutations(range(nn)):
   ort = ort_perm(perm)
   print("ort_perm{} = {:3}".format(perm,ort))

Der gestrige Algorithmus von Myrvold & Frankey hat zwar eine Laufzeit von nur O(n), aber er ist komplizierter, und da Python3 keine maschinennahe Sprache ist, ist dessen Laufzeit für n=11 immer noch doppelt so lang. Mir ist auch nichts eingefallen, wie man das itertool-Modul für so etwas einsetzen kann.


@BlackJack: Ich gehe davon aus, dass Python3 keinerlei Swapping macht; wenn es das täte, hätte es ja keinerlei Anlass, wegen MemoryError abzustürzen.

[BlackJack]

@Goswin: Natürlich macht Python kein Swapping, aber das Betriebssystem macht das wenn kein physikalischer Speicher mehr frei ist, der Adressraum des Prozesses aber noch Luft hat (und genug Platz in der Swapdatei/-partition ist).

[jerch]

@Goswin:
Die Daten passen nicht in den Speicher und mehr Speicher ist offentsichtlich keine Option - ergo brauchst Du was, um effizient vom Speicher auf die eigentlichen Daten abbilden zu können. Für sowas gibts Datenbanken.
Wenn Dir die Nutzung eines fertigen DBMS zu simpel ist, kannst Du das auch selber in deutlich schlechter nachbauen:
1. Tupel bzw. Stringrepräsentationen in eine Binärdatei schreiben, Offsets merken
2. Offsets in eine Indexdatei schreiben, die Durchnummerierung hier entspräche dem PK in DB-Logik. Wenn die Indexdatei typisiert ist (immer gleiche Breite der Einträge), klappen spätere Zugriffe über den PK in O(1).
3. "DB-Index" erstellen - da Deine Daten Strings sind, wäre die simpleste mögliche Baumstruktur ein unbalancierter Baum mit erlaubten Bytes in den Blättern und Abstieg über die Stringlänge.

1. und 2. machen alle (relationalen) DBMS im Prinzip ähnlich. 3. baut man nicht mal eben nach, da hierfür sehr viel Knowhow über optimierte Bäume für bestimmte Datentypen und Operationen hierauf nötig ist, hier beginnt eigentliche Leistungsfähigkeit von DBMSen. Warum ist die Nutzung einer Datenbank keine Option für Dich?

@snafu:
Den Versuch, die Daten verlustfrei in eine kleinere Speicherrepräsentation zu packen, halte ich für nicht zweckdienlich. Das geht spätestens dann wieder krachen, wenn sich die Anzahl der Datensätze deutlich erhöht.

[Goswin]

Den Versuch, die Daten verlustfrei in eine kleinere Speicherrepräsentation zu packen, halte ich für nicht zweckdienlich. Das geht spätestens dann wieder krachen, wenn sich die Anzahl der Datensätze deutlich erhöht.

Das ist richtig - in allen den Fällen, wo ein externer Benutzer Einfluss auf die Datengröße hat. In meinem Fall brauche ich das Ergebnis nur intern um eine Spiel-Applikation zu entwickeln, weshalb die Skalierung bis auf weiteres unwichtig ist.

[jerch]

Das ist richtig - in allen den Fällen, wo ein externer Benutzer Einfluss auf die Datengröße hat. In meinem Fall brauche ich das Ergebnis nur intern um eine Spiel-Applikation zu entwickeln, weshalb die Skalierung bis auf weiteres unwichtig ist.

Dann solltest Du vllt. nochmal grundlegender über Dein Datenmodell nachdenken. Keine Ahnung, wofür Deine Einträge in den Tupeln stehen, allerdings sind 22 Mio. Einträge à 10 Bytes (gemäß Deines Bsp.) schon eine Hausnummer für "Verkehrsdaten" in einer laufenden App. Evtl. lässt sich ein Teil deutlich kürzer darstellen oder selten gebrauchte Daten auslagern.

[Goswin]

Allerdings sind 22 Mio. Einträge à 10 Bytes (gemäß Deines Bsp.) schon eine Hausnummer für "Verkehrsdaten" in einer laufenden App. Evtl. lässt sich ein Teil deutlich kürzer darstellen oder selten gebrauchte Daten auslagern.

Wenn du nur eine Ahnung hättest, was Forschung und Number-Crunching für große Datenmengen erzeugen kann! Oft schreibt man einen Code, weil man ein bestimmtes Ergebnis braucht: dieser Code wird theoretisch nur einmal ausgeführt (in der Praxis ein paar Male, um die Ausgabe zu verschönern oder zu überprüfen), und sobald man das Ergebnis hat, kann man den Code fast wegwerfen. Das tut man freilich nicht, weil man ihn manchmal für ähnliche Aufgaben abändern kann (und auch besseres Codieren dabei lernt). Ich kann auch nicht voraussehen, welche Daten "selten gebraucht" werden, das ist nämlich gerade, was ich hier herausfinden möchte.

Ich denke, gerade Python, welches für "schnelles Prototyping" entworfen wurde, dürfte für Wegwerf-Code die geeignete Sprache sein. Nur darf man eben Wergwerf-Code nicht mit "einfachem Code" oder "kurzem Code" verwechseln.

[jerch]

@Goswin:
Keine Ahnung, warum Du mit der Numbercrunching/Forschungssache kommst - wenn das Deine Domäne ist, dann solltest Du vllt. mal Euren Institutschef nach aktueller Hardware fragen. Selbst Desktoprechner kann man heutzutage schon mit 128GB RAM bekommen.

[Goswin]

@Goswin: Keine Ahnung, warum Du mit der Numbercrunching/Forschungssache kommst.

Hobby

[Goswin]

Jedem Tripel kann ich auf eindeutige Art eine Permutation der Zahlen 0,...,10 zuordnen (das ist möglich, weil keines der Zeichen sich wiederholen darf).

Das ist zwar richtig, aber (wie ich nun sehe) immer noch unnötig und viel zu kompliziert. 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 fast anderthalb Stunden.

Wenn man faul ist, dann nimmt man dafür ``dein_set.add(pickle.dumps(triple, pickle.HIGHEST_PROTOCOL))``. Vielleicht spart das ja schon genug Speicher ein.

Diese pickle-Idee funktioniert nicht; mein Programm stürzt genau an derselben Stelle wie ehemals mit MemoryError ab. Im Nachhinein wundert mich das wenig: offenbar muss beim pickle zusammen mit dem Objekt auch die Struktur des Objektes abgespeichert werden, was ich mit meinen Zahlen ja nicht tue; nur mein Maincode weiß, wie diese Zahlen zu interpretieren sind.

[jerch]

@Goswin:
Permutationen sind teuer in der Berechnung. Deine Zahl 1020300104002050607 deutet die Bytes des Strings als Stellenwertsystem, was dann zwar nur dünn besetzt ist, aber deutlich einfacher zu berechnen ist. Die Zahl kannst Du noch weiter einkürzen, in dem Du mit den Indices der erlaubten Bytes zur Basis der Länge des Zeichenvorrates nimmst und den Feldtrenner z.B. als nulltes Element. In puncto Geschwindigkeit dürfte helfen, unter Pythons long-Grenze zu bleiben.

[snafu]

Man müsste auch prüfen, ob das System zum Ende hin swappt, d.h. ob Daten anderer Programme aus dem Hauptspeicher (RAM) in eine Auslagerungsdatei geschrieben werden, um Platz für die letzten Elemente zu machen. Dieses Auslagern kann dann nämlich auch zu größeren Zeiteinbußen führen. Auch dagegen hilft es, die Daten bestmöglich zu komprimieren und sie dabei trotzdem noch voneinander unterscheidbar zu machen.

[Dav1d]

Ich verstehe immer noch nicht den Sinn des ganzen. Bevor ich mir i-welche Permutationen etc überlege, importiere ich SQLAlchemy, schreib mir ein bis zwei Model, schieb alles in eine Datenbank (SQLite wenn ich keine andere zur Auswahl habe) und bin fertig. Bonus: Ich kann SQL-Queries auf meine Daten nutzen.

[snafu]

@Dav1d
Wurde dem OP ja bereits von mehreren Leuten vorgeschlagen. Bisher kam keine Begründung, warum dies offenbar keine Option für ihn ist.

[Goswin]

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


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]

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

Ich hoffe Dein Rechner hatte eine Halbzeitpause, sonst müssen wir das leider dem FIFA-Comitee melden

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

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

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

[Sirius3]

@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.

[Goswin]

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.