JavaScript for循环执行耗时过长 如何优化性能及实现递归方案

你代码跑的慢和用for循环还是递归没关系，核心是写出来的逻辑时间复杂度到了O(n²)，存在大量无意义的重复计算：

• 每次循环都调用indexOf、lastIndexOf全量扫描数组判断元素是否唯一，两个方法本身就是O(n)复杂度
• 遇到重复区域时，又全量遍历整个price数组筛选同区域价格，又是一次O(n)扫描
• 同一个区域的均值、标准差会被重复计算N次：比如某个区域出现了m次，这段代码就会重复算m次几乎相同的均值、标准差，做了大量无用功
• 递归不仅解决不了这个问题，还会额外增加函数调用栈开销，数据量大了甚至可能触发栈溢出，性能比普通循环还差。

不要纠结循环写法，先把重复计算干掉：先做一次遍历把同区域的价格提前归集分组，一次性算完每个区域的是否唯一、均值、标准差，最后再遍历一次原数组做3sigma判断即可，整体时间复杂度直接降到O(n)，数据量越大性能提升越明显。
优化后代码：

const store = [];
const areaStatsMap = new Map();

// 第一遍遍历：按区域分组归集价格
for (let i = 0; i < area.length; i++) {
  const curArea = area[i];
  if (!areaStatsMap.has(curArea)) {
    areaStatsMap.set(curArea, {
      priceList: [],
      mean: 0,
      std: 0,
      isUnique: false
    });
  }
  areaStatsMap.get(curArea).priceList.push(price[i]);
}

// 第二遍：一次性计算每个区域的统计值
for (const stats of areaStatsMap.values()) {
  const list = stats.priceList;
  stats.isUnique = list.length === 1;
  if (stats.isUnique) continue;
  // 计算均值
  stats.mean = list.reduce((sum, val) => sum + val, 0) / list.length;
  // 计算标准差
  const variance = list.reduce((sum, val) => sum + (val - stats.mean) ** 2, 0) / list.length;
  stats.std = variance ** 0.5;
}

// 第三遍遍历：按规则筛选符合条件的条目
for (let i = 0; i < area.length; i++) {
  const curArea = area[i];
  const curPrice = price[i];
  const stats = areaStatsMap.get(curArea);
  if (stats.isUnique) {
    store.push([curArea, curPrice]);
    continue;
  }
  if (Math.abs(stats.mean - curPrice) <= 3 * stats.std) {
    store.push([curArea, curPrice]);
  }
}

递归本质是逻辑拆分的手段，不是性能优化手段，如果你出于代码结构考虑一定要写递归版本，可以参考下面的写法，但是性能不会比上面的迭代版本更好：

const store = [];
const areaStatsMap = new Map();

// 递归完成区域分组
function groupData(index = 0) {
  if (index >= area.length) return;
  const curArea = area[index];
  if (!areaStatsMap.has(curArea)) {
    areaStatsMap.set(curArea, { priceList: [], mean: 0, std: 0, isUnique: false });
  }
  areaStatsMap.get(curArea).priceList.push(price[index]);
  groupData(index + 1);
}

// 递归完成结果归集
function collectValidData(index = 0) {
  if (index >= area.length) return;
  const curArea = area[index];
  const curPrice = price[index];
  const stats = areaStatsMap.get(curArea);
  if (stats.isUnique || Math.abs(stats.mean - curPrice) <= 3 * stats.std) {
    store.push([curArea, curPrice]);
  }
  collectValidData(index + 1);
}

// 执行逻辑
groupData();
// 区域统计值计算和之前迭代版逻辑一致，这里省略重复代码
collectValidData();

补充一点：你原逻辑里计算同区域价格列表时会排除当前索引的价格，这种写法会让同区域每个条目计算的均值、标准差都存在微小差异，从统计角度来说做3sigma异常值过滤一般是用全量样本计算统计值，如果你需要严格对齐原逻辑的计算结果，只需要在分组时同步存储价格对应的索引，计算统计值时排除当前索引即可，整体复杂度依然远低于原写法。

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