Explication graphique détaillée du type d'ensemble Python (générateur d'ensemble de dict de tuple de liste)

Les types de collections intégrés

Python incluent list, tuple, set et dict.

Liste : ressemble à un tableau, mais est plus puissant qu'un tableau et prend en charge des fonctions telles que l'indexation, le découpage, la recherche et l'addition.

Tuple tuple : La fonction est similaire à la liste, mais une fois générée, la longueur et les éléments ne sont pas variables (les éléments des éléments sont toujours variables), ce qui semble être une liste plus légère et plus sûre.

Dictionnaire de dictionnaire : une table de hachage à structure de paire clé-valeur, qui a les mêmes propriétés qu'une table de hachage clé est non ordonnée et non répétitive, et l'ajout, la suppression et la modification sont pratiques. et rapide.

set : un ensemble non ordonné et non répétitif, qui est un dict avec uniquement des clés et aucune valeur. Le HashSet de Java est implémenté en utilisant HashMap. Après tout, set n'en a pas besoin. valeur, donc il est omis. Beaucoup de pointeurs.

Générateur :

est appelé un générateur, ou une compréhension de liste, qui est un type de données , n'est pas réellement une structure de données, elle inclut uniquement l'algorithme et l'état temporaire, et a la fonction d'itération.

Examinez d'abord leur utilisation de la mémoire et utilisez des générateurs pour générer un ensemble, un dict, un générateur, un tuple et une liste de 100 000 éléments. La mémoire consommée par dict, set, list et tuple diminue en séquence, et la taille des objets générés est également la même. Étant donné que le générateur ne génère pas de table de données, il n'a pas besoin de consommer de mémoire :

import sys
from memory_profiler import profile

@profile
def create_data(data_size):
    data_generator = (x for x in xrange(data_size))
    data_set = {x for x in xrange(data_size)}
    data_dict = {x:None for x in xrange(data_size)}
    data_tuple = tuple(x for x in xrange(data_size))
    data_list = [x for x in xrange(data_size)]
    return data_set, data_dict, data_generator, data_tuple, data_list

data_size = 100000
for data in create_data(data_size):
    print data.__class__, sys.getsizeof(data)

Line #    Mem usage    Increment   Line Contents
================================================
    14.6 MiB      0.0 MiB   @profile
                            def create_data(data_size):
    14.7 MiB      0.0 MiB       data_generator = (x for x in xrange(data_size))
    21.4 MiB      6.7 MiB       data_set = {x for x in xrange(data_size)}
    29.8 MiB      8.5 MiB       data_dict = {x:None for x in xrange(data_size)}
    33.4 MiB      3.6 MiB       data_tuple = tuple(x for x in xrange(data_size))
    38.2 MiB      4.8 MiB       data_list = [x for x in xrange(data_size)]
    38.2 MiB      0.0 MiB       return data_set, data_dict, data_generator, data_tuple, data_list
 
<type &#39;set&#39;> 4194528
<type &#39;dict&#39;> 6291728
<type &#39;generator&#39;> 72
<type &#39;tuple&#39;> 800048
<type &#39;list&#39;> 824464

Regardez les performances de recherche dict et set sont des temps de recherche constants (O(1)) et une liste. et tuple sont des temps de recherche linéaires. (O(n)), utilisez le générateur pour générer un objet d'éléments de taille spécifiée et utilisez des nombres générés aléatoirement pour rechercher :

import time
import sys
import random
from memory_profiler import profile

def create_data(data_size):
    data_set = {x for x in xrange(data_size)}
    data_dict = {x:None for x in xrange(data_size)}
    data_tuple = tuple(x for x in xrange(data_size))
    data_list = [x for x in xrange(data_size)]
    return data_set, data_dict, data_tuple, data_list

def cost_time(func):
    def cost(*args, **kwargs):
        start = time.time()
        r = func(*args, **kwargs)
        cost = time.time() - start
        print 'find in %s cost time %s' % (r, cost)
        return r, cost  #返回数据的类型和方法执行消耗的时间
    return cost

@cost_time
def test_find(test_data, data):
    for d in test_data:
        if d in data:
            pass
    return data.__class__.__name__

data_size = 100
test_size = 10000000
test_data = [random.randint(0, data_size) for x in xrange(test_size)]
#print test_data
for data in create_data(data_size):
    test_find(test_data, data)

输出：
----------------------------------------------
find in <type &#39;set&#39;> cost time 0.47200012207
find in <type &#39;dict&#39;> cost time 0.429999828339
find in <type &#39;tuple&#39;> cost time 5.36500000954
find in <type &#39;list&#39;> cost time 5.53399991989

Un ensemble de 100 éléments, recherchez. 1000 W fois respectivement, la différence est très évidente. Cependant, ces nombres aléatoires se retrouvent tous dans la collection. Modifiez la méthode des nombres aléatoires afin que la moitié des nombres générés puissent être trouvés et l'autre moitié ne puisse pas être trouvée. Il ressort des informations imprimées que les listes et les tuples fonctionnent encore moins bien lorsqu'il existe la moitié des pires exemples de recherche.

def randint(index, data_size):
    return random.randint(0, data_size) if (x % 2) == 0 else random.randint(data_size, data_size * 2)

test_data = [randint(x, data_size) for x in xrange(test_size)]

输出：
----------------------------------------------
find in <type &#39;set&#39;> cost time 0.450000047684
find in <type &#39;dict&#39;> cost time 0.397000074387
find in <type &#39;tuple&#39;> cost time 7.83299994469
find in <type &#39;list&#39;> cost time 8.27800011635

Le nombre d'éléments passe de 10 à 500. Les statistiques du temps nécessaire pour rechercher 100 000 fois à chaque fois sont utilisées pour ajuster la courbe de consommation de temps. Les résultats sont présentés ci-dessous. dict et set n'ont pas d'importance sur le nombre d'éléments. Le temps de recherche a toujours été constant. À mesure que les éléments grandissent, dict et tuple affichent un temps de croissance linéaire :

import matplotlib.pyplot as plot
from numpy import *

data_size = array([x for x in xrange(10, 500, 10)])
test_size = 100000
cost_result = {}
for size in data_size:
    test_data = [randint(x, size) for x in xrange(test_size)]
    for data in create_data(size):
        name, cost = test_find(test_data, data) #装饰器函数返回函数的执行时间
        cost_result.setdefault(name, []).append(cost)

plot.figure(figsize=(10, 6))
xline = data_size
for data_type, result in cost_result.items():
    yline = array(result)
    plot.plot(xline, yline, label=data_type)

plot.ylabel('Time spend')
plot.xlabel('Find times')

plot.grid()

plot.legend()
plot.show()

.

La différence de temps d'itération est très faible, et dict et set nécessitent Cela prend un peu plus de temps :

@cost_time
def test_iter(data):
    for d in data:
        pass
    return data.__class__ .__name__

data_size = array([x for x in xrange(1, 500000, 1000)])
cost_result = {}
for size in data_size:
    for data in create_data(size):
        name, cost = test_iter(data)
        cost_result.setdefault(name, []).append(cost)

#拟合曲线图
plot.figure(figsize=(10, 6))
xline = data_size
for data_type, result in cost_result.items():
    yline = array(result)
    plot.plot(xline, yline, label=data_type)  

plot.ylabel('Time spend')
plot.xlabel('Iter times')

plot.grid()

plot.legend()
plot.show()

La consommation de temps de suppression d'éléments est indiquée ci-dessous . 1000 éléments sont supprimés aléatoirement. Le type tuple ne peut pas supprimer d'éléments, donc aucune comparaison n'est effectuée :

Supprimez aléatoirement la moitié des éléments. , le graphique grandira en temps exponentiel (O(n2)) :

La consommation de temps pour l'ajout d'éléments est présentée ci-dessous. Les statistiques du temps d'ajout du nombre de. les éléments par incréments de 10 000 sont tous des temps de croissance linéaires. Il n'y a aucune différence. Les types de tuples ne peuvent pas en ajouter de nouveaux, donc aucune comparaison n'est effectuée :

@cost_time
def test_dict_add(test_data, data):
    for d in test_data:
        data[d] = None
    return data.__class__ .__name__

@cost_time
def test_set_add(test_data, data):
    for d in test_data:
        data.add(d)
    return data.__class__ .__name__

@cost_time
def test_list_add(test_data, data):
    for d in test_data:
        data.append(d)
    return data.__class__ .__name__

#初始化数据，指定每种类型对应它添加元素的方法
def init_data():
    test_data = {
        'list': (list(), test_list_add),
        'set': (set(), test_set_add),
        'dict': (dict(), test_dict_add)
    }
    return test_data

#每次检测10000增量大小的数据的添加时间
data_size = array([x for x in xrange(10000, 1000000, 10000)])
cost_result = {}
for size in data_size:
    test_data = [x for x in xrange(size)]
    for data_type, (data, add) in init_data().items():
        name, cost = add(test_data, data) #返回方法的执行时间
        cost_result.setdefault(data_type, []).append(cost)

plot.figure(figsize=(10, 6))
xline = data_size
for data_type, result in cost_result.items():
    yline = array(result)
    plot.plot(xline, yline, label=data_type)

plot.ylabel('Time spend')
plot.xlabel('Add times')

plot.grid()

plot.legend()
plot.show()

.

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!