golang 各种排序大比拼实例

(编辑:jimmy 日期: 2024/12/23 浏览:2)

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 := root<<1 + 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完成定时任务。

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