Insertion d'éléments dans une liste fréquemment triée par insertion

Question

J'ai une liste fréquemment triée par insertion. Y a-t-il une bonne position (autre que la fin) pour ajouter à cette liste afin de minimiser le travail que le tri d'insertion doit faire?

Answer 1

Le meilleur endroit à insérer serait l'endroit où l'élément appartient à la liste triée. Cela serait similaire au tri préemptif d'insertion.

Answer 2

Votre question n'a pas de sens. Soit la liste est triée par insertion (ce qui signifie que vous ne pouvez pas ajouter à la fin par définition, l'élément finira toujours à l'endroit où il appartient, sinon la liste ne serait pas triée).

Si vous devez ajouter beaucoup d'éléments, la meilleure solution est de cloner la liste, d'ajouter tous les éléments, de trier une fois la nouvelle liste et de remplacer la première liste par le clone.

[EDIT] En réponse à vos commentaires: Après avoir fait quelques ajouts, vous devez trier la liste avant de pouvoir faire l'insertion triée suivante. Donc, la question n'est pas de savoir comment vous pouvez rendre l'insertion triée moins chère, mais le type entre les ajouts et les insertions triées. La réponse est que la plupart des algorithmes de tri fonctionnent plutôt bien avec des listes partiellement triées. Les questions que vous devez poser sont les suivantes: Quel algorithme de tri est utilisé, quelles propriétés a-t-il et, surtout, pourquoi devriez-vous vous en soucier? La dernière question signifie que vous devez mesurer les performances avant d'effectuer toute optimisation, car vous avez 90% de chances que cela fasse plus de mal que de bien, à moins que cela ne soit basé sur des chiffres réels.

Retour au tri. Java utilise une version de quicksort pour trier les collections. Quicksort sélectionne un élément pivot pour partitionner la collection. Cette sélection est cruciale pour la performance de l'algorithme. Pour de meilleures performances, l'élément de pivot doit être aussi proche que possible de l'élément au milieu du résultat. Habituellement, quicksort utilise un élément du milieu de la partition actuelle comme élément pivot. De plus, quicksort commencera à traiter la liste avec les petits index. Par conséquent, l'ajout des nouveaux éléments à la fin peut ne pas vous donner de bonnes performances. Cela n'affectera pas la sélection de l'élément pivot, mais quicksort examinera les nouveaux éléments après avoir vérifié tous les éléments triés. L'ajout des nouveaux éléments au milieu affectera la sélection du pivot et nous ne pouvons pas vraiment dire si cela aura une influence sur la performance ou non. Ma conjecture instinctive est que l'élément pivot sera meilleur si quicksort trouve des éléments triés au milieu des partitions.

Cela laisse l'ajout de nouveaux éléments au début. De cette façon, quicksort trouvera généralement un élément de pivot parfait (puisque le milieu de la liste sera trié) et il récupérera les nouveaux éléments en premier. L'inconvénient est que vous devez copier le tableau entier pour chaque insertion. Il y a deux façons d'éviter cela: a) As I said elsewhere, les PC d'aujourd'hui copient d'énormes quantités de RAM en un rien de temps, vous pouvez donc ignorer ce petit succès. b) Vous pouvez utiliser une seconde ArrayList, y mettre tous les nouveaux éléments, puis utiliser addAll(). Java effectuera certaines optimisations en interne pour ce cas et déplacera simplement les éléments existants une fois.

[EDIT2] J'ai complètement mal compris votre question. Pour l'algorithme insertion sort, le meilleur endroit est probablement quelque part au milieu. Cela devrait réduire de moitié les chances de déplacer un élément dans toute la liste. Mais comme je ne suis pas sûr à 100%, je suggère de créer quelques petits tests pour vérifier cela.