• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    golang 各种排序大比拼实例

    1、准备工作

    准备数据:

    生成随机数并写入文件,之后在把数据读取出来

    //新生成整数随机数,并存储在txt文件中,
    func NewIntRandm(fileName string, number, maxrandm int) {
     filename := fileName
     file, err := os.Create(filename)
     if err != nil {
      return
     }
     r := rand.New(rand.NewSource(time.Now().UnixNano()))
     rans := make([]string, 0, number)
     for i := 0; i  number; i++ {
      rans = append(rans, strconv.Itoa(r.Intn(maxrandm)))
     }
     file.WriteString(strings.Join(rans, " "))
     defer file.Close()
    }
    //把一串数组存入文件总
    func SavaRandmInt(fileName string, data []int) {
     if fileName == " " || len(data) == 0 {
      return
     }
     var file *os.File
     var openerr error
     file, openerr = os.Open(fileName)
     if openerr != nil {
      var newerr error
      file, newerr = os.Create(fileName)
      if newerr != nil {
       return
      }
     }
     rans := make([]string, 0, len(data))
     for _, v := range data {
      rans = append(rans, strconv.Itoa(v))
     }
     file.WriteString(strings.Join(rans, " "))
     defer file.Close()
    }
    

    准备计时的程序:

    package util
    import "time"
    type Stopwatch struct {
     start time.Time
     stop time.Time
    }
    func (s *Stopwatch) Start() {
     s.start = time.Now()
    }
    func (s *Stopwatch) Stop() {
     s.stop = time.Now()
    }
    //纳秒
    func (s Stopwatch) RuntimeNs() int {
     return s.stop.Nanosecond() - s.start.Nanosecond()
    }
    //微妙
    func (s Stopwatch) RuntimeUs() float64 {
     return (float64)(s.stop.Nanosecond()-s.start.Nanosecond()) / 1000.00
    }
    //毫秒
    func (s Stopwatch) RuntimeMs() float64 {
     return (float64)(s.stop.Nanosecond()-s.start.Nanosecond()) / 1000000.00
    }
    //秒
    func (s Stopwatch) RuntimeS() float64 {
     return (float64)(s.stop.Nanosecond()-s.start.Nanosecond()) / 10000000000.00
    }
    

    2、开始写排序

    我模仿golang中的sort源码包中的写法,暴露了一个接口,把排序的实现都写在内部

    package sort
    // package main
    type Interface interface {
     //获取数据的长度
     Len() int
     //判读索引为i和索引为j的值的大小,在实现的时候如果判断i>j 返回true,则为升序,反之为降序
     Less(i, j int) bool
     //交换索引i,j的值
     Swap(i, j int)
    }
    //冒泡排序
    func BubbleSort(data Interface) {
     n := data.Len()
     for index := 0; index  n; index++ {
      for j := index + 1; j  n; j++ {
       if data.Less(index, j) {
        data.Swap(index, j)
       }
      }
     }
    }
    //此方法比上面的冒泡算法快,因为我找最小元素是指记住下标,并没有每一次都做元素交换
    func SelectSort(data Interface) {
     n := data.Len()
     var min int
     for index := 0; index  n; index++ {
      min = index
      for j := index + 1; j  n; j++ {
       if data.Less(min, j) {
        min = j
       }
      }
      data.Swap(index, min)
     }
    }
    //插入排序
    func InsertSrot(data Interface) {
     count := data.Len()
     for index := 1; index  count; index++ {
      for j := index; j > 0  data.Less(j, j-1); j-- { //j>0 做一个边界守护,不让下标小于0
       data.Swap(j, j-1)
      }
     }
    }
    //希尔排序
    func ShellSort(data Interface) {
     N := data.Len()
     h := 1
     for h  N/3 {
      h = 3*h + 1
     }
     for h > 0 {
      for index := h; index  N; index++ {
       for j := index; j >= h  data.Less(j, j-h); j -= h { //j>0 做一个边界守护,不让下标小于0
        data.Swap(j, j-h)
       }
      }
      h = h / 3
     }
    }
    //快速排序
    func QuickSort(data Interface) {
     n := data.Len()
     low, row := 0, n-1
     quickSort(data, low, row)
    }
    func quickSort(data Interface, low, row int) {
     if low  row {
      i, j, x, last := low, row, low, 0 //0就是使用第一个作为基准值,last这个变量时为了基准最后一次交换变量时出现在那次
      for i  j {
       for i  j  data.Less(x, j) { //比x小的放在前面出现的坑中
        j--
       }
       if i  j {
        data.Swap(i, j)
        i++
        x = j
        last = 1
       }
       for i  j  data.Less(i, x) { //比x大的放在后面出现的坑中
        i++
       }
       if i  j {
        data.Swap(i, j)
        j--
        x = i
        last = -1
       }
      }
      if last == 1 {
       data.Swap(j, x)
      } else if last == -1 {
       data.Swap(i, x)
      }
      quickSort(data, low, i-1)
      quickSort(data, i+1, row)
     }
    }
    //通过控制Less方法来控制升序降序
    func HeapSort(data Interface) {
     makeHeap(data)
     n := data.Len()
     for i := n - 1; i >= 1; i-- {
      data.Swap(0, i)
      heapFixdown(data, 0, i)
     }
    }
    func makeHeap(data Interface) {
     n := data.Len()
     for i := (n - 1) >> 1; i >= 0; i-- {
      heapFixdown(data, i, n)
     }
    }
    func heapFixdown(data Interface, r, n int) {
     root := r //跟结点
     for {
      leftChildIndex := root1 + 1
      if leftChildIndex >= n {
       break
      }
      if leftChildIndex+1  n  data.Less(leftChildIndex+1, leftChildIndex) {
       leftChildIndex++
      }
      if data.Less(root, leftChildIndex) {
       return
      }
      data.Swap(leftChildIndex, root)
      root = leftChildIndex
     }
    }
    

    3、开始使用

    //先实现这个排序接口
    type InSort []int
    func (is InSort) Len() int {
     return len(is)
    }//降序
    func (is InSort) Less(i, j int) bool {
     return is[i] > is[j]
    }
    func (is InSort) Swap(i, j int) {
     is[i], is[j] = is[j], is[i]
    }
    func main() {
     fileName := "randm.txt"
     // util.NewIntRandm(fileName, 1000000, 10000) //封装生成5000000个随机数字
     fileUtil := util.FileUtil{}
     insort := InSort{}
     insort = fileUtil.ReaderAllInt(fileName) //读取生成的随机数
     fmt.Println(insort.Len())
     t := new(util.Stopwatch) //封装的计时间的方法
     t.Start()
     // sort.HeapSort(insort) //开始排序,519.8732 ms
     sort.QuickSort(insort) //开始排序,7.0267 ms
     t.Stop()
     fmt.Println(t.RuntimeMs(), "ms")
     util.SavaRandmInt("result.txt", insort)
    }
    

    快排:10000数组 7.0267 ms,1000000数组 37.7612 ms

    堆排序:10000数组 10.0039 ms,1000000数组 358.6429 ms

    下面是我测试的一些数据:

    HeapSort(insort) //堆排序 10000个数 4.0013 ms,100000个数 54.0659 ms,很稳定,500000个数 208.1511 ms 很稳定
    sort.QuickSort(insort, 0, len(insort)-1) //快速排序 10000个数 3.0017 ms,100000个数,33.0222 ms,很稳定,500000个数 150.1096 ms 很稳定,100000个数 94.0823 ms 很稳定
    sort.SelectSort(insort) //选择排序 10000个数 130.8017 ms,100000个数 时间很长
    sort.BubbleSort(insort) //冒泡排序 10000个数 203.5344ms ,100000个数 187.7438 ms
    sort.InsertSrot(insort) // 插入排序 10000个数 858.6085 ms,100000个数,时间很长
    sort.ShellSort(insort) //希尔插入 10000个数 10.9876 ms,100000个数 46.0322 m ,就做这个范围,很稳定,500000个数 141.8833 ms,相对稳定
    sort.Sort(insort) //golang源码的排序 10000个数 6.0062 ms ,100000个数 19.9988 ms~89.0574 ms 不稳定,500000个数 358.2536 ms 稳定
    

    补充:golang 定时任务方面time.Sleep和time.Tick的优劣对比

    golang 写循环执行的定时任务,常见的有以下三种实现方式:

    1、time.Sleep方法:

    for {
     time.Sleep(time.Second)
     fmt.Println("我在定时执行任务")
    }
    

    2、time.Tick函数:

    t1:=time.Tick(3*time.Second)
    for {
     select {
     case -t1:
      fmt.Println("t1定时器")
     }
    }
    

    3、其中Tick定时任务,也可以先使用time.Ticker函数获取Ticker结构体,然后进行阻塞监听信息,这种方式可以手动选择停止定时任务,在停止任务时,减少对内存的浪费。

    t:=time.NewTicker(time.Second)
    for {
     select {
     case -t.C:
      fmt.Println("t1定时器")
      t.Stop()
     }
    }
    

    其中第二种和第三种可以归为同一类

    这三种定时器的实现原理

    一般来说,你在使用执行定时任务的时候,一般旁人会劝你不要使用time.Sleep完成定时任务,但是为什么不能使用Sleep函数完成定时任务呢,它和Tick函数比,有什么劣势呢?这就需要我们去探讨阅读一下源码,分析一下它们之间的优劣性。

    首先,我们研究一下Tick函数,func Tick(d Duration) -chan Time

    调用Tick函数会返回一个时间类型的channel,如果对channel稍微有些了解的话,我们首先会想到,既然是返回一个channel,在调用Tick方法的过程中,必然创建了goroutine,该Goroutine负责发送数据,唤醒被阻塞的定时任务。我在阅读源码之后,确实发现函数中go出去了一个协程,处理定时任务。

    按照当前的理解,使用一个tick,需要go出去一个协程,效率和对内存空间的占用肯定不能比sleep函数强。我们需要继续阅读源码才拿获取到真理。

    简单的调用过程我就不陈述了,我在这介绍一下核心结构体和方法(删除了部分判断代码,解释我写在表格中):

    func (tb *timersBucket) addtimerLocked(t *timer) {
     t.i = len(tb.t) //计算timersBucket中,当前定时任务的长度
     tb.t = append(tb.t, t)// 将当前定时任务加入timersBucket
     siftupTimer(tb.t, t.i) //维护一个timer结构体的最小堆(四叉树),排序关键字为执行时间,即该定时任务下一次执行的时间
     if !tb.created {
      tb.created = true
      go timerproc(tb)// 如果还没有创建过管理定时任务的协程,则创建一个,执行通知管理timer的协程,最核心代码
     }
    }
    

    timersBucket,顾名思义,时间任务桶,是外界不可见的全局变量。每当有新的timer定时器任务时,会将timer加入到timersBucket中的timer切片。

    timerBucket结构体如下:

    type timersBucket struct {
     lock   mutex //添加新定时任务时需要加锁(冲突点在于维护堆)
     t   []*timer //timer切片,构造方式为四叉树最小堆
    }
    

    func timerproc(tb *timersBucket) 详细介绍

    可以称之为定时任务处理器,所有的定时任务都会加入timersBucket,然后在该函数中等待被处理。等待被处理的timer,根据when字段(任务执行的时间,int类型,纳秒级别)构成一个最小堆,每次处理完成堆顶的某个timer时,会给它的when字段加上定时任务循环间隔时间(即Tick(d Duration) 中的d参数),然后重新维护堆,保证when最小的timer在堆顶。当堆中没有可以处理的timer(有timer,但是还不到执行时间),需要计算当前时间和堆顶中timer的任务执行时间差值delta,定时任务处理器沉睡delta段时间,等待被调度器唤醒。核心代码如下(注释写在每行代码的后面,删除一些判断代码以及不利于阅读的非核心代码):

    func timerproc(tb *timersBucket) {
     for {
      lock(tb.lock) //加锁
      now := nanotime() //当前时间的纳秒值
      delta := int64(-1) //最近要执行的timer和当前时间的差值
      for {
       if len(tb.t) == 0 {
       delta = -1
       break
       }//当前无可执行timer,直接跳出该循环
       t := tb.t[0]
       delta = t.when - now //取when组小的的timer,计算于当前时间的差值
       if delta > 0 {
       break
       }// delta大于0,说明还未到发送channel时间,需要跳出循环去睡眠delta时间
       if t.period > 0 {
       // leave in heap but adjust next time to fire
       t.when += t.period * (1 + -delta/t.period)// 计算该timer下次执行任务的时间
       siftdownTimer(tb.t, 0) //调整堆
       } else {
       // remove from heap,如果没有设定下次执行时间,则将该timer从堆中移除(time.after和time.sleep函数即是只执行一次定时任务)
       last := len(tb.t) - 1
       if last > 0 {
        tb.t[0] = tb.t[last]
        tb.t[0].i = 0
       }
       tb.t[last] = nil
       tb.t = tb.t[:last]
       if last > 0 {
        siftdownTimer(tb.t, 0)
       }
       t.i = -1 // mark as removed
       }
       f := t.f
       arg := t.arg
       seq := t.seq
       unlock(tb.lock)//解锁
       f(arg, seq) //在channel中发送time结构体,唤醒阻塞的协程
       lock(tb.lock)
      }
      if delta  0 {
       // No timers left - put goroutine to sleep.
       goparkunlock(tb.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
       continue
      }// delta小于0说明当前无定时任务,直接进行阻塞进行睡眠
      tb.sleeping = true
      tb.sleepUntil = now + delta
      unlock(tb.lock)
      notetsleepg(tb.waitnote, delta) //睡眠delta时间,唤醒之后就可以执行在堆顶的定时任务了
     }
    }
    

    至此,time.Tick函数涉及到的主要功能就讲解结束了,总结一下就是启动定时任务时,会创建一个唯一协程,处理timer,所有的timer都在该协程中处理。

    然后,我们再阅读一下sleep的源码实现,核心源码如下:

    //go:linkname timeSleep time.Sleep
    func timeSleep(ns int64) {
     *t = timer{} //创建一个定时任务
     t.when = nanotime() + ns //计算定时任务的执行时间点
     t.f = goroutineReady //执行方法
     tb.addtimerLocked(t) //加入timer堆,并在timer定时任务执行协程中等待被执行
     goparkunlock(tb.lock, "sleep", traceEvGoSleep, 2) //睡眠,等待定时任务协程通知唤醒
    }
    

    读了sleep的核心代码之后,是不是突然发现和Tick函数的内容很类似,都创建了timer,并加入了定时任务处理协程。神奇之处就在于,实际上这两个函数产生的timer都放入了同一个timer堆,都在定时任务处理协程中等待被处理。

    优劣性对比,使用建议

    现在我们知道了,Tick,Sleep,包括time.After函数,都使用的timer结构体,都会被放在同一个协程中统一处理,这样看起来使用Tick,Sleep并没有什么区别。

    实际上是有区别的,Sleep是使用睡眠完成定时任务,需要被调度唤醒。Tick函数是使用channel阻塞当前协程,完成定时任务的执行。当前并不清楚golang 阻塞和睡眠对资源的消耗会有什么区别,这方面不能给出建议。

    但是使用channel阻塞协程完成定时任务比较灵活,可以结合select设置超时时间以及默认执行方法,而且可以设置timer的主动关闭,以及不需要每次都生成一个timer(这方面节省系统内存,垃圾收回也需要时间)。

    所以,建议使用time.Tick完成定时任务。

    以上为个人经验,希望能给大家一个参考,也希望大家多多支持脚本之家。如有错误或未考虑完全的地方,望不吝赐教。

    您可能感兴趣的文章:
    • golang/python实现归并排序实例代码
    • Golang 实现插入排序的方法示例(2种)
    • Golang实现拓扑排序(DFS算法版)
    • golang对自定义类型进行排序的解决方法
    • Golang算法问题之数组按指定规则排序的方法分析
    • Golang正整数指定规则排序算法问题分析
    上一篇:利用golang的字符串解决leetcode翻转字符串里的单词
    下一篇:Golang压缩Jpeg图片和PNG图片的操作
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

    golang 各种排序大比拼实例 golang,各种,排序,大,比拼,