給定一個周期列表，已經(jīng)排序，并且不包含任何 dups。periods := periods{ period{min: 0, max: time.Millisecond}, period{min: time.Millisecond, max: time.Millisecond * 1}, period{min: time.Millisecond * 1, max: time.Millisecond * 2}, period{min: time.Millisecond * 2, max: time.Millisecond * 7}, period{min: time.Millisecond * 7, max: 0},}與類型一起定義，并定義為periodsperiodtype periods []periodfunc (ks periods) index(v time.Duration) period { for i := 0; i < len(ks); i++ { if ks[i].contains(v) { return ks[i] } } return period{}}type period struct { min time.Duration max time.Duration}func (k period) String() string { if k.max == 0 && k.max < k.min { return fmt.Sprintf("%v-", k.min) } return fmt.Sprintf("%v-%v", k.min, k.max)}func (k period) contains(t time.Duration) bool { if t <= 0 && k.min == 0 { return true } return t > k.min && (k.max == 0 || t <= k.max)}完整代碼可在 https://play.golang.org/p/cDmQ7Ho6hUI您能建議解決方案來改進(jìn)函數(shù)中的搜索實(shí)現(xiàn)嗎？periods.index另外，您能否提供一個因式解決方案，例如可以重用該實(shí)現(xiàn)？包含泛型的解決方案是可以的，因?yàn)槲胰匀豢梢詫ｉT使用代碼生成。包括基準(zhǔn)測試func BenchmarkIndex(b *testing.B) { periods := periods{ period{min: 0, max: 8000}, period{min: 8000, max: 16000}, period{min: 16000, max: 24000}, period{min: 24000, max: 32000}, period{min: 32000, max: 40000}, period{min: 40000, max: 48000}, period{min: 48000, max: 56000}, period{min: 56000, max: 64000}, period{min: 64000, max: 72000}, period{min: 72000, max: 80000}, period{min: 80000, max: 0}, } inputs := []time.Duration{ time.Duration(0), time.Duration(72000 + 1), time.Duration(80000 + 1), } b.ResetTimer() b.ReportAllocs() for i := 0; i < b.N; i++ { for _, input := range inputs { _ = periods.index(input) } }}
1 回答
慕碼人8056858
TA貢獻(xiàn)1803條經(jīng)驗(yàn) 獲得超6個贊
與簡單、按順序搜索像您這樣的列表（11 個元素）相比，您不太可能獲得更好的性能。
如果你的切片會大得多（例如，數(shù)百甚至數(shù)千個周期），因?yàn)槟愕呐判蚴悄懵暦Q的，那么你可以使用二進(jìn)制搜索。periods
二進(jìn)制搜索在排序中實(shí)現(xiàn)。搜索（）。您基本上只需要為 提供一個實(shí)現(xiàn)。這是它的樣子：lessOrContains()period
func (k period) lessOrContains(t time.Duration) bool {
return k.max == 0 || t <= k.max
}
現(xiàn)在是一個使用二進(jìn)制搜索的函數(shù)：index()
func (ks periods) indexBinary(v time.Duration) period {
idx := sort.Search(len(ks), func(i int) bool {
return ks[i].lessOrContains(v)
})
if idx < len(ks) && ks[idx].contains(v) {
return ks[idx]
}
return period{}
}
現(xiàn)在開始對標(biāo)。讓我們創(chuàng)建一個幫助器函數(shù)，用于創(chuàng)建小周期或大周期切片：createPeriods()
func createPeriods(big bool) periods {
ps := periods{
period{min: 0, max: 8000},
period{min: 8000, max: 16000},
period{min: 16000, max: 24000},
period{min: 24000, max: 32000},
period{min: 32000, max: 40000},
period{min: 40000, max: 48000},
period{min: 48000, max: 56000},
period{min: 56000, max: 64000},
period{min: 64000, max: 72000},
period{min: 72000, max: 80000},
period{min: 80000, max: 0},
}
if big {
psbig := periods{}
for i := 0; i < 1000; i++ {
psbig = append(psbig, period{time.Duration(i), time.Duration(i + 1)})
}
psbig = append(psbig, ps[1:]...)
ps = psbig
}
return ps
}
現(xiàn)在，讓我們?yōu)樗星闆r編寫基準(zhǔn)測試函數(shù)：
func BenchmarkIndexSmall(b *testing.B) {
benchmarkIndexImpl(b, false)
}
func BenchmarkIndexBinarySmall(b *testing.B) {
benchmarkIndexBinaryImpl(b, false)
}
func BenchmarkIndexBig(b *testing.B) {
benchmarkIndexImpl(b, true)
}
func BenchmarkIndexBinaryBig(b *testing.B) {
benchmarkIndexBinaryImpl(b, true)
}
func benchmarkIndexImpl(b *testing.B, big bool) {
periods := createPeriods(big)
inputs := []time.Duration{
time.Duration(0),
time.Duration(72000 + 1),
time.Duration(80000 + 1),
}
b.ResetTimer()
b.ReportAllocs()
for i := 0; i < b.N; i++ {
for _, input := range inputs {
_ = periods.index(input)
}
}
}
func benchmarkIndexBinaryImpl(b *testing.B, big bool) {
periods := createPeriods(big)
inputs := []time.Duration{
time.Duration(0),
time.Duration(72000 + 1),
time.Duration(80000 + 1),
}
b.ResetTimer()
b.ReportAllocs()
for i := 0; i < b.N; i++ {
for _, input := range inputs {
_ = periods.indexBinary(input)
}
}
}
現(xiàn)在讓我們看看基準(zhǔn)測試結(jié)果：
BenchmarkIndexSmall-8 44408948 25.50 ns/op 0 B/op 0 allocs/op
BenchmarkIndexBinarySmall-8 18441049 58.35 ns/op 0 B/op 0 allocs/op
BenchmarkIndexBig-8 562202 1908 ns/op 0 B/op 0 allocs/op
BenchmarkIndexBinaryBig-8 9234846 125.1 ns/op 0 B/op 0 allocs/op
如您所見，比具有 11 個元素的小列表（25 ns 對 58 ns）更快。index()indexBinary()
但是，當(dāng)列表變大（超過一千個周期，上面的基準(zhǔn)中有1010個周期）時，表現(xiàn)超過一個數(shù)量級（125 ns vs 2000 ns），如果列表變大，這種差異會變得更大。indexBinary()index()
- 1 回答
- 0 關(guān)注
- 98 瀏覽
添加回答
舉報(bào)
0/150
提交
取消