Beste Datenstruktur für die folgenden Einschränkungen?

Question

Hier sind einige Einschränkungen für eine Datenstruktur, die ich brauche. Es sieht so aus, als ob keine der üblichen Datenstrukturen (ich werde die, an die ich im Folgenden gedacht habe) so gut passen. Kann jemand einen vorschlagen, an den ich vielleicht nicht gedacht habe?

1. Ich muss Lookups durch unsigned Integer-Schlüssel durchführen können.
2. Die Elemente, die gespeichert werden sollen, sind benutzerdefinierte Strukturen.
3. Diese Indizes werden spärlich sein, normalerweise extrem. Reguläre Arrays sind out.
4. Die Häufigkeit jedes Index wird eine ungleichmäßige Verteilung haben, wobei kleine Indizes viel häufiger sind als große Indizes.
5. N wird normalerweise klein sein, wahrscheinlich nicht größer als 5 oder 10, aber ich möchte mich nicht zu sehr darauf verlassen, weil es manchmal viel größer sein könnte.
6. Der konstante Begriff ist sehr wichtig. Ich brauche wirklich schnelle Lookups, wenn N klein ist. Ich habe bereits generische Hashtabellen ausprobiert und, empirisch, sind sie zu langsam, , selbst wenn N = 1, was keine Kollisionen bedeutet, wahrscheinlich wegen der Menge an involvierter Indirektion. Ich wäre jedoch offen für Vorschläge zu speziellen Hash-Tabellen, die andere erwähnte Einschränkungen nutzen.
7. Insertionszeit ist nicht wichtig, solange die Retrieval-Zeit ist schnell. Sogar die Einsetzzeit von O (N) ist gut genug.
8. Platzeffizienz ist nicht besonders wichtig, obwohl es wichtig genug ist, nicht nur normale Arrays zu verwenden.

Answer 1

Wenn N klein ein einfaches Array oder einzelne verknüpfte Liste mit Schlüsseln + Wert als Nutzlast ist sehr effizient. Auch wenn es nicht das Beste ist, wenn N größer wird.

Sie erhalten O (N) Lookup-Zeit, was bedeutet, dass Lookups k * N Zeit nehmen. Ein O (1) -Lookup benötigt eine konstante K Zeit. So erhalten Sie besser Leistung mit O (N) für N < K/k. Hier k ist sehr klein, so können Sie zu interessanten Werten von N gelangen. Denken Sie daran, dass die Big O-Notation nur Verhalten für großeN s beschreibt, nicht was Sie wollen. Für kleine Tische

void *lookup(int key_to_lookup) 
{ 
    int n = 0; 
    while (table_key[n] != key_to_lookup) 
    n++; 
    return table_data[n]; 
} 

kann schwer zu schlagen sein.

Benchmark Ihre Hash-Tabellen, Balanced Tree und einfache Array/Linked List und sehen Sie, bei welchen Werten von N sie beginnen, besser zu sein. Dann wirst du wissen, was besser für dich ist.

Fast hätte ich vergessen: Behalten Sie die häufig verwendeten Schlüssel am Anfang Ihres Arrays. Angesichts Ihrer Beschreibung bedeutet das, sortiere es.

Answer 2

Sie könnten versuchen, das Beste aus beiden Welten zu kombinieren: Wenn der Schlüssel klein ist, legen Sie ihn in eine Array-artige Datenstruktur, die nicht größer als ein vordefinierter maximaler Schlüssel wird. Wenn der Schlüssel groß ist, lege ihn in eine Hashtabelle.

Answer 3

ist ein Hash-Lookup-Tabelle etwa so schnell wie es sein kann:

Das einzige, was sie von einem regulären Array-Lookup unterscheidet, ist die Berechnung des Hash und (wenn Ihr Hashfunktion gut genug ist, oder Sie verbringen Genug Zeit, um während der Einfügung eine optimale Hash-Funktion zu erzeugen, die Ihre Eingabe O (N) nehmen würde), dann im Wesentlichen eine Array-Suche.

Im Wesentlichen, da es passieren kann (es sei denn, Sie verwenden eine optimale Hash-Funktion), müssen Sie eine sehr kleine verkettete Liste erneut anzeigen oder verfolgen.

Da die meisten Hash-Funktionen für Hash-Tabellen k * c_1% c_2 sind, besteht der Unterschied zu einer Array-Suche in einer eher spärlichen und/oder optimalen Hash-Tabelle aus einer Indirektion, zwei Multiplikationen, einer Subtraktion und einer Division (eine effiziente Modulo-Implementierung unter Verwendung der CPU-Fähigkeiten könnte dies durch eine Subtraktion und eine Multiplikation reduzieren und die Array-Suche.

Es wird einfach nicht schneller als das.

Answer 4

Ich würde eine Hashtabelle betrachten, die Hash-Kollisionen mit einem selbstbalancierenden binären Baum statt einfacher Verkettung behandelt. Sie sollten in der Lage sein, O (1) amortisierten Lookup über alle Schlüssel und Worst-Case-Lookup von O (logN) zu bekommen. Da Ihre Schlüsselverteilung verzerrt ist, ist es wahrscheinlich, dass Sie Kollisionen mit niedrigen Werten des Indexes haben, und die Baumsuche wird sich dort wirklich auszahlen.

Answer 5

Dieser Rat geht davon aus modernen CPUs mit:

• schnell Caches
• viel langsamer Speicherlatenz im Vergleich zu der Taktfrequenz.
• vernünftige Verzweigungsvorhersage (wirklich erstaunlich, in den neuesten Desktop/Server-Prozessoren)

ich, dass Hybridstrukturen kann auch Trumpf eine einzelne Struktur vorschlagen würde.

Verwendung einfacher Array-basierter Schlüsselwertpaare mit O (N) -Zugriff wie erwähnt, aber sehr geringen konstanten Faktoren und extrem gutem Caching-Verhalten. Diese anfängliche Struktur sollte klein sein (wahrscheinlich nicht größer als 16 und möglicherweise 8 Werte), um zu vermeiden, dass über eine einzelne Cache-Zeile hinausgegangen wird. Leider ist ein Parameter, den Sie selbst einstellen müssen.

Sobald Sie über diese Zahl hinausgehen, würden Sie auf eine Struktur mit besserem O (N) Verhalten zurückgreifen, würde ich empfehlen, eine anständige Hash-Tabelle zu beginnen, da dies wahrscheinlich von 16 - mehrere tausend vernünftig sein wird Bereich und wenn Sie dazu neigen, ähnliche Werte häufiger nachzuschlagen, werden Sie eher in den schnelleren Caches bleiben.

Wenn Sie auch entfernen sowie einfügen müssen Sie darauf achten, nicht zwischen den beiden Zuständen hin- und herzuwechseln. Wenn man die Zahl auf die Hälfte reduzieren möchte, um die "sekundäre" Struktur aufzurüsten, sollte dies verhindert werden, aber bedenken Sie, dass jegliches deterministische Crossover-Verhalten für Eingaben im schlechtesten Fall anfällig ist.
Dies kann ein Problem sein, wenn Sie versuchen, sich gegen schädliche Eingabedaten zu verteidigen. Wenn dies der Fall ist, schützt ein zufälliger Faktor in der Entscheidung dagegen. Es ist wahrscheinlich, dass dir das egal ist, da du es nicht erwähnt hast.

Wenn Sie möchten, können Sie versuchen, das erste primäre Array zu sortieren, indem Sie eine binäre Suche mit O (log (N)) zulassen, jedoch auf Kosten eines komplexeren Suchcodes.Ich würde denken, dass der einfache Array-Walk es tatsächlich schlagen wird, aber Sie würden dies für unterschiedliche Werte von N benchmarken, könnte es Ihnen erlauben, mit einem primären Array länger zu bleiben, aber ich würde denken, dass dies eine Funktion der Größe ist der Cache-Zeilengröße mehr als das O (N) -Verhalten.

Weitere Optionen sind:

• alle Schlüsselwerte < 256 unterschiedlich behandeln und sie in einem Byte -> struct Paar von Arrays spart Platz auf den Tasten (und möglicherweise die Speicherung so dass sie dort bleiben, wenn Sie zu wechseln die sekundäre Struktur) dies kann schlecht funktionieren aufgrund der Notwendigkeit, das Array im laufenden Betrieb auf die native Wortlänge zu entpacken.
• Verwenden einer Trie-ähnlichen Struktur, die jeweils ein Byte zum Schlüssel macht. Ich bezweifle die Komplexität dieser wird es in der Praxis gut machen

Noch einmal werde ich den sehr guten Rat von kmkaplan wiederholen. Benchmark es gründlich Microbenchmarks zu vermeiden. Bei dieser Art von Analyse können die reellen Zahlen überraschend anders sein als die Theorie ...

Answer 6

Sie könnten versuchen, einen offen adressierten Hash mit quadratischer Sondierung anstelle einer separaten Verkettung zu verwenden, wenn Ihr N normalerweise klein ist. Sie müssten beispielsweise von einer anfänglichen Größe von 32 zu größeren Breiten neu zuweisen, wenn Sie den seltenen N-Fall erhalten, der ihn überfüllt. Lineares Sondieren oder Kuckuckshashing wird Ihnen eine gute Leistung bringen, wenn Sie die gesamte Struktur in ein paar Cachezeilen einfügen können.

Ehrlich gesagt bin ich überrascht, dass sogar eine Standard-Hash-Tabelle Sie so miserable Leistung gibt. Vielleicht könnten Sie in das Profil hineinschauen, um zu sehen, was es so langsam macht - wenn es die Hash-Funktion selbst ist, verwenden Sie ein einfaches wie ein Zweierpotenz-Modul (zB Schlüssel & (N-1) wo N bekannt ist) sei 2^x), die sowieso Distributionen um 0 bevorzugen. Wenn es der Dcache-Fehler ist, die separate Kette zu verfolgen, schreiben Sie eine Implementierung, die die ersten vier Elemente in jedem Bucket im Bucket selbst speichert, so dass Sie diese zumindest schnell erhalten. Wie langsam ist N = 1?

Ich würde Zeiger auf Strukturen und nicht die Strukturen selbst in den Bucket-Ketten speichern: Wenn die Strukturen groß sind, dann wird das Durchlaufen einer Kette von ihnen viele Cache-Misses haben. Auf der anderen Seite können Sie etwa 16 Schlüssel-/Zeigerpaare in einer einzigen Cache-Zeile anpassen und nur für einen Fehlschlag bezahlen, wenn Sie das richtige Element finden.

Answer 7

Die einzige Erklärung, die ich für das beschriebene Problem sehe, ist, dass die Hash-Funktion viel zu komplex ist. Ich würde zu einem zweistufigen Ansatz geneigt sein:

1) Für kleine Schlüssel, ein einfaches Array von Zeigern. Kein Hash oder irgendetwas.

2) Für Schlüssel, die größer ist als die Größe der Tabelle sind Sie vergeben:

Wie wäre es eine sehr einfache Hash-Funktion, die die gruppierten Tasten verteilt:

Die links 5 Bits (Ich nehme 32-Bit-Ganzzahlen an.Wenn es 64-Bit ist, dann addiere ein weiteres Bit.) Sind die Anzahl der Bits, die tatsächlich Daten enthalten, der Rest ist einfach die Summe (verwerfen trägt) des ursprünglichen Schlüssels in Stücke von jedoch geschnitten viele Bits, die Sie für diesen Zweck verwenden und zusammenfügen.

Beachten Sie, dass die Anzahl der signifikanten Bits teilweise vorberechnet werden kann - erstellen Sie eine 64k-Tabelle mit hohen Bitwerten. Wenn das Wort höherer Ordnung ungleich Null ist, verwenden Sie es als Index für die Tabelle und addieren Sie 16, andernfalls verwenden Sie das Wort niedriger Ordnung als Index. Für 64-Bit-Integer müssen Sie natürlich 4 statt 2 Schritte verwenden.

Answer 8

Sie könnten Judy Arrays betrachten:

Judy ist eine C-Bibliothek, die eine Kerntechnologie state-of-the-Art liefert, die eine spärliche dynamische Array implementiert. Judy-Arrays werden einfach mit einem Nullzeiger deklariert. Ein Judy Array verbraucht Speicher nur dann, wenn es ausgefüllt ist, noch kann wachsen Vorteil aller verfügbaren Speicher zu nehmen, wenn gewünscht ... Judy können viele gemeinsame Daten Strukturen wie Arrays, spärlich Arrays, Hash-Tabellen ersetzen, B-Bäume, binäre Bäume, lineare Listen, Skipisten, andere Sortier- und Suchalgorithmen und Zählfunktionen.

Answer 9

Hier ist eine allgemeine Idee für eine Hash-Funktion. Sie sagten, dass Einsätze teuer sein können.

Hash der Schlüssel, die eine ganze Zahl ist, mit einem einfachen Modul, wobei jede Instanz eines

Hashtable gespeichert

wenn ein Einsatz eine Kollision verursachen würde, erneut optimieren Ihre Hashtable, indem die Anzahl der Kollisionen Rechen das würde für jeden Modul in einem vernünftigen Bereich passieren, sagen wir die Anzahl der Elemente in Ihrer Karte durch ein konstantes Vielfaches davon.

offensichtlich werden Ihre Inserts tatsächlich ziemlich teuer, um O (n^2) wenn Sie Zuweisungen minimieren, aber Sie werden wahrscheinlich in der Lage sein, Nachschlagevorgänge mit einer einzigen Ganzzahldivision und einer einzigen Zeigerindirection zu erreichen, und Sie wissen, weil Sie haben es zum Zeitpunkt des Einfügens berechnet, was die Suche nach dem schlimmsten Fall sein wird.

Answer 10

Ich würde hier eine Skip list empfehlen. Das Paket java.util.concurrent hat eine gute Implementierung, wenn Sie daran interessiert sind.