itertools.islice en comparación con el segmento de lista

Question

He estado tratando de aplicar un algoritmo para reducir una lista de python a una más pequeña en función de ciertos criterios. Debido al gran volumen de la lista original, en el orden de 100 mil elementos, traté de itertools para evitar múltiples asignaciones de memoria por lo que se me ocurrió esto:

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) ] 

Tiempo de ejecución para esta toma una preocupante mucho tiempo en el orden de unos minutos, cuando vec tiene alrededor de 100k elementos. Cuando lo intenté en su lugar:

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 esencia reemplazar islice con una rebanada, la ejecución es instantánea.

¿Puedes pensar en una explicación plausible para esto? Hubiera pensado que evitar asignar repetidamente una nueva lista con una cantidad sustancial de elementos me ahorraría unos pocos ciclos computacionales en lugar de paralizar toda la ejecución.

Cheers, Themis

Answer 1

islice funciona con iterables arbitrarios. Para hacer esto, en lugar de saltar directamente al n-ésimo elemento, tiene que iterar sobre el primer n-1, tirarlos, y luego dar los que desee.

Mira la implementación de Python puro a partir del 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) 

---

Hablando de la documentación itertools, si yo estaba tratando de hacer esta operación, probablemente me utilizo la receta grouper. En realidad, no le ahorrará ningún recuerdo, pero podría hacerlo si lo reescribiera para que sea más flojo, lo que no sería difícil.

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') 

me gusta usar grouper abstraer los cortes consecutivos y encontrar el código mucho más fácil de leer que el original

Answer 2

Mi conjetura sería que el uso de islice() implica una llamada a la función de Python para cada elemento de vec, mientras que la notación de rebanada extendida se entiende por el analizador y se traduce directamente en CPython llama.