python - control - Almacenamiento en caché de un generador

cache control html

Question

Una pregunta similar reciente (¿ instancia (foo, types.GeneratorType) o inspect.isgenerator (foo)? ) Me dio curiosidad sobre cómo implementar esto genéricamente.

Parece una cosa generalmente útil tener, en realidad, un objeto generador que itertools.cycle por primera vez (como itertools.cycle ), informe StopIteration y luego devuelva los elementos del caché la próxima vez, pero si el objeto no es un generador (es decir, una lista o dict que inherentemente admite la búsqueda O (1)), luego no guarda en caché, y tiene el mismo comportamiento, pero para la lista original.

Posibilidades:

1) Modificar itertools.cycle. Se parece a esto:

def cycle(iterable):
    saved = []
    try: 
         saved.append(iterable.next())
         yield saved[-1]
         isiter = True
    except:
         saved = iterable
         isiter = False
    # cycle(''ABCD'') --> A B C D A B C D A B C D ...
    for element in iterable:
        yield element
        if isiter: 
            saved.append(element)

     # ??? What next?

Si pudiera reiniciar el generador, sería perfecto - podría enviar una StopIteration, y luego en el próximo gen.next (), devolver la entrada 0, es decir `ABCD StopIteration ABCD StopIteration '', pero no parece que eso sea realmente posible .

En segundo lugar, una vez que se golpea StopIteration, se guarda un caché. Pero no parece que haya alguna forma de llegar al campo guardado interno []. Tal vez una versión de clase de esto?

2) O podría pasar la lista directamente:

def cycle(iterable, saved=[]):
    saved.clear()
    try: 
         saved.append(iterable.next())
         yield saved[-1]
         isiter = True
    except:
         saved = iterable
         isiter = False
    # cycle(''ABCD'') --> A B C D A B C D A B C D ...
    for element in iterable:
        yield element
        if isiter: 
            saved.append(element)

mysaved = []
myiter = cycle(someiter, mysaved)

Pero eso se ve desagradable. Y en C / ++ podría pasar algo de referencia, y cambiar la referencia real por "saved to point to iterable", no se puede hacer eso en python. Entonces esto ni siquiera funciona.

¿Otras opciones?

Editar: Más datos. El método CachingIterable parece ser demasiado lento para ser efectivo, pero me empujó en una dirección que podría funcionar. Es un poco más lento que el método ingenuo (convirtiéndolo en mi lista), pero parece no recibir el hit si ya es iterable.

Algunos códigos y datos:

def cube_generator(max=100):
    i = 0
    while i < max:
        yield i*i*i
        i += 1

# Base case: use generator each time
%%timeit
cg = cube_generator(); [x for x in cg]
cg = cube_generator(); [x for x in cg]
cg = cube_generator(); [x for x in cg]
10000 loops, best of 3: 55.4 us per loop

# Fastest case: flatten to list, then iterate
%%timeit
cg = cube_generator()
cl = list(cg)
[x for x in cl]
[x for x in cl]
[x for x in cl]
10000 loops, best of 3: 27.4 us per loop

%%timeit
cg = cube_generator()
ci2 = CachingIterable(cg)
[x for x in ci2]
[x for x in ci2]
[x for x in ci2]
1000 loops, best of 3: 239 us per loop

# Another attempt, which is closer to the above
# Not exactly the original solution using next, but close enough i guess
class CacheGen(object):
    def __init__(self, iterable):
        if isinstance(iterable, (list, tuple, dict)):
            self._myiter = iterable
        else:
            self._myiter = list(iterable)
    def __iter__(self):
        return self._myiter.__iter__()
    def __contains__(self, key):
        return self._myiter.__contains__(key)
    def __getitem__(self, key):
        return self._myiter.__getitem__(key)

%%timeit
cg = cube_generator()
ci = CacheGen(cg)
[x for x in ci]
[x for x in ci]
[x for x in ci]
10000 loops, best of 3: 30.5 us per loop

# But if you start with a list, it is faster
cg = cube_generator()
cl = list(cg)
%%timeit
[x for x in cl]
[x for x in cl]
[x for x in cl]
100000 loops, best of 3: 11.6 us per loop

%%timeit
ci = CacheGen(cl)
[x for x in ci]
[x for x in ci]
[x for x in ci]
100000 loops, best of 3: 13.5 us per loop

¿Alguna receta más rápida que pueda acercarse al bucle "puro"?

Answer 1

Basado en este comentario:

mi intención aquí es que esto solo se usaría si el usuario sabe que quiere iterar varias veces sobre el ''iterable'', pero no sabe si la entrada es un generador o iterable. esto le permite ignorar esa distinción, sin perder (mucho) el rendimiento.

Esta simple solución hace exactamente eso:

def ensure_list(it):
    if isinstance(it, (list, tuple, dict)):
        return it
    else:
        return list(it)

ahora ensure_list(a_list) es prácticamente una ensure_list(a_list) no operativa, dos llamadas a función, mientras que ensure_list(a_generator) convertirá en una lista y la devolverá, que resultó ser más rápida que cualquier otro método.

Answer 2

Lo que quieres no es un iterador, sino un iterable. Un iterador solo puede iterar una vez a través de su contenido. Desea algo que tome un iterador y sobre el cual puede iterar varias veces, produciendo los mismos valores desde el iterador, incluso si el iterador no los recuerda, como un generador. Entonces solo se trata de una cuestión especial: almacenar aquellas entradas que no necesitan almacenamiento en caché. Aquí hay un ejemplo que no es seguro para subprocesos (EDIT: actualizado para mayor eficiencia):

import itertools
class AsYouGoCachingIterable(object):
    def __init__(self, iterable):
        self.iterable = iterable
        self.iter = iter(iterable)
        self.done = False
        self.vals = []

    def __iter__(self):
        if self.done:
            return iter(self.vals)
        #chain vals so far & then gen the rest
        return itertools.chain(self.vals, self._gen_iter())

    def _gen_iter(self):
        #gen new vals, appending as it goes
        for new_val in self.iter:
            self.vals.append(new_val)
            yield new_val
        self.done = True

Y algunos tiempos:

class ListCachingIterable(object):
    def __init__(self, obj):
        self.vals = list(obj)

    def __iter__(self):
        return iter(self.vals)

def cube_generator(max=1000):
    i = 0
    while i < max:
        yield i*i*i
        i += 1

def runit(iterable_factory):
    for i in xrange(5):
        for what in iterable_factory():
            pass

def puregen():
    runit(lambda: cube_generator())
def listtheniter():
    res = list(cube_generator())
    runit(lambda: res)
def listcachingiterable():
    res = ListCachingIterable(cube_generator())
    runit(lambda: res)
def asyougocachingiterable():
    res = AsYouGoCachingIterable(cube_generator())
    runit(lambda: res)

Los resultados son:

In [59]: %timeit puregen()
1000 loops, best of 3: 774 us per loop

In [60]: %timeit listtheniter()
1000 loops, best of 3: 345 us per loop

In [61]: %timeit listcachingiterable()
1000 loops, best of 3: 348 us per loop

In [62]: %timeit asyougocachingiterable()
1000 loops, best of 3: 630 us per loop

Entonces, el enfoque más simple en términos de una clase, ListCachingIterable , funciona tan bien como hacer la list manualmente. La variante "as-you-go" es casi dos veces más lenta, pero tiene ventajas si no consume toda la lista, por ejemplo, si solo está buscando el primer cubo por encima de 100:

def first_cube_past_100(cubes):
    for cube in cubes:
        if cube > 100:
            return cube
    raise Error("No cube > 100 in this iterable")

Entonces:

In [76]: %timeit first_cube_past_100(cube_generator())
100000 loops, best of 3: 2.92 us per loop

In [77]: %timeit first_cube_past_100(ListCachingIterable(cube_generator()))
1000 loops, best of 3: 255 us per loop

In [78]: %timeit first_cube_past_100(AsYouGoCachingIterable(cube_generator()))
100000 loops, best of 3: 10.2 us per loop