R语言如何实现基于近似多值匹配的数值向量过滤

我们需要实现类似 x %near_in% y 的效果：判断x中每个元素是否存在至少一个y中的元素，二者差值小于指定容差，且避免生成n×m的大矩阵带来的性能损耗。

方案1：基础R向量化实现（无额外依赖） #

核心思路是先对y排序，再用findInterval找到每个x元素在排序后y中的相邻位置，仅对比相邻的1-2个元素即可判断是否匹配，时间复杂度为O(m log m + n log m)（m为y长度，n为x长度），远高于原有O(nm)的方案。

# 自定义近似匹配中缀运算符
`%near_in%` <- function(x, y, tol = .Machine$double.eps^0.5) {
  y_sorted <- sort(y)
  n_y <- length(y_sorted)
  # 定位x元素在y中的相邻索引，处理边界溢出
  idx <- pmax(pmin(findInterval(x, y_sorted), n_y - 1), 1)
  # 仅对比相邻的两个候选元素
  abs(x - y_sorted[idx]) < tol | abs(x - y_sorted[idx + 1]) < tol
}

测试示例：

x <- c(1.123456789, 2.123456789, 3.123456789)
y <- c(1.12345, 2.12345)
# 指定容差为0.0001
x %near_in% y
# 输出：[1] TRUE TRUE FALSE

方案2：data.table滚动连接（超大数据量最优） #

如果处理百万级以上的向量，推荐使用data.table的滚动连接，底层C实现效率极高：

library(data.table)
near_in_dt <- function(x, y, tol = 0.0001) {
  x_dt <- data.table(val = x)
  y_dt <- data.table(val = y, flag = TRUE)
  setkey(y_dt, val)
  # 滚动连接，允许向前后滚动匹配，最大滚动距离为容差值
  res <- y_dt[x_dt, on = "val", roll = tol, rollends = c(TRUE, TRUE)]
  !is.na(res$flag)
}

测试调用：

near_in_dt(x, y, tol = 0.0001)
# 输出：[1] TRUE TRUE FALSE

性能对比 #

当y长度为10万、x长度为10万时，原有生成矩阵的方案会占用近80G内存直接无法运行，上述两种方案均可在20ms内完成计算。

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