优雅实现列表2倍缩减：合并相邻元素的问题与优化方案

问题分析与解决方案 #

现有代码的核心问题

1. 循环逻辑错误：while循环中调用reduceByHalf(v)，始终传入原数组而非当前迭代的ret，导致每次处理后长度固定为65536，无法继续缩减。
2. 奇数长度元素丢失：reduce逻辑仅在偶数索引时处理元素，奇数索引的元素暂存后未被最终加入结果，若数组长度为奇数，最后一个元素会被丢弃。
3. 类型不严谨：reduceByHalf参数使用any[]，不符合TypeScript类型规范。
4. 合并策略粗糙：简单平均相邻元素的方式未考虑直方图（概率分布）的特性，无法保证概率总和或密度的合理性。

修复bug的基础实现

先修正核心逻辑错误，确保数组能正常缩减至目标长度：

#!/usr/bin/env ts-node
'use strict';

const goFrom_131072_to_1024 = (v: number[]) => {
  // 输入已升序，无需重复排序
  let ret = [...v];

  const reduceByHalf = (arr: number[]) => {
    const result: number[] = [];
    for (let i = 0; i < arr.length; i += 2) {
      if (i + 1 < arr.length) {
        // 基础合并：相邻元素平均（后续可替换为直方图专属策略）
        result.push((arr[i] + arr[i+1]) / 2);
      } else {
        // 处理奇数长度的最后一个元素，直接保留
        result.push(arr[i]);
      }
    }
    return result;
  };

  while (ret.length > 1024) {
    console.log(ret.length);
    ret = reduceByHalf(ret);
  }

  return ret;
}

console.log(
  goFrom_131072_to_1024(
    new Array(131072).fill(null).map((v,i) => i)
  )
);

针对直方图的优化合并策略

由于你的列表代表概率分布直方图，需根据数据类型选择合适的合并规则，保证概率特性不变：

1. 如果是频率计数（区间样本数）：合并相邻区间时应求和，总样本数保持不变：

const reduceByHalf = (arr: number[]) => {
  const result: number[] = [];
  for (let i = 0; i < arr.length; i += 2) {
    if (i + 1 < arr.length) {
      // 合并两个区间的样本计数
      result.push(arr[i] + arr[i+1]);
    } else {
      result.push(arr[i]);
    }
  }
  return result;
};

2. 如果是概率密度（单位区间概率）：合并后的区间宽度翻倍，密度取相邻元素的平均（等宽区间下等价于保持概率总和）：

const reduceByHalf = (arr: number[]) => {
  const result: number[] = [];
  for (let i = 0; i < arr.length; i += 2) {
    if (i + 1 < arr.length) {
      // 等宽区间下，密度取平均保证概率合理性
      result.push((arr[i] + arr[i+1]) / 2);
    } else {
      result.push(arr[i]);
    }
  }
  return result;
};

更优雅的递归实现

如果偏好函数式风格，可使用递归缩减至目标长度：

const reduceToTargetLength = (arr: number[], target: number): number[] => {
  if (arr.length <= target) return arr;
  
  const reduced = arr.reduce((acc, curr, idx) => {
    if (idx % 2 === 0) {
      acc.push(curr);
    } else {
      // 替换这里的合并逻辑为上述直方图策略
      acc[acc.length - 1] = (acc[acc.length - 1] + curr) / 2;
    }
    return acc;
  }, [] as number[]);

  // 处理奇数长度导致的剩余元素
  if (arr.length % 2 !== 0) {
    reduced.push(arr[arr.length - 1]);
  }

  return reduceToTargetLength(reduced, target);
};

// 主函数调用
const goFrom_131072_to_1024 = (v: number[]) => {
  return reduceToTargetLength([...v], 1024);
};

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