mode_fast.js

/* globals Map: false */

/**
 * [众数](https://en.wikipedia.org/wiki/Mode_%28statistics%29)是
 * 数据集中出现频率最高的元素。一个数据集可能包含
 * 多个众数：当出现频率相同时，本算法将返回最近遇到的众数。
 *
 * modeFast使用Map对象替代`mode`方法的排序数组方案来跟踪状态，
 * 因此效率更高且支持所有可通过`==`比较的数据类型。
 * 要求
 * [JavaScript环境支持Map对象](https://kangax.github.io/compat-table/es6/#test-Map)，
 * 若不可用将抛出错误。
 *
 * 这是[集中趋势度量](https://en.wikipedia.org/wiki/Central_tendency)方法，
 * 用于寻找数据集的典型中心值。
 *
 * @param {Array<*>} x 包含一个或多个数据点的样本数组
 * @returns {?*} 众数
 * @throws {ReferenceError} 当JavaScript环境不支持Map时抛出
 * @throws {Error} 输入数组为空时抛出
 * @example
 * modeFast(['rabbits', 'rabbits', 'squirrels']); // => 'rabbits'
 */
function modeFast(x) {
    // 建立哈希索引用于记录不同值的出现频率，结构为
    // { 值: 出现次数 }
    const index = new Map();

    // 当前众数值及其出现次数
    let mode;
    let modeCount = 0;

    for (let i = 0; i < x.length; i++) {
        let newCount = index.get(x[i]);
        if (newCount === undefined) {
            newCount = 1;
        } else {
            newCount++;
        }
        if (newCount > modeCount) {
            mode = x[i];
            modeCount = newCount;
        }
        index.set(x[i], newCount);
    }

    if (modeCount === 0) {
        throw new Error("计算众数需要至少一个数据点");
    }

    return mode;
}

export default modeFast;