Les performances de la liste(...).insérer(…)
j'ai pensé à la question suivante sur l'architecture de l'ordinateur. Supposons que je le fasse en Python
from bisect import bisect
index = bisect(x, a) # O(log n) (also, shouldn't it be a standard list function?)
x.insert(index, a) # O(1) + memcpy()
qui prend log n , plus, si je comprends bien, une opération de copie de mémoire pour x[index:] . Maintenant, j'ai lu récemment que le goulot d'étranglement est habituellement dans la communication entre le processeur et la mémoire de sorte que la copie de mémoire pourrait être fait par RAM assez rapidement. Est-il comment cela fonctionne?
3 réponses
Python est un langage. Plusieurs implémentations existent , et ils peut ont différentes implémentations pour les listes. Donc, sans regarder le code d'une implémentation réelle, vous ne pouvez pas savoir avec certitude comment les listes sont implémentées et comment elles se comportent dans certaines circonstances.
Mon pari serait que les références aux objets de la liste sont stockés dans la mémoire contiguë (certainement pas comme une liste chaînée...). Si c'est en effet le cas, alors l'insertion par x.insert entraînera le déplacement de tous les éléments situés derrière l'élément inséré. Cela peut être fait efficacement par le matériel, mais la complexité serait toujours O(n) .
pour les petites listes , l'opération bisect peut prendre plus de temps que x.insert , même si la première est O(log n) tandis que la seconde est o(n) . Pour les longues listes, cependant, je risque une conjecture x.insert est le goulot d'étranglement. Dans de tels cas, vous devez envisager d'utiliser une autre structure de données.
utilisez le module blist si vous avez besoin d'une liste avec de meilleures performances d'insertion.
les listes CPython sont des tableaux contigus. Lequel des o(log n) bisect et O (n) insert domine votre profil de performance dépend de la taille de votre liste et aussi des facteurs constants à l'intérieur du O (). En particulier, la fonction de comparaison invoquée par bisect peut être quelque chose de coûteux en fonction du type d'objets dans la liste.
si vous avez besoin de tenir des séquences triées mutables potentiellement grandes alors le tableau linéaire sous-jacent au type de liste Pythons n'est pas un bon choix. Selon vos besoins, des tas, des arbres ou des listes de sauts peuvent être appropriés.