Ich habe [dieses Rad] sicherlich erfunden, als ich die Vereinigung und die Schnittmenge und Diff zweier Sätze (die als Listen gespeichert waren) gleichzeitig berechnen wollten. Anfangscode (nicht der engste):
%Vor%Dann erkannte ich, dass ich 00, 01, 10 und 11 anstelle von -1, 1, 0, ... verwenden sollte. Ein Bit an der Position n zeigt also die Zugehörigkeit zu Menge n an.
Dies kann auf bis zu 32 Sets mit einem 32-Bit-Int oder auf eine beliebige Anzahl von Sets mit einem Bitarray oder einer Zeichenfolge verallgemeinert werden. Sie berechnen dieses Wörterbuch also einmal vor und verwenden dann sehr schnelle O (n) -Abfragen, um interessante Elemente zu extrahieren. Zum Beispiel bedeutet alle 1s Kreuzung aller Sätze. Alle 0 sind eine spezielle - wird nicht auftreten.
Jedenfalls soll das nicht mein eigenes Horn sein. Dies wurde sicherlich vorher erfunden und hat einen Namen. Wie heißt es? Wird dieser Ansatz irgendwo in Datenbanken verwendet?
Ja, manchmal wird es in Datenbanken verwendet, zum Beispiel PostgreSQL. Wie erwähnt Wikipedia:
Einige Datenbanksysteme, die dies nicht tun bieten persistente Bitmap-Indizes an Bitmaps intern, um die Abfrage zu beschleunigen wird bearbeitet. Zum Beispiel PostgreSQL Versionen 8.1 und später implementieren a "Bitmap Index Scan" -Optimierung zu beschleunigen beliebig komplex logisch Operationen zwischen verfügbaren Indizes auf einer einzigen Tabelle.
(aus Ссылка )
Die Verwendung einer N-Bit-Ganzzahl zur Darstellung von N-Booleschen Werten ist ein Spezialfall der Datenstruktur, die als perfekte Hash-Tabelle bekannt ist. Beachten Sie, dass Sie explizit dicts (die allgemeine Hash-Tabellen sind) in der Idee verwenden, die Sie dazu veranlasste, über Bitsets nachzudenken. Es handelt sich um eine Hash-Tabelle, weil Sie Hashwerte verwenden, um einen Wert zu finden, und es ist perfekt, weil Sie nie Kollisionen haben. Der Spezialfall ist, wie die Tabelle gepackt und gespeichert wird.
Formuliere die Hash-Funktion, die zeigt, wie sie sich von einem Array unterscheidet:
%Vor%Beachten Sie, dass bitset_hash (3) 0b1000 ist, was dem 4. Element (offset / index 3) entspricht, wenn C int und bitweise Operationen verwendet werden. (Wegen der Speicherimplementierungsdetails werden bitweise Operationen auch verwendet, um ein bestimmtes Element aus dem Hash zu manipulieren.)
Erweitern Sie den Ansatz, bitwise-und / or / -xor für Set-Operationen zu verwenden, common , und erfordert keinen speziellen Namen außer "set operations" oder, wenn Sie ein Schlagwort benötigen, "set theory".
Zum Schluss noch ein Beispiel für die Verwendung in einem Prime-Sieb (Ich habe diesen Code in Project Euler-Lösungen verwendet ):
%Vor%Es ist sehr üblich, eine Ganzzahl zu verwenden, um eine Menge kleiner Ganzzahlen darzustellen. Es wird oft als bitset oder bitvector bezeichnet. Hier verwenden Sie eine Ganzzahl, um "die Menge der Eingabesequenzen darzustellen, die diesen Wert enthalten".
Die Operation, die Sie gerade ausführen, erinnert mich an das Rückgängigmachen einer Multimap .
In Ihrem Fall ist die Eingabe eine Liste von Listen:
%Vor%Aber du könntest es stattdessen als eine Tüte mit geordneten Paaren betrachten, so:
%Vor%Sie erstellen einfach eine Tabelle mit den umgekehrten Paaren
%Vor%Das sieht so aus:
%Vor%und Sie repräsentieren diese Arrays von ganzen Zahlen unter Verwendung von Bitvektoren.
Die ursprüngliche Datenstruktur (die Liste der Listen) machte es leicht, über alle Werte für eine gegebene Liste zu iterieren. Die umgekehrte Datenstruktur (das Listenwörterbuch) erleichtert das Auffinden aller Listen mit einem bestimmten Wert.
Ist die Idee eines Bitfeldes , wonach Sie suchen? Jedes Bit Ihres ... Feldes (mangels eines besseren Wortes) repräsentiert eine Flagge. In diesem Fall ist Ihre Flagge Mitglied in Menge N.
Edit - Ich glaube, ich habe missverstanden, auf welche Idee Sie sich bezogen haben. Missachtung?
Tags und Links python algorithm language-agnostic set bit-fields