Discussion :

[LeVicThor]

Bonjour,
Dans un projet, j'utilise des objets deque du module collections. A un moment je souhaite pouvoir iterer avec une boucle for seulement sur une partie d'une deque. C'est à dire que je souhaite iterer sur tous les éléments d'une deque dqe dont les indices sont contenus dans un itérable indexes
La première façon de faire serait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
def part_iter_1(dqe, indexes) :
    for i in indexes :
        yield dqe[i]

Seulement, dans la documentation officielle de python, il est écrit à propos des deque :

L'accès par indice est en O(1) aux extrémités mais en O(n) au milieu. Pour des accès aléatoires rapides, il est préférable d'utiliser des listes

En effet, j'ai déjà lu quelque part que les deque en python sont implémentées comme des listes chainées.
Le premier algorithme part_iter_1 n'est donc pas censé être très efficace car il répète len(indexes) fois une opération dont la complexité est quelque part entre O(1) et O(n)
Une deuxième façon de faire serait donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
def part_iter_2(dqe, indexes):
    itr = iter(dqe)
    start = 0
    for stop in indexes:
        for j in range(start, stop) :
            next(itr)
        yield next(itr)
        start = stop+1

Dans ce second algorithme, on itère sur l'entièreté de la deque dqe ce qui est de complexité O(n), et on ne renvoi avec yield que les élements dont les indices sont donnés par l'itérable itr. Si on se fie à la documentation, cet algorithme devrait donc être plus efficace que le premier.

Seulement, j'ai effectué quelques tests rapides avec %timeit et le premier algorithme semble systématiquement être plus rapide. Y-a-t-il quelque chose que je n'ai pas compris ? Qu'est-ce qui peut bien faire que la deuxième méthode d'itération est plus lente que la première ?

Voici les tests que j'ai effectué :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
>>> dqe = deque(range(1000))
>>> indexes = range(0, 1000, 5) # On ne va iterer que sur 1/5 des 1000 élements
 
>>> %timeit for elem in part_iter_1(dqe, indexes) : pass
22.7 µs ± 717 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
 
>>> %timeit for elem in part_iter_2(dqe, indexes) : pass
185 µs ± 26.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Cordialement

PS : Existe-t-il un type d'itérables pour lesquels l'ajout d'éléments à droite et à gauche est rapide, et pour lesquels on conserve un accès rapide aux éléments du milieu ? Une sorte de compromis quoi

[wiztricks]

Salut,

En première approximation, au plus il y a de lignes de code, au plus il y a d'instructions de la machine virtuelle à exécuter et les allers retours avec le code C qui les interprète... prendra plus de temps.

Pour le reste vous avez peut être d'autres options à tester: si la deque n'est pas trop grande, créer une liste pour aller y piocher dedans pourrait être intéressant.

La deque est un itérable, on peut écrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> from collections import deque
>>> d = deque('ghi')
>>> for e in d: print(e)

Si les indices à récupérer sont "ordonnées", vous pouvez les récupérer en une seule itération et un minimum de tests (quitte à ordonner les indices pour les sortir dans l'ordre demandé ensuite).

Existe-t-il un type d'itérables pour lesquels l'ajout d'éléments à droite et à gauche est rapide, et pour lesquels on conserve un accès rapide aux éléments du milieu ?

L'insertion aux extrémités est rapide parce que c'est une liste chainée... Et la recherche du ième élément est lente car il va falloir balayer les i premiers éléments pour trouver "l'adresse" du suivant.

Une liste, c'est un tableau, l'adresse du ième élément, c'est i fois la taille du pointeur (+ l'adresse de base). Un truc mixte, c'est maintenir 2 structures de données et çà sera plus lent.

- W

[LeVicThor]

Le premier algorithme va chercher les éléments un à un par leurs indices. C'est censé être lent car les deques sont des listes chainées donc on doit à chaque fois les reparcourir depuis une de leur extrémité pour accéder à un élément. Je pensais que le second algorithme serait plus rapide car il n'itère au total qu'une seule fois sur la deque. Mais il est néanmoins plus lent. Est-ce uniquement dû au fait que l'instanciation de beaucoup d'objets python range est au final plus long que d'aller reparcourir plusieurs fois la deque depuis une de ses extrémités ?
Au final, la tache d'aller sélectionner seulement certains éléments d'une deque peut-elle réellement être optimisée avec du code en python pur ?

[tyrtamos]

Bonjour,

Une idée complémentaire. L’efficacité d'une opération ne dépend pas seulement de la structure de l'objet contenant les données (list, deque), mais aussi du type d'opération à mener avec.

Par exemple, si la liste une fois établie ne bouge plus, et qu'on a de nombreuses recherches à faire dans cette même liste, alors, une simple liste avec un tri (indexé si nécessaire) et une recherche dichotomique est très efficace. Par exemple, une telle liste de 1024 éléments ne nécessite que 10 tests pour trouver l'un des éléments triés (2**10=1024). Alors qu'une recherche sans ça nécessitera en moyenne de parcourir la moitié de la liste soit 512 tests.

Dans certains cas aussi, l'opération de recherche sera plus rapide avec un dictionnaire grâce au fait que les clés sont alors "hashées": elles sont donc retrouvé par calcul d'adresse et non par tests multiples. Mais il faut, bien sûr, que les éléments de recherche soient uniques et "hashables".

[wiztricks]

Salut,

Le premier algorithme va chercher les éléments un à un par leurs indices. C'est censé être lent car les deques sont des listes chainées donc on doit à chaque fois les reparcourir depuis une de leur extrémité pour accéder à un élément. Je pensais que le second algorithme serait plus rapide car il n'itère au total qu'une seule fois sur la deque.

Si j'écris dqe[i], la recherche se fait entièrement en C.

C'est à comparer avec l'accès à liste[i] (qui se fait aussi entièrement en C) et plus rapidement puisque c'est un tableau et non une liste chaînée.

Si on remplace dqe[i] par un itérateur, des "next" et un seul parcours de la liste... le code sera moins efficace (parce qu'écrit en "pur" Python) tant que le nombre d'index à récupérer sera "petit" (i.e que n*dqe[i] sera plus rapides que...).


- W

[LeVicThor]

Merci pour votre réponse, la rapidité du premier algorithme est donc uniquement due au fait que les accès par indices sont exécutés en C. C'est frustrant qu'il n'y ai aucun moyen de faire quelque chose de plus efficace que le premier algorithme alors qu'il est très mauvais du point de vue de sa complexité.

[wiztricks]

C'est frustrant qu'il n'y ai aucun moyen de faire quelque chose de plus efficace que le premier algorithme alors qu'il est très mauvais du point de vue de sa complexité.

Si c'est vraiment une préoccupation, il y a toujours la possibilité de coder çà en C (il y a des outils pour çà) et être moins pénalisé par le "pur" Python.

- W

[fred1599]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> %timeit for elem in part_iter_1(dqe, indexes) : pass22.7 µs ± 717 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
 
>>> %timeit for elem in part_iter_2(dqe, indexes) : pass 185 µs ± 26.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Le nombre d'itérations ne semble pas identiques, je me trompe ?

[LeVicThor]

Le nombre d'itérations ne semble pas identiques, je me trompe ?

Je compare la moyenne des temps d'exécution