2

私はPython3の機能容量で遊んでおり、ハミング数を計算するための古典的なアルゴリズムを実装しようとしました。これが素因数として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)

マージが機能しないように見えるという問題。その前に、私はエラトステネスのふるいを同じ方法で実装しました、そしてそれは完全にうまくいきました：

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：Will Nessの場合、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)))))
4

2 に答える 2

3

アルゴリズムが正しくありません。ではなく、スケーリングするm2, m3, m5必要があります。hamming_numbersintegers

主な問題はこれです：あなたmerge()はnext()無条件に両方の引数を要求するので、両方とも一歩進んでいます。したがって、たとえばジェネレーターの最初の数値を生成した後2、m23次の呼び出しで、最初の引数をとして4(,6,8,...)、2番目の引数をとして認識し6(,9,12,...)ます。は3すでになくなっています。したがって、常に両方の引数をプルし、常に1番目の先頭を返します（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()アダプターは入力ストリームの上に持ち上げられますが、適切なタイミングで、または早すぎる（つまり、アダプターが多すぎることになります）。

于 2013-02-01T14:29:53.730 に答える
1

私はこの異なるアプローチを提案します-ジェネレーター（遅延評価）でPython heapq（ ）を使用します（関数を維持することを主張しない場合）min-heapqmerge()

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]
于 2020-11-30T02:03:24.773 に答える