Je dois garder des milliers de chaînes en mémoire pour pouvoir y accéder en série en Java. Dois-je les stocker dans un tableau ou dois-je utiliser une sorte de liste?

Étant donné que les tableaux conservent toutes les données dans un bloc de mémoire contigu (contrairement aux listes), l'utilisation d'un tableau pour stocker des milliers de chaînes poserait-elle des problèmes?

Je vous suggère d'utiliser un profileur pour tester ce qui est plus rapide.

Mon opinion personnelle est que vous devriez utiliser les listes.

Je travaille sur une grande base de code et un groupe précédent de développeurs utilisait des tableaux partout . Cela a rendu le code très rigide. Après avoir changé de gros morceaux en listes, nous n'avons remarqué aucune différence de vitesse.

La manière Java est que vous devriez considérer quelle abstraction de données convient le mieux à vos besoins. N'oubliez pas qu'en Java, une liste est un type de données abstrait et non concret. Vous devez déclarer les chaînes comme une liste, puis l'initialiser à l'aide de l'implémentation ArrayList.

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

Cette séparation du type de données abstrait et de l'implémentation spécifique est l'un des aspects clés de la programmation orientée objet.

Un ArrayList implémente le type de données abstrait de liste en utilisant un tableau comme implémentation sous-jacente. La vitesse d'accès est pratiquement identique à un tableau, avec les avantages supplémentaires de pouvoir ajouter et soustraire des éléments à une liste (bien qu'il s'agisse d'une opération O (n) avec une liste de tableaux) et que si vous décidez de modifier l'implémentation sous-jacente plus tard vous pouvez. Par exemple, si vous réalisez que vous avez besoin d'un accès synchronisé, vous pouvez changer l'implémentation en un vecteur sans réécrire tout votre code.

En fait, ArrayList a été spécialement conçu pour remplacer la construction de tableaux de bas niveau dans la plupart des contextes. Si Java était en cours de conception aujourd'hui, il est tout à fait possible que les tableaux aient été totalement exclus en faveur de la construction ArrayList.

Étant donné que les tableaux conservent toutes les données dans un bloc de mémoire contigu (contrairement aux listes), l'utilisation d'un tableau pour stocker des milliers de chaînes poserait-elle des problèmes?

En Java, toutes les collections stockent uniquement les références aux objets, pas les objets eux-mêmes. Les tableaux et ArrayList stockent quelques milliers de références dans un tableau contigu, ils sont donc essentiellement identiques. Vous pouvez considérer qu'un bloc contigu de quelques milliers de références 32 bits sera toujours facilement disponible sur le matériel moderne. Cela ne garantit pas que vous ne manquerez pas complètement de mémoire, bien sûr, juste que le bloc contigu de mémoire requise n'est pas difficile à remplir.

Bien que les réponses proposant d'utiliser ArrayList aient un sens dans la plupart des scénarios, la question réelle des performances relatives n'a pas vraiment été résolue.

Il y a quelques choses que vous pouvez faire avec un tableau:

• le créer
• définir un élément
• obtenir un article
• cloner / copier

Conclusion générale

Bien que les opérations get et set soient un peu plus lentes sur une ArrayList (resp. 1 et 3 nanosecondes par appel sur ma machine), il y a très peu de temps supplémentaire pour utiliser une ArrayList par rapport à une baie pour toute utilisation non intensive. Il y a cependant quelques points à garder à l'esprit:

• le redimensionnement des opérations sur une liste (lors de l'appel list.add(...)) est coûteux et il convient d'essayer de définir la capacité initiale à un niveau adéquat lorsque cela est possible (notez que le même problème se pose lors de l'utilisation d'un tableau)
• lorsqu'il s'agit de primitives, les tableaux peuvent être beaucoup plus rapides car ils permettent d'éviter de nombreuses conversions boxing / unboxing
• une application qui obtient / définit uniquement des valeurs dans une ArrayList (pas très courant!) pourrait voir un gain de performances de plus de 25% en passant à un tableau

Résultats détaillés

Voici les résultats que j'ai mesurés pour ces trois opérations en utilisant la bibliothèque d'analyse comparative jmh (temps en nanosecondes) avec JDK 7 sur une machine de bureau x86 standard. Notez que ArrayList n'est jamais redimensionné dans les tests pour s'assurer que les résultats sont comparables. Code de référence disponible ici .

Création de tableaux / tableaux

J'ai exécuté 4 tests, exécutant les instructions suivantes:

• 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);

Résultats (en nanosecondes par appel, confiance à 95%):

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]

Conclusion: pas de différence notable .

obtenir des opérations

J'ai exécuté 2 tests, exécutant les instructions suivantes:

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

Résultats (en nanosecondes par appel, confiance à 95%):

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

Conclusion: obtenir à partir d'un tableau est environ 25% plus rapide que d'obtenir à partir d'une ArrayList, bien que la différence ne soit que de l'ordre de la nanoseconde.

définir les opérations

J'ai exécuté 2 tests, exécutant les instructions suivantes:

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

Résultats (en nanosecondes par appel):

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

Conclusion: les opérations de définition sur les tableaux sont environ 40% plus rapides que sur les listes, mais, comme pour get, chaque opération de définition prend quelques nanosecondes - pour que la différence atteigne 1 seconde, il faudrait définir des éléments dans la liste / le tableau des centaines des millions de fois!

cloner / copier

Les délégués constructeur de copie de ArrayList à Arrays.copyOfsi le rendement est identique à la copie de matrice (copie d' une matrice via clone, Arrays.copyOfou ne System.arrayCopy fait aucune différence en terme de performance matériel ).

Vous devriez préférer les types génériques aux tableaux. Comme mentionné par d'autres, les tableaux sont inflexibles et n'ont pas le pouvoir expressif des types génériques. (Ils prennent cependant en charge la vérification de typage à l'exécution, mais cela se mélange mal avec les types génériques.)

Mais, comme toujours, lors de l'optimisation, vous devez toujours suivre ces étapes:

• N'optimisez pas avant d'avoir une version agréable, propre et fonctionnelle de votre code. Le passage aux types génériques pourrait très bien être déjà motivé à cette étape.
• Lorsque vous avez une version agréable et propre, décidez si elle est assez rapide.
• S'il n'est pas assez rapide, mesurez ses performances . Cette étape est importante pour deux raisons. Si vous ne mesurez pas, vous (1) ne connaîtrez pas l'impact des optimisations que vous effectuez et (2) ne saurez pas où optimiser.
• Optimisez la partie la plus chaude de votre code.
• Mesurez à nouveau. C'est tout aussi important que de mesurer avant. Si l'optimisation n'a pas amélioré les choses, revenez-y . N'oubliez pas que le code sans optimisation était propre, agréable et fonctionnel.

Je suppose que l'affiche d'origine provient d'un arrière-plan C ++ / STL, ce qui crée une certaine confusion. En C ++ std::listest une liste doublement liée.

En Java [java.util.]Listest une interface sans implémentation (pure classe abstraite en termes C ++). Listpeut être une liste doublement liée - java.util.LinkedListest fournie. Cependant, 99 fois sur 100 lorsque vous voulez en créer un nouveau List, vous souhaitez l'utiliser à la java.util.ArrayListplace, ce qui est l'équivalent approximatif de C ++ std::vector. Il existe d'autres implémentations standard, telles que celles renvoyées par java.util.Collections.emptyList()et java.util.Arrays.asList().

Du point de vue des performances, il est très difficile de passer par une interface et un objet supplémentaire, mais la mise en ligne d'exécution signifie que cela a rarement une signification. Souvenez-vous également qu'il Strings'agit généralement d'un objet et d'un tableau. Donc, pour chaque entrée, vous avez probablement deux autres objets. En C ++ std::vector<std::string>, bien que la copie par valeur sans pointeur en tant que tel, les tableaux de caractères forment un objet pour la chaîne (et ceux-ci ne sont généralement pas partagés).

Si ce code particulier est vraiment sensible aux performances, vous pouvez créer un seul char[]tableau (ou même byte[]) pour tous les caractères de toutes les chaînes, puis un tableau de décalages. IIRC, c'est ainsi que javac est implémenté.

Je suis d'accord que dans la plupart des cas, vous devriez choisir la flexibilité et l'élégance des ArrayLists par rapport aux tableaux - et dans la plupart des cas, l'impact sur les performances du programme sera négligeable.

Cependant, si vous effectuez une itération constante et lourde avec peu de changements structurels (sans ajout ni suppression) pour, par exemple, le rendu graphique de logiciels ou une machine virtuelle personnalisée, mes tests d'analyse comparative d'accès séquentiel montrent que les listes de tableaux sont 1,5 fois plus lentes que les tableaux sur mon système (Java 1.6 sur mon iMac d'un an).

Du 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
    }
}

Eh bien tout d'abord, il vaut la peine de clarifier voulez-vous dire «liste» dans le sens classique des structures de données comp sci (c'est-à-dire une liste liée) ou voulez-vous dire java.util.List? Si vous voulez dire une java.util.List, c'est une interface. Si vous souhaitez utiliser un tableau, utilisez simplement l'implémentation ArrayList et vous obtiendrez un comportement et une sémantique de type tableau. Problème résolu.

Si vous voulez dire un tableau par rapport à une liste chaînée, c'est un argument légèrement différent pour lequel nous revenons à Big O (voici une explication simple en anglais s'il s'agit d'un terme inconnu.

Array;

• Accès aléatoire: O (1);
• Insérer: O (n);
• Supprimer: O (n).

Liste liée:

• Accès aléatoire: O (n);
• Insérer: O (1);
• Supprimer: O (1).

Vous choisissez donc celui qui convient le mieux à la façon dont vous redimensionnez votre baie. Si vous redimensionnez, insérez et supprimez beaucoup, alors une liste chaînée est peut-être un meilleur choix. Il en va de même si l'accès aléatoire est rare. Vous mentionnez l'accès série. Si vous faites principalement un accès série avec très peu de modifications, peu importe ce que vous choisissez.

Les listes liées ont un surcoût légèrement plus élevé car, comme vous le dites, vous avez affaire à des blocs de mémoire potentiellement non contigus et (effectivement) des pointeurs vers l'élément suivant. Ce n'est probablement pas un facteur important, sauf si vous avez affaire à des millions d'entrées.

J'ai écrit une petite référence pour comparer les listes de tableaux avec les tableaux. Sur mon ordinateur portable ancien, le temps de parcourir une liste de 5000 éléments, 1000 fois, était environ 10 millisecondes plus lent que le code de tableau équivalent.

Donc, si vous ne faites rien d'autre que d'itérer la liste, et que vous le faites beaucoup, alors peut-être que cela vaut la peine d'être optimisé. Sinon j'utiliser la liste, car il sera plus facile lorsque vous avez besoin d'optimiser le code.

NB Je l'ai fait remarquer que l' usage for String s: stringsListétait d' environ 50% plus lent que d' utiliser une ancienne boucle pour accéder à la liste. Allez comprendre ... Voici les deux fonctions que j'ai chronométrées; le tableau et la liste étaient remplis de 5000 chaînes aléatoires (différentes).

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();
        }
    }
}

Non, car techniquement, le tableau stocke uniquement la référence aux chaînes. Les chaînes elles-mêmes sont allouées à un emplacement différent. Pour mille articles, je dirais qu'une liste serait mieux, elle est plus lente, mais elle offre plus de flexibilité et elle est plus facile à utiliser, surtout si vous allez les redimensionner.

Si vous en avez des milliers, pensez à utiliser un trie. Un trie est une structure arborescente qui fusionne les préfixes communs de la chaîne stockée.

Par exemple, si les chaînes étaient

intern
international
internationalize
internet
internets

Le trie stockerait:

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

Les chaînes nécessitent 57 caractères (y compris le terminateur nul, «\ 0») pour le stockage, plus la taille de l'objet String qui les contient. (En vérité, nous devrions probablement arrondir toutes les tailles jusqu'à des multiples de 16, mais ...) Appelez-le à peu près 57 + 5 = 62 octets.

Le trie requiert 29 (y compris le terminateur nul, «\ 0») pour le stockage, plus la taille des nœuds de trie, qui sont une référence à un tableau et une liste de nœuds de trie enfants.

Pour cet exemple, cela sort probablement de la même manière; pour des milliers, il sort probablement moins tant que vous avez des préfixes communs.

Maintenant, lorsque vous utilisez le trie dans un autre code, vous devrez convertir en String, en utilisant probablement un StringBuffer comme intermédiaire. Si de nombreuses cordes sont utilisées en même temps comme cordes, en dehors du trie, c'est une perte.

Mais si vous n'en utilisez que quelques-uns à l'époque - par exemple, pour rechercher des choses dans un dictionnaire - le trie peut vous faire économiser beaucoup d'espace. Certainement moins d'espace que de les stocker dans un HashSet.

Vous dites que vous y accédez "en série" - si cela signifie séquentiellement et alphabétiquement, le trie vous donne également évidemment l'ordre alphabétique gratuitement, si vous l'itérez en profondeur en premier.

MISE À JOUR:

Comme Mark l'a noté, il n'y a pas de différence significative après l'échauffement de la JVM (plusieurs tests réussis). Vérifié avec un tableau recréé ou même une nouvelle passe commençant par une nouvelle ligne de matrice. Il est très probable que cela signifie qu'un tableau simple avec accès à un index ne doit pas être utilisé en faveur des collections.

Les premiers 1-2 passages simples sont toujours 2-3 fois plus rapides.

POSTE ORIGINAL:

Trop de mots pour le sujet trop simple à vérifier. Sans aucun tableau de questions est plusieurs fois plus rapide que n'importe quel conteneur de classe . Je cours sur cette question à la recherche d'alternatives pour ma section critique de performance. Voici le code prototype que j'ai construit pour vérifier la situation réelle:

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);
    }
}

Et voici la réponse:

Basé sur le tableau (la ligne 16 est active):

Time: 7064

Basé sur la liste (la ligne 17 est active):

Time: 20950

Avez-vous d'autres commentaires sur "plus vite"? C'est bien compris. La question est quand environ 3 fois plus vite est meilleur pour vous que la flexibilité de List. Mais c'est une autre question. Au fait, j'ai également vérifié cela sur la base de la construction manuelle ArrayList. Presque le même résultat.

Puisqu'il y a déjà beaucoup de bonnes réponses ici, je voudrais vous donner quelques autres informations de vue pratique, qui est la comparaison des performances d'insertion et d'itération: tableau primitif vs liste liée en Java.

Il s'agit d'une simple vérification des performances.
Ainsi, le résultat dépendra des performances de la machine.

Le code source utilisé pour cela est ci-dessous:

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.");
    }
}

Le résultat de performance est ci-dessous:

list est plus lent que les tableaux.Si vous avez besoin d'efficacité, utilisez des tableaux.Si vous avez besoin de flexibilité, utilisez list.

N'oubliez pas qu'une ArrayList encapsule un tableau, il y a donc peu de différence par rapport à l'utilisation d'un tableau primitif (sauf pour le fait qu'une liste est beaucoup plus facile à utiliser en java).

La seule fois où il est logique de préférer un tableau à une ArrayList est lorsque vous stockez des primitives, c'est-à-dire octet, entier, etc. et que vous avez besoin de l'espace particulièrement efficace que vous obtenez en utilisant des tableaux primitifs.

Le choix du tableau par rapport à la liste n'est pas si important (compte tenu des performances) dans le cas du stockage d'objets chaîne. Parce que le tableau et la liste stockent les références aux objets chaîne, et non les objets réels.

1. Si le nombre de chaînes est presque constant, utilisez un tableau (ou ArrayList). Mais si le nombre varie trop, vous feriez mieux d'utiliser LinkedList.
2. S'il est (ou sera) nécessaire d'ajouter ou de supprimer des éléments au milieu, vous devez certainement utiliser LinkedList.

Je suis venu ici pour mieux comprendre l'impact sur les performances de l'utilisation de listes sur des tableaux. J'ai dû adapter le code ici pour mon scénario: tableau / liste de ~ 1000 ints utilisant principalement des getters, ce qui signifie tableau [j] vs list.get (j)

Prenant le meilleur de 7 pour ne pas être scientifique à ce sujet (les premiers avec une liste où 2,5x plus lent) j'obtiens ceci:

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

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

- donc, environ 30% plus rapide avec le tableau

La deuxième raison de la publication est que personne ne mentionne l'impact si vous faites du code mathématique / matriciel / simulation / optimisation avec des boucles imbriquées .

Supposons que vous ayez trois niveaux imbriqués et que la boucle intérieure soit deux fois plus lente que vous regardez 8 fois les performances. Quelque chose qui se déroulerait en une journée prend maintenant une semaine.

* EDIT Assez choqué ici, pour les coups de pied, j'ai essayé de déclarer int [1000] plutôt que Integer [1000]

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

L'utilisation d'Integer [] par rapport à int [] représente un double gain de performances, ListArray avec itérateur est 3 fois plus lent que int []. Vraiment pensé que les implémentations de liste de Java étaient similaires aux tableaux natifs ...

Code de référence (appelez plusieurs fois):

    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);
    }

Si vous savez à l'avance la taille des données, un tableau sera plus rapide.

Une liste est plus flexible. Vous pouvez utiliser un ArrayList qui est soutenu par un tableau.

Si vous pouvez vivre avec une taille fixe, les tableaux seront plus rapides et nécessiteront moins de mémoire.

Si vous avez besoin de la flexibilité de l'interface List pour ajouter et supprimer des éléments, la question reste de savoir quelle implémentation vous devez choisir. Souvent, ArrayList est recommandé et utilisé dans tous les cas, mais ArrayList a également ses problèmes de performances si des éléments au début ou au milieu de la liste doivent être supprimés ou insérés.

Vous voudrez donc peut-être jeter un œil à http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list qui présente GapList. Cette nouvelle implémentation de liste combine les points forts d'ArrayList et de LinkedList, ce qui se traduit par de très bonnes performances pour presque toutes les opérations.

Selon l'implémentation. il est possible qu'un tableau de types primitifs soit plus petit et plus efficace que ArrayList. En effet, le tableau stockera les valeurs directement dans un bloc de mémoire contigu, tandis que l'implémentation ArrayList la plus simple stockera des pointeurs vers chaque valeur. Sur une plate-forme 64 bits en particulier, cela peut faire une énorme différence.

Bien sûr, il est possible que l'implémentation jvm ait un cas particulier pour cette situation, auquel cas les performances seront les mêmes.

La liste est la méthode préférée dans Java 1.5 et au-delà car elle peut utiliser des génériques. Les tableaux ne peuvent pas avoir de génériques. Les tableaux ont également une longueur prédéfinie, qui ne peut pas croître dynamiquement. L'initialisation d'un tableau avec une grande taille n'est pas une bonne idée. ArrayList est le moyen de déclarer un tableau avec des génériques et il peut croître dynamiquement. Mais si la suppression et l'insertion sont utilisées plus fréquemment, la liste liée est la structure de données la plus rapide à utiliser.

Les tableaux sont recommandés partout où vous pouvez les utiliser au lieu de la liste, surtout si vous savez que le nombre et la taille des éléments ne changeront pas.

Voir les meilleures pratiques Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

Bien sûr, si vous avez besoin d'ajouter et de supprimer des objets de la collection plusieurs fois, utilisez des listes faciles.

Aucune des réponses ne contenait d'informations qui m'intéressaient - analyse répétitive du même tableau plusieurs fois. J'ai dû créer un test JMH pour cela.

Résultats (Java 1.8.0_66 x32, l'itération d'un tableau simple est au moins 5 fois plus rapide que 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

Tester

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);
    }

}

"Des milliers" n'est pas un grand nombre. Quelques milliers de chaînes de longueur de paragraphe sont de l'ordre de quelques mégaoctets. Si tout ce que vous voulez faire, c'est y accéder en série, utilisez une liste immuable liée individuellement .

N'entrez pas dans le piège de l'optimisation sans analyse comparative appropriée. Comme d'autres l'ont suggéré, utilisez un profileur avant de faire une supposition.

Les différentes structures de données que vous avez énumérées ont des objectifs différents. Une liste est très efficace pour insérer des éléments au début et à la fin mais souffre beaucoup lors de l'accès à des éléments aléatoires. Une baie a un stockage fixe mais fournit un accès aléatoire rapide. Enfin, une ArrayList améliore l'interface d'un tableau en lui permettant de se développer. Normalement, la structure de données à utiliser doit être dictée par la façon dont les données stockées seront accessibles ou ajoutées.

À propos de la consommation de mémoire. Vous semblez mélanger certaines choses. Un tableau ne vous donnera qu'un morceau de mémoire continu pour le type de données que vous avez. N'oubliez pas que java a un type de données fixe: booléen, char, int, long, float et Object (cela inclut tous les objets, même un tableau est un objet). Cela signifie que si vous déclarez un tableau de chaînes de chaînes [1000] ou MyObject myObjects [1000], vous obtenez seulement 1000 boîtes de mémoire suffisamment grandes pour stocker l'emplacement (références ou pointeurs) des objets. Vous n'avez pas 1000 boîtes de mémoire assez grandes pour s'adapter à la taille des objets. N'oubliez pas que vos objets sont d'abord créés avec "nouveau". C'est lorsque l'allocation de mémoire est effectuée et plus tard une référence (leur adresse mémoire) est stockée dans le tableau. L'objet n'est pas copié dans le tableau mais seulement sa référence.

Je ne pense pas que cela fasse une réelle différence pour Strings. Ce qui est contigu dans un tableau de chaînes, ce sont les références aux chaînes, les chaînes elles-mêmes sont stockées à des endroits aléatoires en mémoire.

Les tableaux et les listes peuvent faire la différence pour les types primitifs, pas pour les objets. SI vous connaissez à l'avance le nombre d'éléments et n'avez pas besoin de flexibilité, un tableau de millions d'entiers ou de doubles sera plus efficace en mémoire et légèrement en vitesse qu'une liste, car en effet ils seront stockés de manière contiguë et accessibles instantanément. C'est pourquoi Java utilise toujours des tableaux de caractères pour les chaînes, des tableaux d'entiers pour les données d'image, etc.

La baie est plus rapide - toute la mémoire est préallouée à l'avance.

Un grand nombre de microbenchmarks donnés ici ont trouvé des nombres de quelques nanosecondes pour des choses comme les lectures array / ArrayList. C'est tout à fait raisonnable si tout est dans votre cache L1.

Un cache de niveau supérieur ou un accès à la mémoire principale peut avoir des temps d'ordre de grandeur de quelque chose comme 10nS-100nS, contre plus comme 1nS pour le cache L1. L'accès à une ArrayList a une indirection de mémoire supplémentaire, et dans une application réelle, vous pourriez payer ce coût de presque jamais à chaque fois, selon ce que fait votre code entre les accès. Et, bien sûr, si vous avez beaucoup de petites listes de tableaux, cela pourrait ajouter à votre utilisation de la mémoire et augmenter le risque de manquer de cache.

L'affiche originale semble en utiliser un seul et accéder à un grand nombre de contenus en peu de temps, donc cela ne devrait pas être très difficile. Mais cela peut être différent pour d'autres personnes, et vous devez faire attention lors de l'interprétation des microbenchmarks.

Les chaînes Java, cependant, sont terriblement inutiles, surtout si vous en stockez beaucoup de petites (regardez-les simplement avec un analyseur de mémoire, cela semble être> 60 octets pour une chaîne de quelques caractères). Un tableau de chaînes a une indirection vers l'objet String et une autre de l'objet String vers un char [] qui contient la chaîne elle-même. Si quelque chose va faire exploser votre cache L1, c'est cela, combiné à des milliers ou des dizaines de milliers de chaînes. Donc, si vous êtes sérieux - vraiment sérieux - pour éliminer autant de performances que possible, vous pouvez envisager de le faire différemment. Vous pouvez, par exemple, contenir deux tableaux, un char [] avec toutes les chaînes, un après l'autre, et un int [] avec des décalages au début. Ce sera un PITA pour faire quoi que ce soit, et vous n'en avez presque certainement pas besoin. Et si vous le faites, vous '

Cela dépend de la façon dont vous devez y accéder.

Après le stockage, si vous souhaitez principalement effectuer une opération de recherche, avec peu ou pas d'insertion / suppression, optez pour Array (car la recherche se fait dans O (1) dans les tableaux, tandis que l'ajout / suppression peut nécessiter un réordonnancement des éléments) .

Après le stockage, si votre objectif principal est d'ajouter / supprimer des chaînes, avec peu ou pas d'opération de recherche, optez pour la liste.

ArrayList utilise en interne un objet tableau pour ajouter (ou stocker) les éléments. En d'autres termes, ArrayList est soutenu par la structure de données Array. Le tableau d'ArrayList est redimensionnable (ou dynamique).

Array est plus rapide qu'Array car ArrayList utilise en interne un tableau. si nous pouvons ajouter directement des éléments dans Array et indirectement ajouter des éléments dans Array via ArrayList, le mécanisme est toujours directement plus rapide que le mécanisme indirect.

Il existe deux méthodes add () surchargées dans la classe ArrayList:
1 add(Object) .: ajoute un objet à la fin de la liste.
2 add(int index , Object ) .: insère l'objet spécifié à la position spécifiée dans la liste.

Comment la taille d'ArrayList augmente-t-elle dynamiquement?

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

Le point important à noter du code ci-dessus est que nous vérifions la capacité de la ArrayList, avant d'ajouter l'élément. assureCapacity () détermine quelle est la taille actuelle des éléments occupés et quelle est la taille maximale du tableau. Si la taille des éléments remplis (y compris le nouvel élément à ajouter à la classe ArrayList) est supérieure à la taille maximale du tableau, augmentez la taille du tableau. Mais la taille du tableau ne peut pas être augmentée dynamiquement. Donc, ce qui se passe en interne est que la nouvelle matrice est créée avec une capacité

Jusqu'à Java 6

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

(Mise à jour) Depuis Java 7

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

les données de l'ancien tableau sont également copiées dans le nouveau tableau.

Avoir des méthodes de surcharge dans ArrayList c'est pourquoi Array est plus rapide que ArrayList.

Tableaux - Il serait toujours préférable de récupérer plus rapidement les résultats

Listes - Effectue des résultats sur l'insertion et la suppression car ils peuvent être effectués dans O (1) et cela fournit également des méthodes pour ajouter, récupérer et supprimer des données facilement. Beaucoup plus facile à utiliser.

Mais rappelez-vous toujours que la récupération des données serait rapide lorsque la position d'index dans le tableau où les données sont stockées - est connue.

Cela pourrait être bien réalisé en triant le tableau. Par conséquent, cela augmente le temps nécessaire pour récupérer les données (c'est-à-dire; stocker les données + trier les données + rechercher la position où les données sont trouvées). Par conséquent, cela augmente la latence supplémentaire pour extraire les données de la baie même si elles peuvent être utiles pour extraire les données plus tôt.

Par conséquent, cela pourrait être résolu avec une structure de données trie ou une structure de données ternaire. Comme discuté ci-dessus, la structure de données trie serait très efficace pour rechercher les données, la recherche d'un mot en particulier peut être effectuée en magnitude O (1). Quand le temps compte, c'est-à-dire; si vous devez rechercher et récupérer des données rapidement, vous pouvez utiliser la structure de données trie.

Si vous souhaitez que votre espace mémoire soit moins consommé et que vous souhaitez avoir de meilleures performances, optez pour la structure de données ternaire. Ces deux sont adaptés pour stocker un grand nombre de chaînes (par exemple, comme les mots contenus dans le dictionnaire).