Golang差劲的查找prime算法

FredricZhu · · 1035 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

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。