本文介绍一种专为小规模（通常1–3个）非重叠、非相邻区间设计的高性能 Difference 算法，可在不排序、低内存分配前提下，快速计算新区间与现有区间集合的相对补集（即“新区间中未被覆盖的部分”）。
本文介绍一种专为小规模（通常1–3个）非重叠、非相邻区间设计的高性能 `difference` 算法，可在不排序、低内存分配前提下，快速计算新区间与现有区间集合的相对补集（即“新区间中未被覆盖的部分”）。
在处理动态区间合并与排除场景（如内存分配追踪、日志范围过滤、时间窗口剔除等）时，常需频繁执行「给定新区间，求其与当前已知不重叠区间集合的差集」操作。问题关键在于：集合规模极小（95% 为 1 或 2 个区间），但调用频次高；排序开销成为瓶颈，需避免 sort.Sort 的 O(n log n) 成本。
针对该约束，peterSO 提出的 Difference 实现是目前最优解：它采用原地选择性最小化排序 + 单次线性扫描策略，在保持代码简洁的同时，将平均耗时降低近 40%，内存分配减少 25%。
核心思路
不预先对整个区间集合排序，而是在遍历过程中，每次仅将当前待处理的最小起始点区间“冒泡”至切片头部（通过一次内层循环完成局部最小值提取）。随后，用该区间与目标区间 b 逐段裁剪：
- 若
b完全位于当前区间左侧 → 整个b加入结果； - 若
b起始点在当前区间左侧 → 截取[b.Start, a[0].Start−1]，并推进b.Start； - 若
b结束点在当前区间内或右侧 → 推进b.Start至a[0].End + 1； - 处理完所有区间后，剩余
b（若有效）直接追加。
该逻辑天然适配小规模数据：最坏情况（3 个区间）仅需最多 3 次局部查找 + 3 次比较，无递归、无额外切片扩容（预估容量为 3），零指针间接访问。
示例代码（Go 实现）
func (a Intervals) Difference(b Interval) Intervals {
if len(a) == 0 {
return Intervals{b}
}
var d Intervals // 预分配容量可设为 3，因最多产生 len(a)+1 段
for len(a) > 0 {
// ⚡ 局部最小化：将起始点最小的区间移到 a[0]
for i := 1; i < len(a); i++ {
if a[i].Start < a[0].Start {
a[i], a[0] = a[0], a[i]
}
}
// ? 裁剪逻辑
if b.Start < a[0].Start {
if b.End < a[0].Start {
d = append(d, b)
break // b 已完全位于首个区间左侧，无需后续处理
}
d = append(d, Interval{b.Start, a[0].Start - 1})
b.Start = a[0].Start
}
if b.End <= a[0].End {
break // b 已被当前区间完全覆盖或截断完毕
}
if b.Start <= a[0].End {
b.Start = a[0].End + 1 // 跳过已覆盖部分
}
if len(a) == 1 {
// 最后一个区间：检查剩余 b 是否有效
if b.Start <= b.End {
d = append(d, b)
}
break
}
a = a[1:] // 移除已处理区间
}
return d
}注意事项与最佳实践
-
输入假设必须满足：
a中的区间必须是非重叠（non-overlapping）且非相邻（non-adjacent），否则裁剪边界可能出错（相邻区间如{10,15}和{16,20}应被合并为{10,20}后再参与差集计算）； -
性能敏感点：该算法优势在
len(a) ≤ 3时最大化；若集合规模增长（如 > 10），应切换为先排序 + 双指针扫描方案； -
内存友好性：返回切片
d使用var d Intervals声明，避免make(Intervals, 0, 3)的显式初始化（Go 编译器对零值切片追加有优化）； -
边界安全：所有区间端点比较均使用
≤/显式判断，杜绝整数溢出或空区间误判（如 <code>Start > End时自动跳过）。
综上，此方案以极简逻辑、零依赖、亚百纳秒级延迟，完美匹配高频、小规模区间差集场景，是生产环境区间运算库的推荐实现范式。
