2

素数を生成するために、FP スタイルでいくつかの go コードを作成しました。

package main
import (
    "fmt"
)

func gen_number_stream() func() (int, bool) {
    i := 1
    return func() (int, bool) {
        i += 1
        return i, true
    }
}

func filter_stream(stream func() (int, bool), f func(int) bool) func() (int, bool) {
    return func() (int, bool) {
        for i, ok := stream(); ok; i, ok = stream() {
            if f(i) {
                return i, true
            }
        }
    return 0, false
    }
}

func sieve(stream func() (int, bool)) func() (int, bool) {
    return func() (int, bool) {
        if p, ok := stream(); ok {
            remaining := filter_stream(stream, func(q int) bool { return q % p != 0 })
            stream = sieve(remaining)
            return p, true
        }
        return 0, false
    }
}


func take(stream func() (int, bool), n int) func() (int, bool) {
    return func() (int, bool) {
        if n > 0 {
            n -= 1
            return stream()
        }
        return 0, false
    }
}

func main() {

    primes := take(sieve(gen_number_stream()), 50)

    for i, ok := primes(); ok; i, ok = primes() {
        fmt.Println(i)
    }

}

このコードを実行すると、どんどん遅くなり、最終的に次のようなランタイム エラーが発生します。

runtime: out of memory:  [...]

これは Python コードのバージョンで、問題なく動作します。

def gen_numbers():
    i = 2
    while True:
        yield i
        i += 1

def sieve(stream):
    p =  stream.next()
    yield p
    for i in sieve( i for i in stream if i % p != 0 ):
        yield i

def take(stream,n):
    for i,s in enumerate(stream):
        if i == 50: break
        yield s

def main():
    for i in take(sieve(gen_numbers()),50):
        print i


if __name__ == '__main__':
    main()

なぜ、どのように修正するのだろうか。私のコードまたは golang コンパイラの問題ですか? ありがとう！

PS: 下手な英語で申し訳ありません。

4

2 に答える 2

2

問題は、再帰的なふるい機能です。ループ内で再帰的に sieve を継続的に呼び出すことで、スタックを吹き飛ばしていると思われます。

func sieve(stream func() (int, bool)) func() (int, bool) {
    return func() (int, bool) {
        if p, ok := stream(); ok {
            remaining := filter_stream(stream, func(q int) bool { return q % p != 0 })
            stream = sieve(remaining) // just keeps calling sieve recursively which eventually blows your stack.
            return p, true
        }
        return 0, false
    }
}
于 2012-08-22T16:32:48.547 に答える
1

ストリームを再利用します

    if p, ok := stream(); ok {
        remaining := filter_stream(stream, func(q int) bool { return q % p != 0 })

しかし、すべての新しい「 」については、新しい「 」pを作成する必要がありますstream2

    if p, ok := stream(); ok {
        stream2 := ....
        remaining := filter_stream(stream2, func(q int) bool { return q % p != 0 })
于 2012-08-22T12:10:28.370 に答える