Golang差劲的查找prime算法

FredricZhu · · 1052 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

pips/pip_prime.go

package pips

type PrimePip struct {
}

func NewPrimePip() *PrimePip {
    primePip := &PrimePip{}
    return primePip
}

func (primePip *PrimePip) RepeatFn(
    done <-chan interface{},
    fn func() interface{},
) <-chan interface{} {
    valueStream := make(chan interface{})
    go func() {
        defer close(valueStream)
        for {
            select {
            case <-done:
                return
            case valueStream <- fn():
            }
        }
    }()
    return valueStream
}

func (primePip *PrimePip) Take(
    done <-chan interface{},
    valueStream <-chan interface{},
    num int,
) <-chan interface{} {
    takeStream := make(chan interface{})
    go func() {
        defer close(takeStream)
        for i := 0; i < num; i++ {
            select {
            case <-done:
                return
            case takeStream <- <-valueStream:
            }
        }
    }()
    return takeStream
}

func (primePip *PrimePip) ToInt(
    done <-chan interface{},
    valueStream <-chan interface{},
) <-chan int {
    intStream := make(chan int)
    go func() {
        defer close(intStream)
        for v := range valueStream {
            select {
            case <-done:
                return
            case intStream <- v.(int):
            }
        }
    }()
    return intStream
}

func (primePip *PrimePip) PrimeFinder(
    done <-chan interface{},
    intStream <-chan int,
) <-chan interface{} {
    primeStream := make(chan interface{})
    go func() {
        defer close(primeStream)
        for integer := range intStream {
            integer -= 1
            prime := true
            for divisor := integer - 1; divisor > 1; divisor-- {
                if integer%divisor == 0 {
                    prime = false
                    break
                }
            }

            if prime {
                select {
                case <-done:
                    return
                case primeStream <- integer:
                }
            }
        }
    }()
    return primeStream
}

fanin1.go

package main

import (
    "fanin1/pips"
    "fmt"
    "math/rand"
    "time"
)

func main() {
    rand := func() interface{} {
        return rand.Intn(50000000)
    }

    done := make(chan interface{})
    defer close(done)

    primeP := pips.NewPrimePip()
    intStream := primeP.ToInt(done, primeP.RepeatFn(done, rand))

    start := time.Now()
    for prime := range primeP.Take(done, primeP.PrimeFinder(done, intStream), 10) {
        fmt.Printf("\t%v\n", prime)
    }

    fmt.Printf("Time consomed: %v \n", time.Since(start))
}

程序输出如下,可见使用pipline的效率极低,查找10个 5000万内的素数,花了18s。


image.png

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:FredricZhu

查看原文:Golang差劲的查找prime算法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1052 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传