itertools.islice par rapport à la liste slice

Question

J'ai essayé d'appliquer un algorithme pour réduire une liste python en une plus petite basée sur un certain critère. En raison du grand volume de la liste initiale, dans l'ordre de 100k éléments, j'ai essayé de itertools pour éviter les allocations de mémoire multiples, donc je suis venu avec ceci:

reducedVec = [ 'F' if sum(1 for x in islice(vec, i, i+ratio) if x == 'F') 
         > ratio/3.0 else 'T' 
       for i in xrange(0, len(vec), ratio) ] 

Temps d'exécution pour cela prend inquiétant longtemps l'ordre de quelques minutes, quand vec a environ 100k éléments. Quand j'ai essayé à la place:

reducedVec = [ 'F' if sum(1 for x in vec[i:i+ratio] if x == 'F') 
         > ratio/3.0 else 'T' 
       for i in xrange(0, len(vec), ratio) ] 

En substance remplacer l'islice avec une tranche l'exécution est instantanée. Pouvez-vous penser à une explication plausible pour cela?

J'aurais pensé qu'éviter d'allouer à plusieurs reprises une nouvelle liste avec un nombre substantiel d'éléments me sauverait quelques cycles de calcul au lieu de paralyser toute l'exécution.

Cheers, Themis

Answer 1

islice fonctionne avec des itérations arbitraires. Pour ce faire, plutôt que de sauter directement au nième élément, il doit parcourir le premier n-1, les jeter, puis céder ceux que vous voulez.

Vérifiez la pure implémentation Python de la itertools documentation:

def islice(iterable, *args): 
    # islice('ABCDEFG', 2) --> A B 
    # islice('ABCDEFG', 2, 4) --> C D 
    # islice('ABCDEFG', 2, None) --> C D E F G 
    # islice('ABCDEFG', 0, None, 2) --> A C E G 
    s = slice(*args) 
    it = iter(xrange(s.start or 0, s.stop or sys.maxint, s.step or 1)) 
    nexti = next(it) 
    for i, element in enumerate(iterable): 
     if i == nexti: 
      yield element 
      nexti = next(it) 

---

En parlant de la documentation itertools, si je tentais de faire cette opération, je serais probablement utiliser la recette grouper. Il ne vous sauvera pas de mémoire, mais il pourrait si vous l'avez réécrit pour être plus paresseux, ce qui ne serait pas difficile.

from __future__ import division 

from itertools import izip_longest 
def grouper(n, iterable, fillvalue=None): 
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx" 
    args = [iter(iterable)] * n 
    return izip_longest(fillvalue=fillvalue, *args) 

reducedVec = [] 
for chunk in grouper(ratio, vec): 
    if sum(1 for x in chunk if x == 'F') > ratio/3: 
     reducedVec.append('F') 
    else: 
     reducedVec.append('T') 

J'aime utiliser grouper faire abstraction des tranches consécutives et trouver ce code beaucoup plus facile à lire que l'original

Answer 2

Je dirais que l'utilisation islice() implique un appel de fonction Python pour chaque élément de vec, alors que la notation tranche étendue est comprise par l'analyseur et se traduit directement aux appels CPython.