Es gibt eine beliebige Anzahl von verschiedenen vorzeichenlosen Ganzzahlwerten innerhalb eines bekannten Bereichs .
Die Anzahl der ganzzahligen Werte ist & lt; & lt; die Anzahl der ganzen Zahlen innerhalb des Bereichs.
Ich möchte eine Datenstruktur erstellen, die die folgenden Laufzeitkomplexitäten ermöglicht:
Speicherkomplexität ist nicht eingeschränkt. Eine astronomisch große Menge an Speicher ist jedoch nicht verfügbar ;-)
Hier ist ein Beispiel:
Ist eine solche Datenstruktur überhaupt möglich? (mit Hilfe von Tabellen usw.)?
Eine Annäherung, an die ich gedacht habe wäre:
Ordnen Sie die eingefügten Werte in Buckets ein. 0..31 = & gt; Bucket 0, 32..63 = & gt; Bucket 1, 64..95 = & gt; Eimer 2, 96..127 = & gt; Eimer 3, ...
Einfügen: Suchen Sie die Bucket-ID mithilfe einfacher Verschiebungsarithmetik und fügen Sie sie dann pro Bucket in ein Array ein
Finden: Finde die Bucket-ID von Start und Endpunkt unter Verwendung von Verschiebungsarithmetik. Sehen Sie sich alle Werte im ersten und letzten Bucket an und prüfen Sie, ob sie innerhalb des Bereichs oder außerhalb des Bereichs liegen. Fügen Sie dem Suchergebnis alle Werte in allen Zwischen-Buckets hinzu
Löschen: Finde die Bucket-ID mit Shifting. Tauschen Sie den zu löschenden Wert mit dem letzten Wert im Bucket und dekrementieren Sie dann die Anzahl für diesen Bucket.
Nachteil: Wenn es viele Abfragen gibt, die einen Bereich mit einem Bereich von weniger als 32 Werten abfragen, wird der gesamte Bucket jedes Mal durchsucht.
Downside 2: Wenn innerhalb des Bereichs leere Buckets vorhanden sind, werden diese auch während der Suchphase aufgerufen.
Theoretisch gesehen ist ein Baum van Emde Boas die beste Wahl, mit O (log log M) -Zeitoperationen, wobei M die Größe des Bereichs ist. Der Platzbedarf ist ziemlich groß, obwohl es effizientere Varianten gibt.
Tatsächlich ist der theoretische Stand der Technik in der Veröffentlichung On Range Reporting in One Dimension
Ich bin mir nicht sicher, ob die bestehenden unteren Schranken O (1) ausschließen, aber M wird nicht groß genug sein, um den Unterschied ausmachen zu können. Anstelle der vEB-Struktur würde ich einfach einen k-ary Trie mit k einer Potenz von zwei wie 32 oder 64 verwenden.
EDIT: Hier ist eine Möglichkeit, die Bereichssuche mit einem Trie durchzuführen.
Nehmen wir an, jedes Datum ist ein Bitmuster (einfach genug; so denkt die CPU darüber). Jeder Teilbaum besteht aus allen Knoten mit einem bestimmten Präfix. Zum Beispiel wird {0000, 0011, 0101, 1001} durch den folgenden vierwertigen Trie dargestellt, wobei X einen Nullzeiger bezeichnet.
Eine paar Optimierungen werden schnell offensichtlich. Erstens, wenn alle Bitmuster die gleiche Länge haben, müssen wir sie nicht an den Blättern speichern - sie können aus dem Abstiegspfad rekonstruiert werden. Alles, was wir brauchen, ist die Bitmap, die, wenn k die Anzahl der Bits in einem Maschinenwort ist, gut passt, wo der Zeiger von der vorherigen Ebene war.
%Vor%Um den Trie nach einem Bereich wie [0001, 1000] zu suchen, beginnen wir bei der Wurzel, bestimmen, welche Teilbäume den Bereich schneiden und auf ihnen rekrutieren. In diesem Beispiel sind die relevanten untergeordneten Elemente der Wurzel 00, 01 und 10. Die relevanten untergeordneten Elemente von 00 sind die Teilbäume, die die Präfixe 0001, 0010 und 0011 darstellen.
Für k fixed ist das Melden von einem k-artigen Trie O (log M + s), wobei M die Anzahl der Bitmuster und s die Anzahl der Treffer ist. Lassen Sie sich jedoch nicht täuschen - wenn k mittel ist, belegt jeder Knoten ein paar Cache-Zeilen, aber der Trie ist nicht sehr hoch, daher ist die Anzahl der Cache-Misses ziemlich klein.
Sie könnten Ihr Ziel (O (1), O (1) und O (k)) erreichen, wenn der Abfragevorgang den Wert mindestens eines vorhandenen Elements, das bereits im relevanten Bereich (der Untergrenze vielleicht). Können Sie eine Garantie geben, dass Sie bereits mindestens ein Mitglied des Sortiments kennen? Ich denke nicht. Ich werde erweitern, wenn Sie können.
Ich konzentriere mich jetzt auf das Problem wie angegeben. Jede Nummer in der Datenstruktur sollte Teil einer verknüpften Liste sein, so dass jede Nummer die nächsthöhere Nummer kennt, die sich in der Datenstruktur befindet. In C ++
%Vor% Offensichtlich hat der größte Wert in der Menge next_highest==NULL , aber sonst this->value < this->next_highest->value
Um hinzuzufügen, zu entfernen oder abzufragen, müssen wir in der Lage sein, die vorhandenen Number s zu finden, die in der Nähe eines bestimmten Lookup-Wertes liegen.
Einfügen und Löschen wäre O (log (N)), und Abfrage wäre O (log (N) + k). N ist die Anzahl der Werte, die sich derzeit in der Menge befinden, die, wie Sie sagen, viel kleiner als M ist (die Anzahl der möglichen Werte des relevanten Datentyps). Daher log (N) & lt; log (M). In der Praxis sollten aber auch andere Methoden wie Versuche und solche Datenstrukturen in Betracht gezogen werden.
Tags und Links algorithm optimization data-structures