Problème de complexité pour itérer sur une sélection de certains éléments d'une deque
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:
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 :
Citation:
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:
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:
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 :?
