Ich muss Tausende von Zeichenfolgen im Speicher behalten, um in Java seriell darauf zugreifen zu können. Soll ich sie in einem Array speichern oder eine Art Liste verwenden?

Würde die Verwendung eines Arrays zum Speichern von Tausenden von Zeichenfolgen Probleme verursachen, da Arrays alle Daten in einem zusammenhängenden Speicherblock speichern (im Gegensatz zu Listen)?

Ich schlage vor, dass Sie einen Profiler verwenden, um zu testen, welcher schneller ist.

Meine persönliche Meinung ist, dass Sie Listen verwenden sollten.

Ich arbeite an einer großen Codebasis und eine frühere Gruppe von Entwicklern verwendete überall Arrays . Es machte den Code sehr unflexibel. Nachdem wir große Teile davon in Listen geändert hatten, stellten wir keinen Geschwindigkeitsunterschied fest.

Auf Java sollten Sie überlegen, welche Datenabstraktion Ihren Anforderungen am besten entspricht. Denken Sie daran, dass eine Liste in Java eine Zusammenfassung und kein konkreter Datentyp ist. Sie sollten die Zeichenfolgen als Liste deklarieren und dann mithilfe der ArrayList-Implementierung initialisieren.

List<String> strings = new ArrayList<String>();

Diese Trennung von abstraktem Datentyp und spezifischer Implementierung ist einer der Schlüsselaspekte der objektorientierten Programmierung.

Eine ArrayList implementiert den List Abstract Data Type unter Verwendung eines Arrays als zugrunde liegende Implementierung. Die Zugriffsgeschwindigkeit ist praktisch identisch mit einem Array, mit dem zusätzlichen Vorteil, dass Elemente zu einer Liste hinzugefügt und von dieser entfernt werden können (obwohl dies eine O (n) -Operation mit einer ArrayList ist), wenn Sie die zugrunde liegende Implementierung später ändern möchten Sie können. Wenn Sie beispielsweise feststellen, dass Sie einen synchronisierten Zugriff benötigen, können Sie die Implementierung in einen Vektor ändern, ohne den gesamten Code neu schreiben zu müssen.

Tatsächlich wurde die ArrayList speziell entwickelt, um das Array-Konstrukt auf niedriger Ebene in den meisten Kontexten zu ersetzen. Wenn Java heute entworfen worden wäre, wäre es durchaus möglich, dass Arrays zugunsten des ArrayList-Konstrukts ganz weggelassen worden wären.

Würde die Verwendung eines Arrays zum Speichern von Tausenden von Zeichenfolgen Probleme verursachen, da Arrays alle Daten in einem zusammenhängenden Speicherblock speichern (im Gegensatz zu Listen)?

In Java speichern alle Sammlungen nur Verweise auf Objekte, nicht auf die Objekte selbst. Sowohl Arrays als auch ArrayList speichern einige tausend Referenzen in einem zusammenhängenden Array, sodass sie im Wesentlichen identisch sind. Sie können davon ausgehen, dass ein zusammenhängender Block mit einigen tausend 32-Bit-Referenzen auf moderner Hardware immer verfügbar ist. Dies garantiert natürlich nicht, dass Ihnen nicht der Speicherplatz ausgeht, nur dass der zusammenhängende Block des Speicherbedarfs nicht schwer zu erfüllen ist.

Obwohl die Antworten, die die Verwendung von ArrayList vorschlagen, in den meisten Szenarien sinnvoll sind, wurde die eigentliche Frage nach der relativen Leistung nicht wirklich beantwortet.

Mit einem Array können Sie einige Dinge tun:

• erstelle es
• setze einen Gegenstand
• Holen Sie sich einen Artikel
• klonen / kopieren

Allgemeine Schlussfolgerung

Obwohl Get- und Set-Operationen auf einer ArrayList etwas langsamer sind (bzw. 1 und 3 Nanosekunden pro Aufruf auf meinem Computer), ist der Aufwand für die Verwendung einer ArrayList im Vergleich zu einem Array für eine nicht intensive Verwendung sehr gering. Es sind jedoch einige Dinge zu beachten:

• Das Ändern der Größe von Vorgängen in einer Liste (beim Aufrufen list.add(...)) ist kostspielig und es sollte versucht werden, die anfängliche Kapazität nach Möglichkeit auf ein angemessenes Niveau einzustellen (beachten Sie, dass bei Verwendung eines Arrays dasselbe Problem auftritt).
• Beim Umgang mit Grundelementen können Arrays erheblich schneller sein, da sie es ermöglichen, viele Boxing / Unboxing-Konvertierungen zu vermeiden
• Eine Anwendung, die nur Werte in einer ArrayList abruft / festlegt (nicht sehr häufig!), kann durch den Wechsel zu einem Array einen Leistungsgewinn von mehr als 25% erzielen

Detaillierte Ergebnisse

Hier sind die Ergebnisse, die ich für diese drei Vorgänge mithilfe der jmh-Benchmarking-Bibliothek (Zeiten in Nanosekunden) mit JDK 7 auf einem Standard-x86-Desktop-Computer gemessen habe . Beachten Sie, dass die Größe von ArrayList in den Tests niemals geändert wird, um sicherzustellen, dass die Ergebnisse vergleichbar sind. Benchmark-Code finden Sie hier .

Array / ArrayList-Erstellung

Ich habe 4 Tests durchgeführt und die folgenden Anweisungen ausgeführt:

• createArray1: Integer[] array = new Integer[1];
• createList1: List<Integer> list = new ArrayList<> (1);
• createArray10000: Integer[] array = new Integer[10000];
• createList10000: List<Integer> list = new ArrayList<> (10000);

Ergebnisse (in Nanosekunden pro Anruf, 95% iges Vertrauen):

a.p.g.a.ArrayVsList.CreateArray1         [10.933, 11.097]
a.p.g.a.ArrayVsList.CreateList1          [10.799, 11.046]
a.p.g.a.ArrayVsList.CreateArray10000    [394.899, 404.034]
a.p.g.a.ArrayVsList.CreateList10000     [396.706, 401.266]

Fazit: kein spürbarer Unterschied .

Operationen bekommen

Ich habe 2 Tests durchgeführt und die folgenden Anweisungen ausgeführt:

• getList: return list.get(0);
• getArray: return array[0];

Ergebnisse (in Nanosekunden pro Anruf, 95% iges Vertrauen):

a.p.g.a.ArrayVsList.getArray   [2.958, 2.984]
a.p.g.a.ArrayVsList.getList    [3.841, 3.874]

Fazit: Das Abrufen von einem Array ist etwa 25% schneller als das Abrufen von einer ArrayList, obwohl der Unterschied nur in der Größenordnung von einer Nanosekunde liegt.

Operationen einstellen

Ich habe 2 Tests durchgeführt und die folgenden Anweisungen ausgeführt:

• setList: list.set(0, value);
• setArray: array[0] = value;

Ergebnisse (in Nanosekunden pro Anruf):

a.p.g.a.ArrayVsList.setArray   [4.201, 4.236]
a.p.g.a.ArrayVsList.setList    [6.783, 6.877]

Fazit: Set-Operationen auf Arrays sind etwa 40% schneller als auf Listen, aber wie bei get dauert jede Set-Operation einige Nanosekunden. Damit die Differenz 1 Sekunde erreicht, müssten Elemente in der Liste / im Array Hunderte gesetzt werden millionenfach!

Klon / Kopie

Array des Copykonstruktor Delegierten Arrays.copyOfso Leistung ist identisch mit Array copy (kopieren ein Array über clone, Arrays.copyOfoder System.arrayCopy macht keinen wesentlichen Unterschied Performance-weise ).

Sie sollten generische Typen Arrays vorziehen. Wie von anderen erwähnt, sind Arrays unflexibel und haben nicht die Ausdruckskraft generischer Typen. (Sie unterstützen jedoch Laufzeit-Typchecking, aber das mischt sich schlecht mit generischen Typen.)

Aber wie immer sollten Sie bei der Optimierung immer die folgenden Schritte ausführen:

• Optimieren Sie nicht, bis Sie eine schöne, saubere und funktionierende haben Version Ihres Codes haben. Der Wechsel zu generischen Typen könnte bereits in diesem Schritt durchaus motiviert sein.
• Wenn Sie eine Version haben, die schön und sauber ist, entscheiden Sie, ob sie schnell genug ist.
• Wenn es nicht schnell genug ist, messen Sie die Leistung . Dieser Schritt ist aus zwei Gründen wichtig. Wenn Sie nicht messen, wissen Sie nicht (1), wie sich Optimierungen auswirken, und (2) wissen, wo Sie optimieren müssen.
• Optimieren Sie den heißesten Teil Ihres Codes.
• Wieder messen. Dies ist genauso wichtig wie das vorherige Messen. Wenn die Optimierung die Dinge nicht verbessert hat, setzen Sie sie zurück . Denken Sie daran, der Code ohne die Optimierung war sauber, nett und funktionierte.

Ich vermute, das Originalposter stammt aus einem C ++ / STL-Hintergrund, was einige Verwirrung stiftet. In C ++ std::listist eine doppelt verknüpfte Liste.

In Java [java.util.]Listgibt es eine implementierungsfreie Schnittstelle (reine abstrakte Klasse in C ++). Listkann eine doppelt verknüpfte Liste sein - java.util.LinkedListwird bereitgestellt. 99 von 100 Fällen, in denen Sie ein neues Listerstellen möchten, möchten Sie java.util.ArrayListstattdessen verwenden. Dies entspricht in etwa C ++ std::vector. Es gibt andere Standardimplementierungen, z. B. die von java.util.Collections.emptyList()und zurückgegebenenjava.util.Arrays.asList() .

Unter Leistungsgesichtspunkten gibt es einen sehr kleinen Nachteil, wenn eine Schnittstelle und ein zusätzliches Objekt durchlaufen werden müssen. Laufzeit-Inlining bedeutet jedoch, dass dies selten eine Bedeutung hat. Denken Sie auch daran, dass Stringes sich normalerweise um ein Objekt plus Array handelt. Für jeden Eintrag haben Sie wahrscheinlich zwei weitere Objekte. In C ++ std::vector<std::string>bilden die Zeichenarrays, obwohl sie als Wert ohne Zeiger als solchen kopiert werden, ein Objekt für eine Zeichenfolge (und diese werden normalerweise nicht gemeinsam genutzt).

Wenn dieser bestimmte Code wirklich leistungsabhängig ist, können Sie ein einzelnes char[]Array (oder sogar byte[]) für alle Zeichen aller Zeichenfolgen und dann ein Array von Offsets erstellen . IIRC, so wird javac implementiert.

Ich bin damit einverstanden, dass Sie in den meisten Fällen die Flexibilität und Eleganz von ArrayLists gegenüber Arrays wählen sollten - und in den meisten Fällen sind die Auswirkungen auf die Programmleistung vernachlässigbar.

Wenn Sie jedoch eine konstante, umfangreiche Iteration mit geringen strukturellen Änderungen (kein Hinzufügen und Entfernen) durchführen, z. B. für das Rendern von Softwaregrafiken oder eine benutzerdefinierte virtuelle Maschine, zeigen meine Benchmarking-Tests für sequentiellen Zugriff, dass ArrayLists 1,5-mal langsamer sind als Arrays auf meinem System (Java 1.6 auf meinem einjährigen iMac).

Etwas Code:

import java.util.*;

public class ArrayVsArrayList {
    static public void main( String[] args ) {

        String[] array = new String[300];
        ArrayList<String> list = new ArrayList<String>(300);

        for (int i=0; i<300; ++i) {
            if (Math.random() > 0.5) {
                array[i] = "abc";
            } else {
                array[i] = "xyz";
            }

            list.add( array[i] );
        }

        int iterations = 100000000;
        long start_ms;
        int sum;

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += array[j].length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" );
        // Prints ~13,500 ms on my system

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += list.get(j).length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" );
        // Prints ~20,800 ms on my system - about 1.5x slower than direct array access
    }
}

Zunächst ist zu klären, ob Sie "Liste" im Sinne der klassischen Comp-Sci-Datenstrukturen (dh eine verknüpfte Liste) oder java.util.List meinen. Wenn Sie eine java.util.List meinen, ist es eine Schnittstelle. Wenn Sie ein Array verwenden möchten, verwenden Sie einfach die ArrayList-Implementierung, und Sie erhalten ein Array-ähnliches Verhalten und eine semantische Semantik. Problem gelöst.

Wenn Sie ein Array mit einer verknüpften Liste meinen, ist dies ein etwas anderes Argument, für das wir auf Big O zurückgreifen (hier ist eine einfache englische Erklärung, wenn dies ein unbekannter Begriff ist.

Array;

• Direktzugriff: O (1);
• Einfügen: O (n);
• Löschen: O (n).

Verknüpfte Liste:

• Direktzugriff: O (n);
• Einfügen: O (1);
• Löschen: O (1).

Sie wählen also diejenige aus, die am besten zu Ihrer Größe passt. Wenn Sie die Größe ändern, viel einfügen und löschen, ist möglicherweise eine verknüpfte Liste die bessere Wahl. Gleiches gilt, wenn der Direktzugriff selten ist. Sie erwähnen den seriellen Zugriff. Wenn Sie hauptsächlich seriellen Zugriff mit sehr geringen Änderungen durchführen, spielt es wahrscheinlich keine Rolle, welche Sie wählen.

Verknüpfte Listen haben einen etwas höheren Overhead, da es sich, wie Sie sagen, um potenziell nicht zusammenhängende Speicherblöcke und (effektiv) Zeiger auf das nächste Element handelt. Dies ist wahrscheinlich kein wichtiger Faktor, es sei denn, Sie haben es mit Millionen von Einträgen zu tun.

Ich habe einen kleinen Benchmark geschrieben, um ArrayLists mit Arrays zu vergleichen. Auf meinem alten Laptop war die Zeit zum 1000-maligen Durchlaufen einer Arrayliste mit 5000 Elementen etwa 10 Millisekunden langsamer als der entsprechende Array-Code.

Wenn Sie also nur die Liste iterieren und viel tun, lohnt sich die Optimierung möglicherweise . Ansonsten würde ich die Liste verwenden, weil es wird es einfacher machen , wenn Sie tun müssen , den Code zu optimieren.

nb Ich habe festgestellt, dass die Verwendung for String s: stringsListetwa 50% langsamer war als die Verwendung einer alten for-Schleife für den Zugriff auf die Liste. Go figure ... Hier sind die beiden Funktionen, die ich zeitlich festgelegt habe. Das Array und die Liste wurden mit 5000 zufälligen (verschiedenen) Zeichenfolgen gefüllt.

private static void readArray(String[] strings) {
    long totalchars = 0;
    for (int j = 0; j < ITERATIONS; j++) {
        totalchars = 0;
        for (int i = 0; i < strings.length; i++) {
            totalchars += strings[i].length();

        }
    }
}

private static void readArrayList(List<String> stringsList) {
    long totalchars = 0;
    for (int j = 0; j < ITERATIONS; j++) {
        totalchars = 0;
        for (int i = 0; i < stringsList.size(); i++) {
            totalchars += stringsList.get(i).length();
        }
    }
}

Nein, da das Array technisch nur den Verweis auf die Zeichenfolgen speichert. Die Zeichenfolgen selbst werden an einer anderen Stelle zugewiesen. Für tausend Elemente würde ich sagen, dass eine Liste besser wäre, langsamer, aber flexibler und benutzerfreundlicher, insbesondere wenn Sie die Größe ändern möchten.

Wenn Sie Tausende haben, sollten Sie einen Versuch in Betracht ziehen. Ein Trie ist eine baumartige Struktur, die die allgemeinen Präfixe der gespeicherten Zeichenfolge zusammenführt.

Zum Beispiel, wenn die Zeichenfolgen wären

intern
international
internationalize
internet
internets

Der Versuch würde speichern:

intern
 -> \0
 international
 -> \0
 -> ize\0
 net
 ->\0
 ->s\0

Die Zeichenfolgen erfordern 57 Zeichen (einschließlich des Nullterminators '\ 0') für die Speicherung sowie die Größe des String-Objekts, in dem sie gespeichert sind. (In Wahrheit sollten wir wahrscheinlich alle Größen auf ein Vielfaches von 16 aufrunden, aber ...) Nennen wir es ungefähr 57 + 5 = 62 Bytes.

Der Trie benötigt 29 (einschließlich des Null-Terminators '\ 0') für die Speicherung plus Größe der Trie-Knoten, die sich auf ein Array und eine Liste von untergeordneten Trie-Knoten beziehen.

In diesem Beispiel ist das wahrscheinlich ungefähr dasselbe. Für Tausende kommt es wahrscheinlich weniger heraus, solange Sie gemeinsame Präfixe haben.

Wenn Sie den Versuch in einem anderen Code verwenden, müssen Sie ihn in String konvertieren, wahrscheinlich unter Verwendung eines StringBuffers als Vermittler. Wenn viele der Saiten gleichzeitig als Saiten außerhalb des Tries verwendet werden, ist dies ein Verlust.

Wenn Sie jedoch nur wenige gleichzeitig verwenden, um beispielsweise in einem Wörterbuch nachzuschlagen, können Sie mit dem Versuch viel Platz sparen. Definitiv weniger Speicherplatz als das Speichern in einem HashSet.

Sie sagen, Sie greifen "seriell" auf sie zu - wenn dies sequentiell alphabetisch bedeutet, gibt Ihnen der Versuch natürlich auch kostenlos eine alphabetische Reihenfolge, wenn Sie sie mit der Tiefe zuerst wiederholen.

AKTUALISIEREN:

Wie Mark feststellte, gibt es nach dem Aufwärmen der JVM keinen signifikanten Unterschied (mehrere Testdurchläufe). Überprüft mit einem neu erstellten Array oder sogar einem neuen Durchgang, beginnend mit einer neuen Matrixzeile. Mit großer Wahrscheinlichkeit darf dieses einfache Array mit Indexzugriff nicht zugunsten von Sammlungen verwendet werden.

Noch erste 1-2 Durchgänge einfaches Array ist 2-3 mal schneller.

ORIGINAL POST:

Zu viele Wörter für das Thema zu einfach zu überprüfen. Ohne Frage ist das Array um ein Vielfaches schneller als jeder Klassencontainer . Ich gehe auf diese Frage ein und suche nach Alternativen für meinen leistungskritischen Abschnitt. Hier ist der Prototyp-Code, den ich erstellt habe, um die reale Situation zu überprüfen:

import java.util.List;
import java.util.Arrays;

public class IterationTest {

    private static final long MAX_ITERATIONS = 1000000000;

    public static void main(String [] args) {

        Integer [] array = {1, 5, 3, 5};
        List<Integer> list = Arrays.asList(array);

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i) {
//            for (int e : array) {
            for (int e : list) {
                test_sum += e;
            }
        }
        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }
}

Und hier ist die Antwort:

Basierend auf dem Array (Zeile 16 ist aktiv):

Time: 7064

Basierend auf der Liste (Zeile 17 ist aktiv):

Time: 20950

Noch ein Kommentar zu 'schneller'? Das ist ganz klar. Die Frage ist, wann ungefähr 3 mal schneller für Sie besser ist als die Flexibilität von List. Aber das ist eine andere Frage. Übrigens habe ich das auch anhand von manuell konstruierten überprüft ArrayList. Fast das gleiche Ergebnis.

Da es hier bereits viele gute Antworten gibt, möchte ich Ihnen einige weitere Informationen zur praktischen Sichtweise geben, nämlich den Vergleich der Einfügung und der Iterationsleistung: primitives Array vs. verknüpfte Liste in Java.

Dies ist eine einfache Leistungsprüfung.
Das Ergebnis hängt also von der Maschinenleistung ab.

Der dafür verwendete Quellcode ist unten:

import java.util.Iterator;
import java.util.LinkedList;

public class Array_vs_LinkedList {

    private final static int MAX_SIZE = 40000000;

    public static void main(String[] args) {

        LinkedList lList = new LinkedList(); 

        /* insertion performance check */

        long startTime = System.currentTimeMillis();

        for (int i=0; i<MAX_SIZE; i++) {
            lList.add(i);
        }

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");

        int[] arr = new int[MAX_SIZE];

        startTime = System.currentTimeMillis();
        for(int i=0; i<MAX_SIZE; i++){
            arr[i] = i; 
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        /* iteration performance check */

        startTime = System.currentTimeMillis();

        Iterator itr = lList.iterator();

        while(itr.hasNext()) {
            itr.next();
            // System.out.println("Linked list running : " + itr.next());
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        startTime = System.currentTimeMillis();

        int t = 0;
        for (int i=0; i < MAX_SIZE; i++) {
            t = arr[i];
            // System.out.println("array running : " + i);
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    }
}

Das Leistungsergebnis ist unten aufgeführt:

Liste ist langsamer als Arrays. Wenn Sie Effizienz benötigen, verwenden Sie Arrays. Wenn Sie Flexibilität benötigen, verwenden Sie Liste.

Denken Sie daran, dass eine ArrayList ein Array kapselt, sodass es kaum einen Unterschied zur Verwendung eines primitiven Arrays gibt (mit Ausnahme der Tatsache, dass die Arbeit mit einer Liste in Java viel einfacher ist).

Das einzige Mal, dass es sinnvoll ist, ein Array einer ArrayList vorzuziehen, ist, wenn Sie Grundelemente, dh Byte, Int usw., speichern und die besondere Raumeffizienz benötigen, die Sie durch die Verwendung primitiver Arrays erhalten.

Die Auswahl von Array vs. Liste ist (unter Berücksichtigung der Leistung) beim Speichern von Zeichenfolgenobjekten nicht so wichtig. Da sowohl das Array als auch die Liste Zeichenfolgenobjektreferenzen speichern, nicht die tatsächlichen Objekte.

1. Wenn die Anzahl der Zeichenfolgen nahezu konstant ist, verwenden Sie ein Array (oder ArrayList). Wenn die Anzahl jedoch zu stark variiert, sollten Sie LinkedList verwenden.
2. Wenn in der Mitte Elemente hinzugefügt oder gelöscht werden müssen (oder werden), müssen Sie auf jeden Fall LinkedList verwenden.

Ich bin hierher gekommen, um ein besseres Gefühl für die Auswirkungen der Verwendung von Listen über Arrays auf die Leistung zu bekommen. Ich musste hier den Code für mein Szenario anpassen: Array / Liste von ~ 1000 Ints, wobei hauptsächlich Getter verwendet wurden, was Array [j] vs. list.get (j) bedeutet.

Wenn ich das Beste aus 7 nehme, um unwissenschaftlich zu sein (die ersten mit einer Liste, in der 2,5x langsamer), bekomme ich Folgendes:

array Integer[] best 643ms iterator
ArrayList<Integer> best 1014ms iterator

array Integer[] best 635ms getter
ArrayList<Integer> best 891ms getter (strange though)

- also sehr ungefähr 30% schneller mit Array

Der zweite Grund für die Veröffentlichung ist, dass niemand die Auswirkungen erwähnt, wenn Sie Mathematik / Matrix / Simulation / Optimierungscode mit verschachtelten Schleifen ausführen .

Angenommen, Sie haben drei verschachtelte Ebenen und die innere Schleife ist doppelt so langsam, wie Sie es beim 8-fachen Leistungstreffer sehen. Etwas, das an einem Tag laufen würde, dauert jetzt eine Woche.

* EDIT Ziemlich schockiert hier, für Kicks habe ich versucht, int [1000] anstatt Integer [1000] zu deklarieren.

array int[] best 299ms iterator
array int[] best 296ms getter

Die Verwendung von Integer [] vs. int [] stellt einen doppelten Leistungstreffer dar. ListArray mit Iterator ist dreimal langsamer als int []. Ich dachte wirklich, Javas Listenimplementierungen ähneln nativen Arrays ...

Referenzcode (mehrmals anrufen):

    public static void testArray()
    {
        final long MAX_ITERATIONS = 1000000;
        final int MAX_LENGTH = 1000;

        Random r = new Random();

        //Integer[] array = new Integer[MAX_LENGTH];
        int[] array = new int[MAX_LENGTH];

        List<Integer> list = new ArrayList<Integer>()
        {{
            for (int i = 0; i < MAX_LENGTH; ++i)
            {
                int val = r.nextInt();
                add(val);
                array[i] = val;
            }
        }};

        long start = System.currentTimeMillis();
        int test_sum = 0;
        for (int i = 0; i < MAX_ITERATIONS; ++i)
        {
//          for (int e : array)
//          for (int e : list)          
            for (int j = 0; j < MAX_LENGTH; ++j)
            {
                int e = array[j];
//              int e = list.get(j);
                test_sum += e;
            }
        }

        long stop = System.currentTimeMillis();

        long ms = (stop - start);
        System.out.println("Time: " + ms);
    }

Wenn Sie im Voraus wissen, wie groß die Daten sind, ist ein Array schneller.

Eine Liste ist flexibler. Sie können eine ArrayList verwenden, die von einem Array unterstützt wird.

Wenn Sie mit einer festen Größe leben können, sind Arrays schneller und benötigen weniger Speicher.

Wenn Sie die Flexibilität der List-Oberfläche beim Hinzufügen und Entfernen von Elementen benötigen, bleibt die Frage, welche Implementierung Sie wählen sollten. Oft wird ArrayList empfohlen und in jedem Fall verwendet, aber auch ArrayList hat Leistungsprobleme, wenn Elemente am Anfang oder in der Mitte der Liste entfernt oder eingefügt werden müssen.

Vielleicht möchten Sie deshalb einen Blick auf http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list werfen, in dem GapList vorgestellt wird. Diese neue Listenimplementierung kombiniert die Stärken von ArrayList und LinkedList und führt zu einer sehr guten Leistung für nahezu alle Vorgänge.

Abhängig von der Implementierung. Es ist möglich, dass ein Array primitiver Typen kleiner und effizienter als ArrayList ist. Dies liegt daran, dass das Array die Werte direkt in einem zusammenhängenden Speicherblock speichert, während die einfachste ArrayList-Implementierung Zeiger auf jeden Wert speichert. Insbesondere auf einer 64-Bit-Plattform kann dies einen großen Unterschied machen.

Natürlich kann die jvm-Implementierung einen speziellen Fall für diese Situation haben. In diesem Fall ist die Leistung dieselbe.

List ist die bevorzugte Methode in Java 1.5 und höher, da Generika verwendet werden können. Arrays können keine Generika haben. Auch Arrays haben eine vordefinierte Länge, die nicht dynamisch wachsen kann. Das Initialisieren eines Arrays mit einer großen Größe ist keine gute Idee. Mit ArrayList können Sie ein Array mit Generika deklarieren und es kann dynamisch wachsen. Wenn Löschen und Einfügen jedoch häufiger verwendet wird, ist die verknüpfte Liste die am schnellsten zu verwendende Datenstruktur.

Überall empfohlene Arrays können anstelle der Liste verwendet werden, insbesondere wenn Sie wissen, dass sich Anzahl und Größe der Elemente nicht ändern würden.

Siehe Best Practice für Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

Wenn Sie Objekte hinzufügen und aus der Sammlung entfernen müssen, verwenden Sie natürlich einfach Listen.

Keine der Antworten enthielt Informationen, an denen ich interessiert war - wiederholtes Scannen desselben Arrays viele Male. Musste dafür einen JMH-Test erstellen.

Ergebnisse (Java 1.8.0_66 x32, iterierendes einfaches Array ist mindestens fünfmal schneller als ArrayList):

Benchmark                    Mode  Cnt   Score   Error  Units
MyBenchmark.testArrayForGet  avgt   10   8.121 ? 0.233  ms/op
MyBenchmark.testListForGet   avgt   10  37.416 ? 0.094  ms/op
MyBenchmark.testListForEach  avgt   10  75.674 ? 1.897  ms/op

Prüfung

package my.jmh.test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Fork(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class MyBenchmark {

    public final static int ARR_SIZE = 100;
    public final static int ITER_COUNT = 100000;

    String arr[] = new String[ARR_SIZE];
    List<String> list = new ArrayList<>(ARR_SIZE);

    public MyBenchmark() {
        for( int i = 0; i < ARR_SIZE; i++ ) {
            list.add(null);
        }
    }

    @Benchmark
    public void testListForEach() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( String str : list ) {
                if( str != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

    @Benchmark
    public void testListForGet() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( int j = 0; j < ARR_SIZE; j++ ) {
                if( list.get(j) != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

    @Benchmark
    public void testArrayForGet() {
        int count = 0;
        for( int i = 0; i < ITER_COUNT; i++ ) {
            for( int j = 0; j < ARR_SIZE; j++ ) {
                if( arr[j] != null )
                    count++;
            }
        }
        if( count > 0 )
            System.out.print(count);
    }

}

"Tausende" ist keine große Zahl. Einige tausend Zeichenfolgen mit Absatzlänge liegen in der Größenordnung von einigen Megabyte. Wenn Sie nur seriell auf diese zugreifen möchten, verwenden Sie eine unveränderliche, einfach verknüpfte Liste .

Gehen Sie nicht in die Falle der Optimierung ohne angemessenes Benchmarking. Wie andere vorgeschlagen haben, verwenden Sie einen Profiler, bevor Sie eine Annahme treffen.

Die verschiedenen Datenstrukturen, die Sie aufgezählt haben, haben unterschiedliche Zwecke. Eine Liste ist sehr effizient beim Einfügen von Elementen am Anfang und am Ende, leidet jedoch stark unter dem Zugriff auf zufällige Elemente. Ein Array verfügt über einen festen Speicher, bietet jedoch einen schnellen Direktzugriff. Schließlich verbessert eine ArrayList die Schnittstelle zu einem Array, indem es es wachsen lässt. Normalerweise sollte die zu verwendende Datenstruktur davon abhängen, wie auf die gespeicherten Daten zugegriffen oder diese hinzugefügt werden.

Informationen zum Speicherverbrauch. Sie scheinen einige Dinge zu mischen. Ein Array gibt Ihnen nur einen kontinuierlichen Speicherblock für den Datentyp, über den Sie verfügen. Vergessen Sie nicht, dass Java einen festen Datentyp hat: boolean, char, int, long, float und Object (dies schließt alle Objekte ein, auch ein Array ist ein Objekt). Wenn Sie ein Array von String-Zeichenfolgen [1000] oder MyObject myObjects [1000] deklarieren, erhalten Sie nur 1000 Speicherfelder, die groß genug sind, um die Position (Referenzen oder Zeiger) der Objekte zu speichern. Sie erhalten nicht 1000 Speicherboxen, die groß genug sind, um der Größe der Objekte zu entsprechen. Vergessen Sie nicht, dass Ihre Objekte zuerst mit "neu" erstellt werden. Dies ist der Fall, wenn die Speicherzuordnung abgeschlossen ist und später eine Referenz (ihre Speicheradresse) im Array gespeichert wird. Das Objekt wird nicht nur als Referenz in das Array kopiert.

Ich denke nicht, dass es für Strings einen wirklichen Unterschied macht. Was in einem Array von Strings zusammenhängend ist, sind die Verweise auf die Strings. Die Strings selbst werden an zufälligen Stellen im Speicher gespeichert.

Arrays vs. Listen können für primitive Typen einen Unterschied machen, nicht für Objekte. Wenn Sie die Anzahl der Elemente im Voraus kennen und keine Flexibilität benötigen, ist ein Array von Millionen von Ganzzahlen oder Doppelwerten im Speicher effizienter und geringfügig schneller als eine Liste, da sie tatsächlich zusammenhängend gespeichert werden und sofort abgerufen werden. Aus diesem Grund verwendet Java immer noch Zeichenfelder für Zeichenfolgen, Intra-Arrays für Bilddaten usw.

Array ist schneller - der gesamte Speicher wird im Voraus vorab zugewiesen.

Viele der hier angegebenen Mikrobenchmarks haben Zahlen von wenigen Nanosekunden für Dinge wie Array / ArrayList-Lesevorgänge gefunden. Dies ist durchaus sinnvoll, wenn sich alles in Ihrem L1-Cache befindet.

Ein Cache auf höherer Ebene oder ein Hauptspeicherzugriff kann Größenordnungen von etwa 10nS-100nS aufweisen, im Gegensatz zu 1nS für den L1-Cache. Der Zugriff auf eine ArrayList hat eine zusätzliche Speicher-Indirektion, und in einer realen Anwendung können Sie diese Kosten von fast nie bis jedes Mal bezahlen, je nachdem, was Ihr Code zwischen den Zugriffen tut. Und wenn Sie viele kleine ArrayLists haben, kann dies natürlich zu Ihrer Speichernutzung beitragen und die Wahrscheinlichkeit erhöhen, dass Cache-Fehler auftreten.

Das Originalplakat scheint nur eines zu verwenden und in kurzer Zeit auf viele Inhalte zuzugreifen, daher sollte es keine große Schwierigkeit sein. Bei anderen Personen kann dies jedoch anders sein, und Sie sollten bei der Interpretation von Mikrobenchmarks aufpassen.

Java-Zeichenfolgen sind jedoch erschreckend verschwenderisch, insbesondere wenn Sie viele kleine Zeichenfolgen speichern (sehen Sie sie sich nur mit einem Speicheranalysator an, es scheint> 60 Byte für eine Zeichenfolge mit wenigen Zeichen zu sein). Ein Array von Strings hat eine Indirektion zum String-Objekt und eine andere vom String-Objekt zu einem char [], das den String selbst enthält. Wenn irgendetwas Ihren L1-Cache sprengen wird, dann mit Tausenden oder Zehntausenden von Strings. Wenn Sie es also ernst meinen - wirklich ernst -, so viel Leistung wie möglich herauszuholen, könnten Sie es anders sehen. Sie könnten beispielsweise zwei Arrays halten, ein char [] mit allen Zeichenfolgen nacheinander und ein int [] mit Offsets zu den Starts. Dies wird eine PITA sein, mit der man alles machen kann, und man braucht sie mit ziemlicher Sicherheit nicht. Und wenn du das tust, bist du '

Es hängt davon ab, wie Sie darauf zugreifen müssen.

Wenn Sie nach dem Speichern hauptsächlich Suchvorgänge mit wenig oder keinem Einfügen / Löschen ausführen möchten, wählen Sie Array (da die Suche in O (1) in Arrays erfolgt, während beim Hinzufügen / Löschen möglicherweise die Elemente neu angeordnet werden müssen). .

Wenn Sie nach dem Speichern hauptsächlich Zeichenfolgen mit wenig oder keiner Suchoperation hinzufügen / löschen möchten, wählen Sie Liste.

ArrayList verwendet intern ein Array-Objekt, um die Elemente hinzuzufügen (oder zu speichern). Mit anderen Worten, ArrayList wird durch die Array-Datenstruktur unterstützt. Das Array von ArrayList kann in der Größe geändert (oder dynamisch) werden.

Array ist schneller als Array, da ArrayList das Array intern verwendet. Wenn wir Elemente direkt in Array hinzufügen und indirekt Elemente in Array über ArrayList hinzufügen können, ist der direkte Mechanismus immer schneller als der indirekte Mechanismus.

In der ArrayList-Klasse gibt es zwei überladene add () -Methoden:
1 . add(Object) : Fügt ein Objekt am Ende der Liste hinzu.
2 . add(int index , Object ) : Fügt das angegebene Objekt an der angegebenen Position in die Liste ein.

Wie wächst die Größe von ArrayList dynamisch?

public boolean add(E e)        
{       
     ensureCapacity(size+1);
     elementData[size++] = e;         
     return true;
}

Ein wichtiger Punkt aus dem obigen Code ist, dass wir die Kapazität der ArrayList überprüfen, bevor wir das Element hinzufügen. sureCapacity () bestimmt die aktuelle Größe der belegten Elemente und die maximale Größe des Arrays. Wenn die Größe der gefüllten Elemente (einschließlich des neuen Elements, das der ArrayList-Klasse hinzugefügt werden soll) größer als die maximale Größe des Arrays ist, erhöhen Sie die Größe des Arrays. Die Größe des Arrays kann jedoch nicht dynamisch erhöht werden. Intern geschieht also, dass ein neues Array mit Kapazität erstellt wird

Bis Java 6

int newCapacity = (oldCapacity * 3)/2 + 1;

(Update) Von Java 7

 int newCapacity = oldCapacity + (oldCapacity >> 1);

Außerdem werden Daten aus dem alten Array in das neue Array kopiert.

Overhead-Methoden in ArrayList sind daher schneller als ArrayList.

Arrays - Es wäre immer besser, wenn wir schneller Ergebnisse abrufen müssten

Listen - Führt Ergebnisse beim Einfügen und Löschen aus, da sie in O (1) ausgeführt werden können. Dies bietet auch Methoden zum einfachen Hinzufügen, Abrufen und Löschen von Daten. Viel einfacher zu bedienen.

Denken Sie jedoch immer daran, dass das Abrufen von Daten schnell erfolgen würde, wenn die Indexposition in dem Array, in dem die Daten gespeichert sind, bekannt ist.

Dies könnte gut durch Sortieren des Arrays erreicht werden. Daher erhöht dies die Zeit zum Abrufen der Daten (dh Speichern der Daten + Sortieren der Daten + Suchen nach der Position, an der die Daten gefunden werden). Daher erhöht dies die zusätzliche Latenz, um die Daten aus dem Array abzurufen, selbst wenn sie die Daten früher abrufen können.

Daher könnte dies mit einer Datenstruktur oder einer ternären Datenstruktur gelöst werden. Wie oben diskutiert, wäre die Trie-Datenstruktur beim Suchen nach den Daten sehr effizient. Die Suche nach einem bestimmten Wort kann in der Größe O (1) durchgeführt werden. Wenn Zeit zählt, dh; Wenn Sie Daten schnell suchen und abrufen müssen, können Sie sich für die Datenstruktur entscheiden.

Wenn Sie möchten, dass Ihr Speicherplatz weniger beansprucht wird und Sie eine bessere Leistung erzielen möchten, wählen Sie die ternäre Datenstruktur. Beide eignen sich zum Speichern einer großen Anzahl von Zeichenfolgen (z. B. Wörter, die im Wörterbuch enthalten sind).