英文:
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 })
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论