* Mit allem meine ich die relativ schnelle Ausführung von Operationen an einem einzelnen Element eines Arrays.Die Datenstrukturen, die die Liste implementieren, sind vollständig. Jeder hat seine eigenen Vor- und Nachteile. In der Java-Welt können Sie beispielsweise - abhängig von den erforderlichen Operationen - Folgendes verwenden:- add (obj), get (obj), set (index, obj): eine Grundmenge fast aller Listen, z. B. ArrayList.
- add (index, obj): baumartige Strukturen, z. B. TreeList aus Apache Common-Collections.
- entfernen (Index): wie oben.
- enthält (obj), indexOf (obj): Sie können eine Reihe von ArrayList und HashMap verwenden.
- remove (obj): ... Ich finde es schwierig zu antworten. In einigen Fällen können Sie mit einem LinkedHashSet auskommen. Es wird in Gegenwart der beiden vorhergehenden Punkte trivial gelöst, aber welche Strukturen können beide schnell?
Als ich eine Struktur mit Quick Add (Obj), Get (Index), Remove (Index) und IndexOf (Obj) benötigte, gab Google keine Antwort. Ich habe keine Codebeispiele oder Beschreibungen solcher Strukturen gefunden. Vielleicht habe ich dort nicht gesucht, ich musste es selbst erfinden. Aber wenn jemand den Link in den Kommentaren fallen lässt, werde ich es sehr schätzen.Vielleicht hat jemand erkannt, dass Sie eine TreeList verwenden können, mit der Sie schnell Elemente in der Mitte der Liste einfügen / entfernen und eine HashMap aus dem Objekt zum Index in der TreeList hinzufügen können, um indexOf (obj) schnell auszuführen. Und es wird eine einfache, elegante, aber falsche Entscheidung sein. Schließlich müssen beim Hinzufügen zur Mitte oder Entfernen aus der Mitte die Indizes im Durchschnitt für die Hälfte der Elemente neu berechnet werden. Dies verschlechtert die Leistung auf O (n).Als nächstes werde ich über eine Datenstruktur sprechen, die all das oben Genannte kann. Womit eine Operation an einem Element in O (log (n)) Zeit ausgeführt wird. Nun, fast - denn der Logarithmus wird in dem Fall ausgeführt, in dem alle Objekte in der Liste unterschiedlich sind. Wenn die Liste dieselben Objekte enthält, kann die Leistung auf O (log (n) ^ 2) gesenkt werden.Ich werde Sie sofort warnen, dass ich den Code hier nicht malen werde. Es kann für den Artikel ziemlich kompliziert sein. Aber es ist in Java geschrieben. Basierend auf der TreeList-Klasse aus Apache Common-Collections. Pull-Anfrage existiert bereits, aber zum Zeitpunkt des Schreibens ist der Artikel noch nicht gegossen.Ich werde auch keine bekannten Algorithmen beschreiben. Zum Beispiel Baumausgleichsalgorithmen. Für die meisten mag es ausreichend sein, die Tatsache als selbstverständlich zu betrachten, dass der Baum im Gleichgewicht gehalten werden kann. Dies hat keinen Einfluss auf das Verständnis der allgemeinen Idee. Wer mehr wissen will, findet leicht Informationen. Aber ich werde Ihnen ganz kurz einige grundlegende Dinge erzählen, denn ohne die Kenntnis der Grundlagen können viele Schlüsselelemente nicht verstanden werden.Links werden am Ende sein.Warum ist es notwendig?
Tatsächlich ist es nicht so einfach, Situationen zu finden, in denen alles direkt von der Liste benötigt wird. Es ist unwahrscheinlich, dass dies eine super notwendige Struktur ist, sonst würde jeder davon wissen. Es können jedoch einige Beispiele angeführt werden, bei denen eine solche Liste nützlich sein könnte.Ich erkenne, dass viele der Beispiele weit hergeholt sind. Alles oder fast alles kann auf andere Weise gelöst werden.Caching und Komprimierung
Meine anfängliche Aufgabe, aufgrund derer ich anfing, das Problem zu untersuchen. Spielte mit der Komprimierung bestimmter Daten und benötigte eine Liste für den Objektcache.Die Idee ist folgende: Wenn wir ein anderes Objekt verarbeiten, suchen wir es in der Liste. Wenn nicht gefunden, speichern Sie das Objekt und fügen Sie es oben in die Liste ein. Wenn gefunden, nehmen wir seinen Index in die Liste und speichern anstelle des Objekts nur seinen Index. Danach verschieben wir das Objekt an den Anfang der Liste. Daher erhalten auftretende Objekte häufig kleine Indizes, und nur einmal vorkommende Objekte werden schließlich an das Ende der Liste verschoben und gelöscht.Wende
Wenn anstelle der üblichen FIFO-Warteschlange für einige Aufgaben eine ähnliche Struktur verwendet wird, können die folgenden Vorgänge ausgeführt werden:- Beantworten Sie die Frage: Wie viele Aufgaben befinden sich vor dieser Aufgabe in der Warteschlange?
- Entfernen Sie Aufgaben aus der Warteschlange.
Es ist wie in einem Supermarkt. Wenn Sie wegen eines Schokoriegels gekommen sind, aber sehen, dass sich die Linie langsam bewegt, wird der Schokoriegel vielleicht nicht so dringend benötigt? :) :)Highscore-Tabelle
Angenommen, wir möchten die Zeit speichern, in der Spieler ein Level in einem Spiel abschließen. Es gibt viele Spieler, die alle gegeneinander antreten und versuchen, die Mindestzeit anzuzeigen. Spielerdaten können in ein Array gestellt und nach Zeit sortiert werden. Mit dieser Struktur können Sie:- Verschieben Sie Spieler höher in die Liste, wenn sie bessere Ergebnisse als zuvor zeigen.
- Entfernen Sie Spieler von der Liste, z. B. im Falle eines Betrugsverbots.
- Zeigen Sie jedem Spieler, wo er ist.
- Zeigen Sie die Tabelle der Datensätze Seite für Seite an.
- Zeigen Sie eine spärliche Tabelle an Stellen an, z. B. Zeit 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 Stellen.
Datenstruktur
Die Struktur basiert auf einem Baum mit einem impliziten Schlüssel. Auf diesem Ansatz basiert beispielsweise TreeList in Apache Common-Collections. Um fortzufahren, müssen Sie verstehen, wie diese Struktur funktioniert.Impliziter Schlüsselbaum
Ein Baum besteht aus Knoten (Knoten). Jeder Knoten enthält eine Verknüpfung zu einem Objekt, das im Knoten gespeichert ist, und zwei Verknüpfungen zu anderen Knoten: links und rechts. Der oberste Knoten wird als Wurzelknoten bezeichnet. Im einfachsten Fall sieht der Knoten ungefähr so aus:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
Im klassischen Binärbaum für jeden Knoten im linken Teilbaum sind alle Objekte kleiner als im aktuellen Knoten und im rechten - groß. Zum Beispiel: [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
Für unseren Zweck ist ein solcher Baum jedoch nicht geeignet. Wir müssen keine sortierten Objekte speichern, aber wir müssen wie in einem Array nach Index darauf zugreifen können.Wie kann ich ein Array in einen Baum einfügen? Wählen wir ein Element mit dem Index i aus der Mitte des Arrays aus. Platzieren Sie das i-te Element aus dem Array im Stammknoten. 2 Teilbäume verlassen den Wurzelknoten. Im linken Teilbaum setzen wir die Hälfte des Arrays mit Index <i und im rechten Teil mit Index> i. Wie kann man das machen? Auf die gleiche Weise: Wir wählen ein Element aus der Mitte in einem Subarray aus, setzen dieses Element in einen Knoten und erhalten zwei weitere kleinere Subarrays. Und so lange, bis wir alle Elemente des Arrays in die Knoten des Baums eingefügt haben.Ein Array mit den Elementen ["q", "w", "e", "r", "t", "y", "u"] könnte beispielsweise folgendermaßen aussehen: [el: r, size: 7]
/ : \
/ : \
[el: w, size: 3] : [el: y, size: 3]
/ : \ : / : \
/ : \ : / : \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Das mittlere Element im Array "r" setzen wir in den Wurzelknoten. Zwei Subarrays ["q", "w", "e"] und ["t", "y", "u"] werden in den linken und rechten Teilbäumen platziert. Dazu werden die zentralen Elemente aus den Subarrays ausgewählt, in unserem Fall "w" und "y", und sie fallen in die Knoten der nächsten Ebene. Und so weiter.In unserem Fall ist der Baum ausgeglichen, die Tiefe aller Teilbäume ist gleich. Das muss aber nicht so sein.In der obigen Abbildung enthält jeder Knoten neben dem Element und den Links zum linken und rechten Knoten die Anzahl der Elemente des gesamten Teilbaums. Diese Informationen müssen korrekt aktualisiert werden, wenn sich der Baum ändert.Mal sehen, wie man zum Beispiel ein Element mit index = 4 in einem solchen Baum findet.Wir starten den Crawl vom Wurzelknoten (Wurzel, in unserem Fall mit dem Element "r"). Wir haben 3 Möglichkeiten: Wir sind bereits am rechten Knoten, der rechte Knoten links, der rechte Knoten rechts. Um zu verstehen, wo nach dem gewünschten Element gesucht werden muss, müssen Sie die Größe des linken Teilbaums (in unserem Fall left.size = 3) und des aktuellen Index (in unserem Fall 4) vergleichen. Wenn diese beiden Zahlen gleich sind, haben wir den erforderlichen Knoten und das gewünschte Element darin gefunden. Wenn der linke Teilbaum größer ist, wird der erforderliche Knoten im linken Teilbaum angezeigt. Wenn es weniger ist, müssen Sie im rechten Teilbaum suchen, aber den gewünschten Index reduzieren: index = index - left.size - 1.Da in unserem Fall left.size <index, suchen wir im rechten Teilbaum nach dem Element mit dem neuen Index 4 - 3 - 1 = 0. Gehen Sie mit dem Element „y“ zum Knoten.Dann machen wir dasselbe wie im Wurzelknoten. Vergleiche left.size und index. Da 1> 0, schauen wir in den linken Teilbaum, bewegen uns zum Knoten mit dem Element "t".Es gibt keinen linken Teilbaum in diesem Knoten und seine Größe ist 0. index = left.size, was bedeutet, dass wir einen Knoten mit Index 4 gefunden haben und das erforderliche Element "t" daraus erhalten können.Im Pseudocode sieht es ungefähr so aus:function get(node: Node<T>, index: int): T {
val leftSize: int = (node.left == null) ? 0 : node.left.size;
if (leftSize == index) {
return node.obj;
} else if (leftSize > index) {
return get(node.left, index);
} else {
return get(node.right, index — leftSize — 1);
}
}
Ich habe versucht, das Schlüsselprinzip zu beschreiben, wie ein Array in einen Baum eingefügt wird. Eine solche Struktur arbeitet natürlich langsamer als das klassische Array für O (log (n)) gegenüber O (1). Dies hat jedoch einen wichtigen Vorteil: Das Hinzufügen eines Elements zur Mitte oder das Entfernen aus der Mitte funktioniert auch für O (log (n)) gegenüber O (n) für das Array. Natürlich vorausgesetzt, der Baum ist mehr oder weniger ausgeglichen. Es gibt viele Algorithmen, um einen Baum nahezu ausgewogen zu pflegen. Zum Beispiel rot-schwarzer Baum, AVL-Baum, kartesischer Baum. Ich werde die Details des Ausgleichs des Baumes nicht aufschreiben, jeder Algorithmus ist für uns geeignet. Nehmen wir einfach an, dass der Baum im Durchschnitt ausgeglichen ist und seine maximale Tiefe sich nicht wesentlich von der minimalen unterscheidet.Leichte Optimierung
Der oben beschriebene Ansatz, bei dem die Größe des Baums links überprüft wird, ist für die Wahrnehmung praktisch, kann jedoch etwas effizienter durchgeführt werden. Um nicht jedes Mal in den linken Teilbaum zu schauen, kann man anstelle der Größe des Baums seine Position relativ zur Position seines übergeordneten Knotens im Knoten speichern. Der Wurzelknoten speichert eine absolute Position, die der Größe des linken Teilbaums entspricht. [el: r, pos: 3]
/ : \
/ : \
[el: w, pos: -2] : [el: y, pos: +2]
/ : \ : / : \
/ : \ : / : \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Zum Beispiel hat der Wurzelknoten "r" Position 3. Der Knoten "w" hat Position -2 relativ zum übergeordneten Knoten oder die absolute Position 3 + (-2) = 1. Ebenso können Sie eine weitere Ebene nach unten gehen, zum Beispiel hat der Knoten "e" Position 3 + (-2) + (+1) = 2. Das heißt, Der Knotenindex ist die Summe der Positionen von der Wurzel des Baums zu diesem Knoten.Diese Optimierung bietet neben einer schnelleren Suche nach einem Element in der Liste eine schnellere und einfachere Suche nach dem Index auf dem Knoten. Natürlich ist es etwas schwieriger geworden, die Position beim Ändern des Baums korrekt zu aktualisieren.Indizierung hinzufügen
Im Baum können wir also ein Element nach Index nehmen, seinen Wert ändern, Elemente zur Mitte hinzufügen und löschen. Im Wesentlichen müssen wir nur eine schnelle Indexsuche nach dem Wert indexOf (obj) hinzufügen. Dann enthält (obj) und entfernen (obj) wird trivial gelöst.Aber zuerst vereinfachen wir die Aufgabe ein wenig. Erstellen wir eine Struktur, in der nur eindeutige Elemente gespeichert werden.Um schnell nach etwas zu suchen, verwenden sie normalerweise eine Tabelle. In der Java-Welt heißen Tabellen Map und haben zwei Hauptimplementierungen: HashMap und TreeMap. Der Schlüssel zur Tabelle ist eine Verknüpfung zum Objekt, und der Wert ist eine Verknüpfung zu seinem Knoten:class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
Jene. Die Struktur besteht aus zwei Teilen: dem Listenbaum selbst und der Tabelle mit Links zu Objekten und Knoten dieses Baums. Beim Aktualisieren des Baums muss auch die Tabelle aktualisiert werden. Ich werde den Prozess nicht im Detail beschreiben. Intuitiv sollte es verständlich sein: Fügen Sie einen Knoten hinzu - fügen Sie ihn in die Tabelle ein, löschen Sie den Knoten - löschen Sie ihn aus der Tabelle. In der Praxis gibt es Nuancen beim Ausgleichen des Baums: Der Algorithmus sollte die Verknüpfungen zwischen Knoten ändern und keine Objekte zwischen Knoten verschieben. Andernfalls müssen Sie viele Aktualisierungen in der Tabelle vornehmen, und die Leistung nimmt ab.Ok, wir gehen davon aus, dass wir den Knoten anhand des darin enthaltenen Elements schnell finden können. Na und? Wir müssen seinen Index finden, aber das ist noch nicht möglich. Wir können die Knotenklasse jedoch so komplizieren, dass sie nicht nur Links zu den linken und rechten Knoten enthält, sondern auch zu deren übergeordneten Knoten:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
Das Aktualisieren des Baums ist natürlich etwas komplizierter, da wir jetzt den Link zum übergeordneten Baum sorgfältig aktualisieren müssen. Wenn wir nun den Knoten kennen, können wir den Baum hochgehen und den Index eines beliebigen Knotens berechnen. Wenn wir die Optimierung aus dem vorherigen Kapitel verwendet haben, müssen wir nur die Summe der Positionen vom aktuellen Knoten zur Wurzel berechnen.Bei einer Liste mit eindeutigen Elementen kann das Problem als gelöst betrachtet werden.Es stimmt, wir haben ein kleines Problem. Angenommen, wir nennen set (index, obj). Wir können ein Element in einem Knoten leicht durch ein anderes ersetzen, aber nur, wenn die Liste noch kein neues Element enthält. Und wenn ja, was soll ich tun? Entfernen Sie den überschüssigen Gegenstand aus der alten Position und setzen Sie einen neuen ein? Oder umgekehrt, erst hinzufügen und dann löschen? Das Ergebnis kann unterschiedlich sein. Und Sie können überhaupt nichts tun oder eine Ausnahme auslösen. Es gibt keine perfekte Lösung.Das Sortieren nach Standardmethoden einer solchen Liste funktioniert höchstwahrscheinlich auch nicht. Schließlich weiß der Sortieralgorithmus nicht, ob Objekte eindeutig sein müssen, und erstellt beim Verschieben von Elementen in der Liste Duplikate.Wir entfernen die Einzigartigkeit
Ok, was die Sache noch komplizierter macht, lassen Sie uns die gleichen Objekte behalten. Natürlich müssen Sie etwas mit dem Tisch machen. Die erste Idee, eine Liste von Knoten darin zu speichern, scheint nicht sehr gut zu sein: Mit zunehmender Länge der Liste nimmt die Leistung ab. Bis zu O (n), wenn alle Listenelemente gleich sind.Versuchen wir dann, einen sortierten Knotenbaum in einer Tabelle anstelle einer Liste zu speichern. Sortiert nach Position in der Liste.class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
Das Einfügen / Löschen in / aus dem TreeSet <Knoten> der Größe m erfolgt dann während log (m) -Vergleichen der Positionen der Knoten, und jeder Vergleich erfolgt über log (n) -Zeit. Die endgültige Komplexität des Einfügens oder Löschens in eine ähnliche Struktur tritt in O (log (n) * (1 + log (m))) auf, wobei n die Gesamtzahl der Elemente in der Liste und m die Anzahl der Elemente in der Liste ist, die dem eingefügten / gelöschten entspricht. Im schlimmsten Fall erhalten wir die Komplexität O (log (n) ^ 2), wenn alle Elemente gleich sind.Ein aufmerksamer Leser wird wahrscheinlich Einwände erheben: Aber was ist mit Unveränderlichkeit? Können wir Objekte nicht ändern, wenn es sich um Tabellenschlüssel handelt? Im Allgemeinen ist es. Für einen Baum, in dem sortierte Objekte in Schlüsseln gespeichert sind, reicht es jedoch zusätzlich zu den Standardregeln für Vergleiche aus, die Invariante beizubehalten: Wenn a <b, sollte sich diese Eigenschaft im Laufe der Zeit nicht ändern. Dies ist nur unser Fall: Wenn die Position eines Knotens kleiner als die Position eines anderen Knotens ist, bleibt diese Eigenschaft erhalten, unabhängig davon, wie viele Knoten zwischen ihnen hinzugefügt oder gelöscht wurden.Ist es möglich, die Struktur dauerhaft zu machen?
Kurze Antwort: Nein, das ist unmöglich. Aufgrund der Doppelverbindung des Baumes, von der Wurzel bis zu den Blättern und zurück, haben wir jeden Baumknoten mit jedem verbunden. Die Persistenz kann nicht auf diese Weise erfolgen. Sie müssen die gesamte Struktur bei jeder Änderung neu erstellen.Ich verstehe jedoch, wie eine persistente Struktur für Fälle implementiert werden kann, in denen keine Elemente in die Mitte der Liste eingefügt werden müssen. Sie können am Anfang oder Ende Elemente hinzufügen und aus der Mitte löschen. Die übrigen Eigenschaften sind gleich.Wenn Sie interessiert sind, werde ich versuchen, einen Artikel über diese Struktur zu schreiben. Vielleicht implementiere ich es sogar in Java, Kotlin oder Scala. Aber höchstwahrscheinlich wird es nicht bald sein.Einige Implementierungsfunktionen
Hier möchte ich einige Funktionen beschreiben, denen ich mich stellen musste.Über eine der Optimierungen zum Speichern der Knotenposition in der Liste habe ich oben geschrieben. Hier zeigt sich die Stärke von Open Source: Ich habe den vorgefertigten TreeList-Code verwendet und mich nicht mit den Details des AVL-Baums, Knotenrotationen, Positionsaktualisierungen usw. befasst.Eine weitere von TreeList geerbte Funktion sind die Links zu Teilbäumen in Baumblättern. Jeder Knoten speichert boolesche leftIsPrevious und rightIsNext. Diese Variablen zeigen das Vorhandensein oder Fehlen eines linken / rechten Teilbaums an. Wenn es keinen Teilbaum gibt, wird links / rechts anstelle einer Verknüpfung mit dem Teilbaum eine Verknüpfung mit dem Knoten gespeichert, der dem vorherigen oder nächsten Element entspricht. In unserem Beispiel ["q", "w", "e", "r", "t", "y", "u"] ist der Knoten "e" belaubt und hat keine Teilbäume. Dementsprechend sind leftIsPrevious und rightIsNext true und left und right zeigen auf die Knoten "w" bzw. "r". Dieser Ansatz hilft dabei, die Liste schneller zu durchlaufen. Und es stört die Programmierung neuer Funktionen :)Ein bisschen über die Arbeit mit dem Tabellenobjekt → Knoten. Idealerweise müssen Sie ein Element beim Hinzufügen zur Struktur einmal in die Tabelle einfügen und beim Löschen aus der Struktur einmal löschen. In der Praxis konnte ich dies nicht erreichen. Wenn Sie ein Element hinzufügen, wird es der Tabelle hinzugefügt. Alles ist so, wie es sollte. Wenn Sie jedoch ein Element löschen, verschiebt der Ausgleichsalgorithmus manchmal Elemente zwischen Knoten. Das Ergebnis sind zwei Löschungen und ein Datensatz in der Tabelle anstelle einer Löschung. Dies kann behoben werden, wenn Sie die Optimierung aus leftIsPrevious und rightIsNext entfernen. Und sogar einen kleinen Leistungsgewinn erzielen, nicht nur beim Entfernen. In einigen Tests betrug der Anstieg 10-20%. Aber die Iterationsgeschwindigkeit sinkt signifikant, 1,5- bis 2,5-mal in meinen Tests. Ich habe mich entschlossen, die Optimierung vorerst zu verlassen.In Java sind die Haupttabellentypen HashMap und TreeMap. Für eine Tabelle verwendet ein Objekt → ein Knoten standardmäßig HashMap. Sie können TreeMap jedoch mit einem aufgabenspezifischen Komparator verwenden. In diesem Fall suchen / löschen indexOf (obj) und remove (obj) das Objekt, das dem angegebenen Objekt gemäß dem Komparatorcode entspricht. Zum Beispiel speichern wir eine Liste von Benutzern, und der Komparator vergleicht Benutzer nur nach Namen. Dann können wir die Frage beantworten: "Welche Positionen der Liste haben Benutzer mit dem Namen 'Napoleon?'". Oder entfernen Sie alle Napoleons von der Liste :).Die Struktur unterstützt null nicht. Sie können es beheben, aber es gibt kein Gefühl, dass es notwendig ist.In Bezug auf die Tatsache, dass die Struktur „alles weiß“, war ich natürlich etwas irreführend. Natürlich ist bei der Arbeit mit einzelnen Elementen alles in Ordnung und unter bestimmten Bedingungen auch für den Logarithmus. Sie weiß jedoch einige Dinge nicht, die andere Strukturen können. Zum Beispiel ein kartesischer Baum mit einem impliziten Schlüssel, es gab Artikel darüber auf dem Hub Es weiß nicht, wie man schnell indexOf macht, aber es weiß, wie man eine Unterliste erstellt und zwei Listen für den Logarithmus zu einer verkettet (im Durchschnitt nicht garantiert), und es kann persistent gemacht werden.Performance
In Java wird die Leistung normalerweise mit dem jmh-Framework gemessen. Tests wurden auf dem 2017 MacBook Pro unter Java11 durchgeführt.Ich habe die Leistung der Standard-ArrayList, TreeList aus Apache Common-Collections und meiner beiden Klassen IndexedTreeList und IndexedTreeListSet in mehreren Szenarien verglichen. In jedem Szenario wurden 1000 Operationen desselben Typs ausgeführt, daher sollte das Ergebnis mit 1000 multipliziert werden.Code unter dem Spoiler@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {
public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
ArrayList.class)
.collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
public static final int ITERATIONS = 1000;
@State(Scope.Benchmark)
public static class Plan {
@Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
public int size;
@Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
public String className;
private Random random;
private List<Integer> list;
@Setup
public void init() throws IllegalAccessException, InstantiationException {
random = new Random();
list = (List<Integer>) CLASSES.get(className).newInstance();
for (int i = 0; i < size; i++) {
list.add(i);
}
}
}
@Benchmark
public void indexOfKnown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value = list.indexOf(random.nextInt(plan.size));
}
blackhole.consume(value);
}
@Benchmark
public void indexOfUnknown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.indexOf(random.nextInt());
}
blackhole.consume(value);
}
@Benchmark
public void addRemoveRandom(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
list.add(random.nextInt(list.size() + 1), random.nextInt());
value += list.remove(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Benchmark
public void get(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.get(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(PerformanceCompare.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
Zunächst habe ich die Geschwindigkeit verglichen, mit der ein zufälliges Element aus einer Liste abgerufen wird. Ich warne Sie sofort, dass bei diesem Test der Overhead sehr hoch ist. Ergebnisse, die sich 100.000 * 1.000 Operationen pro Sekunde nähern, sind stark verzerrt.Testergebnis abrufenPerformanceCompare.get ArrayList 10 thrpt 5 79865.412 ± 10145.202 ops/s
PerformanceCompare.get ArrayList 100 thrpt 5 81862.243 ± 983.727 ops/s
PerformanceCompare.get ArrayList 1000 thrpt 5 81033.507 ± 4540.206 ops/s
PerformanceCompare.get ArrayList 10000 thrpt 5 64096.123 ± 1430.361 ops/s
PerformanceCompare.get ArrayList 100000 thrpt 5 41289.491 ± 11286.114 ops/s
PerformanceCompare.get ArrayList 1000000 thrpt 5 8598.944 ± 2048.461 ops/s
PerformanceCompare.get TreeList 10 thrpt 5 33912.275 ± 3754.284 ops/s
PerformanceCompare.get TreeList 100 thrpt 5 21346.854 ± 863.588 ops/s
PerformanceCompare.get TreeList 1000 thrpt 5 14808.414 ± 508.098 ops/s
PerformanceCompare.get TreeList 10000 thrpt 5 8679.384 ± 109.250 ops/s
PerformanceCompare.get TreeList 100000 thrpt 5 4605.998 ± 1028.945 ops/s
PerformanceCompare.get TreeList 1000000 thrpt 5 2241.381 ± 768.147 ops/s
PerformanceCompare.get IndexedTreeList 10 thrpt 5 34054.357 ± 3682.829 ops/s
PerformanceCompare.get IndexedTreeList 100 thrpt 5 21934.002 ± 2339.947 ops/s
PerformanceCompare.get IndexedTreeList 1000 thrpt 5 14626.691 ± 369.893 ops/s
PerformanceCompare.get IndexedTreeList 10000 thrpt 5 7386.863 ± 342.150 ops/s
PerformanceCompare.get IndexedTreeList 100000 thrpt 5 4562.126 ± 352.772 ops/s
PerformanceCompare.get IndexedTreeList 1000000 thrpt 5 2105.718 ± 702.064 ops/s
PerformanceCompare.get IndexedTreeListSet 10 thrpt 5 33317.503 ± 2307.829 ops/s
PerformanceCompare.get IndexedTreeListSet 100 thrpt 5 21247.440 ± 1253.386 ops/s
PerformanceCompare.get IndexedTreeListSet 1000 thrpt 5 14665.557 ± 487.833 ops/s
PerformanceCompare.get IndexedTreeListSet 10000 thrpt 5 7667.214 ± 80.093 ops/s
PerformanceCompare.get IndexedTreeListSet 100000 thrpt 5 3454.023 ± 82.994 ops/s
PerformanceCompare.get IndexedTreeListSet 1000000 thrpt 5 1768.701 ± 35.878 ops/s
Seltsamerweise ist hier das größte Interesse die Standard-ArrayList. Theoretisch sollte die Geschwindigkeit des Ausstiegs konstant sein und nicht von der Anzahl der Elemente abhängen. In der Praxis hält die Leistung zunächst etwa 90.000 * 1000 Operationen pro Sekunde (beachten Sie den Overhead), aber bei einer Listenlänge von mehreren tausend Elementen beginnt sie zu sinken. Dies ist auf den immer häufiger auftretenden Cache-Fehler zurückzuführen: Der Prozessor-Cache verfügt nicht über die erforderlichen Daten, und Sie müssen immer häufiger Daten im RAM abrufen. Mit einer Million Elementen ist die Geschwindigkeit des Tests zehnmal niedriger, aber in der Praxis ist der Leistungsabfall noch größer.TreeList, IndexedTreeList und IndexedTreeListSet zeigen voraussichtlich ähnliche Ergebnisse. Erwartet viel langsamer als ArrayList. Selbst mit einer kleinen Anzahl von Elementen ist TreeList um ein Vielfaches langsamer als ArrayList, obwohl der Test den Unterschied nur zweimal zeigt.Der nächste Test ist addRemoveRandom. Hier füge ich in jedem Test ein Element an einer zufälligen Position ein und entferne ein Element an einer zufälligen Position.AddRemoveRandom-TestergebnisPerformanceCompare.addRemoveRandom ArrayList 10 thrpt 5 12440.764 ± 485.642 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100 thrpt 5 9880.123 ± 464.014 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000 thrpt 5 5288.905 ± 1219.055 ops/s
PerformanceCompare.addRemoveRandom ArrayList 10000 thrpt 5 1024.942 ± 179.366 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100000 thrpt 5 91.219 ± 25.380 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000000 thrpt 5 5.499 ± 0.400 ops/s
PerformanceCompare.addRemoveRandom TreeList 10 thrpt 5 6242.607 ± 350.290 ops/s
PerformanceCompare.addRemoveRandom TreeList 100 thrpt 5 3117.945 ± 116.066 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000 thrpt 5 1829.778 ± 80.516 ops/s
PerformanceCompare.addRemoveRandom TreeList 10000 thrpt 5 1230.077 ± 53.381 ops/s
PerformanceCompare.addRemoveRandom TreeList 100000 thrpt 5 443.571 ± 69.207 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000000 thrpt 5 308.963 ± 84.077 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10 thrpt 5 3556.511 ± 144.596 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100 thrpt 5 2120.777 ± 83.848 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000 thrpt 5 1211.112 ± 92.288 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10000 thrpt 5 789.458 ± 19.450 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100000 thrpt 5 302.989 ± 40.030 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000000 thrpt 5 178.822 ± 92.853 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10 thrpt 5 4138.007 ± 119.943 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100 thrpt 5 2435.803 ± 20.276 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000 thrpt 5 1445.054 ± 276.909 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10000 thrpt 5 972.256 ± 19.987 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100000 thrpt 5 366.608 ± 94.487 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000000 thrpt 5 227.677 ± 48.276 ops/s
Es ist davon auszugehen, dass ArrayList auf kleinen Listen schneller ist. Interessant ist jedoch, dass er in diesem Test auf Listen mit bis zu 10.000 Elementen gewinnt. Anscheinend ist System.arrayCopy sehr gut optimiert und nutzt alle Funktionen moderner Prozessoren. Ab 10.000 Artikeln beginnen spezialisierte Datenstrukturen zu gewinnen. Bei 1.000.000 Elementen beträgt der Geschwindigkeitsunterschied das 30-50-fache.Es wird erwartet, dass IndexedTreeList und IndexedTreeListSet langsamer als TreeList sind. Etwa 1,5 - 2 mal.Die verbleibenden 2 Tests indexOfKnown und indexOfUnknown sollten nur das Hauptmerkmal dieser Struktur demonstrieren. Der Unterschied zwischen den Tests besteht darin, dass wir in einem Fall nach einem Element suchen, das in der Liste enthalten ist, und in dem anderen Fall nach einem Element, das nicht in der Liste enthalten ist.Testergebnis indexOfKnown und indexOfUnknownPerformanceCompare.indexOfKnown ArrayList 10 thrpt 5 41424.356 ± 549.047 ops/s
PerformanceCompare.indexOfKnown ArrayList 100 thrpt 5 17216.477 ± 1444.744 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000 thrpt 5 2296.306 ± 76.372 ops/s
PerformanceCompare.indexOfKnown ArrayList 10000 thrpt 5 233.863 ± 26.926 ops/s
PerformanceCompare.indexOfKnown ArrayList 100000 thrpt 5 23.208 ± 2.776 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000000 thrpt 5 0.919 ± 0.455 ops/s
PerformanceCompare.indexOfKnown TreeList 10 thrpt 5 26740.708 ± 1323.125 ops/s
PerformanceCompare.indexOfKnown TreeList 100 thrpt 5 5670.923 ± 99.638 ops/s
PerformanceCompare.indexOfKnown TreeList 1000 thrpt 5 745.408 ± 26.827 ops/s
PerformanceCompare.indexOfKnown TreeList 10000 thrpt 5 52.288 ± 1.362 ops/s
PerformanceCompare.indexOfKnown TreeList 100000 thrpt 5 4.224 ± 0.855 ops/s
PerformanceCompare.indexOfKnown TreeList 1000000 thrpt 5 0.193 ± 0.052 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10 thrpt 5 34485.128 ± 1582.703 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100 thrpt 5 29209.412 ± 1544.268 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000 thrpt 5 21139.584 ± 1442.867 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10000 thrpt 5 12544.306 ± 312.097 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100000 thrpt 5 3538.201 ± 272.537 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000000 thrpt 5 1420.119 ± 538.476 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10 thrpt 5 39201.995 ± 1887.065 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100 thrpt 5 34204.112 ± 1122.517 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000 thrpt 5 25374.557 ± 1596.746 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10000 thrpt 5 14291.317 ± 391.180 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100000 thrpt 5 4215.898 ± 283.680 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000000 thrpt 5 1729.100 ± 1260.815 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10 thrpt 5 59053.313 ± 1845.665 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100 thrpt 5 10867.572 ± 142.823 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000 thrpt 5 1186.583 ± 28.003 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10000 thrpt 5 120.953 ± 4.146 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100000 thrpt 5 11.936 ± 0.320 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000000 thrpt 5 0.566 ± 0.335 ops/s
PerformanceCompare.indexOfUnknown TreeList 10 thrpt 5 28134.237 ± 2291.670 ops/s
PerformanceCompare.indexOfUnknown TreeList 100 thrpt 5 3153.930 ± 158.734 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000 thrpt 5 322.383 ± 44.245 ops/s
PerformanceCompare.indexOfUnknown TreeList 10000 thrpt 5 25.674 ± 1.787 ops/s
PerformanceCompare.indexOfUnknown TreeList 100000 thrpt 5 1.867 ± 0.291 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000000 thrpt 5 0.093 ± 0.008 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10 thrpt 5 66625.126 ± 5232.668 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100 thrpt 5 70038.055 ± 5803.848 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000 thrpt 5 63240.467 ± 885.956 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10000 thrpt 5 54731.988 ± 3950.150 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100000 thrpt 5 22049.476 ± 821.924 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000000 thrpt 5 9459.862 ± 804.738 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10 thrpt 5 70274.968 ± 15830.355 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100 thrpt 5 71017.685 ± 6920.447 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000 thrpt 5 66405.960 ± 1127.231 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10000 thrpt 5 57983.963 ± 3276.142 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100000 thrpt 5 41277.110 ± 9919.893 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000000 thrpt 5 9840.185 ± 2159.352 ops/s
Hier haben ArrayList und TreeList fast keine Überraschungen. Mit zunehmender Größe nimmt die Geschwindigkeit nahezu linear ab. Die Suche nach einem Artikel aus einer Nichtliste wird voraussichtlich zweimal langsamer sein als die Suche nach einem Artikel aus der Liste, weil Sie müssen das gesamte Array anstatt der Hälfte im Durchschnitt durchlaufen.IndexedTreeList und IndexedTreeListSet zeigen hier jedoch das erwartete gute Ergebnis. Diese Datenstrukturen zeigen eine mit ArrayList vergleichbare IndexOf-Ausführungsgeschwindigkeit, selbst bei 10 Elementen. Mit 1000 Elementen sind diese Strukturen zehnmal schneller, mit 1.000.000 1000-mal schneller. Bei der Suche nach einem Element, das nicht in der Liste enthalten ist, wird eine höhere Geschwindigkeit erwartet als bei der Suche nach einem Element in der Liste.Interessant ist auch die Leistungssenkung von IndexedTreeList und IndexedTreeListSet im indexOfUnknown-Test. Hier ist die Situation ähnlich wie im Test mit ArrayList.get. Theoretisch hätten wir keinen Leistungsabfall erhalten sollen, aber in der Praxis haben wir ihn aufgrund eines Cache-Fehlers erhalten, und dies ist von Bedeutung.Anstelle einer Schlussfolgerung
Ich weiß immer noch nicht, ob die vorgeschlagene Struktur eine Neuheit aufweist oder nicht. Einerseits ist die Idee nicht kompliziert, wenn Sie wissen, wie der Baum mit einem impliziten Schlüssel funktioniert. Andererseits habe ich keine Beschreibung einer Struktur mit solchen Eigenschaften gesehen. Und wenn ja, dann ist es sinnvoll, die Struktur bekannter zu machen, es könnte für jemanden nützlich sein.Aber selbst wenn dies ein anderes Fahrrad ist, habe ich versucht, es nützlich zu machen. Eine Pull-Anfrage in allgemeinen Sammlungen wurde erstellt, aber zum Zeitpunkt des Schreibens ist dieser Artikel noch nicht ausgegossen. Da ich weiß, wie langsam alles in Open Source ablaufen kann, bin ich nicht überrascht, wenn sich der Prozess monatelang hinzieht.Etwas überrascht über das Ergebnis des Vergleichs der Leistung von ArrayList und TreeList. Tests haben gezeigt, dass TreeList keinen Sinn macht, bis zu 10.000 Elemente in der Listengröße zu verwenden. Es wäre interessant, B-Tree anstelle eines Binärbaums zu versuchen. Diese Struktur sollte den Speicher sorgfältiger nutzen und höchstwahrscheinlich schneller arbeiten. Und dafür können Sie die Idee mit Indizierung anpassen.In jedem Fall macht es Spaß, ein Instrument im Arsenal zu haben, das (fast) alles mit vorhersehbarer Komplexität kann.Verweise
Ursprüngliches
Pull-Anforderungsprojekt in Apache Common-CollectionsTicket in Jira