iteradores - Fusión de corrientes perezosas(usando generadores) en Python

que es un iterable en python

Question

Estoy jugando con las capacidades funcionales de Python 3 e intenté implementar un algoritmo clásico para calcular los números de Hamming. Esos son los números que tienen como factores primarios solo 2, 3 o 5. Los primeros números de Hamming son 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 y así sucesivamente.

Mi implementación es la siguiente:

def scale(s, m):
    return (x*m for x in s)

def merge(s1, s2):
    it1, it2 = iter(s1), iter(s2)
    x1, x2 = next(it1), next(it2)
    if x1 < x2:
        x = x1
        it = iter(merge(it1, s2))
    elif x1 > x2:
        x = x2
        it = iter(merge(s1, it2))
    else:
        x = x1
        it = iter(merge(it1, it2))
    yield x
    while True: yield next(it)

def integers():
    n = 0
    while True:
        n += 1
        yield n

m2 = scale(integers(), 2)
m3 = scale(integers(), 3)
m5 = scale(integers(), 5)

m23 = merge(m2, m3)

hamming_numbers = merge(m23, m5)

El problema es que fusionarse parece que no funciona. Antes de eso, implementé Sieve of Eratosthenes de la misma manera, y funcionó perfectamente bien:

def sieve(s):
    it = iter(s)
    x = next(it)
    yield x
    it = iter(sieve(filter(lambda y: x % y, it)))
    while True: yield next(it)

Este usa las mismas técnicas que mi operación de fusión. Entonces no puedo ver ninguna diferencia. ¿Tienes alguna idea?

(Sé que todos estos pueden implementarse de otras maneras, pero mi objetivo es exactamente entender generadores y capacidades funcionales puras, incluida la recursión, de Python, sin utilizar declaraciones de clase o funciones especiales de Python preconstruidas).

UPD: para Will Ness aquí está mi implementación de estos algoritmos en LISP (Racket en realidad):

(define (scale str m)
  (stream-map (lambda (x) (* x m)) str))

(define (integers-from n)
  (stream-cons n
               (integers-from (+ n 1))))

(define (merge s1 s2)
  (let ((x1 (stream-first s1))
        (x2 (stream-first s2)))
    (cond ((< x1 x2)
           (stream-cons x1 (merge (stream-rest s1) s2)))
          ((> x1 x2)
           (stream-cons x2 (merge s1 (stream-rest s2))))
          (else
           (stream-cons x1 (merge (stream-rest s1) (stream-rest s2)))))))


(define integers (integers-from 1))

(define hamming-numbers
  (stream-cons 1 (merge (scale hamming-numbers 2)
                        (merge (scale hamming-numbers 3)
                               (scale hamming-numbers 5)))))

Answer 1

Tu algoritmo es incorrecto Su m2, m3, m5 debería estar escalando hamming_numbers , no integers .

El principal problema es este: su merge() llama a next() para sus dos argumentos incondicionalmente, por lo que ambos avanzan un paso. Entonces, después de producir el primer número, por ej. 2 para el generador m23 , en la siguiente invocación ve su primer argumento como 4(,6,8,...) y 2do como 6(,9,12,...) . El 3 ya se ha ido. Por lo tanto, siempre extrae sus argumentos y siempre devuelve el encabezado de la primera (entrada de prueba en http://ideone.com/doeX2Q ).

Llamar a iter() es totalmente superfluo, no agrega nada aquí. Cuando lo elimino ( http://ideone.com/7tk85h ), el programa funciona exactamente igual y produce exactamente el mismo resultado (incorrecto). Normalmente iter() sirve para crear un objeto iterador perezoso, pero sus argumentos aquí ya son tales generadores.

No es necesario llamar también a iter() en su sieve() ( http://ideone.com/kYh7Di ). sieve() ya define un generador, y filter() en Python 3 crea un iterador a partir de una función y un iterable (los generadores son iterables). Véase también, por ejemplo, Diferencia entre generadores e iteradores de Python .

Podemos hacer la fusión así, en su lugar:

def merge(s1, s2):
  x1, x2 = next(s1), next(s2)
  while True:
    if x1 < x2:
        yield x1
        x1 = next(s1)
    elif x1 > x2:
        yield x2
        x2 = next(s2)
    else:
        yield x1
        x1, x2 = next(s1), next(s2)

La recursividad en sí misma no es esencial para definir también la función sieve() . De hecho, solo sirve para ocultar una enorme deficiencia de ese código. Cualquier primo que produzca será probado por todos los números primos debajo de él en valor, pero solo aquellos que están debajo de su raíz cuadrada son realmente necesarios. Podemos arreglarlo bastante fácilmente en un estilo no recursivo ( http://ideone.com/Qaycpe ):

def sieve(s):    # call as: sieve( integers_from(2))
    x = next(s)  
    yield x
    ps = sieve( integers_from(2))           # independent primes supply
    p = next(ps) 
    q = p*p       ; print((p,q))
    while True:
        x = next(s)
        while x<q: 
            yield x
            x = next(s)
        # here x == q
        s = filter(lambda y,p=p: y % p, s)  # filter creation postponed 
        p = next(ps)                        #   until square of p seen in input
        q = p*p 

Esto es ahora mucho, mucho, mucho más eficiente (ver también: Explicar este trozo de código haskell que genera una secuencia de números primos ).

Recursivo o no, es solo una característica sintáctica de un código . Las estructuras de tiempo de ejecución reales son las mismas: los adaptadores de filter() que se elevan sobre un flujo de entrada, ya sea en los momentos apropiados, o demasiado pronto (por lo que terminaríamos con muchos de ellos).