Gebrauch von __slots__ für set()

[Goswin]

In einer Python3-Code Funktion verwende ich einen Container menge=set() die ich mit zig-Millionen String-Tripeln der Form ('ab','cdefg','ijk') fülle, was das Programm kurz vor seinem Abschluss mit MemoryError abstürzen lässt. Kann ich das mit Hilfe von __slots__ vermeiden? Wenn ja, muss ich dafür eine besondere Klasse definieren? Ich habe bisher nie __slots__ verwendet und wüßte nicht, wie man das bei einem Standard-Objekt wie set() macht.

[Goswin]

(Fortsetzung. Wieso kann ich meine eigenen Fragen eigentlich nicht editieren? Wofür ist das Editier-Icon gut?)


Ich habe bisher nie __slots__ verwendet und wüßte nicht, wie man das bei einem Standard-Objekt wie set() macht. Zum Beispiel stürzt folgender Code bei etwa zz=22000000 ab:

Code: Alles auswählen

plainset = set()
for zz in range(100000000):
   if zz%1000000==0: print("zz={:9}".format(zz))
   zz_str = str(zz)
   plainset.add((zz_str,zz_str,zz_str))

Als Beispiel was NICHT funktioniert, stürzt folgender Code genau an derselben Stelle ab:

Code: Alles auswählen

class Sparset(set):
   __slots__ = ['menge']
   #
   def __init__(self):
      self.menge = set()

sparset = Sparset()
for zz in range(100000000):
   if zz%1000000==0: print("zz={:9}".format(zz))
   zz_str = str(zz)
   sparset.menge.add((zz_str,zz_str,zz_str))

[Sirius3]

@Goswin: ab Python 3.4 ist die Speicherverschwendung bei selbst erzeugten Klassen nicht mehr so gravierend, weil die Instanzen die Keys ihrer __dict__s teilen. Bei internen Klassen gibt es aber kein __dict__, und somit ist __slots__ auch unnötig. Wenn nur ein Exemplar der Klasse existiert, ist das Speicherargument für __slots__ auch hinfällig. Die tuple allein benötigen ungefähr 1GB Speicher. Dann noch ungefähr 1 GB für das set und entsprechend Speicher für die Strings.

[BlackJack]

@Goswin: Das hat ja nichts mit dem Container zu tun, den gibt es ja eh nur *einmal*, da würde es nichts nützen pro Exemplar Speicher zu sparen.

Die zig Millionen Objekte, die Du in das `set` steckst, könnten davon profitieren wenn sie denn von einem selbst geschriebenen Datentyp wären, aber wenn Du da `tuple`-Exemplare in dem `set` speicherst, wird eine eigene Klasse statt `tuple` nichts nützen. Wenn man Glück hätte würde mit `__slots__` genau so viel Speicher verbraucht, wenn man Pech hätte trotz `__slots__` mehr als bei `tuple`-Exemplaren.

[Goswin]

Die tuple allein benötigen ungefähr 1GB Speicher. Dann noch ungefähr 1 GB für das set und entsprechend Speicher für die Strings.

(1)
Gibt es eine Funktion, die mir anzeigt, wieviel Speicherplatz ein Tripel wie ('ab','cdfg','hij') oder sonst ein Objekt benötigt?
(2)
Obwohl ich maximal 22_Millionen tuple's in einem set speichern kann, stelle ich fest, dass der Code bei einem set mit int's erst bei 42_Millionen abstürzt; auch dann, wenn ich diese Zahlen alle größer als 900000000 wähle. Würde ich Platz sparen, wenn ich mir eine bijektive Funktion definiere, die jedem Tripel eine natürliche Zahl zuordnet? (die Hashfunktion ist offenbar nicht bijektiv)
(3)
Vermutlich würde ich auch Platz sparen, wenn ich die Tripel in einer Liste abspeichere, die ich von Zeit zu Zeit ordnen könnte. Die einzige Operation, die ich für diese Liste benötigen würde, ist die Suche nach dem Index eines vorgegebenen Tripels und die Änderung des entsprechenden Tripels in der Liste. Würde bei 40_Millionen solcher Suchen die Rechenzeit ins Unermessliche steigen?

[DasIch]

Es gibt da so eine Technologie die sich Datenbank nennt, vielleicht mal mit beschäftigen. Ansonsten kann man sich noch Server anmieten, was Arbeitsspeicher angeht sind da noch oben kaum Grenzen gesetzt.

[BlackJack]

@Goswin: Ad (1): Du könntest die `__sizeof__()`-Methode auf dem Tupel und den Inhalt anwenden und alles zusammenrechnen. Allerdings kann es sein das es Tupel gibt bei denen gleiche Zeichenketten auch durch das selbe Objekt repräsentiert werden.

Ad (2): Wenn es eine solche Funktion gibt, könntest Du das natürlich machen.

Ad (3): Das Leistungsproblem bei der Liste ist sortiert einfügen. Man könnte zwar mit dem `bisect`-Modul den Einfügepunkt relativ leicht herausfinden, aber zum Einfügen müssen dann potentiell sehr viele Elemente verschoben werden. Und das bei jedem Einfügen.

----

Bei solchen Datenmengen würde ich mal über eine Datenbank nachdenken. Die sind nicht durch den verfügbaren Arbeitsspeicher begrenzt.

[snafu]

Würde ich Platz sparen, wenn ich mir eine bijektive Funktion definiere, die jedem Tripel eine natürliche Zahl zuordnet? (die Hashfunktion ist offenbar nicht bijektiv)

In einem Set wird halt auch immer das eigentliche Objekt abgespeichert. Oder genauer gesagt die Referenz auf das Objekt. Und solange diese Referenz besteht, solange muss auch das eigentliche Objekt existieren. Das wird ja nicht erst beim Abruf durch das Set generiert, sondern es kann durch ein Set lediglich schneller aufgrund des Hashwertes gefunden werden.

Eine Funktion zum Generieren von Objekten aufgrund bestimmter Informationen, die weniger Platz im Speicher als das zu erzeugende Objekt einnehmen, wäre eine Möglichkeit. 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.

Üblicher wäre es aber, eine Datenbank zu nutzen. Mit dem `sqlite3`-Modul kannst du via ``sqlite3.connect(':memory:')`` auch Datenbanken erzeugen, die nur im Speicher existieren, d.h. du bräuchtest keine Schreibrechte auf dem System und hättest auch relativ wenig Arbeit für das Anlegen der Datenbank. Das wäre vermutlich der Weg, den ich gehen würde. Ein Triple könnte man ja mit einem 3-spaltigen Datensatz repräsentieren, den man sich später mittels `fetchone()` wieder schön als Python-Objekt aufbereiten lassen kann.

[BlackJack]

@snafu: Das mit `pickle` ist keine gute Idee. Gleiche Tuple müssen nicht zur gleichen Bytefolge beim serialisieren führen:

Code: Alles auswählen

In [28]: pickle.dumps(A)
Out[28]: "(S'a b'\np0\ng0\nS'xy'\np1\ntp2\n."

In [29]: pickle.dumps(B)
Out[29]: "(S'a b'\np0\nS'a b'\np1\nS'xy'\np2\ntp3\n."

In [30]: A
Out[30]: ('a b', 'a b', 'xy')

In [31]: B
Out[31]: ('a b', 'a b', 'xy')

In [32]: A[0] is A[1]
Out[32]: True

In [33]: B[0] is B[1]
Out[33]: False

In [34]: A == B
Out[34]: True

[Goswin]

Den Tupeln eindeutige ganze Zahlen zuordnen hat funktioniert!

Die zahlenzuordnende Funktion muss ja nicht alle Zahlen erfassen, es genügt, dass jeder Zahl entweder ein oder kein Tupel zugeordnet wird. Bisher geht das zwar etwas schmerzlich in die Zeit (3_Stunden statt 10_Minuten), aber es ist machbar, und die Funktion welche eindeutige Zahlen zuordnet kann vermutlich auch etwas verschnellert werden.

Vielen Dank für eure Hinweise!

[snafu]

@Goswin
Magst du zeigen, was du da gebastelt hast? Der Performance-Verlust ist schon ziemlich krass. Vielleicht können wir dir helfen, die Funktion zu verbessern.

Falls alle Zeichen im ASCII-Bereich liegen, dann könnte man ja (unter Python 3) mal `int.from_bytes()` ausprobieren:

Code: Alles auswählen

>>> number = int.from_bytes(b'xyz', 'big')
>>> number
7895418
>>> number.to_bytes(10, 'big').strip(b'\x00')
b'xyz'

Das mit dem `.strip()` ist eher unschön. Aber man muss der `.to_bytes()`-Methode die Anzahl der Bytes mitgeben. Würde man die mit abspeichern, dann hätte man ja wieder den Platzverbrauch erhöht. Daher habe ich willkürlich 10 Bytes eingetragen und ziehe die überflüssigen Null-Bytes aus dem Ergebnis wieder heraus.

Und noch als zusätzlicher Hinweis: Allein schon die Verwendung von Bytes anstelle von (Unicode-)Strings verbraucht deutlich weniger Platz:

Code: Alles auswählen

>>> (7895418).__sizeof__()
16
>>> b'xyz'.__sizeof__()
20
>>> 'xyz'.__sizeof__()
28

[BlackJack]

@snafu: Vorsicht mit dem `strip()` denn nur auf *einer* Seite haben die Nullbytes keine Auswirkung auf das Ergebnis!

[snafu]

Das Ganze kann man natürlich noch lustig weitertreiben. Hier mal eine veranschaulichende Ausgabe aus der IPython-Shell:

Code: Alles auswählen

In [131]: %paste
def to_number(strings):
    bytestring = b'\x00'.join(s.encode('ascii') for s in strings)
    return int.from_bytes(bytestring, 'big')

def to_strings(number, total_bytes=30):
    bytestring = number.to_bytes(total_bytes, 'big').lstrip(b'\x00')
    return tuple(s.decode('ascii') for s in bytestring.split(b'\x00'))

## -- End pasted text --

In [132]: triple
Out[132]: ('ab', 'cdefg', 'ijk')

In [133]: number = to_number(triple)

In [134]: number
Out[134]: 30138522516454669591685720683

In [135]: to_strings(number)
Out[135]: ('ab', 'cdefg', 'ijk')

In [136]: number.__sizeof__()
Out[136]: 26

In [137]: triple.__sizeof__() + sum(s.__sizeof__() for s in triple)
Out[137]: 109

Man beachte die deutliche Platzersparnis: 26 Bytes vs. 109 Bytes für das im Eröffnungsbeitrag des OPs gezeigte Triple.

`to_strings()` könnte man grundsätzlich noch etwas schlauer schreiben, sodass die zu erwartenden Bytes z.B. durch stumpfes Probieren ermittelt werden. Oder aber man lässt `to_number()` zusätzlich die Anzahl der erzeugten Bytes ausgeben. Davon müsste sich der Anwender ja dann nur das Maximum merken, um die Rückumwandlung sinnvoll betreiben zu können.

[BlackJack]

@snafu: Na das kann man aber einfacher kleiner haben:

Code: Alles auswählen

In [4]: T
Out[4]: ('ab', 'cdefg', 'ijk')

In [5]: len(b'\0'.join(s.encode('ascii') for s in T))
Out[5]: 12

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.

[snafu]

@BlackJack
Inwieweit hilft `len()` einem zur Bestimmung des Speicherverbrauchs in Bytes? Wenn schon, müsste man doch wohl so messen:

Code: Alles auswählen

In [141]: b'\0'.join(s.encode('ascii') for s in triple).__sizeof__()
Out[141]: 29

Oder hab ich was übersehen?

Sind immer noch 3 Bytes mehr als in der `int`-basierten Lösung. Aber simpler ist es auf jeden Fall und hier womöglich schon ausreichend.

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