如何在不改动现有代码前提下加速R语言find_rules函数并保证计算一致

现有以下R代码定义的数据、规则列表及匹配函数：

数据定义 #

set.seed(1)
n <- 100
df <- data.frame(
  x = sample(1:30, n, replace = T),
  y = sample(1:30, n, replace = T),
  z = sample(1:30, n, replace = T)
)

规则列表 #

rules <- list(function(i) df$x[i]==26,
              function(i) df$y[i]==17,
              function(i) df$z[i]==14)

原匹配函数 #

原函数find_rules按顺序匹配规则：先找第一个满足x[i]==26的行，接着在该行之后找第一个满足y[i]==17的行，再在该行之后找第一个满足z[i]==14的行，找到所有规则后提前终止循环。

# search sequence
# first x[i]==26 then y[i]==17 then z[i]==14
find_rules <- function(df, rules){
ln <- length(rules)
n <- 1
res <- matrix(0,nrow = ln, ncol = 2, dimnames = list(NULL, c("row","res")))
for(i in 1:nrow(df)){
  if(rules[[n]](i)){
    res[n,"row"] <- i
    res[n,"res"] <- 1
    n <- n+1
  }
  if(n==ln+1) break
}
return(res)
}

要求：不改动上述所有代码的前提下，实现一个加速版本的匹配函数，且在任意set.seed()设置下，结果与原find_rules完全一致。

原函数的核心瓶颈是逐行循环检查，数据量较大时效率极低。我们通过预计算每个规则的所有匹配行索引，再按顺序筛选符合「后一个匹配行号大于前一个找到的行号」的第一个结果来优化，避免逐行遍历：

find_rules_fast <- function(df, rules) {
  ln <- length(rules)
  res <- matrix(0, nrow = ln, ncol = 2, dimnames = list(NULL, c("row", "res")))
  
  # 预计算每个规则的所有匹配行索引（按行号升序）
  rule_matches <- lapply(rules, function(rule) {
    which(sapply(1:nrow(df), rule))
  })
  
  last_row <- 0
  for (n in 1:ln) {
    # 在当前规则的匹配行中，找到第一个大于last_row的行号
    match_idx <- which(rule_matches[[n]] > last_row)
    if (length(match_idx) > 0) {
      res[n, "row"] <- rule_matches[[n]][match_idx[1]]
      res[n, "res"] <- 1
      last_row <- res[n, "row"]
    } else {
      # 没有找到匹配，后续规则无需检查
      break
    }
  }
  
  return(res)
}

一致性验证 #

用以下代码可验证加速版本与原函数结果完全一致：

# 测试不同随机种子
for (seed in 1:100) {
  set.seed(seed)
  n <- 1000
  df <- data.frame(
    x = sample(1:30, n, replace = T),
    y = sample(1:30, n, replace = T),
    z = sample(1:30, n, replace = T)
  )
  rules <- list(function(i) df$x[i]==sample(1:30,1),
                function(i) df$y[i]==sample(1:30,1),
                function(i) df$z[i]==sample(1:30,1))
  
  res_original <- find_rules(df, rules)
  res_fast <- find_rules_fast(df, rules)
  
  if (!all.equal(res_original, res_fast)) {
    stop(paste("Seed", seed, "results mismatch!"))
  }
}
cat("All tests passed: fast version matches original results.\n")

效率说明 #

• 原函数最坏情况需遍历所有行，时间复杂度为O(N*K)（N为数据行数，K为规则数）
• 加速版本通过预计算匹配行+有序索引快速查找，时间复杂度降为O(N + K*M)（M为每个规则的平均匹配数），数据量较大时（如N>10000）效率提升显著。

内容的提问来源于stack exchange，提问作者mr.T