Quelle liste < Objet > la mise en œuvre sera la plus rapide pour un passage écrire, lire, puis détruire?

Question

Quelle est l’implémentation la plus rapide de la liste (en java) dans un scénario où la liste sera créée élément par élément, puis lue ultérieurement, élément par élément? Les lectures se feront avec un itérateur, puis la liste sera détruite.
Je sais que la notation Big O pour get est O (1) et add est O (1) pour ArrayList, tandis que LinkedList est O (n) pour get et O (1) pour add. L'itérateur se comporte-t-il avec la même notation Big O?

Answer 1

Cela dépend en grande partie de votre connaissance préalable de la taille maximale de chaque liste.

Si vous le faites, utilisez ArrayList ; ce sera certainement plus rapide.

Sinon, vous devrez probablement profiler. Bien que l'accès à ArrayList soit défini sur O (1), sa création n'est pas aussi simple en raison du redimensionnement dynamique.

Un autre point à considérer est que le compromis espace-temps n’est pas clairement défini. Chaque objet Java a un peu de surcharge. Bien qu'un ArrayList puisse gaspiller de l'espace sur les emplacements en surplus, chaque emplacement ne contient que 4 octets (ou 8 sur une machine virtuelle Java 64 bits). Chaque élément d'une LinkedList représente probablement environ 50 octets (peut-être 100 dans une JVM 64 bits). Vous devez donc disposer de plusieurs emplacements inutilisés dans un ArrayList avant qu'un LinkedList ne gagne réellement son avantage d'espace présumé. La localisation de la référence est également un facteur, et ArrayList y est également préférable.

En pratique, j'utilise presque toujours ArrayList .

Answer 2

Premières réflexions:

• Refactorisez votre code pour ne pas avoir besoin de la liste.
• Simplifiez les données jusqu'à un type de données scalaire, puis utilisez: int []
• Ou même, utilisez simplement un tableau d'objets de votre choix: Objet [] - John Gardner
• Initialisez la liste à la taille complète: new ArrayList (123);

Bien sûr, comme tout le monde le dit, effectuez des tests de performance, montrez que votre nouvelle solution est une amélioration.

Answer 3

Itérer dans une liste chaînée est O (1) par élément.

Le runtime Big O est le même pour chaque option. ArrayList sera probablement plus rapide grâce à une meilleure localisation mémoire, mais vous devrez le mesurer pour le savoir avec certitude. Choisissez ce qui rend le code le plus clair.

Answer 4

Notez que itérer via une instance de LinkedList peut être O (n ^ 2) si cela est fait naïvement. Plus précisément:

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

C’est absolument horrible en termes d’efficacité car la liste doit être parcourue jusqu’à i deux fois à chaque itération. Si vous utilisez LinkedList , veillez à utiliser un Iterator ou le amélioré de Java 5 pour -loop:

.

for (Object o : list) {
    // ...
}

Le code ci-dessus est O (n), car la liste est traversée de manière fixe sur place.

Pour éviter les tracas ci-dessus, utilisez simplement ArrayList . Ce n’est pas toujours le meilleur choix (en particulier pour l’économie de l'espace), mais c'est généralement une valeur sûre.

Answer 5

Je suggère de l’analyser. C’est une chose de lire l’API, mais jusqu’à ce que vous l’essayiez vous-même, c’est théorique.

Devrait être assez facile à tester, assurez-vous simplement que vous effectuez des opérations significatives, sinon hotspot vous intelligera et optimisera tout pour un NO-OP:)

Answer 6

Vous souhaitez certainement créer une liste de tableaux . L’ajout et la lecture sont à la fois "amortis à temps constant" et (ie O (1)) comme spécifié dans la documentation (notez que ceci est vrai même si la liste doit augmenter sa taille - elle est conçue comme ça, voir http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html ). Si vous connaissez à peu près le nombre d'objets que vous allez stocker, même l'augmentation de la taille de ArrayList est éliminée.

L'ajout à la fin d'une liste chaînée est O (1), mais le multiplicateur constant est supérieur à ArrayList (étant donné que vous créez généralement un objet nœud à chaque fois). La lecture est pratiquement identique à ArrayList si vous utilisez un itérateur.

C’est une bonne règle de toujours utiliser la structure la plus simple possible, sauf s’il ya une bonne raison de ne pas le faire. Ici, la raison n’existe pas.

La citation exacte de la documentation de ArrayList est la suivante: "L'opération add s'exécute en temps constant amorti, c'est-à-dire que l'ajout de n éléments nécessite un temps O (n). Toutes les autres opérations se déroulent en temps linéaire (en gros). Le facteur constant est faible par rapport à celui de l’implémentation de LinkedList. "

Answer 7

Une nouvelle implémentation de la liste appelée GlueList est plus rapide que toutes les implémentations classiques de la liste.

Answer 8

J'ai en fait commencé à penser que toute utilisation de structures de données à comportement non déterministe, telles que ArrayList ou HashMap, devrait être évitée. Par conséquent, je dirais que vous n'utilisez ArrayList que si vous pouvez limiter sa taille; toute liste non limitée utilise LinkedList. C’est parce que je code principalement des systèmes avec des exigences en temps quasi-réel.

Le principal problème est que toute allocation de mémoire (ce qui pourrait se produire de manière aléatoire avec n'importe quelle opération d'ajout) pourrait également entraîner un nettoyage de la mémoire, ce qui pourrait vous faire perdre une cible. Plus l'attribution est importante, plus cela est susceptible de se produire. Cette situation est également aggravée si vous utilisez CMS Collector. Le système de gestion de contenu étant non compact, il est généralement plus facile de trouver de la place pour un nouveau nœud de liste liée que pour un nouveau tableau de 10 000 éléments.

Plus votre approche de codage est rigoureuse, plus vous pouvez vous rapprocher du temps réel avec une JVM standard. Mais choisir uniquement des structures de données ayant un comportement déterministe est l’une des premières étapes à franchir.