Golang使用扇入法寻找素数

栏目: Go · 发布时间: 5年前

内容简介:pips/pip_prime.gofanin2.go程序输出如下,可知相比于不使用扇入写法,效率从25s提升至5s,提升了五分之四。

pips/pip_prime.go

package pips

import (
    "sync"
)

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
}

func (primePip *PrimePip) FanIn(
    done <-chan interface{},
    channels ...<-chan interface{},
) <-chan interface{} {
    var wg sync.WaitGroup
    multiplexedStream := make(chan interface{})

    multiplexed := func(c <-chan interface{}) {
        defer wg.Done()
        for i := range c {
            select {
            case <-done:
                return
            case multiplexedStream <- i:
            }
        }
    }

    wg.Add(len(channels))
    for _, c := range channels {
        go multiplexed(c)
    }

    go func() {
        wg.Wait()
        close(multiplexedStream)
    }()

    return multiplexedStream
}

fanin2.go

// fanin2
package main

import (
    "fanin2/pips"
    "fmt"
    "math/rand"
    "runtime"
    "time"
)

func main() {
    done := make(chan interface{})
    defer close(done)
    start := time.Now()
    rand := func() interface{} {
        return rand.Intn(50000000)
    }

    primeP := pips.NewPrimePip()
    randIntStream := primeP.ToInt(done, primeP.RepeatFn(done, rand))
    numFinders := runtime.NumCPU()
    fmt.Printf("Spinning up %d prime Finders \n", numFinders)
    finders := make([]<-chan interface{}, numFinders)

    fmt.Println("Primes:")
    for i := 0; i < numFinders; i++ {
        finders[i] = primeP.PrimeFinder(done, randIntStream)
    }

    for prime := range primeP.Take(done, primeP.FanIn(done, finders...), 10) {
        fmt.Printf("\t%d \n", prime)
    }

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

程序输出如下,可知相比于不使用扇入写法,效率从25s提升至5s,提升了五分之四。

Golang使用扇入法寻找素数

image.png


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员的自我修养

程序员的自我修养

陈逸鹤 / 清华大学出版社 / 2017-5 / 49.00

程序员作为一个职业、也作为一个群体,正逐渐从幕后走向前台,并以他们自己的能力加速改变着世界,也改变着人们生活的方方面面。然而,对于程序员,特别是年轻程序员们来说,如何理解自己的职业与发展,如何看待自己的工作与生活,这些问题往往比那些摆在面前的技术难题更让他们难以解答。 这本书从一个成熟程序员、一名IT管理者的角度,以杂记的形式为大家分享关于国内程序员职业生涯、个人发展、编程中的实践与认知乃至......一起来看看 《程序员的自我修养》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码