1、準(zhǔn)備工作
準(zhǔn)備數(shù)據(jù)：
生成隨機(jī)數(shù)并寫入文件，之后在把數(shù)據(jù)讀取出來
//新生成整數(shù)隨機(jī)數(shù)，并存儲在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()
}
//把一串?dāng)?shù)組存入文件總
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()
}
準(zhǔn)備計(jì)時(shí)的程序：
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源碼包中的寫法，暴露了一個(gè)接口，把排序的實(shí)現(xiàn)都寫在內(nèi)部
package sort
// package main
type Interface interface {
//獲取數(shù)據(jù)的長度
Len() int
//判讀索引為i和索引為j的值的大小，在實(shí)現(xiàn)的時(shí)候如果判斷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)
}
}
}
}
//此方法比上面的冒泡算法快，因?yàn)槲艺易钚≡厥侵赣涀∠聵?biāo)，并沒有每一次都做元素交換
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 做一個(gè)邊界守護(hù)，不讓下標(biāo)小于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 做一個(gè)邊界守護(hù)，不讓下標(biāo)小于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就是使用第一個(gè)作為基準(zhǔn)值,last這個(gè)變量時(shí)為了基準(zhǔn)最后一次交換變量時(shí)出現(xiàn)在那次
for i j {
for i j data.Less(x, j) { //比x小的放在前面出現(xiàn)的坑中
j--
}
if i j {
data.Swap(i, j)
i++
x = j
last = 1
}
for i j data.Less(i, x) { //比x大的放在后面出現(xiàn)的坑中
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 //跟結(jié)點(diǎn)
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、開始使用
//先實(shí)現(xiàn)這個(gè)排序接口
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個(gè)隨機(jī)數(shù)字
fileUtil := util.FileUtil{}
insort := InSort{}
insort = fileUtil.ReaderAllInt(fileName) //讀取生成的隨機(jī)數(shù)
fmt.Println(insort.Len())
t := new(util.Stopwatch) //封裝的計(jì)時(shí)間的方法
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數(shù)組 7.0267 ms，1000000數(shù)組 37.7612 ms
堆排序：10000數(shù)組 10.0039 ms，1000000數(shù)組 358.6429 ms
下面是我測試的一些數(shù)據(jù)：
HeapSort(insort) //堆排序 10000個(gè)數(shù) 4.0013 ms,100000個(gè)數(shù) 54.0659 ms,很穩(wěn)定，500000個(gè)數(shù) 208.1511 ms 很穩(wěn)定
sort.QuickSort(insort, 0, len(insort)-1) //快速排序 10000個(gè)數(shù) 3.0017 ms,100000個(gè)數(shù),33.0222 ms,很穩(wěn)定，500000個(gè)數(shù) 150.1096 ms 很穩(wěn)定,100000個(gè)數(shù) 94.0823 ms 很穩(wěn)定
sort.SelectSort(insort) //選擇排序 10000個(gè)數(shù) 130.8017 ms,100000個(gè)數(shù) 時(shí)間很長
sort.BubbleSort(insort) //冒泡排序 10000個(gè)數(shù) 203.5344ms ，100000個(gè)數(shù) 187.7438 ms
sort.InsertSrot(insort) // 插入排序 10000個(gè)數(shù) 858.6085 ms，100000個(gè)數(shù),時(shí)間很長
sort.ShellSort(insort) //希爾插入 10000個(gè)數(shù) 10.9876 ms，100000個(gè)數(shù) 46.0322 m ，就做這個(gè)范圍，很穩(wěn)定，500000個(gè)數(shù) 141.8833 ms，相對穩(wěn)定
sort.Sort(insort) //golang源碼的排序 10000個(gè)數(shù) 6.0062 ms ，100000個(gè)數(shù) 19.9988 ms~89.0574 ms 不穩(wěn)定,500000個(gè)數(shù) 358.2536 ms 穩(wěn)定
補(bǔ)充：golang 定時(shí)任務(wù)方面time.Sleep和time.Tick的優(yōu)劣對比
golang 寫循環(huán)執(zhí)行的定時(shí)任務(wù)，常見的有以下三種實(shí)現(xiàn)方式:
1、time.Sleep方法：
for {
time.Sleep(time.Second)
fmt.Println("我在定時(shí)執(zhí)行任務(wù)")
}
2、time.Tick函數(shù)：
t1:=time.Tick(3*time.Second)
for {
select {
case -t1:
fmt.Println("t1定時(shí)器")
}
}
3、其中Tick定時(shí)任務(wù)，也可以先使用time.Ticker函數(shù)獲取Ticker結(jié)構(gòu)體，然后進(jìn)行阻塞監(jiān)聽信息，這種方式可以手動選擇停止定時(shí)任務(wù)，在停止任務(wù)時(shí)，減少對內(nèi)存的浪費(fèi)。
t:=time.NewTicker(time.Second)
for {
select {
case -t.C:
fmt.Println("t1定時(shí)器")
t.Stop()
}
}
其中第二種和第三種可以歸為同一類
這三種定時(shí)器的實(shí)現(xiàn)原理
一般來說，你在使用執(zhí)行定時(shí)任務(wù)的時(shí)候，一般旁人會勸你不要使用time.Sleep完成定時(shí)任務(wù)，但是為什么不能使用Sleep函數(shù)完成定時(shí)任務(wù)呢，它和Tick函數(shù)比，有什么劣勢呢？這就需要我們?nèi)ヌ接戦喿x一下源碼，分析一下它們之間的優(yōu)劣性。
首先，我們研究一下Tick函數(shù)，func Tick(d Duration) -chan Time
調(diào)用Tick函數(shù)會返回一個(gè)時(shí)間類型的channel，如果對channel稍微有些了解的話，我們首先會想到，既然是返回一個(gè)channel，在調(diào)用Tick方法的過程中，必然創(chuàng)建了goroutine,該Goroutine負(fù)責(zé)發(fā)送數(shù)據(jù)，喚醒被阻塞的定時(shí)任務(wù)。我在閱讀源碼之后，確實(shí)發(fā)現(xiàn)函數(shù)中g(shù)o出去了一個(gè)協(xié)程，處理定時(shí)任務(wù)。
按照當(dāng)前的理解，使用一個(gè)tick,需要go出去一個(gè)協(xié)程，效率和對內(nèi)存空間的占用肯定不能比sleep函數(shù)強(qiáng)。我們需要繼續(xù)閱讀源碼才拿獲取到真理。
簡單的調(diào)用過程我就不陳述了，我在這介紹一下核心結(jié)構(gòu)體和方法（刪除了部分判斷代碼，解釋我寫在表格中）：
func (tb *timersBucket) addtimerLocked(t *timer) {
t.i = len(tb.t) //計(jì)算timersBucket中，當(dāng)前定時(shí)任務(wù)的長度
tb.t = append(tb.t, t)// 將當(dāng)前定時(shí)任務(wù)加入timersBucket
siftupTimer(tb.t, t.i) //維護(hù)一個(gè)timer結(jié)構(gòu)體的最小堆（四叉樹），排序關(guān)鍵字為執(zhí)行時(shí)間，即該定時(shí)任務(wù)下一次執(zhí)行的時(shí)間
if !tb.created {
tb.created = true
go timerproc(tb)// 如果還沒有創(chuàng)建過管理定時(shí)任務(wù)的協(xié)程，則創(chuàng)建一個(gè)，執(zhí)行通知管理timer的協(xié)程，最核心代碼
}
}
timersBucket，顧名思義，時(shí)間任務(wù)桶，是外界不可見的全局變量。每當(dāng)有新的timer定時(shí)器任務(wù)時(shí)，會將timer加入到timersBucket中的timer切片。
timerBucket結(jié)構(gòu)體如下：
type timersBucket struct {
lock mutex //添加新定時(shí)任務(wù)時(shí)需要加鎖（沖突點(diǎn)在于維護(hù)堆）
t []*timer //timer切片，構(gòu)造方式為四叉樹最小堆
}
func timerproc(tb *timersBucket) 詳細(xì)介紹
可以稱之為定時(shí)任務(wù)處理器，所有的定時(shí)任務(wù)都會加入timersBucket，然后在該函數(shù)中等待被處理。等待被處理的timer，根據(jù)when字段（任務(wù)執(zhí)行的時(shí)間，int類型，納秒級別）構(gòu)成一個(gè)最小堆，每次處理完成堆頂?shù)哪硞€(gè)timer時(shí)，會給它的when字段加上定時(shí)任務(wù)循環(huán)間隔時(shí)間（即Tick(d Duration) 中的d參數(shù)），然后重新維護(hù)堆，保證when最小的timer在堆頂。當(dāng)堆中沒有可以處理的timer(有timer,但是還不到執(zhí)行時(shí)間)，需要計(jì)算當(dāng)前時(shí)間和堆頂中timer的任務(wù)執(zhí)行時(shí)間差值delta，定時(shí)任務(wù)處理器沉睡delta段時(shí)間，等待被調(diào)度器喚醒。核心代碼如下（注釋寫在每行代碼的后面，刪除一些判斷代碼以及不利于閱讀的非核心代碼）：
func timerproc(tb *timersBucket) {
for {
lock(tb.lock) //加鎖
now := nanotime() //當(dāng)前時(shí)間的納秒值
delta := int64(-1) //最近要執(zhí)行的timer和當(dāng)前時(shí)間的差值
for {
if len(tb.t) == 0 {
delta = -1
break
}//當(dāng)前無可執(zhí)行timer,直接跳出該循環(huán)
t := tb.t[0]
delta = t.when - now //取when組小的的timer，計(jì)算于當(dāng)前時(shí)間的差值
if delta > 0 {
break
}// delta大于0，說明還未到發(fā)送channel時(shí)間，需要跳出循環(huán)去睡眠delta時(shí)間
if t.period > 0 {
// leave in heap but adjust next time to fire
t.when += t.period * (1 + -delta/t.period)// 計(jì)算該timer下次執(zhí)行任務(wù)的時(shí)間
siftdownTimer(tb.t, 0) //調(diào)整堆
} else {
// remove from heap，如果沒有設(shè)定下次執(zhí)行時(shí)間，則將該timer從堆中移除（time.after和time.sleep函數(shù)即是只執(zhí)行一次定時(shí)任務(wù)）
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中發(fā)送time結(jié)構(gòu)體,喚醒阻塞的協(xié)程
lock(tb.lock)
}
if delta 0 {
// No timers left - put goroutine to sleep.
goparkunlock(tb.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
continue
}// delta小于0說明當(dāng)前無定時(shí)任務(wù)，直接進(jìn)行阻塞進(jìn)行睡眠
tb.sleeping = true
tb.sleepUntil = now + delta
unlock(tb.lock)
notetsleepg(tb.waitnote, delta) //睡眠delta時(shí)間，喚醒之后就可以執(zhí)行在堆頂?shù)亩〞r(shí)任務(wù)了
}
}
至此，time.Tick函數(shù)涉及到的主要功能就講解結(jié)束了，總結(jié)一下就是啟動定時(shí)任務(wù)時(shí)，會創(chuàng)建一個(gè)唯一協(xié)程，處理timer,所有的timer都在該協(xié)程中處理。
然后，我們再閱讀一下sleep的源碼實(shí)現(xiàn)，核心源碼如下：
//go:linkname timeSleep time.Sleep
func timeSleep(ns int64) {
*t = timer{} //創(chuàng)建一個(gè)定時(shí)任務(wù)
t.when = nanotime() + ns //計(jì)算定時(shí)任務(wù)的執(zhí)行時(shí)間點(diǎn)
t.f = goroutineReady //執(zhí)行方法
tb.addtimerLocked(t) //加入timer堆，并在timer定時(shí)任務(wù)執(zhí)行協(xié)程中等待被執(zhí)行
goparkunlock(tb.lock, "sleep", traceEvGoSleep, 2) //睡眠，等待定時(shí)任務(wù)協(xié)程通知喚醒
}
讀了sleep的核心代碼之后，是不是突然發(fā)現(xiàn)和Tick函數(shù)的內(nèi)容很類似，都創(chuàng)建了timer,并加入了定時(shí)任務(wù)處理協(xié)程。神奇之處就在于，實(shí)際上這兩個(gè)函數(shù)產(chǎn)生的timer都放入了同一個(gè)timer堆，都在定時(shí)任務(wù)處理協(xié)程中等待被處理。
優(yōu)劣性對比，使用建議
現(xiàn)在我們知道了，Tick，Sleep，包括time.After函數(shù)，都使用的timer結(jié)構(gòu)體，都會被放在同一個(gè)協(xié)程中統(tǒng)一處理，這樣看起來使用Tick，Sleep并沒有什么區(qū)別。
實(shí)際上是有區(qū)別的，Sleep是使用睡眠完成定時(shí)任務(wù)，需要被調(diào)度喚醒。Tick函數(shù)是使用channel阻塞當(dāng)前協(xié)程，完成定時(shí)任務(wù)的執(zhí)行。當(dāng)前并不清楚golang 阻塞和睡眠對資源的消耗會有什么區(qū)別，這方面不能給出建議。
但是使用channel阻塞協(xié)程完成定時(shí)任務(wù)比較靈活，可以結(jié)合select設(shè)置超時(shí)時(shí)間以及默認(rèn)執(zhí)行方法，而且可以設(shè)置timer的主動關(guān)閉，以及不需要每次都生成一個(gè)timer(這方面節(jié)省系統(tǒng)內(nèi)存，垃圾收回也需要時(shí)間)。
所以，建議使用time.Tick完成定時(shí)任務(wù)。
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。
您可能感興趣的文章:- golang/python實(shí)現(xiàn)歸并排序?qū)嵗a
- Golang 實(shí)現(xiàn)插入排序的方法示例(2種)
- Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版)
- golang對自定義類型進(jìn)行排序的解決方法
- Golang算法問題之?dāng)?shù)組按指定規(guī)則排序的方法分析
- Golang正整數(shù)指定規(guī)則排序算法問題分析
