当前位置：首页 > 文章列表 > Golang > Go问答 > 判断范围列表是否包含特定范围的方法

判断范围列表是否包含特定范围的方法

来源：stackoverflow 2024-03-24 12:42:37 0浏览收藏

在判断范围列表是否包含特定范围时，采用传统方法可能效率低下。为了优化性能，推荐使用以下算法： 1. 创建一个 Condense 方法，将输入的范围列表排序并合并重叠范围，返回一个新的、经过优化的范围列表。 2. 使用二分搜索在 Condense 后的范围内查找给定范围的开始值。 3. 如果找到的范围的结束值大于或等于给定范围的结束值，则返回 true，否则返回 false。

问题内容

我想有效地确定范围列表是否涵盖给定范围。例如，范围列表 [(0-3), (3-5), (4-8), (6-10)] 涵盖范围 (0-10)，而 [(5-10), (0- 3)] 没有。该列表可以包含重叠部分，并且不一定是有序的。

我尝试实现如下所示的 continously 函数，该函数检查字节范围切片是否包含传递范围的给定 start 和 end 。

type byteRange struct {
    start int64
    end   int64
}

type byteRanges []*byteRange

func (brs byteRanges) Len() int {
    return len(brs)
}

func (brs byteRanges) Swap(i, j int) {
    brs[i], brs[j] = brs[j], brs[i]
}

func (brs byteRanges) Less(i, j int) bool {
    return brs[i].start < brs[j].start
}

func (brs byteRanges) Continuous(start int64, end int64) bool {
    curPos := start
    sort.Sort(brs)

    for _, br := range brs {
        if br.start > curPos+1 {
            return false
        }

        if curPos < br.end {
            curPos = br.end
        }

        if curPos >= end {
            return true
        }
    }

    return false
}

该函数行为正确，但在处理大量范围列表和经常调用时性能不是很好。有人可以推荐一种可以加速这个逻辑的算法/实现吗？

解决方案

由于您将在同一组范围上重复调用 Continously，因此最好创建一个 Condense 方法（或任何您希望调用的方法），该方法将获取一个切片并返回一个新切片，其中包含已排序的范围和任意值。重叠范围合并。对于任何给定的范围集，您只需调用 Condense 一次。然后，Continously 可以要求仅在 Condense 的结果上调用它。（为了强制执行此要求，最好让 Condense 实际上返回自定义类型的 struct，该类型只是切片的包装器，并仅在该 Continously 类型上定义 Continously。如果您愿意（为了方便起见），您可以然后可以定义一个单独的 Continously 方法，可以直接在切片上调用该方法，该方法调用 Condense ，然后调用 Continously 。当然，这种便捷方法会再次变慢，但对于仅包含集合的集合来说可能很方便检查一次。）

Condense 中的合并逻辑非常简单：

如果切片为空，则返回它（提前退出）。
按 start 对范围进行排序。
创建一个名为 result 的新切片。
将 prevRange 初始化为第一个范围。
迭代范围。为每一个：
- 如果当前范围在 prevRange.end + 1 之后开始，请将 prevRange 添加到 result，然后将 prevRange 设置为当前范围。
- 否则，如果当前范围在 prevRange.end 之后结束，请将 prevRange.end 设置为当前范围的 end。
将 prevRange 添加到 result。