如何高效查找R中超长向量a元素在向量b中的匹配索引？

我有两个超长整数向量：

a <- sample(1e+08L, size = 1e+09L, replace = TRUE)
b <- sample(1e+08L, size = 1e+09L, replace = TRUE)

需要生成一个与a长度相同的整数向量r，使得r[i]为a[i]在b中首次出现的索引。尝试过pmatch(a, b)但速度极慢，求更高效的实现方法。

示例说明 #

小样本下的期望输出：

a <- c(1, 3, 5, 7, 8)
b <- c(3, 1, 7, 8, 5)
f(a, b)
## [1] 2 1 5 3 4

高效解决方案 #

1. 使用data.table的fmatch（推荐）

data.table包的fmatch基于哈希表实现完全匹配，性能远优于base包的pmatch和match，尤其适合处理超大规模数据：

install.packages("data.table")
library(data.table)

r <- fmatch(a, b)

2. 原生R构建哈希映射

通过命名向量预先构建值到首次索引的映射，避免重复遍历查找：

# 提取b的唯一值，并获取每个值的首次出现索引
b_unique <- unique(b)
b_index_map <- setNames(match(b_unique, b), b_unique)

# 通过映射快速获取a中元素的索引
r <- as.integer(b_index_map[as.character(a)])

此方法会自动保留每个值在b中首次出现的索引，完全符合需求。

3. Rcpp自定义哈希查找（极致性能）

如果需要极致的速度，可以用Rcpp实现底层哈希查找，时间复杂度为O(n+m)，适合处理百亿级别的数据：

#include <Rcpp.h>
#include <unordered_map>
using namespace Rcpp;

// [[Rcpp::export]]
IntegerVector get_first_index(IntegerVector a, IntegerVector b) {
  std::unordered_map<int, int> value_index;
  
  // 遍历b，存储每个值的首次出现索引（R索引从1开始）
  for (int i = 0; i < b.size(); ++i) {
    if (value_index.find(b[i]) == value_index.end()) {
      value_index[b[i]] = i + 1;
    }
  }
  
  // 遍历a，查找对应索引
  IntegerVector result(a.size());
  for (int i = 0; i < a.size(); ++i) {
    auto iter = value_index.find(a[i]);
    result[i] = (iter != value_index.end()) ? iter->second : NA_INTEGER;
  }
  
  return result;
}

将代码保存为find_index.cpp后，编译并调用：

install.packages("Rcpp")
library(Rcpp)

sourceCpp("find_index.cpp")
r <- get_first_index(a, b)

为什么pmatch速度慢 #

pmatch支持部分匹配（如字符串前缀匹配），内部逻辑比单纯的完全匹配复杂很多，而我们只需要完全匹配的首次索引，因此使用pmatch属于用错工具，改用哈希类的完全匹配方法能大幅提升速度。

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