愚公上岸说

11-11 23:01 四川大学前端工程师发布于四川

关注

【前端面试小册】JS-第19节：实现 reduce

第19节：实现 reduce

一、reduce 的核心概念

1.1 什么是 reduce

reduce 是数组的一个高阶函数，用于将数组中的所有元素通过指定的函数累积计算，最终返回一个单一的值。

语法：

array.reduce(callback(accumulator, currentValue, currentIndex, array), initialValue)

参数：

callback：执行每个元素的函数
- accumulator：累积值
- currentValue：当前元素
- currentIndex：当前索引（可选）
- array：原数组（可选）
initialValue：初始值（可选）

1.2 基本使用

const arr = [1, 2, 3, 4];
const sum = arr.reduce((acc, cur) => acc + cur, 0);
console.log(sum);  // 10

// 不提供初始值
const sum2 = arr.reduce((acc, cur) => acc + cur);
console.log(sum2);  // 10

二、实现原理

2.1 完整实现

Array.prototype.myReduce = function(callback, initialValue) {
    // 1. 检查 this 是否为 undefined 或 null
    if (this == undefined) {
        throw new TypeError('this is null or not defined');
    }
    
    // 2. 检查 callback 是否为函数
    if (typeof callback !== 'function') {
        throw new TypeError(`${callback} is not a function`);
    }
    
    // 3. myReduce 的调用者
    const caller = Object(this);
    
    // 4. >>> 无符号右移，保证 this.length 有意义为数字类型，且是正整数
    // 在有效的数组范围内（0 ～ 0xFFFFFFFF），在无意义的情况下是 0
    const len = this.length >>> 0;
    
    let accumulator = initialValue;
    let k = 0;
    
    // 5. 如果第二个参数为 undefined 的情况下
    // 则数组的第一个有效值作为累加器的初始值
    if (accumulator === undefined) {
        // 跳过空位（稀疏数组）
        while (k < len && !(k in caller)) {
            k++;
        }
        
        // 如果超出数组界限还没有找到累加器的初始值，则 TypeError
        if (k >= len) {
            throw new TypeError('Reduce of empty array with no initial value');
        }
        accumulator = caller[k++];
    }
    
    // 6. 遍历数组，执行回调函数
    while (k < len) {
        if (k in caller) {
            accumulator = callback.call(undefined, accumulator, caller[k], k, caller);
        }
        k++;
    }
    
    return accumulator;
};

2.2 关键点解析

2.2.1 类型检查

if (this == undefined) {
    throw new TypeError('this is null or not defined');
}

为什么使用 == 而不是 ===：

== 会进行类型转换，null == undefined 为 true
这样可以同时检查 null 和 undefined

2.2.2 无符号右移 `>>>`

const len = this.length >>> 0;

作用：

>>> 0 将值转换为 32 位无符号整数
确保 length 是正整数
如果 length 无效，结果为 0

示例：

-1 >>> 0;      // 4294967295
'10' >>> 0;    // 10
null >>> 0;    // 0
undefined >>> 0;  // 0

2.2.3 处理稀疏数组

while (k < len && !(k in caller)) {
    k++;
}

稀疏数组：数组中存在空位（hole）

const sparse = [1, , , 4];  // 索引 1 和 2 是空位
console.log(1 in sparse);    // false
console.log(3 in sparse);    // true

2.2.4 初始值处理

if (accumulator === undefined) {
    // 跳过空位，找到第一个有效值
    while (k < len && !(k in caller)) {
        k++;
    }
    
    // 如果数组为空或全是空位，抛出错误
    if (k >= len) {
        throw new TypeError('Reduce of empty array with no initial value');
    }
    accumulator = caller[k++];
}

逻辑：

如果没有提供初始值，使用数组的第一个有效值作为初始值
需要跳过空位
如果数组为空，抛出错误

三、执行流程

3.1 流程图

graph TD
    A[调用 myReduce] --> B{this 是否为 undefined?}
    B -->|是| C[抛出 TypeError]
    B -->|否| D{callback 是否为函数?}
    D -->|否| E[抛出 TypeError]
    D -->|是| F[获取数组长度]
    F --> G{是否有初始值?}
    G -->|否| H[查找第一个有效值]
    H --> I{找到有效值?}
    I -->|否| J[抛出 TypeError]
    I -->|是| K[使用第一个有效值作为初始值]
    G -->|是| L[使用提供的初始值]
    K --> M[开始遍历数组]
    L --> M
    M --> N{是否在数组中?}
    N -->|是| O[执行回调函数]
    N -->|否| P[跳过]
    O --> Q[更新累积值]
    Q --> R{是否遍历完?}
    P --> R
    R -->|否| M
    R -->|是| S[返回累积值]

3.2 执行示例

const arr = [1, 2, 3, 4];
const sum = arr.myReduce((acc, cur) => acc + cur, 0);

// 执行过程：
// 初始值：accumulator = 0, k = 0
// k=0: accumulator = callback(0, 1, 0, arr) = 0 + 1 = 1
// k=1: accumulator = callback(1, 2, 1, arr) = 1 + 2 = 3
// k=2: accumulator = callback(3, 3, 2, arr) = 3 + 3 = 6
// k=3: accumulator = callback(6, 4, 3, arr) = 6 + 4 = 10
// 返回：10

四、测试用例

4.1 基础测试

// 测试 1：基本求和
const arr = [1, 2, 3, 4];
const reducer = (acc, cur) => acc + cur;
console.log(arr.myReduce(reducer));        // 10
console.log(arr.myReduce(reducer, 0));     // 10

// 测试 2：求最大值
const max = arr.myReduce((acc, cur) => Math.max(acc, cur));
console.log(max);  // 4

// 测试 3：数组转对象
const obj = arr.myReduce((acc, cur, index) => {
    acc[index] = cur;
    return acc;
}, {});
console.log(obj);  // { 0: 1, 1: 2, 2: 3, 3: 4 }

4.2 边界情况测试

// 测试 4：空数组（无初始值）
try {
    [].myReduce((acc, cur) => acc + cur);
} catch (error) {
    console.log(error.message);  // Reduce of empty array with no initial value
}

// 测试 5：空数组（有初始值）
const result = [].myReduce((acc, cur) => acc + cur, 0);
console.log(result);  // 0

// 测试 6：稀疏数组
const sparse = [1, , , 4];
const sum = sparse.myReduce((acc, cur) => acc + cur, 0);
console.log(sum);  // 5（跳过空位）

// 测试 7：只有一个元素（无初始值）
const single = [5].myReduce((acc, cur) => acc + cur);
console.log(single);  // 5（直接返回该元素）

// 测试 8：只有一个元素（有初始值）
const single2 = [5].myReduce((acc, cur) => acc + cur, 10);
console.log(single2);  // 15

4.3 复杂场景测试

// 测试 9：扁平化数组
const nested = [[1, 2], [3, 4], [5, 6]];
const flat = nested.myReduce((acc, cur) => acc.concat(cur), []);
console.log(flat);  // [1, 2, 3, 4, 5, 6]

// 测试 10：统计字符出现次数
const chars = ['a', 'b', 'a', 'c', 'b', 'a'];
const count = chars.myReduce((acc, cur) => {
    acc[cur] = (acc[cur] || 0) + 1;
    return acc;
}, {});
console.log(count);  // { a: 3, b: 2, c: 1 }

// 测试 11：按属性分组
const people = [
    { name: 'Alice', age: 20 },
    { name: 'Bob', age: 25 },
    { name: 'Charlie', age: 20 }
];
const grouped = people.myReduce((acc, cur) => {
    const age = cur.age;
    if (!acc[age]) {
        acc[age] = [];
    }
    acc[age].push(cur);
    return acc;
}, {});
console.log(grouped);
// {
//   20: [{ name: 'Alice', age: 20 }, { name: 'Charlie', age: 20 }],
//   25: [{ name: 'Bob', age: 25 }]
// }

五、常见应用场景

5.1 数组求和

const numbers = [1, 2, 3, 4, 5];
const sum = numbers.reduce((acc, cur) => acc + cur, 0);

5.2 数组求积

const numbers = [1, 2, 3, 4, 5];
const product = numbers.reduce((acc, cur) => acc * cur, 1);

5.3 数组转对象

const arr = [
    { id: 1, name: 'Alice' },
    { id: 2, name: 'Bob' }
];
const obj = arr.reduce((acc, cur) => {
    acc[cur.id] = cur;
    return acc;
}, {});
// { 1: { id: 1, name: 'Alice' }, 2: { id: 2, name: 'Bob' } }

5.4 函数组合

const compose = (...fns) => (value) => 
    fns.reduceRight((acc, fn) => fn(acc), value);

const add1 = x => x + 1;
const multiply2 = x => x * 2;
const subtract3 = x => x - 3;

const composed = compose(subtract3, multiply2, add1);
console.log(composed(5));  // ((5 + 1) * 2) - 3 = 9

六、与原生的区别

6.1 行为一致性

我们的实现应该与原生 reduce 行为一致：

// 原生 reduce
const arr = [1, 2, 3];
const native = arr.reduce((acc, cur) => acc + cur);

// 我们的实现
const custom = arr.myReduce((acc, cur) => acc + cur);

console.log(native === custom);  // true

6.2 错误处理

// 原生 reduce 的错误
try {
    [].reduce((acc, cur) => acc + cur);
} catch (error) {
    console.log(error.message);  // Reduce of empty array with no initial value
}

// 我们的实现应该抛出相同的错误
try {
    [].myReduce((acc, cur) => acc + cur);
} catch (error) {
    console.log(error.message);  // Reduce of empty array with no initial value
}

七、性能优化

7.1 优化版本

Array.prototype.myReduce = function(callback, initialValue) {
    if (this == null) {
        throw new TypeError('this is null or not defined');
    }
    
    if (typeof callback !== 'function') {
        throw new TypeError(`${callback} is not a function`);
    }
    
    const caller = Object(this);
    const len = caller.length >>> 0;
    
    if (len === 0 && initialValue === undefined) {
        throw new TypeError('Reduce of empty array with no initial value');
    }
    
    let accumulator = initialValue;
    let k = 0;
    
    if (accumulator === undefined) {
        while (k < len && !(k in caller)) {
            k++;
        }
        if (k >= len) {
            throw new TypeError('Reduce of empty array with no initial value');
        }
        accumulator = caller[k++];
    }
    
    while (k < len) {
        if (k in caller) {
            accumulator = callback(accumulator, caller[k], k, caller);
        }
        k++;
    }
    
    return accumulator;
};