在排序周期列表中优化迭代

Question

给定一个周期列表，已经排序，并且不包含任何 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},

}

与类型一起定义，并定义为periodsperiod

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)

        }

    }

}

Answer 1

与简单、按顺序搜索像您这样的列表（11 个元素）相比，您不太可能获得更好的性能。如果你的切片会大得多（例如，数百甚至数千个周期），因为你的排序是你声称的，那么你可以使用二进制搜索。periods二进制搜索在排序中实现。搜索（）。您基本上只需要为 提供一个实现。这是它的样子：lessOrContains()periodfunc (k period) lessOrContains(t time.Duration) bool {&nbsp; &nbsp; return k.max == 0 || t <= k.max}现在是一个使用二进制搜索的函数：index()func (ks periods) indexBinary(v time.Duration) period {&nbsp; &nbsp; idx := sort.Search(len(ks), func(i int) bool {&nbsp; &nbsp; &nbsp; &nbsp; return ks[i].lessOrContains(v)&nbsp; &nbsp; })&nbsp; &nbsp; if idx < len(ks) && ks[idx].contains(v) {&nbsp; &nbsp; &nbsp; &nbsp; return ks[idx]&nbsp; &nbsp; }&nbsp; &nbsp; return period{}}现在开始对标。让我们创建一个帮助器函数，用于创建小周期或大周期切片：createPeriods()func createPeriods(big bool) periods {&nbsp; &nbsp; ps := periods{&nbsp; &nbsp; &nbsp; &nbsp; period{min: 0, max: 8000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 8000, max: 16000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 16000, max: 24000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 24000, max: 32000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 32000, max: 40000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 40000, max: 48000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 48000, max: 56000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 56000, max: 64000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 64000, max: 72000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 72000, max: 80000},&nbsp; &nbsp; &nbsp; &nbsp; period{min: 80000, max: 0},&nbsp; &nbsp; }&nbsp; &nbsp; if big {&nbsp; &nbsp; &nbsp; &nbsp; psbig := periods{}&nbsp; &nbsp; &nbsp; &nbsp; for i := 0; i < 1000; i++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; psbig = append(psbig, period{time.Duration(i), time.Duration(i + 1)})&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; psbig = append(psbig, ps[1:]...)&nbsp; &nbsp; &nbsp; &nbsp; ps = psbig&nbsp; &nbsp; }&nbsp; &nbsp; return ps}现在，让我们为所有情况编写基准测试函数：func BenchmarkIndexSmall(b *testing.B) {&nbsp; &nbsp; benchmarkIndexImpl(b, false)}func BenchmarkIndexBinarySmall(b *testing.B) {&nbsp; &nbsp; benchmarkIndexBinaryImpl(b, false)}func BenchmarkIndexBig(b *testing.B) {&nbsp; &nbsp; benchmarkIndexImpl(b, true)}func BenchmarkIndexBinaryBig(b *testing.B) {&nbsp; &nbsp; benchmarkIndexBinaryImpl(b, true)}func benchmarkIndexImpl(b *testing.B, big bool) {&nbsp; &nbsp; periods := createPeriods(big)&nbsp; &nbsp; inputs := []time.Duration{&nbsp; &nbsp; &nbsp; &nbsp; time.Duration(0),&nbsp; &nbsp; &nbsp; &nbsp; time.Duration(72000 + 1),&nbsp; &nbsp; &nbsp; &nbsp; time.Duration(80000 + 1),&nbsp; &nbsp; }&nbsp; &nbsp; b.ResetTimer()&nbsp; &nbsp; b.ReportAllocs()&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; for _, input := range inputs {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; _ = periods.index(input)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}func benchmarkIndexBinaryImpl(b *testing.B, big bool) {&nbsp; &nbsp; periods := createPeriods(big)&nbsp; &nbsp; inputs := []time.Duration{&nbsp; &nbsp; &nbsp; &nbsp; time.Duration(0),&nbsp; &nbsp; &nbsp; &nbsp; time.Duration(72000 + 1),&nbsp; &nbsp; &nbsp; &nbsp; time.Duration(80000 + 1),&nbsp; &nbsp; }&nbsp; &nbsp; b.ResetTimer()&nbsp; &nbsp; b.ReportAllocs()&nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; for _, input := range inputs {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; _ = periods.indexBinary(input)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}现在让我们看看基准测试结果：BenchmarkIndexSmall-8&nbsp; &nbsp; &nbsp; &nbsp; 44408948&nbsp; &nbsp; &nbsp; 25.50 ns/op&nbsp; &nbsp; 0 B/op&nbsp; &nbsp; &nbsp;0 allocs/opBenchmarkIndexBinarySmall-8&nbsp; 18441049&nbsp; &nbsp; &nbsp; 58.35 ns/op&nbsp; &nbsp; 0 B/op&nbsp; &nbsp; &nbsp;0 allocs/opBenchmarkIndexBig-8&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 562202&nbsp; &nbsp; 1908 ns/op&nbsp; &nbsp; &nbsp; &nbsp;0 B/op&nbsp; &nbsp; &nbsp;0 allocs/opBenchmarkIndexBinaryBig-8&nbsp; &nbsp; &nbsp;9234846&nbsp; &nbsp; &nbsp;125.1 ns/op&nbsp; &nbsp; &nbsp;0 B/op&nbsp; &nbsp; &nbsp;0 allocs/op如您所见，比具有 11 个元素的小列表（25 ns 对 58 ns）更快。index()indexBinary()但是，当列表变大（超过一千个周期，上面的基准中有1010个周期）时，表现超过一个数量级（125 ns vs 2000 ns），如果列表变大，这种差异会变得更大。indexBinary()index()