为什么这段 Go 代码会失败?

huangapple go评论75阅读模式
英文:

Why does this go code fail?

问题

我用函数式编程风格写了一些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:对我的英语很抱歉。

英文:

I have written some go code in FP style to generate primes:

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)
    }

}

when I run this code, it becomes slower and slower and finally gets a runtime error like this:

runtime: out of memory:  [...]

here is a version of python code, and it just runs fine:

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()

I wonder why and how to fix it. Is it a problem of my code or golang compiler?
Thanks!

PS: Sorry for my poor english.

答案1

得分: 2

问题出在你的筛选函数上,它是递归的。我怀疑你在循环中不断地递归调用筛选函数,导致堆栈溢出。

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
    }
}
英文:

The problem is your sieve function which is recursive. I suspect that you are blowing your stack by continually calling sieve recursively in a loop.

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
    }
}

答案2

得分: 1

如果p, ok := stream(); ok,则可以重复使用stream。

但是对于每个新的“p”,您必须创建一个新的“stream2”。

如果p, ok := stream(); ok,则可以重复使用stream。

但是对于每个新的“p”,您必须创建一个新的“stream2”。

英文:

You reuse stream

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

BUT for every new "p" you must create a new "stream2"

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

huangapple
  • 本文由 发表于 2012年8月22日 18:21:18
  • 转载请务必保留本文链接:https://go.coder-hub.com/12071040.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定