已排序无重复周期列表的搜索实现优化及可复用泛型方案问询

嘿，针对你提出的两个技术需求，我整理了具体的实现方案，一起来看看吧：

原实现采用线性遍历（O(n)时间复杂度），但由于你的periods是已排序且无重复的连续区间，完全可以用二分查找将时间复杂度降到O(logn)，尤其是当periods数量较多时，性能提升会非常明显。

优化思路分析 #

首先回顾原contains方法的匹配规则：

• 若输入值t <= 0，仅匹配min=0的第一个period；
• 其他情况，匹配满足t > min且（max=0或t <= max）的period；
• 由于区间连续且按min递增排序，每个输入值只会匹配唯一的一个period。

基于此，二分查找的核心逻辑是：

1. 先处理t <= 0的特殊场景，直接返回第一个period；
2. 对于正常输入，找到最大的min小于t的period（因为区间连续，这就是唯一可能匹配的候选）；
3. 验证该period是否包含输入值（最后一个period的max=0，必然匹配所有大于其min的值）。

优化后的代码实现 #

func (ks periods) indexBinary(v time.Duration) period {
    // 处理t<=0的特殊情况，匹配min=0的第一个period
    if v <= 0 {
        if len(ks) > 0 && ks[0].min == 0 {
            return ks[0]
        }
        return period{}
    }

    left, right := 0, len(ks)-1
    resultIdx := -1

    // 二分查找最大的min < v的period
    for left <= right {
        mid := left + (right-left)/2
        if ks[mid].min < v {
            resultIdx = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    // 验证找到的period是否包含v（最后一个period必然满足）
    if resultIdx != -1 && ks[resultIdx].contains(v) {
        return ks[resultIdx]
    }

    return period{}
}

Go 1.18+支持泛型，我们可以实现一个通用的区间查找组件，支持所有可排序的类型（如int、time.Duration等），同时保留原有的匹配逻辑。如果需要兼容旧版本Go，也可以通过代码生成来生成特定类型的特化实现。

泛型版本核心代码 #

import "golang.org/x/exp/constraints"

// GenericPeriod 泛型区间类型，Max为类型零值表示无上限
type GenericPeriod[T constraints.Ordered] struct {
    Min T
    Max T
}

// GenericPeriods 泛型区间列表
type GenericPeriods[T constraints.Ordered] []GenericPeriod[T]

// Contains 判断当前区间是否包含值v
func (gp GenericPeriod[T]) Contains(v T) bool {
    var zero T
    // 处理v<=零值且当前区间Min为零值的场景
    if v <= zero && gp.Min == zero {
        return true
    }
    // 常规匹配逻辑：v>Min 且 (Max是零值 或 v<=Max)
    return v > gp.Min && (gp.Max == zero || v <= gp.Max)
}

// Index 查找值v所属的区间
func (gps GenericPeriods[T]) Index(v T) GenericPeriod[T] {
    var zero T
    if v <= zero {
        if len(gps) > 0 && gps[0].Min == zero {
            return gps[0]
        }
        return GenericPeriod[T]{}
    }

    left, right := 0, len(gps)-1
    resultIdx := -1

    // 二分查找核心逻辑
    for left <= right {
        mid := left + (right-left)/2
        if gps[mid].Min < v {
            resultIdx = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if resultIdx != -1 && gps[resultIdx].Contains(v) {
        return gps[resultIdx]
    }

    return GenericPeriod[T]{}
}

泛型版本使用示例 #

适配time.Duration场景

func main() {
    genericPeriods := GenericPeriods[time.Duration]{
        {Min: 0, Max: time.Millisecond},
        {Min: time.Millisecond, Max: time.Millisecond * 2},
        {Min: time.Millisecond * 2, Max: time.Millisecond * 7},
        {Min: time.Millisecond * 7, Max: 0},
    }

    v := time.Millisecond * 3
    p := genericPeriods.Index(v)
    fmt.Printf("值%s所属区间：%v-%v\n", v, p.Min, p.Max)
    // 输出：值3ms所属区间：2ms-7ms
}

适配int类型场景

func main() {
    intPeriods := GenericPeriods[int]{
        {Min: 0, Max: 10},
        {Min: 10, Max: 20},
        {Min: 20, Max: 0},
    }

    fmt.Println(intPeriods.Index(15)) // 输出：{10 20}
    fmt.Println(intPeriods.Index(25)) // 输出：{20 0}
}

代码生成特化方案（兼容旧版Go） #

如果需要支持Go 1.17及以下版本，可以编写Go模板文件，通过go generate命令生成特定类型的实现。例如，创建模板文件period.tmpl：

// Code generated by go generate; DO NOT EDIT.

package main

type {{.Type}}Period struct {
    Min {{.Type}}
    Max {{.Type}}
}

type {{.Type}}Periods []{{.Type}}Period

func (k {{.Type}}Period) Contains(v {{.Type}}) bool {
    var zero {{.Type}}
    if v <= zero && k.Min == zero {
        return true
    }
    return v > k.Min && (k.Max == zero || v <= k.Max)
}

// 此处省略Index方法的模板代码，与泛型版本逻辑一致

然后在代码中添加//go:generate go run generate.go，编写generate.go读取模板并生成int_period.go、duration_period.go等文件。

我更新了基准测试代码，加入线性遍历、二分查找、泛型版本的对比：

func BenchmarkIndexLinear(b *testing.B) {
    periods := periods{
        {min: 0, max: 8000},
        {min: 8000, max: 16000},
        {min: 16000, max: 24000},
        {min: 24000, max: 32000},
        {min: 32000, max: 40000},
        {min: 40000, max: 48000},
        {min: 48000, max: 56000},
        {min: 56000, max: 64000},
        {min: 64000, max: 72000},
        {min: 72000, max: 80000},
        {min: 80000, max: 0},
    }
    inputs := []time.Duration{0, 72001, 80001}
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        for _, input := range inputs {
            _ = periods.index(input)
        }
    }
}

func BenchmarkIndexBinary(b *testing.B) {
    periods := periods{
        {min: 0, max: 8000},
        {min: 8000, max: 16000},
        {min: 16000, max: 24000},
        {min: 24000, max: 32000},
        {min: 32000, max: 40000},
        {min: 40000, max: 48000},
        {min: 48000, max: 56000},
        {min: 56000, max: 64000},
        {min: 64000, max: 72000},
        {min: 72000, max: 80000},
        {min: 80000, max: 0},
    }
    inputs := []time.Duration{0, 72001, 80001}
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        for _, input := range inputs {
            _ = periods.indexBinary(input)
        }
    }
}

func BenchmarkIndexGeneric(b *testing.B) {
    periods := GenericPeriods[time.Duration]{
        {Min: 0, Max: 8000},
        {Min: 8000, Max: 16000},
        {Min: 16000, Max: 24000},
        {Min: 24000, Max: 32000},
        {Min: 32000, Max: 40000},
        {Min: 40000, Max: 48000},
        {Min: 48000, Max: 56000},
        {Min: 56000, Max: 64000},
        {Min: 64000, Max: 72000},
        {Min: 72000, Max: 80000},
        {Min: 80000, Max: 0},
    }
    inputs := []time.Duration{0, 72001, 80001}
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        for _, input := range inputs {
            _ = periods.Index(input)
        }
    }
}

预期结果 #

• 二分版本的性能远高于线性版本，当periods数量越多，优势越明显；
• 泛型版本的性能与二分版本几乎一致，因为Go泛型会在编译时进行特化，无额外运行时开销。

内容的提问来源于stack exchange，提问作者user4466350