Gibt es einen Namen für diese Sammlung von Datenstrukturen sortierter Arrays?

Gibt es einen Namen für die folgende Datenstruktur? Gibt es Papiere und Zitate?Gibt es einen Namen für diese Sammlung von Datenstrukturen sortierter Arrays?

Ein Weg to implement ein effizienter set abstrakter Datentyp ist eine Sammlung von sortierten Arrays haben, wo jedes Array eine einzigartige Power-of-2-Größe hat.

Zum Beispiel kann eine Gruppe von 13 Elementen {1, 2, ..., 13} durch diese Sammlung sortierter Felder dargestellt werden: {[5], [2, 3, 9, 13], [1 , 4, 6, 7, 8, 10, 11, 12]}.

Im Allgemeinen haben die Arrays in der Sammlung Größen, die den 1 Bits in der binären Darstellung der Größe des Satzes entsprechen. Die Datenstruktur ist effizient, da die Insertion kann in fortgeführten O (1) Zeit durchgeführt werden, und die Suche kann in O ((log n)) Zeit (die als lineare Suche ist besser) durchgeführt werden. Außerdem verwendet er nur O Raum Overhead für Zeiger (n log), im Gegensatz zu ausgewogenen Binärbäumen und B-Bäume, die O (n) zusätzlichen Platz für Zeiger verwenden. Somit wird fast der gesamte Raum für Nutzlastdaten verwendet.

Ich habe Wikipedia list of data structures angesehen, aber fand keine Übereinstimmung. Es ist wahr, dass das Buch Einführung in Algorithmen ("CLRS") diese Datenstruktur als ein Hausaufgabe-Problem in der Sektion "Amortized Analysis" beschreibt, aber weil es eher eine Frage als ein Beispiel ist, sagt das Buch nicht viel darüber aus.

Quelle

2013-06-07 Nayuki

Ich konnte nur an die Bezeichnung "Datenstrukturen" denken. Ich würde mich über Vorschläge für relevante Tags freuen! – Nayuki

Diese bestehenden Fragen sind über die gleiche Datenstruktur, aber sie fragen nach Implementierung und Erklärung: http://stackoverflow.com/questions/2602110/, http://stackoverflow.com/questions/4701433/. Ich weiß, wie die Datenstruktur funktioniert, deshalb suche ich speziell nach veröffentlichter Literatur darüber. – Nayuki

Eine ähnliche Idee stammt zumindest aus Jean Vuillemins original publication on binomial heaps in der April 1978-Ausgabe von CACM. Ich würde erwarten, dass das Papier, das diese Datenstruktur eingeführt hat, von Vuillemin zitiert oder zitiert wird, aber keines der Papiere auf den Listen "Referenzen" und "zitiert nach" sieht vielversprechend aus.

Wenn ich Sie wäre, würde ich cstheory fragen und dann an CLRS schreiben, aber angesichts der suboptimalen Grenzen und des Fehlens der Löschung, erwarte ich nichts, bis die succinct data structure Gemeinschaft Interesse an einem bestimmten Punkt hat.

Gibt es etwas Bestimmtes, das Sie wissen wollten?

Quelle

2013-06-07 17:32:43

Danke für die Referenzierung von SE: Theorie und prägnante DS, die relevant aber neu für mich sind. Ich habe die Frage gestellt, weil ich für diese Datenstruktur schreiben möchte, was ich tun kann. Aber ich möchte ihm einen bereits akzeptierten Namen geben und auch auf existierende Literatur aufbauen, anstatt mich nur auf meine eigenen Ideen zu verlassen. – Nayuki

Es ist wahr, dass die Suchzeit suboptimal ist, aber ich nutzte die Prägnanz in einer meiner Anwendungen, weil sie Millionen von bereits besuchten Spielständen im Gedächtnis behalten musste. Wie beim Löschen sagt CLRS "Diskutieren Sie, wie Sie DELETE implementieren.", Aber bei leichtem Denken kann ich mir keinen offensichtlichen Weg vorstellen, es innerhalb der amortisierten O (n log n) -Zeit zu implementieren ... – Nayuki

@NayukiMinase Come to Denken Sie daran, die Löschung sollte auch am O (1) amortisiert werden, über das übliche Hilfsmittel, Bitmaps zu haben, die nicht gelöschte Elemente anzeigen und ein halbleeres Array nach unten zusammenführen. –

Gibt es einen Namen für diese Sammlung von Datenstrukturen sortierter Arrays?

Antwort

Verwandte Themen