快排和堆排性能对比

Damon_330b · · 370 次点击 · · 开始浏览

``````//sort.go
package mysort

import (
"math/rand"
"time"
)

func swap(nums []int, i, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func parition(nums []int, start, end int) int {
idx := rand.Int()%(end-start) + 1 + start
swap(nums, idx, end)
idx = end
for start < end {
for nums[start] <= nums[idx] && start < end {
start++
}
for nums[end] >= nums[idx] && start < end {
end--
}
swap(nums, start, end)
}
swap(nums, start, idx)
return start
}

//quick sort
func QSort(nums []int, start, end int) {
rand.Seed(time.Now().UnixNano())
if start < end {
p := parition(nums, start, end)
QSort(nums, start, p-1)
QSort(nums, p+1, end)
}
}

//生成一个随机的数组，长度为len, 元素最大值不超过max
func GenRandSlice(len, max int) []int {
rand.Seed(time.Now().UnixNano())
a := make([]int, 0)
for i := 0; i < len; i++ {
a = append(a, rand.Int()%max)
}
return a
}

//堆排序
func left(i int) int {
return i << 1
}

func right(i int) int {
return i<<1 + 1
}

func maxHeapify(a []int, i int) {
l := left(i)
r := right(i)
max := i
aLen := len(a)
if l < aLen && a[l] > a[max] {
max = l
}
if r < aLen && a[r] > a[max] {
max = r
}
if max != i {
swap(a, i, max)
maxHeapify(a, max)
}
}

func BuildMaxHeap(a []int) {
aLen := len(a)
if aLen == 0 {
return
}
for i := aLen/2 - 1; i >= 0; i-- {
maxHeapify(a, i)
}
}

func HeapSort(a []int) {
BuildMaxHeap(a)
aLen := len(a)
tmp := a[:]
for i := aLen - 1; i >= 1; i-- {
swap(tmp, 0, i)
tmp = tmp[:len(tmp)-1]
maxHeapify(tmp, 0)
}
}
``````

``````//sort_test.go
import (
"testing"
)

func BenchmarkHeapSort(b *testing.B) {
a := GenRandSlice(10000, 10000)
for i := 0; i < b.N; i++ {
HeapSort(a)
}
}

func BenchmarkQSort(b *testing.B) {
a := GenRandSlice(10000, 10000)
for i := 0; i < b.N; i++ {
QSort(a, 0, len(a)-1)
}
}
``````

``````go test -bench=.

goos: darwin
goarch: amd64
pkg: go_practice/algorithm/mysort
BenchmarkHeapSort-4         2000        914686 ns/op
BenchmarkQSort-4              10     120658646 ns/op
PASS
ok      go_practice/algorithm/mysort    3.269s
``````

``````go test -h
``````

``````
-cpuprofile cpu.out
Write a CPU profile to the specified file before exiting.
Writes test binary as -c would.

-memprofile mem.out
Write an allocation profile to the file after all tests have passed.
Writes test binary as -c would.

-memprofilerate n
Enable more precise (and expensive) memory allocation profiles by
setting runtime.MemProfileRate. See 'go doc runtime.MemProfileRate'.
To profile all memory allocations, use -test.memprofilerate=1.

-mutexprofile mutex.out
Write a mutex contention profile to the specified file
when all tests are complete.
Writes test binary as -c would.

-mutexprofilefraction n
Sample 1 in n stack traces of goroutines holding a
contended mutex.

-outputdir directory
Place output files from profiling in the specified directory,
by default the directory in which "go test" is running.

-trace trace.out
Write an execution trace to the specified file before exiting.
``````

`cpu.out mysort.test` cpu.out是cpu采样结果，mysort.test是测试的二进制文件，使用命令`go tool pprof mysort.test cpu.out`可得到如下结果：

``````File: mysort.test
Type: cpu
Time: Feb 17, 2019 at 12:55pm (CST)
Duration: 2.06s, Total samples = 1.67s (80.90%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top10
Showing nodes accounting for 1.67s, 100% of 1.67s total
Showing top 10 nodes out of 16
flat  flat%   sum%        cum   cum%
1.06s 63.47% 63.47%      1.38s 82.63%  go_practice/algorithm/mysort.maxHeapify
0.30s 17.96% 81.44%      0.30s 17.96%  go_practice/algorithm/mysort.swap (inline)
0.12s  7.19% 88.62%      0.12s  7.19%  runtime.newstack
0.08s  4.79% 93.41%      0.08s  4.79%  go_practice/algorithm/mysort.left (inline)
0.05s  2.99% 96.41%      1.50s 89.82%  go_practice/algorithm/mysort.HeapSort
0.04s  2.40% 98.80%      0.04s  2.40%  runtime.nanotime
0.01s   0.6% 99.40%      0.14s  8.38%  go_practice/algorithm/mysort.BuildMaxHeap
0.01s   0.6%   100%      0.01s   0.6%  runtime.kevent
0     0%   100%      1.50s 89.82%  go_practice/algorithm/mysort.BenchmarkHeapSort
0     0%   100%      0.12s  7.19%  runtime.morestack
``````

``````go test -test.bench="BenchmarkQSort" -cpuprofile cpu.out

go tool pprof mysort.test cpu.out

File: mysort.test
Type: cpu
Time: Feb 17, 2019 at 12:58pm (CST)
Duration: 1.45s, Total samples = 1.16s (79.90%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top10
Showing nodes accounting for 1.16s, 100% of 1.16s total
Showing top 10 nodes out of 20
flat  flat%   sum%        cum   cum%
0.80s 68.97% 68.97%      0.80s 68.97%  math/rand.seedrand (inline)
0.25s 21.55% 90.52%      1.05s 90.52%  math/rand.(*rngSource).Seed
0.05s  4.31% 94.83%      0.05s  4.31%  runtime.nanotime
0.03s  2.59% 97.41%      0.03s  2.59%  runtime.walltime
0.02s  1.72% 99.14%      0.02s  1.72%  runtime.usleep
0.01s  0.86%   100%      0.01s  0.86%  runtime.kevent
0     0%   100%      1.08s 93.10%  go_practice/algorithm/mysort.BenchmarkQSort
0     0%   100%      1.08s 93.10%  go_practice/algorithm/mysort.QSort
0     0%   100%      1.05s 90.52%  math/rand.(*Rand).Seed
0     0%   100%      1.05s 90.52%  math/rand.(*lockedSource).seedPos

``````

1 回复  |  直到 2019-02-22 15:35:05

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

``````//sort.go
package mysort

import (
"math/rand"
"time"
)

func swap(nums []int, i, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

func parition(nums []int, start, end int) int {
idx := rand.Int()%(end-start) + 1 + start
swap(nums, idx, end)
idx = end
for start < end {
for nums[start] <= nums[idx] && start < end {
start++
}
for nums[end] >= nums[idx] && start < end {
end--
}
swap(nums, start, end)
}
swap(nums, start, idx)
return start
}

//quick sort
func QSort(nums []int, start, end int) {
rand.Seed(time.Now().UnixNano())
if start < end {
p := parition(nums, start, end)
QSort(nums, start, p-1)
QSort(nums, p+1, end)
}
}

//生成一个随机的数组，长度为len, 元素最大值不超过max
func GenRandSlice(len, max int) []int {
rand.Seed(time.Now().UnixNano())
a := make([]int, 0)
for i := 0; i < len; i++ {
a = append(a, rand.Int()%max)
}
return a
}

//堆排序
func left(i int) int {
return i << 1
}

func right(i int) int {
return i<<1 + 1
}

func maxHeapify(a []int, i int) {
l := left(i)
r := right(i)
max := i
aLen := len(a)
if l < aLen && a[l] > a[max] {
max = l
}
if r < aLen && a[r] > a[max] {
max = r
}
if max != i {
swap(a, i, max)
maxHeapify(a, max)
}
}

func BuildMaxHeap(a []int) {
aLen := len(a)
if aLen == 0 {
return
}
for i := aLen/2 - 1; i >= 0; i-- {
maxHeapify(a, i)
}
}

func HeapSort(a []int) {
BuildMaxHeap(a)
aLen := len(a)
tmp := a[:]
for i := aLen - 1; i >= 1; i-- {
swap(tmp, 0, i)
tmp = tmp[:len(tmp)-1]
maxHeapify(tmp, 0)
}
}
``````

``````//sort_test.go
import (
"testing"
)

func BenchmarkHeapSort(b *testing.B) {
a := GenRandSlice(10000, 10000)
for i := 0; i < b.N; i++ {
HeapSort(a)
}
}

func BenchmarkQSort(b *testing.B) {
a := GenRandSlice(10000, 10000)
for i := 0; i < b.N; i++ {
QSort(a, 0, len(a)-1)
}
}
``````

``````go test -bench=.

goos: darwin
goarch: amd64
pkg: go_practice/algorithm/mysort
BenchmarkHeapSort-4         2000        914686 ns/op
BenchmarkQSort-4              10     120658646 ns/op
PASS
ok      go_practice/algorithm/mysort    3.269s
``````

``````go test -h
``````

``````
-cpuprofile cpu.out
Write a CPU profile to the specified file before exiting.
Writes test binary as -c would.

-memprofile mem.out
Write an allocation profile to the file after all tests have passed.
Writes test binary as -c would.

-memprofilerate n
Enable more precise (and expensive) memory allocation profiles by
setting runtime.MemProfileRate. See 'go doc runtime.MemProfileRate'.
To profile all memory allocations, use -test.memprofilerate=1.

-mutexprofile mutex.out
Write a mutex contention profile to the specified file
when all tests are complete.
Writes test binary as -c would.

-mutexprofilefraction n
Sample 1 in n stack traces of goroutines holding a
contended mutex.

-outputdir directory
Place output files from profiling in the specified directory,
by default the directory in which "go test" is running.

-trace trace.out
Write an execution trace to the specified file before exiting.
``````

`cpu.out mysort.test` cpu.out是cpu采样结果，mysort.test是测试的二进制文件，使用命令`go tool pprof mysort.test cpu.out`可得到如下结果：

``````File: mysort.test
Type: cpu
Time: Feb 17, 2019 at 12:55pm (CST)
Duration: 2.06s, Total samples = 1.67s (80.90%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top10
Showing nodes accounting for 1.67s, 100% of 1.67s total
Showing top 10 nodes out of 16
flat  flat%   sum%        cum   cum%
1.06s 63.47% 63.47%      1.38s 82.63%  go_practice/algorithm/mysort.maxHeapify
0.30s 17.96% 81.44%      0.30s 17.96%  go_practice/algorithm/mysort.swap (inline)
0.12s  7.19% 88.62%      0.12s  7.19%  runtime.newstack
0.08s  4.79% 93.41%      0.08s  4.79%  go_practice/algorithm/mysort.left (inline)
0.05s  2.99% 96.41%      1.50s 89.82%  go_practice/algorithm/mysort.HeapSort
0.04s  2.40% 98.80%      0.04s  2.40%  runtime.nanotime
0.01s   0.6% 99.40%      0.14s  8.38%  go_practice/algorithm/mysort.BuildMaxHeap
0.01s   0.6%   100%      0.01s   0.6%  runtime.kevent
0     0%   100%      1.50s 89.82%  go_practice/algorithm/mysort.BenchmarkHeapSort
0     0%   100%      0.12s  7.19%  runtime.morestack
``````

``````go test -test.bench="BenchmarkQSort" -cpuprofile cpu.out

go tool pprof mysort.test cpu.out

File: mysort.test
Type: cpu
Time: Feb 17, 2019 at 12:58pm (CST)
Duration: 1.45s, Total samples = 1.16s (79.90%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top10
Showing nodes accounting for 1.16s, 100% of 1.16s total
Showing top 10 nodes out of 20
flat  flat%   sum%        cum   cum%
0.80s 68.97% 68.97%      0.80s 68.97%  math/rand.seedrand (inline)
0.25s 21.55% 90.52%      1.05s 90.52%  math/rand.(*rngSource).Seed
0.05s  4.31% 94.83%      0.05s  4.31%  runtime.nanotime
0.03s  2.59% 97.41%      0.03s  2.59%  runtime.walltime
0.02s  1.72% 99.14%      0.02s  1.72%  runtime.usleep
0.01s  0.86%   100%      0.01s  0.86%  runtime.kevent
0     0%   100%      1.08s 93.10%  go_practice/algorithm/mysort.BenchmarkQSort
0     0%   100%      1.08s 93.10%  go_practice/algorithm/mysort.QSort
0     0%   100%      1.05s 90.52%  math/rand.(*Rand).Seed
0     0%   100%      1.05s 90.52%  math/rand.(*lockedSource).seedPos

``````