时间序列递归函数适配小DataFrame，大DF报错：C栈内存接近上限

问题根源 #

你的递归函数find.next.smaller会在分组数据量较大时触发C栈溢出，原因是：

• 递归深度等于分组内的行数，当分组行数达到数万级时，远超R默认的栈空间限制（默认栈大小仅能支撑几千层递归）
• 系统总内存充足也无法解决，因为这是R进程的栈深度限制，不是堆内存不足的问题

原递归函数的另一个问题是时间复杂度为O(n²)，数据量大时运行效率极低。

优化方案：非递归单调栈实现 #

改用单调栈算法实现"查找下一个小于等于当前值的位置"，时间复杂度O(n)，无递归栈溢出风险，同时大幅提升运行效率。

非递归函数实现 #

find_next_smaller_non_recursive <- function(vec) {
  n <- length(vec)
  result <- rep(NA_integer_, n)
  # 用单调栈存储候选索引，从后往前遍历
  stack <- integer(0)
  
  for (i in n:1) {
    # 弹出栈中所有大于当前值的元素，这些元素无法成为后续位置的候选
    while (length(stack) > 0 && vec[stack[length(stack)]] > vec[i]) {
      stack <- stack[-length(stack)]
    }
    # 栈顶元素即为当前位置之后第一个小于等于它的索引
    if (length(stack) > 0) {
      result[i] <- stack[length(stack)]
    }
    # 当前索引入栈，作为前面位置的候选
    stack <- c(stack, i)
  }
  result
}

整合到原有工作流 #

替换原递归函数，直接在分组操作中调用新函数：

library(dplyr)

# 原数据格式化逻辑保持不变
df <- data.frame(
  "Date_time" = seq(from=as.POSIXct("2022-01-01 00:00"), by=15*60, to=as.POSIXct("2022-01-01 07:00")), 
  "Site" = rep(c("Site A", "Site B"), each = 29),
  "Value" = c(10,10.1,10.2,10.3,12.5,14.8,12.4,11.3,10.3,10.1,10.2,10.5,10.4,10.3,14.7,10.1,
              16.7,16.3,16.4,14.2,10.2,10.1,10.3,10.2,11.7,13.2,13.2,11.1,11.4,
              rep(10.3,times=29))
) %>%
  group_by(Site) %>%
  mutate(Lead_Value = lead(Value)) %>%
  ungroup() %>%
  mutate(
    Surge_start = ifelse(Lead_Value - Value >= 2, paste0("Surge", row_number()), NA)
  ) %>%
  mutate(Date_time = as.character(Date_time))

# 处理大数据帧
df2 <- do.call("rbind", replicate(1000, df, simplify = FALSE))

# 应用非递归函数生成结果
Output2 <- df2 %>%
  group_by(Site) %>%
  mutate(
    next_smaller_idx = find_next_smaller_non_recursive(Value),
    Surge_end = ifelse(grepl("Surge", Surge_start), Date_time[next_smaller_idx], NA)
  ) %>%
  select(-next_smaller_idx) # 可选：移除中间辅助列

额外说明 #

1. 结果一致性：新函数的输出与原递归函数完全一致，但处理速度提升几个数量级
2. 栈限制的误区：无需调整Shell/PowerShell的内存参数，因为R的栈限制是进程内的配置，若确实需要临时调整栈大小（不推荐），可使用utils::memory.limit()（Windows）或ulimit（Linux/macOS），但此问题根本解决方式是改用非递归实现

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