-
Notifications
You must be signed in to change notification settings - Fork 0
/
topk_test.go
119 lines (108 loc) · 1.99 KB
/
topk_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// Copyright (c) 2020 Meng Huang (mhboy@outlook.com)
// This package is licensed under a MIT license that can be found in the LICENSE file.
package topk
import (
"math/rand"
"testing"
)
type list []int
func (h list) Len() int { return len(h) }
func (h list) Less(i, j int) bool { return h[i] < h[j] }
func (h list) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func TestTopK(t *testing.T) {
testTopK(3, false, t)
testTopK(3, true, t)
testTopK(9, true, t)
}
func testTopK(k int, sortK bool, t *testing.T) {
l := list{10, 7, 1, 5, 2}
Top(l, k, sortK)
n := l.Len()
if k > n {
k = n
}
for j := k; j < l.Len(); j++ {
for i := 0; i < k; i++ {
if l.Less(i, j) {
t.Error("top error")
}
}
}
if sortK {
for i := 0; i < k-1; i++ {
if l.Less(i, i+1) {
t.Error("out of order")
}
}
}
t.Log(l)
}
func TestHeapInsert(t *testing.T) {
l := list{10, 7, 2, 5, 1}
n := l.Len()
for i := 1; i < n; i++ {
up(l, i)
}
for i := 1; i < n; i++ {
if l.Less(i, 0) {
t.Error("HeapInsert error")
}
}
t.Log(l)
}
func TestHeapify(t *testing.T) {
l := list{10, 7, 2, 5, 1}
n := l.Len()
for i := n/2 - 1; i >= 0; i-- {
down(l, i, n)
}
for i := 1; i < n; i++ {
if l.Less(i, 0) {
t.Error("Heapify error")
}
}
t.Log(l)
}
func BenchmarkHeapInsert(b *testing.B) {
var l list
num := 1000
for i := 0; i < num; i++ {
l = append(l, rand.Intn(1000000))
}
cp := make(list, num)
for i := 0; i < b.N; i++ {
copy(cp, l)
n := cp.Len()
for j := 1; j < n; j++ {
up(cp, j)
}
}
}
func BenchmarkHeapify(b *testing.B) {
var l list
num := 1000
for i := 0; i < num; i++ {
l = append(l, rand.Intn(1000000))
}
cp := make(list, num)
for i := 0; i < b.N; i++ {
copy(cp, l)
n := cp.Len()
for j := n/2 - 1; j >= 0; j-- {
down(cp, j, n)
}
}
}
func BenchmarkTopk(b *testing.B) {
var l list
num := 1000
for i := 0; i < num; i++ {
l = append(l, rand.Intn(1000000))
}
cp := make(list, num)
k := 10
for i := 0; i < b.N; i++ {
copy(cp, l)
Top(cp, k, false)
}
}