You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
232 lines
6.1 KiB
232 lines
6.1 KiB
// Copyright 2020 PingCAP, Inc.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
package selection
|
|
|
|
import (
|
|
"math/rand"
|
|
"sort"
|
|
"testing"
|
|
"time"
|
|
|
|
. "github.com/pingcap/check"
|
|
)
|
|
|
|
type testSuite struct{}
|
|
|
|
var _ = Suite(&testSuite{})
|
|
|
|
func TestT(t *testing.T) {
|
|
CustomVerboseFlag = true
|
|
*CustomParallelSuiteFlag = true
|
|
TestingT(t)
|
|
}
|
|
|
|
type testSlice []int
|
|
|
|
func (a testSlice) Len() int { return len(a) }
|
|
func (a testSlice) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
|
|
func (a testSlice) Less(i, j int) bool { return a[i] < a[j] }
|
|
|
|
var (
|
|
globalCase10000000 testSlice
|
|
globalCase1000000 testSlice
|
|
globalCase100000 testSlice
|
|
globalCase10000 testSlice
|
|
globalCase1000 testSlice
|
|
globalCase100 testSlice
|
|
globalCase50 testSlice
|
|
)
|
|
|
|
func init() {
|
|
globalCase10000000 = randomTestCase(10000000)
|
|
globalCase1000000 = randomTestCase(1000000)
|
|
globalCase100000 = randomTestCase(100000)
|
|
globalCase10000 = randomTestCase(10000)
|
|
globalCase1000 = randomTestCase(1000)
|
|
globalCase100 = randomTestCase(100)
|
|
globalCase50 = randomTestCase(50)
|
|
}
|
|
|
|
func (s *testSuite) TestSelection(c *C) {
|
|
data := testSlice{1, 2, 3, 4, 5}
|
|
index := Select(data, 3)
|
|
c.Assert(data[index], Equals, 3)
|
|
}
|
|
|
|
func (s *testSuite) TestSelectionWithDuplicate(c *C) {
|
|
data := testSlice{1, 2, 3, 3, 5}
|
|
index := Select(data, 3)
|
|
c.Assert(data[index], Equals, 3)
|
|
index = Select(data, 5)
|
|
c.Assert(data[index], Equals, 5)
|
|
}
|
|
|
|
func (s *testSuite) TestSelectionWithRandomCase(c *C) {
|
|
data := randomTestCase(1000000)
|
|
index := Select(data, 500000)
|
|
actual := data[index]
|
|
sort.Stable(data)
|
|
expected := data[499999]
|
|
c.Assert(actual, Equals, expected)
|
|
}
|
|
|
|
func (s *testSuite) TestSelectionWithSerialCase(c *C) {
|
|
data := serialTestCase(1000000)
|
|
sort.Sort(sort.Reverse(data))
|
|
index := Select(data, 500000)
|
|
actual := data[index]
|
|
sort.Stable(data)
|
|
expected := data[499999]
|
|
c.Assert(actual, Equals, expected)
|
|
}
|
|
|
|
func randomTestCase(size int) testSlice {
|
|
data := make(testSlice, 0, size)
|
|
rand.Seed(time.Now().Unix())
|
|
for i := 0; i < size; i++ {
|
|
data = append(data, rand.Int()%100)
|
|
}
|
|
return data
|
|
}
|
|
|
|
func serialTestCase(size int) testSlice {
|
|
data := make(testSlice, 0, size)
|
|
for i := 0; i < size; i++ {
|
|
data = append(data, i)
|
|
}
|
|
return data
|
|
}
|
|
|
|
func BenchmarkSelection(b *testing.B) {
|
|
runSelect := func(b *testing.B, testCase testSlice, benchFunc func(*testing.B, testSlice, int)) {
|
|
for i := 1; i <= b.N; i++ {
|
|
var k int
|
|
if b.N < len(testCase) {
|
|
k = len(testCase) / b.N * i
|
|
} else {
|
|
k = i%len(testCase) + 1
|
|
}
|
|
benchFunc(b, testCase, k)
|
|
}
|
|
}
|
|
b.ReportAllocs()
|
|
// Ten Million
|
|
b.Run("BenchmarkIntroSelection10000000", func(b *testing.B) {
|
|
runSelect(b, globalCase10000000, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection10000000", func(b *testing.B) {
|
|
runSelect(b, globalCase10000000, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort10000000", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase10000000)
|
|
}
|
|
})
|
|
// Million
|
|
b.Run("BenchmarkIntroSelection1000000", func(b *testing.B) {
|
|
runSelect(b, globalCase1000000, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection1000000", func(b *testing.B) {
|
|
runSelect(b, globalCase1000000, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort1000000", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase1000000)
|
|
}
|
|
})
|
|
// Hundred thousands
|
|
b.Run("BenchmarkIntroSelection100000", func(b *testing.B) {
|
|
runSelect(b, globalCase100000, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection100000", func(b *testing.B) {
|
|
runSelect(b, globalCase100000, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort100000", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase100000)
|
|
}
|
|
})
|
|
// Ten thousands
|
|
b.Run("BenchmarkIntroSelection10000", func(b *testing.B) {
|
|
runSelect(b, globalCase10000, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection10000", func(b *testing.B) {
|
|
runSelect(b, globalCase10000, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort10000", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase10000)
|
|
}
|
|
})
|
|
// Thousand
|
|
b.Run("BenchmarkIntroSelection1000", func(b *testing.B) {
|
|
runSelect(b, globalCase1000, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection1000", func(b *testing.B) {
|
|
runSelect(b, globalCase1000, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort1000", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase1000)
|
|
}
|
|
})
|
|
// Hundred
|
|
b.Run("BenchmarkIntroSelection100", func(b *testing.B) {
|
|
runSelect(b, globalCase100, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection100", func(b *testing.B) {
|
|
runSelect(b, globalCase100, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort100", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase100)
|
|
}
|
|
})
|
|
// Tens
|
|
b.Run("BenchmarkIntroSelection50", func(b *testing.B) {
|
|
runSelect(b, globalCase50, benchmarkIntroSelection)
|
|
})
|
|
b.Run("BenchmarkQuickSelection50", func(b *testing.B) {
|
|
runSelect(b, globalCase50, benchmarkQuickSelection)
|
|
})
|
|
b.Run("BenchmarkSort50", func(b *testing.B) {
|
|
for i := 1; i <= b.N; i++ {
|
|
benchmarkSort(b, globalCase50)
|
|
}
|
|
})
|
|
}
|
|
|
|
func benchmarkIntroSelection(b *testing.B, testCase testSlice, k int) {
|
|
b.StopTimer()
|
|
data := make(testSlice, len(testCase))
|
|
copy(data, testCase)
|
|
b.StartTimer()
|
|
Select(data, k)
|
|
}
|
|
|
|
func benchmarkQuickSelection(b *testing.B, testCase testSlice, k int) {
|
|
b.StopTimer()
|
|
data := make(testSlice, len(testCase))
|
|
copy(data, testCase)
|
|
b.StartTimer()
|
|
quickselect(data, 0, len(testCase)-1, k-1)
|
|
}
|
|
|
|
func benchmarkSort(b *testing.B, testCase testSlice) {
|
|
b.StopTimer()
|
|
data := make(testSlice, len(testCase))
|
|
copy(data, testCase)
|
|
b.StartTimer()
|
|
sort.Sort(data)
|
|
}
|
|
|