Python effiziente Lookup-Struktur für dynamische Teilmengen?

Question

Ich versuche, Konstante-Zeit-Lookup für Werte im Zusammenhang mit den Teilmengen einer bestimmten Menge, wo Reihenfolge nicht garantiert ist.

Ich werde aktiv mit dem ursprünglichen Satz arbeiten, Entfernen/Hinzufügung von Elementen, und würde gerne assoziierte Werte der übrigen Elemente nachsehen, wie ich entlang gehe.

Zum Beispiel, wenn mein gegebenen Satz ist given = {1, 2, 3}, vielleicht würde ich ein dict bauen, der so aussieht ...

{ 
    frozenset([]): 'apple', 
    frozenset([1]): 'orange', 
    frozenset([2]): 'ice bear', 
    frozenset([3]): 'peach', 
    frozenset([1, 2]): 'grizzly', 
    frozenset([2, 3]): 'pear', 
    frozenset([1, 3]): 'panda', 
    frozenset([1, 2, 3]): 'banana', 
} 

nehme ich ein Element entfernen über given.remove(2) gesetzt gegeben und ließ mich mit {1, 3}, und ich wollte den zugehörigen Wert sehen. Ich müsste mein Set auf "eingefroren" setzen, um es im Diktat nachzuschlagen und den Wert 'panda' abzurufen. Folglich, wenn ich das Element über given.add(2) zurücksetze, das ursprüngliche {1, 2, 3} wieder herstellend, würde ich wieder gezwungen werden, zu gefrorenem set vor dem Abrufen banana vom dict.

Ich fühle mich wie gezwungen, zu einem Frozenset zu zwingen ist eine O (n) -Operation, die den Zweck eines O (1) Lookup vereitelt.

Gibt es eine Möglichkeit, diese Art der Suche in Python effizienter zu implementieren? Oder gibt es irgendwelche Datenstrukturen, die mir hier helfen können?

Ich bin auf Py2.7, aber wenn Py3 dafür besser ist, lass es mich wissen. Vielen Dank!

Answer 1

I wie mit fühlen zu einer frozenset zu zwingen ist O (n) Operation, die den Zweck eines O (1) lookup besiegt.

Es ist linear in der Größe von given, nicht in der Größe des dict. Zum Vergleich: Der Hashwert ist auch linear in der Größe given, sodass Sie selbst dann, wenn Sie kein fixedset erstellen mussten, immer noch die gleiche asymptotische Komplexität haben.

Wenn diese Kosten für Sie zu teuer sind, können Sie versuchen, Ihre eigene Wrapper-Klasse mit einer Hash-Funktion zu schreiben, die inkrementelle Updates zulässt und die normale Bedingung, dass Hash-Objekte nicht veränderbar sind, auf ihren Hash-Wert ändert. Ich persönlich hatte gute Ergebnisse mit einem Schema, das auf Zobrist hashing basiert, wo Elemente des Satzes zufällig erzeugte Hash-Codes zugewiesen werden, die für die Lebenszeit des Programms persistieren, und der Hash der Menge das XOR aller Element-Hashes ist. Wenn ein Element hinzugefügt oder entfernt wird, kann der Hash des Satzes durch XOR-Verknüpfung mit dem Hash des Elements aktualisiert werden.

Answer 2

Basiert auf der Antwort des Benutzers2357112. Ungeprüft, weil ich das Interesse verloren habe.

from random import Random 

class FastRehashableSet(set): 
    _initial_hash = 12345 

    def __init__(self, seq=()): 
     super(FastRehashableSet, self).__init__(seq) 
     self._hash = self._initial_hash 
     for x in seq: 
      self._hash_single_value(x) 

    def _hash_single_value(self, val): 
     # Introduce extra randomness since the intended elements are ints 
     # which just return themselves when hashed 
     self._hash ^= Random(hash(val)).randrange(4294967296) 

    def __hash__(self): 
     return self._hash 

    def add(self, elem): 
     super(FastRehashableSet, self).add(elem) 
     self._hash_single_value(elem) 

    def remove(self, elem): 
     super(FastRehashableSet, self).remove(elem) 
     self._hash_single_value(elem) 

    def discard(self, elem): 
     change = elem in self 
     super(FastRehashableSet, self).discard(elem) 
     if change: 
      self._hash_single_value(elem) 

    def pop(self): 
     val = super(FastRehashableSet, self).pop() 
     self._hash_single_value(val) 
     return val 

    def clear(self): 
     super(FastRehashableSet, self).clear() 
     self._hash = self._initial_hash 

    # You get the idea, I'm not doing these 

    def update(self): 
     raise NotImplemented 

    def intersection_update(self): 
     raise NotImplemented 

    def difference_update(self): 
     raise NotImplemented 

    def symmetric_difference_update(self): 
     raise NotImplemented 

Answer 3

Was ist die Codierung der indice der Wörter in einer Liste in binär aus der Liste des Elements:

words = ["apple","orange","ice bear","peach","grizzly","panda","pear","banana"] 

def get_indice(L): 
    return sum(2**(i-1) for i in L) 

# initial serie of elements 
serie = [1,2,3] 

# first computation of indice 
ind = get_indice([1,2,3]) 

print serie,words[ind] 

# remove the 2 
val = 2 
serie.remove(val) 
ind -= 2**(val-1) 

print serie,words[ind] 

# add the 2 
val = 2 
serie.append(val) 
serie = sorted(serie) 
ind += 2**(val-1) 

print serie,words[ind] 

Ausgang:

[1, 2, 3] banana 
[1, 3] panda 
[1, 2, 3] banana 

Beachten Sie, dass die ersten Rechenaufwand N Operationen Dabei ist N die Anzahl der Elemente in der Serie, die besser ist als die Anzahl der Elemente in Wörtern. Die folgenden Operationen zum Hinzufügen und Entfernen sind direkt und kosten O (1).

Da das Entfernen des Elements in der Serie einige nach https://wiki.python.org/moin/TimeComplexity kosten kann. Vielleicht ist es besser, get_indices trotzdem direkt aufzurufen.