Comparaison de l'efficacité des listes et des ensembles Python

Efficacité opérationnelle du programme

L'efficacité opérationnelle du programme est divisée en deux types : le premier est l'efficacité temporelle et le second est l'efficacité spatiale. L’efficacité temporelle est appelée complexité temporelle, tandis que l’efficacité spatiale est appelée complexité spatiale. La complexité temporelle mesure principalement la vitesse d'exécution d'un programme, tandis que la complexité spatiale mesure principalement l'espace de stockage supplémentaire requis par un programme.

Le temps nécessaire à l'exécution d'un programme ne peut pas être calculé théoriquement. Ce n'est que lorsque vous exécutez le programme sur une machine que vous pouvez savoir que les résultats obtenus par différentes machines à des moments différents peuvent être différents. Mais devons-nous tester chaque programme sur l’ordinateur ? C'est évidemment irréaliste, c'est pourquoi la méthode d'analyse de la complexité temporelle est développée. En pratique, lorsque l'on calcule la complexité temporelle, on n'a pas nécessairement besoin de calculer le nombre exact d'exécutions, mais seulement le nombre approximatif d'exécutions. On utilise généralement la représentation asymptotique Big O. Si le nombre d'exécutions est généralement de 1, on utilise généralement la représentation asymptotique Big O. peut dire la complexité temporelle. C'est O(1). Si cela prend n fois, on peut dire que la complexité temporelle est O(n).

La complexité spatiale est une mesure de la quantité d'espace de stockage qu'un algorithme occupe temporairement pendant son fonctionnement. La complexité spatiale ne correspond pas au nombre d'octets d'espace occupés par le programme, car elle est difficile à calculer pendant le fonctionnement réel, donc la complexité spatiale compte le nombre de variables. Les règles de calcul de la complexité spatiale sont fondamentalement similaires à la complexité temporelle et utilisent également la notation asymptotique grand O.

Les types de données combinés couramment utilisés en Python sont les tuples, les listes, les ensembles et les dictionnaires. Pour connaître la complexité temporelle des différentes opérations de chaque type de données, veuillez vous référer au lien officiel de Python. Il y a des instructions détaillées sur la page Web,

• https. :/ /wiki.python.org/moin/TimeComplexity

Les tuples et les listes sont des types de séquence, et leurs mécanismes de stockage sont fondamentalement les mêmes ; les ensembles et les dictionnaires sont également fondamentalement les mêmes, la seule différence est que chaque élément du set n’a pas de valeur correspondante. Ensuite, nous prenons des ensembles et des listes comme exemples pour voir leur efficacité de recherche et leur surcharge de stockage.

Efficacité de la recherche de données

Quelle est l'ampleur de l'écart entre l'efficacité de la recherche de données d'ensemble et de liste ? Regardons d'abord un ensemble d'exemples :

import time
import random
nums = [random.randint(0, 2000000) for i in range(1000)]
list_test = list(range(1000000))
set_test = set(list_test)
count_list, count_set = 0, 0
t1 = time.time()# 测试在列表中进行查找
for num in nums:
 if num in list_test:
 count_list += 1
t2 = time.time()
for num in nums:# 测试在集合中进行查找
 if num in set_test:
 count_set += 1
t3 = time.time()# 测试在集合中进行查找
print('找到个数，列表：{}，集合：{}'.format(count_list, count_set))
print('使用时间，列表：{:.4f}s'.format(t2 - t1))
print('使用时间，集合：{:.4f}s'.format(t3 - t2))

Le résultat de sortie est :

找到个数，列表：515，集合：515
使用时间，列表：7.7953s
使用时间，集合：0.0010s

Il ressort clairement de l'exemple ci-dessus que l'efficacité de la recherche des ensembles est bien supérieure à celle des listes, donc dans différents scénarios d'application, vous doit choisir le type de données approprié, aucune différence de performances n'est visible sous une petite quantité de données, mais une fois qu'elle est remplacée par une grande quantité de données, la différence deviendra très grande.

Surcharge de stockage de données

L'efficacité de la recherche des ensembles est beaucoup plus rapide que celle des listes. La raison principale est que leurs principes de stockage sont différents. Les ensembles doivent consommer plus d'espace pour stocker des informations supplémentaires. Ensuite, regardons la différence dans leur surcharge de stockage via la fonction getsizeof(). La fonction getiszeof() est une fonction utilisée dans le module sys de Python pour obtenir la taille de la mémoire d'un objet.

import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('列表占用大小：', sys.getsizeof(list_test))
print('集合占用大小：', sys.getsizeof(set_test))

Le résultat de sortie est :

列表占用大小：9000112
集合占用大小：33554656

Les résultats montrent que pour le même contenu de données, le coût de stockage d'une collection est plusieurs fois supérieur à celui d'une liste.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!