Auf Doubletten prüfen

[mkesper]

Hallo,

Ich lese User aus einer Datenbank (Active Directory). Dabei können Doubletten auftreten. Daher merke ich mir die User in einem Set. Das frisst aber pro User ca. 10kB Hauptspeicher. (Zuerst hatte ich ein Dictionary verwendet und dachte, das Set würde weniger Ressourcen beanspruchen.) Gibt es eine effizientere Möglichkeit, auf Doubletten zu prüfen?

[lutz.horn]

Gibt es irgendein Merkmal, das einen User eindeutig identifiziert? Um Dubletten zu finden, musst Du ja vermutlich nicht die vollständigen User speichern.

Wie werden übrigens zwei User verglichen?

[Defnull]

a) Du benutzt Mechanismen von AD für die Aussortierung von Doubletten (da weis ich allerdings nicht, wie).

b) Du speicherst nicht den kompletten Benutzer-Datensatz, sondern nur die ID, den Namen oder etwas anderes Vergleichbares und holst die echten Daten erst später.

c) Du holst alle Daten, sortierst sie und wirfst dann alle doppelten raus:

Code: Alles auswählen

# Ungetestet
user = sorted([...])
for i in reversed(range(len(user)-1)):
  if user[i] == user[i+1]:
    del user[i+1]

[mkesper]

So sieht mein Code aus:

Code: Alles auswählen

user_table = set()
...
    elif user.sAMAccountName in user_table:
        return False
    else:
        user_table.add(user.sAMAccountName)
        ...

user.sAMAccountName ist dabei der eindeutige Anmeldename.

Eine Liste habe ich nicht erzeugt, da ich denke, dass das Nachschlagen in einem Dict/Set schneller abläuft als Sortieren einer Liste. Außerdem schleppe ich dann die Doubles bis zum Ende des Programms mit.

[BlackJack]

Um wieviele Benutzer geht es denn hier, dass das ein Problem wird? Bei 10.000 Benutzern reden wir nicht einmal von 100 MiB.

[jerch]

Selbst mit einem set mit 100000 Strings mit random-Strings der Länge 100 komme ich nur auf 10MB für das pickling und ~20MB für den Interpreter. Sicher, daß 'user.sAMAccountName' da nicht noch mehr mitschleppt und eben nicht nur der String des vollständigen Anmeldenamens ist? Ansonsten gibt es doch wahrscheinlich eine Art Id-Kennung, die noch kürzer sein dürfte.

auf die Schnelle getestet mit:

Code: Alles auswählen

set([''.join(random.choice(string.letters) for i in xrange(100)) for i in xrange(100000)])

Evtl. ist es auch sinnvoll, zuerst alle Nutzer zum Set hinzuzufügen und dann Deine Aktionen an allen Elementen vorzunehmen, spart Dir das look up in user_table unter elif.

[ms4py]

Vermutlich ist es die schnellste Lösung, zuerst eine Liste zu erzeugen und diese dann zu einem set zu konvertieren.
Ich denke, dass dabei ein ähnlicher Algorithmus wie der von devnull angewandt wird, nur dass dieser noch optimiert und in C geschrieben ist.
Dieser würde dann in linearer Zeit ablaufen. Diese Vermutung müsste allerdings noch genauer untersucht werden (z.B. direkt im Quellcode von set).

Aus deinem Code-Auschnitt lässt sich vermuten, dass bei dir eine n * m Komplexität vorliegt (für jeden Benutzer überprüfen, ob er schon im set ist). btw: Bei diesem Ansatz ist der Einsatz von set eh sinnlos, da kann man auch eine Liste nehmen.

Vielleicht habe ich in deinen kurzen Codeausschnitt auch etwas falsches hineininterpretiert

[mkesper]

Aus deinem Code-Auschnitt lässt sich vermuten, dass bei dir eine n * m Komplexität vorliegt (für jeden Benutzer überprüfen, ob er schon im set ist). btw: Bei diesem Ansatz ist der Einsatz von set eh sinnlos, da kann man auch eine Liste nehmen.

Eben nicht, die Liste müsste ich ja sequentiell durchsuchen, das Set arbeitet wie ein Dictionary.

Sicher, daß 'user.sAMAccountName' da nicht noch mehr mitschleppt und eben nicht nur der String des vollständigen Anmeldenamens ist? Ansonsten gibt es doch wahrscheinlich eine Art Id-Kennung, die noch kürzer sein dürfte.

Das war eine gute Idee, ich prüfe es mal.

[Defnull]

Vermutlich ist es die schnellste Lösung, zuerst eine Liste zu erzeugen und diese dann zu einem set zu konvertieren.
Ich denke, dass dabei ein ähnlicher Algorithmus wie der von devnull angewandt wird, nur dass dieser noch optimiert und in C geschrieben ist.
Dieser würde dann in linearer Zeit ablaufen. Diese Vermutung müsste allerdings noch genauer untersucht werden (z.B. direkt im Quellcode von set).

Ich vermute eher, das ein "set(list(...))" nichts weiter tut als ein sequenzielles "set.add(item) for item in list", weil das vorherige Sortieren der Liste viel zu lange dauern würde. set.add() hat, genau wie set.__contains__() eine Laufzeit von O(1) bei leeren und O(log n) bei vollen sets. Das ist ja das tolle an HashTables.

[ms4py]

Ich vermute eher, das ein "set(list(...))" nichts weiter tut als ein sequenzielles "set.add(item) for item in list", weil das vorherige Sortieren der Liste viel zu lange dauern würde. set.add() hat, genau wie set.__contains__() eine Laufzeit von O(1) bei leeren und O(log n) bei vollen sets. Das ist ja das tolle an HashTables.

Gut zu wissen, dass das gehashte Objekte in einem set sind...
Aber bei einer Hashtable ohne Kollisionen hat ein Lookup immer O(1). Kommt halt auch darauf an, wie Python diese organisiert. Hast du da Ahnung?

[lunar]

Aber bei einer Hashtable ohne Kollisionen hat ein Lookup immer O(1).

Auch mit Kollisionen ist die amortisierte Laufzeit konstant.

[Defnull]

Aber bei einer Hashtable ohne Kollisionen hat ein Lookup immer O(1).

Auch mit Kollisionen ist die amortisierte Laufzeit konstant.

Die Aussage finde ich irreführend. HastTabellen müssen Kollisionen irgendwie abfangen. Das tun sie meistens indem hinter jedem Hash-Wert ein Suchbaum steckt, in dem alle Werte mit identischem Hash einsortiert werden oder indem sie sich selbst verketten. Im Fall einer Kollision haben solche HastTabellen also keine lineare, sondern eine logarithmische Laufzeit.

Ich gehe eigentlich davon aus, das Python sets ähnlich aufgebaut sind. Aaaaber das weicht langsam vom Thema ab

[lunar]

Du kannst das gerne irreführend finden, so stehts aber nun mal in der Literatur: Eine verkettete Hashtabelle hat – wenn die Hashfunktion gut ist – eine konstante mittlere Laufzeit.

Vor allem aber ist selbst mit Kollisionen die Laufzeit allenfalls dann logarithmisch, wenn alle Elemente kollidieren und Kollisionen über einen balancierten Suchbaum aufgelöst werden. Python aber verwendet meines Wissens verkettete Listen, in diesem Fall wäre die Laufzeit also linear. Das gilt aber nur für den schlechtesten Fall, der bei einer vernünftigen Hashfunktion faktisch nie eintritt.

Wenn nur einzelne Kollisionen vorliegen (was eigentlich immer der Fall ist), dann ist die Laufzeit trotzdem weder linear noch logarithmisch an der Anzahl aller Elemente gemessen.