如何高效将大量数值映射至非重叠区间？

针对百万级数值向量到非重叠区间的映射问题，以下是几种远优于矩阵方法的高效实现：

1. 基础R函数findInterval（首选） #

这是R原生的最优方案，专为数值到区间的映射设计，时间复杂度为O(n log m)（n为数值数量，m为区间数量），内存占用极低——仅需存储结果索引向量，完全避免大矩阵的生成。

步骤与代码： #

首先确保区间按start升序排列（非重叠区间通常已满足，保险起见可手动排序）：

# 假设你的区间数据框为intervals，包含start、end列
intervals <- intervals[order(intervals$start), ]

根据区间的闭合规则调用findInterval：

• 若区间为左闭右开（[start, end)）：

interval_indices <- findInterval(values, intervals$end)

• 若区间为双闭合（[start, end]），需微调避免边界值漏匹配：

interval_indices <- findInterval(values - .Machine$double.eps, intervals$end)

返回的interval_indices即为每个数值对应的区间索引（从1开始），直接对应intervals的行号。

2. GenomicRanges包的专业区间匹配 #

如果需要后续进行更多区间操作（如生物信息学场景），可使用GenomicRanges的findOverlaps，其内部采用高效的区间树算法，内存占用远低于矩阵方法：

library(GenomicRanges)

# 将数值转为单碱基GRanges对象
values_gr <- GRanges(seqnames = "1", ranges = IRanges(start = values, end = values))
# 将区间转为GRanges对象
intervals_gr <- GRanges(seqnames = "1", ranges = IRanges(start = intervals$start, end = intervals$end))

# 查找重叠关系
overlaps <- findOverlaps(values_gr, intervals_gr)

# 提取匹配结果：queryHits为数值索引，subjectHits为对应区间索引
match_result <- data.frame(value_idx = queryHits(overlaps), interval_idx = subjectHits(overlaps))

3. 为什么矩阵方法不可取？ #

你的矩阵方法会生成n×m规模的矩阵（百万级数值×上千区间即达10亿级元素），直接触发内存溢出。而由于区间非重叠，每个数值最多匹配一个区间，仅需存储单个索引向量即可，完全没必要生成全量匹配矩阵。

额外：data.table批量匹配（适用于数据框场景） #

若需将映射结果与原数据结合，可使用data.table的foverlaps进行快速区间匹配：

library(data.table)
setDT(intervals)
setDT(values_df) # 假设数值存储在values_df的value列中

# 排序区间并为数值创建临时区间（单个值的区间）
setorder(intervals, start)
values_df[, `:=`(id = .I, start = value, end = value)]

# 执行区间匹配
match_result <- foverlaps(values_df, intervals, by.x = c("start", "end"), by.y = c("start", "end"), type = "within")

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