Слияние ленивых потоков (с помощью генераторов) в Python

Я играю с функциональными возможностями Python 3, и я попытался реализовать классический алгоритм для вычисления чисел Хэмминга. Это числа, которые имеют в качестве простых множителей только 2, 3 или 5. Первые числа Хэмминга: 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 18, 20 и так далее.

Моя реализация заключается в следующем:

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)

Проблема в том, что слияние кажется просто не работает. До этого я реализовал Sieve of Eratosthenes таким же образом, и он работал совершенно нормально:

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)

Этот использует те же методы, что и моя операция слияния. Так что я не вижу никакой разницы. Есть ли у вас какие-либо идеи?

(Я знаю, что все это может быть реализовано другими способами, но моя цель - точно понять генераторы и чисто функциональные возможности, в том числе рекурсию, Python, без использования объявлений классов или специальных предварительно созданных функций Python.)

UPD: Уилл Несс, вот моя реализация этих алгоритмов в LISP (Racket):

(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)))))
Источник

1 ответ

Решение

Ваш алгоритм неверен. Ваш m2, m3, m5 должно быть масштабирование hamming_numbers не integers,

Основная проблема заключается в следующем: ваш merge() звонки next() для обоих аргументов безоговорочно, поэтому оба продвигаются на один шаг. Таким образом, после производства первого числа, например, 2 для m23 генератор, при следующем вызове он видит свой 1-й аргумент как 4(,6,8,...) и 2-й как 6(,9,12,...), 3 уже ушел. Таким образом, он всегда извлекает оба аргумента и всегда возвращает заголовок первого (тестовая запись на http://ideone.com/doeX2Q).

призвание iter() совершенно лишнее, здесь ничего не добавляется. Когда я его удаляю ( http://ideone.com/7tk85h), программа работает точно так же и выдает точно такой же (неправильный) вывод. Обычно iter() служит для создания ленивого объекта итератора, но его аргументы здесь уже являются такими генераторами.

Там нет необходимости звонить iter() в вашем sieve() а также ( http://ideone.com/kYh7Di). sieve() уже определяет генератор, и filter() в Python 3 создает итератор из функции и итерируемый (генераторы итеративны). Смотрите также, например, Разница между генераторами и итераторами Python.

Мы можем сделать слияние следующим образом:

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)

Сама по себе рекурсия необязательна при определении sieve() функция тоже. На самом деле это служит только для того, чтобы скрыть огромный недостаток этого кода. Любое простое число, которое оно производит, будет проверено всеми простыми числами ниже его по значению, но действительно нужны только те простые числа, которые меньше его квадратного корня. Мы можем легко исправить это в нерекурсивном стиле ( 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

Теперь это намного, намного, намного эффективнее (см. Также: Объясните этот кусок кода на Haskell, который выводит поток простых чисел).

Рекурсивный или нет, это просто синтаксическая характеристика кода. Фактические структуры времени выполнения одинаковы - filter() Адаптеры поднимаются над входным потоком - либо в соответствующие моменты, либо слишком рано (поэтому у нас их будет слишком много).

Источник

Я предложу другой подход - использование Python heapq (min-heapq) с генератором (ленивая оценка) (если вы не настаиваете на сохранении функции merge())

from heapq import heappush, heappop

def hamming_numbers(n):
    ans = [1]

    last = 0
    count = 0

    while count < n:
        x = heappop(ans)

        if x > last:
            yield x

            last = x
            count += 1

            heappush(ans, 2* x)
            heappush(ans, 3* x)
            heappush(ans, 5* x)


    >>> n  = 20
    >>> print(list(hamming_numbers(20)))
       [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]
Источник
Другие вопросы по тегам