Mittlere Einfügung: ArrayList vs. LinkedList

    Irgendwie wurde mir beim Interview die Frage gestellt: Welche Implementierung der Liste wird schneller in die Mitte eingefügt: ArrayList oder LinkedList? Auf den ersten Blick ist die Frage einfach: Sie müssen die algorithmische Komplexität jeder Option berechnen und vergleichen. Das Einfügen in die Mitte kann in zwei Operationen unterteilt werden: Suchen Sie nach der Mitte der Liste und fügen Sie sich selbst ein. Für ArrayList ist es nicht schwierig, ein Element anhand des Index zu finden, da sich die Elemente der Liste in einem Array befinden. Die algorithmische Komplexität ist O (1). Im Fall von LinkedList müssen wir alle Elemente nacheinander sortieren, bis wir zum gewünschten Element gelangen. Die Schwierigkeit wird O (n) sein. Das Einfügen in ArrayList ist mit der Verschiebung aller Elemente verbunden, die sich nach dem Einfügepunkt befinden. Daher ist die algorithmische Komplexität dieser Operation O (n). In LinkedList wird durch Einfügen ein neues Vermittlungsobjekt erstellt und Verknüpfungen zu benachbarten Elementen festgelegt. Komplexität O (1). Insgesamt ist die Komplexität des Einfügens in die Mitte von ArrayList und LinkedList gleich - O (n). Ich habe dem Interviewer diese Argumente gezeigt, zu denen er mir die Frage gestellt hat: „Ist es also noch schneller: über die Elemente gehen oder die Elemente verschieben?“. Ich schätzte schnell, dass der Lesevorgang wesentlich schneller ist als der Schreibvorgang, und sagte, dass LinkedList schneller zurechtkommt.
    Als ich nach Hause kam, dachte ich über dieses Problem nach. Ich habe in den Foren nach einer Lösung für dieses Problem gesucht. Jemand stimmte mir zu, aber viele berücksichtigten, dass die Offset-Operation von der nativen Methode ausgeführt wird, die schneller ist, sodass ArrayList schneller in die Mitte eingefügt wird. Nachdem ich keine endgültige und unwiderlegbare Antwort erhalten hatte, beschloss ich, meine eigenen Forschungen durchzuführen.

    Zuerst habe ich mich mit dem Quellcode für diese Klassen befasst. Ein Element wird wie folgt in eine ArrayList eingefügt: Zuerst wächst das Array, falls erforderlich, dann werden alle Elemente nach der Einfügemarke um die Anzahl der Positionen verschoben, die der Anzahl der einzufügenden Elemente entspricht (ich betrachte ein Element), und am Ende fällt das einzufügende Element ein. Das Array nimmt mit einer Geschwindigkeit von n * 1,5 zu, wobei n die Größe des Arrays ist und die minimale Zunahme unter Standardbedingungen (Kapazität = 10) 5 Elemente beträgt. In dieser Hinsicht kann die Operation zum Erhöhen des Arrays bei der Berechnung der algorithmischen Komplexität der Einfügung vernachlässigt werden. Die Verschiebung der nach der Einfügemarke befindlichen Elemente hat die algorithmische Komplexität O (n). Somit bleibt die Gesamtkomplexität immer noch O (n). Ja, wir denken daran, dass der Vorgang des Erhöhens des Arrays die Komplexität geringfügig erhöht.

    Eine Suche nach einem Element in einer LinkedList beginnt in einer Schleife am Rand der Liste. Befindet sich das zu findende Element in der ersten Hälfte der Liste, erfolgt die Suche vom Anfang, andernfalls vom Ende. Da wir genau in der Mitte einfügen, werden wir im Zyklus genau die Hälfte der Elemente durchlaufen. Komplexität O (n). Die Einfügung selbst besteht, wie ich oben geschrieben habe, darin, ein Objekt zu erstellen und Verweise darauf anzugeben. Komplexität O (1). Auch hier habe ich nichts Neues herausgefunden: Die Gesamtkomplexität blieb O (n), wobei zu berücksichtigen ist, dass das Erstellen eines Objekts eine „teure“ Operation ist.

    Die Analyse des Quellcodes hat die Situation nicht geklärt, also begann ich Tests zu schreiben. Ich beschloss, die Abhängigkeit von zwei Parametern zu untersuchen: der Anfangsgröße der Liste und der Anzahl der Einfügungen in einer Reihe (Anzahl der Iterationen).
    Quellcode-Beispiel
    package com.jonasasx.liststest;
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    public class Main {
    	private static final int	MAX_SIZE		= 1000;
    	private static final int	MAX_ITERATIONS	= 10000;
    	private static final float	STEP_SIZE		= 2f;
    	private static final float	STEP_ITERATIONS	= 5;
    	private static final int	TESTS_COUNT		= 100;
    	public static void main(String[] args) throws InterruptedException {
    		ArrayList arrayList;
    		LinkedList linkedList;
    		for (float size = 1; size < MAX_SIZE; size *= STEP_SIZE) {
    			for (float iterations = 1; iterations < MAX_ITERATIONS; iterations *= STEP_ITERATIONS) {
    				double sum = 0;
    				for (int k = 0; k < TESTS_COUNT; k++) {
    					arrayList = new ArrayList<>();
    					linkedList = new LinkedList<>();
    					fillList(arrayList, (int) size);
    					fillList(linkedList, (int) size);
    					sum += Math.log10(calculateRatio(arrayList, linkedList, (int) iterations));
    				}
    				double logRatio = sum / TESTS_COUNT;
    				System.out.println(String.format("%07d\t%07d\t%07.2f\t%s", (int) size, (int) iterations, logRatio, logRatio > 0 ? "Linked" : "Array"));
    			}
    			System.out.println();
    		}
    	}
    	static void fillList(List list, int size) {
    		for (int i = 0; i < size; i++) {
    			list.add("0");
    		}
    	}
    	static double calculateRatio(ArrayList arrayList, LinkedList linkedList, int iterations) {
    		long l1 = calculateAL(arrayList, iterations);
    		long l2 = calculateLL(linkedList, iterations);
    		if (l1 == 0 || l2 == 0)
    			throw new java.lang.IllegalStateException();
    		return (double) l1 / (double) l2;
    	}
    	static long calculateAL(ArrayList list, int m) {
    		long t = System.nanoTime();
    		for (int i = 0; i < m; i++) {
    			list.add(list.size() / 2, "0");
    		}
    		return System.nanoTime() - t;
    	}
    	static long calculateLL(LinkedList list, int m) {
    		long t = System.nanoTime();
    		for (int i = 0; i < m; i++) {
    			list.add(list.size() / 2, "0");
    		}
    		return System.nanoTime() - t;
    	}
    }
    


    Für jede Listengröße und die Anzahl der Iterationen werden ein ArrayList- und ein LinkedList-Array erstellt. Sie werden mit denselben Objekten gefüllt. Danach werden n Geschwindigkeitsmessungen durchgeführt, indem n ein Objekt in die Mitte einfügt. Als Vergleichswert verwende ich den dezimalen Logarithmus des Verhältnisses der Ausführungszeiten von ArrayList zu LinkedList. Wenn dieser Wert kleiner als Null ist, wird ArrayList schneller verarbeitet, wenn mehr schneller als LinkedList ist.

    Ich gebe die Testergebnisse in der Tabelle an:
     Iterationen          
    Größe 1248163264128256512
     1-0,120,01-0.040,010,03-0.04-0.09-0,19-0,21-0,31
     5-0,140,02-0.020,07-0.080-0,15-0,31-0,42-0,52
     25-0,120,20,190,130,070,04-0.1-0,29-0,47-0,56
     125-0,31-0,010,010-0.03-0,11-0,17-0,35-0,48-0,57
     625-0,47-0,49-0,48-0,45-0,49-0,51-0,53-0,6-0,67-0,78


    Und in der Grafik:

    Bild
    Auf der X-Achse wird die Anfangsgröße der Liste angegeben, die Linien repräsentieren eine unterschiedliche Anzahl von Iterationen und auf der Y-Achse das Verhältnis der Geschwindigkeit zweier Implementierungen der Liste.

    Da die Größe der Liste mit jeder Iteration zunimmt, können wir eine allgemeine Schlussfolgerung ziehen: LinkList arbeitet mit einer kleinen Listengröße schneller. Aber das Wichtigste: Ohne eine klare Spezifikation der Bedingungen kann die Geschwindigkeit dieser beiden Algorithmen nicht verglichen werden!

    Um die Genauigkeit zu erhöhen, habe ich den Parameter für die Anzahl der Einfügungen aufgegeben und den Größenschritt auf eins reduziert. Für jede der Größen habe ich den Test tausendmal durchgeführt und den Durchschnittswert ermittelt. Habe ein Diagramm:
    Bild
    Der Graph hat ausgeprägte Bursts. Sie befinden sich genau dort, wo ArrayList eine Vergrößerung des Arrays bewirkt. Daher können wir sagen, dass diese Operation nicht vernachlässigt werden kann, wie ich zu Beginn bei der Analyse des Quellcodes berechnet habe.

    Die allgemeine Schlussfolgerung kann wie folgt gezogen werden: Die Einfügeoperation in der Mitte erfolgt in ArrayList meist schneller, jedoch nicht immer. Aus theoretischer Sicht ist es unmöglich, die Geschwindigkeit dieser beiden Algorithmen eindeutig zu vergleichen, ohne die anfängliche Größe der Liste zu berücksichtigen.

    Vielen Dank für Ihre Aufmerksamkeit. Ich hoffe, jemand findet meine Arbeit interessant und / oder nützlich.

    Jetzt auch beliebt: