为什么此go代码失败？

Question

我已经以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编译器有问题吗？谢谢！

Answer 1

问题是您的筛选功能是递归的。我怀疑您是通过在循环中连续递归调用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    }}

Answer 2

您重用流    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 })