英文:
optimize iteration over a list of sorted periods
问题
给定一个已排序且不包含重复元素的周期列表。
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},
}
其中periods
和period
类型定义如下:
type periods []period
func (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
你能提供改进periods.index
函数中搜索实现的解决方案吗?
此外,你能提供一个因式分解的解决方案,以便可以重用该实现吗?
包含泛型的解决方案也可以,因为我可以使用代码生成进行特殊化。
代码中还包含了一个基准测试:
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)
}
}
}
英文:
given a list of periods, already sorted, and containing no 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},
}
with the types periods
and period
defined as
type periods []period
func (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)
}
The full code is available at https://play.golang.org/p/cDmQ7Ho6hUI
Can you suggest solution(s) to improve the search implementation in the periods.index
function ?
Also, can you provide a factorized solution such as it is possible to re use the implementation ?
A generics included solution is OK for that i can still specialize using code gen.
A benchmark is included
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
得分: 3
你很难在像你这样小的列表(11个元素)上实现比简单的顺序搜索更好的性能。
如果你的切片要大得多(例如数百甚至数千个周期),并且你所说的periods
是排序的,那么你可以使用二分搜索。
二分搜索在sort.Search()
中实现。你只需要为period
提供一个lessOrContains()
的实现。代码如下:
func (k period) lessOrContains(t time.Duration) bool {
return k.max == 0 || t <= k.max
}
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{}
}
接下来是基准测试。让我们创建一个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
}
现在让我们为所有情况编写基准测试函数:
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)
}
}
}
现在让我们看看基准测试的结果:
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个元素的小列表,index()
比indexBinary()
更快(25 ns vs 58 ns)。
但是当列表变大时(超过一千个周期,在上面的基准测试中为1010个),indexBinary()
比index()
快一个数量级以上(125 ns vs 2000 ns),而且如果列表变得更大,这种差异将变得更大。
英文:
It's unlikely you can achieve better performance than a simple, sequential search for a list as small as yours (11 elements).
If your slice would be much bigger (e.g. hundreds or even thousands of periods), since your periods
is sorted as you claim, then you could use binary search.
Binary search is implemented in sort.Search()
. You just basically have to provide a lessOrContains()
implementation for period
. This is how it could look like:
func (k period) lessOrContains(t time.Duration) bool {
return k.max == 0 || t <= k.max
}
Now an index()
function using binary search:
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{}
}
Now on to benchmarking. Let's create a createPeriods()
helper function that creates either a small or big periods slice:
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
}
Now let's write benchmark functions for all cases:
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)
}
}
}
And now let's see the benchmark results:
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
As you can see, index()
is faster than indexBinary()
for small lists with 11 elements (25 ns vs 58 ns).
But when the list gets big (more than a thousand periods, 1010 in the above benchmark), then indexBinary()
outperforms index()
by more than an order of magnitude (125 ns vs 2000 ns), and this difference will get even bigger if the lists gets bigger.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论