如何高效计算一组数值区间的重叠区间对数量？

我有如下数值区间：

想找高效方法统计相互重叠的区间对数量，目前用的朴素循环方法在百万级数据下速度极慢，希望用foverlaps实现向量化处理。

朴素方法代码：

library(data.table)
setDT(a)
setkey(a, lower, upper)

for (i in 1:nrow(a)) {
    for (j in 1:nrow(a)) {
        foverlaps(a[i,], a[j,])
    }
}

数据结构定义：

data=structure(list(lower = c(-10.4443200112593, -10.5356593568179,
-3.96357398513697, -2.70438891891616, 0.892199380698278, 0.849599807772024,
0.963931532617852, 1.2656723800301, 2.89323680524585, 4.64760986325676
), upper = c(-8.69575093847071, -7.37202901360451, -2.66171192367237,
-1.05123670198647, 2.5253413373515, 2.98256679223578, 3.14970844448057,
3.3626226637927, 5.33242229071662, 5.48988156249026)), row.names = c(NA,
-10L), class = "data.frame")

高效解决方案 #

核心思路 #

朴素嵌套循环的时间复杂度是O(n²)，百万级数据完全不可行。foverlaps是data.table的向量化操作，可一次性找出所有重叠区间，无需逐一遍历。

具体代码实现 #

library(data.table)

# 转换为data.table格式
dt <- as.data.table(data)
# 设置键，用于foverlaps匹配
setkey(dt, lower, upper)

# 执行自连接的foverlaps，仅返回匹配的行索引
overlaps <- foverlaps(dt, dt, type = "any", which = TRUE)

# 过滤重复计数：排除自身配对，且只保留i<j的配对避免(A,B)和(B,A)重复统计
unique_overlaps <- overlaps[i < j]

# 统计最终重叠对数量
overlap_count <- nrow(unique_overlaps)
print(overlap_count)

代码细节说明 #

• type = "any"：匹配所有类型的重叠（包含、交叉等所有有交集的情况）
• which = TRUE：仅返回匹配的行索引，不复制完整数据，大幅节省内存
• i < j：避免重复计数，若需要包含自身与自身的配对，可调整为i != j或移除该条件

百万级数据额外优化 #

• 提前按lower排序，缩小匹配范围
• 利用data.table的内存高效特性，避免不必要的列复制
• 若仅需数量，无需保留所有匹配结果，可直接在foverlaps后做统计

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