Bonjour,
J'aimerais savoir quelle est la manière optimale d'insérer un élément dans une liste triée
Est ce une recherche dichotomique de la place où doit être inséré l'élément puis avec la fonction insert de python l'insérer
Ou plutôt dois je rajouter l'élément à la liste et procéder à un quicksort
Ou encore je peux appliquer l'algorithme d'insertion du tri par insertion
Merci d'avance !
Je ne connais pas Python, mais quand tu parles d'une liste triée, c'est une propriété de la liste ou simplement toi qui la trie ?
Dans pas mal de langages, il y a une propriété de la liste pour dire qu'elle est triée et quand on insère un élément dans cette liste il l'insère automatiquement au bon endroit (en général par dichotomie).
Eyyo
Pour une liste normale (triée ou triable par en O(n log n) vous pourriez poser l'élément à trier comme dernier élément (append donc O(1)) puis quicksort - ce qui reviendra à faire une recherche dichotomique en O(log n) + l'insert qui se fait en O(n). On finit alors avec un O(n) si on considère la liste initiale comme étant triée.
La solution en O(log n) serait d'utiliser une linked list, dans laquelle on peut accéder à n'importe quel index en temps constant, et donc insérer en temps constant. Mais bon, ça c'est la théorie, la vérité est que le cache s'en prendra un coup et que bien qu'en complexité on y gagne, en temps effectif je ne suis pas sûr que cela vaille le coup.
En espérant que ce message vous ait aidé(e)
PS: je considère ici l'insert séparément du quicksort car c'est cela qui, dans ce cas précis, prendrait l'essentiel du temps d'exécution - d'habitude, je dirais qu'il en fait partie
Dernière modification par Dicedead ; 09/12/2019 à 01h10.
Une linked list nécessite de parcourir toute la liste depuis le début pour accéder à un élément. Donc pas en temps constant mais en O(n).Envoyé par Dicedead
Ce qui donne accès à n'importe quel élément en temps constant, c'est le tableau mais qui est est aussi appelé list en python.
Par rapport aux autres solutions qui nécessitent de parcourir l'ensemble, j'ai l'impression que le nombre d'accès à des données hors cache ne va pas être très différent voire inférieur.
Par liste, tu entends liste chainée ou liste au sens python c'est à dire tableau ?
Une insertion naive dans une liste chainée triée tout en gardant le tri est en O(n). Un quicksort est au mieux en O(n log(n)).
Cela ressemble beaucoup à l'approche naive.
Eyyo
Ne serait-ce pas append qui est en O(n) et l'insertion (par la méthode push) en temps constant pour une linked list?
Et en ce qui concerne le quicksort, vu que l'on ne l'applique qu'à un seul élément, une seule recherche dichotomique sera effectuée, d'où O(log n) pour cette étape (et donc ensuite + O(n) si insert dans liste normale aka list ie array d'autres langages, ou + O(1) si push en linked).
Les tris insertion, bubble et sélection ne sont jamais la meilleure option et bien souvent l'une des pires
Dernière modification par Dicedead ; 09/12/2019 à 10h33.
Cela dépend de quoi on parle. Pour un Linked List de base, on ne fait pas d'append mais du prepend qui est en O(1).
Ensuite la "méthode push" ne veut rien dire en soi. Elle n'existe pas sur les types de données standard en Python.
Par ailleurs, toujours en standard, la seule LinkedList en python est la deque qui a un pointeur sur le début et la fin : append & prepend sont en O(1).
Soit tu ne parles que des tableaux et oui, on va avoir une recherche dichotomique mais vu que tu parles aussi des listes, alors la dite recherche ne sera pas en O(log n) puisqu'on ne peut pas faire d'accès aléatoire à un élément par son indice.
Cela va donc être en O(n log n) et donc moins efficace qu'une recherche de base en O(n).
Je ne vois pas l'intérêt d'induire celui qui pose la question en erreur en accumulant réponse fausse sur réponse fausse.
Eyyo
Je pense effectivement qu'il y a un désaccord sur le vocabulaire mais sur le fond nous sommes plutôt d'accord.
push, pour moi, est une convention de nomination pour linkedlist dont l'action et la complexité correspondent au prepend que vous mentionnez. Par liste, j'entends bien l'objet mutable référé en python par deux crochets [] ('list' dans la documentation anglophone) dont l'équivalent souvent non mutable est appelé tableau ou array dans d'autres langages.
Hs
Ce ne sont pas les dictionnaires qui font cela?
Quand ils sont implémentés comme une table de hash ce qui est le cas le plus fréquent oui. Mais la vitesse d'accès est nettement plus lente, la consommation mémoire plus élevée, on ne garde pas d'ordre et on ne peut pas avoir 2 fois la même clé...
C'est vraiment différent.
Dans de nombreux cas, si on veut garder un dictionnaire trié, il est plus efficace d'utiliser une implémentation sous forme d'arbre.
Thx
Ps: pour de la perf, je suppose que le mieux est de passer par numpy ou panda
Code:maliste = np.insert(maliste, maliste.searchsorted(new), new)
Oui, numpy va beaucoup plus vite et consomme moins de mémoire.
Avant tout merci beaucoup ^^
Vous avez parlé de choses très compliquées en réalité je suis pas sûr de tout avoir compris, mais ce que je comprends c'est que l'insertion par dichotomie est la plus efficace (je ne peux pas utiliser l'insertion de numpy car en réalité j'ai une liste python (donc un tableau) de[liste,nombre,liste]).
J'appliquerai donc cette méthode
Merci !
