Complexité de len() par rapport aux ensembles et aux listes

Question

La complexité de len() en ce qui concerne les ensembles et les listes est également O(1). Comment se fait-il qu'il faille plus de temps pour traiter les ensembles ?

~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)"
10000000 loops, best of 3: 0.168 usec per loop
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)"
1000000 loops, best of 3: 0.375 usec per loop

Est-ce lié à l'indice de référence particulier, c'est-à-dire qu'il faut plus de temps pour construire des ensembles que des listes et que l'indice de référence en tient également compte ?

Si la création d'un objet set prend plus de temps que la création d'une liste, quelle en est la raison ?

Answer 1

Tout d'abord, vous n'avez pas mesuré la vitesse de len() vous avez mesuré la vitesse de création d'une liste ou d'un ensemble. en même temps que la vitesse de len() .

Utilisez le --setup argument de timeit :

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop

Les déclarations que vous passez à --setup sont exécutées avant de mesurer la vitesse de len() .

Deuxièmement, vous devez noter que len(a) est une déclaration assez rapide. Le processus de mesure de sa vitesse peut être sujet au "bruit". Considérez que le code exécuté (et mesuré) par timeit est équivalent à ce qui suit :

for i in itertools.repeat(None, number):
    len(a)

Parce que les deux len(a) y itertools.repeat(...).__next__() sont des opérations rapides et leurs vitesses peuvent être similaires, la vitesse de la itertools.repeat(...).__next__() peut influencer les délais.

Pour cette raison, vous feriez mieux de mesurer len(a); len(a); ...; len(a) (répété une centaine de fois) de sorte que le corps de la boucle for prend beaucoup plus de temps que l'itérateur :

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop

(Les résultats indiquent toujours que len() a les mêmes performances sur les listes et les ensembles, mais maintenant vous êtes sûr que le résultat est correct).

Troisièmement, il est vrai que la "complexité" et la "vitesse" sont liées, mais je crois que vous faites une confusion. Le fait que len() a O(1) complexité pour les listes et les ensembles n'implique pas qu'il doive fonctionner avec la même vitesse sur les listes et les ensembles.

Cela signifie que, en moyenne, quelle que soit la longueur de la liste a est, len(a) effectue le même nombre asymptotique d'étapes. Et peu importe la longueur de l'ensemble b est, len(b) effectue le même nombre asymptotique d'étapes. Mais l'algorithme pour calculer la taille des listes et des ensembles peut être différent, ce qui entraîne des performances différentes (timeit montre que ce n'est pas le cas, mais cela peut être une possibilité).

Enfin,

Si la création d'un objet set prend plus de temps que la création d'une liste, quelle en est la raison ?

Un ensemble, comme vous le savez, n'autorise pas les éléments répétés. Les ensembles dans CPython sont implémentés en tant que tables de hachage (pour garantir une valeur moyenne des éléments). O(1) insertion et consultation) : la construction et la maintenance d'une table de hachage sont beaucoup plus complexes que l'ajout d'éléments à une liste.

Plus précisément, lors de la construction d'un ensemble, vous devez calculer des hachages, construire la table de hachage, la consulter pour éviter d'insérer des événements en double, etc. En revanche, les listes dans CPython sont implémentées comme un simple tableau de pointeurs qui est malloc() ed et realloc() au besoin.

Answer 2

Les lignes pertinentes sont http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640

640     static Py_ssize_t
641     set_len(PyObject *so)
642     {
643         return ((PySetObject *)so)->used;
644     }

et http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431

431     static Py_ssize_t
432     list_length(PyListObject *a)
433     {
434         return Py_SIZE(a);
435     }

Les deux ne sont qu'une recherche statique.

Quelle est donc la différence, me direz-vous ? Vous mesurez aussi la création des objets. Et il faut un peu plus de temps pour créer un ensemble qu'une liste.

Answer 3

Utilisez-le avec le -s drapeau pour timeit sin en tenant compte de la première chaîne :

~$ python -mtimeit -s "a=range(1000);" "len(a)"
10000000 loops, best of 3: 0.0424 usec per loop
                           ↑ 

---

~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)"
10000000 loops, best of 3: 0.0423 usec per loop
                           ↑ 

Maintenant, il ne considère que les len et les résultats sont à peu près les mêmes puisque nous n'avons pas pris en compte le temps de création de l'ensemble/de la liste.

Answer 4

Oui, vous avez raison, c'est plus à cause de la différence de temps nécessaire à la création de la set y list par python. Pour une évaluation plus juste, vous pouvez utiliser timeit et passer les objets en utilisant setup argument :

from timeit import timeit

print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)")
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000")

résultat :

1st:  0.04927110672
2nd :  0.0530669689178

Et si vous voulez savoir pourquoi il en est ainsi, passons par le monde de Python. En fait, l'objet défini utilise un table de hachage Une table de hachage utilise une fonction de hachage pour créer les valeurs de hachage des éléments et les mettre en correspondance avec les valeurs. Dans ce cas, l'appel de la fonction, le calcul des valeurs de hachage et d'autres tâches supplémentaires prennent beaucoup de temps. Alors que pour créer une liste, Python crée simplement une séquence d'objets à laquelle on peut accéder par indexation.

Vous pouvez consulter les détails sur set_lookkey de la fonction Code source Cpython .

set_lookkey(PySetObject *so, PyObject *key, register long hash)
    {
        register Py_ssize_t i;
        register size_t perturb;
        register setentry *freeslot;
        register size_t mask = so->mask;
        setentry *table = so->table;
        register setentry *entry;
        register int cmp;
        PyObject *startkey;

        i = hash & mask;
        entry = &table[i];
        if (entry->key == NULL || entry->key == key)
            return entry;
.
.
.

Notez également que si deux algorithmes ont la même complexité, cela ne signifie pas que les deux algorithmes ont exactement le même temps d'exécution, ou la même vitesse d'exécution. 1

---

_{parce que <code>big O</code> décrit le <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow">comportement limite d'une fonction </a>et ne montre pas l'équation de complexité exacte. Par exemple, la complexité des équations suivantes <code>f(x)=100000x+1</code> y <code>f(x)=4x+20</code> est O(1) et cela signifie que les deux sont des équations linéaires ; comme vous pouvez le voir, la première fonction a une pente beaucoup plus grande, et pour une même entrée, elles donneront des résultats différents.}

Answer 5

Permettez-moi d'intégrer les excellentes réponses ici : O(1) ne vous informe que sur le l'ordre de croissance par rapport à la taille de l'entrée.

O(1) en particulier ne signifie que temps constant par rapport à la taille de l'entrée . Une méthode peut toujours prendre 0.1s, pour n'importe quelle entrée, et une autre peut prendre 1000 ans pour n'importe quelle entrée, et elles seraient toutes les deux O(1)

Dans ce cas, bien que la documentation présente un certain degré d'ambiguïté cela signifie que la méthode prend à peu près en même temps pour traiter une liste de taille 1 qu'il faut pour traiter une liste de taille 1000 ; de même, il faut le même temps pour traiter un dictionnaire de taille 1 qu'il faut pour traiter un dictionnaire de taille 1000 .

Aucune garantie n'est donnée en ce qui concerne les différents types de données. .

Cela n'est pas surprenant puisque la mise en œuvre de l'initiative len() à un certain point de la pile d'appels peut différer selon le type de données.

Incidemment, Cette ambiguïté est éliminée dans les langages typés statiquement. donde ClassA.size() y ClassB.size() sont à toutes fins utiles deux méthodes différentes.