伏龙阁资源网

golang 各种排序大比拼实例
站长资源 2024/11/22 佚名
2 0

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完成定时任务。

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

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
www.wwsws.com 伏龙阁资源网
39,976影音资源
44,792技术资源
21,817软件资源
651,128站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接