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

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},}与类型一起定义，并定义为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您能建议解决方案来改进函数中的搜索实现吗？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()period

func (k period) lessOrContains(t time.Duration) bool {

    return k.max == 0 || t <= k.max

}

现在是一个使用二进制搜索的函数：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{}

}

现在开始对标。让我们创建一个帮助器函数，用于创建小周期或大周期切片：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 个元素的小列表（25 ns 对 58 ns）更快。index()indexBinary()

但是，当列表变大（超过一千个周期，上面的基准中有1010个周期）时，表现超过一个数量级（125 ns vs 2000 ns），如果列表变大，这种差异会变得更大。indexBinary()index()