js数组高级函数之reduce()

[FrankKai]

reduce()是一个js数组原型链上的高级函数，没个几年经验估计对这个方法的用法会很模糊。 我最常用的就是用recude()求和，但其实它还有很多值得挖掘的好用之处。 所以开这个issue来系统性学习下reduce()吧。

• 初识reduce()
  • 概念
  • 最简reduce
  • reducer函数的4个参数
• 语法
  • 参数
  • 返回值
  • 如何理解initialValue和acc，cur的关系？
  • 没指定initialValue的空数组reduce，抛什么错？
• 描述
  • reduce callback的四个参数
  • reduce()是如何工作的？
• 实际用途
  • 对一个数组中的元素求和
  • 对对象中的元素求和
  • 抹平一个数组
  • 统计对象的属性值
  • 通过属性分组对象
  • 使用...和初始值绑定对象数组中包含的数组
  • 移除数组中的重复项
  • 使用.reduce()移除.filter()和.map()
  • 按照序列运行Promise
  • 管道式组合函数
  • 使用reduce写map
• leetcode reduce 解法题目
  • 136.只出现一次的数字（easy）
  • 202.快乐数（easy）
  • 258.各位相加（easy）
  • 500.键盘行（easy）

[FrankKai]

初识reduce()

概念

• reduce的中文意思为约简。Hadoop有一个概念叫MapReduce。
• reduce()方法执行一个reducer函数，reducer函数是自定义的。
• 这个reducer函数会遍历数组中的每个元素，并且最终输出一个唯一的值。
• reducer函数的返回值会赋值给accumulator，数组遍历期间每次迭代这个值都会被remembered住，最终成为最后的，单个的结果值。

最简reduce

const array1 = [1, 2, 3, 4];
const reducer = (acc, cur) => acc + cur;
// 1+2+3+4 => 10
console.log(array1.reduce(reducer));
// 5+1+2+3+4 => 15
console.log(array1.reduce(reducer, 5));

reducer函数的4个参数

1. 累加器（Accumulator）（acc）
2. 当前值（Current Value）（cur）
3. 当前索引（Current Index）（idx）
4. 源数组（Source Array）（src）

[FrankKai]

语法

arr.reduce(callback( accumulator, currentValue[, index[, array]] ), [, initialValue])

参数

• callback 这个函数会对数组中的每个元素执行（如果没有initialValue指定的话，第一项除外。） 这个回调函数有4个argument：
  • accumulator 累加器累加callback的返回值。它是callback上一次调用的返回的累加值，或者是initialValue（如果指定initialValue的话，第一项的acc是这个指定的值。）
  • currentValue 数组当前处理的元素。
  • index（可选的）数组当前处理的元素的index。如果指定initialValue的话，index从 0 开始；否则从 1 开始。
  • array（可选的）调用reduce()方法的数组。
• initialValue（可选的）
  • callback执行第一次调用的第一个参数的值。
  • 如果没有initialValue指定的话，数组中的第一项会没当做acc的初始值，并且作为currentValue跳过。
  • 在一个空数组上调用reduce()并且不指定initialValue的话，会抛出一个TypeError。

返回值

由reduce产生的单个值。

如何理解initialValue和acc，cur的关系？

如果指定initialValue的话，index从 0 开始；否则从 1 开始。 如果没有initialValue指定的话，数组中的第一项会没当做acc的初始值，并且作为currentValue跳过。 两句话是同样的意思。

看了下面的demo就明白了：

/* 没有指定initialValue。
* 0未出现，说明没有指定initialValue时，跳过第一次遍历。
* acc初始值为'foo'，说明跳过第一次遍历后，acc将首次的cur作为自己的值。
*/
var arr = ['foo','bar'];
arr.reduce((acc,cur,idx,iarr)=>{
    console.log(acc, cur, idx);
    return acc+cur;
})
VM209:3 foo bar 1
"foobar"

/* 有指定initialValue。
* 0出现，首次acc值为baz。说明有指定initialValue时，第一次遍历将initialValue作为acc的初始值。
* 1时acc值为'bazfoo'，说明经过第一次遍历后，acc将上一次计算的acc+cur作为新的acc传递进来。
*/
var arr = ['foo','bar'];
arr.reduce((acc,cur,idx,iarr)=>{
    console.log(acc, cur, idx);
    return acc+cur;
},'baz')
VM211:3 baz foo 0
VM211:3 bazfoo bar 1
"bazfoobar"

没指定initialValue的空数组reduce，抛什么错？

[].reduce(()=>{},)
TypeError: Reduce of empty array with no initial value

[FrankKai]

描述

reduce callback的四个参数

reduce()方法对数组中的每个元素执行的callback，会接收4个参数：

1. accumulator(acc)
2. currentValue(cur)
3. currentIndex(idx)
4. array(arr)

• acc和cur。
  • callback第一次调用时，acc和cur可以是两个值之一。
  • 如果initialValue在调用reduce()时指定，acc等于initialValue，cur等于arr[0]。
  • 如果initialValue没有指定，acc等于arr[0]，cur等于arr[1]。
• 开始计算index。 如果initialValue没有提供，reduce()会从index 1开始计算，跳过index 0的阶段。若有提供initialValue，从index 0开始计算。
• TypeError。 如果array是空而且没有initialValue，TypeError: Reduce of empty array with no initial value 会抛出。
• 有两种不调用callback的情况。 如果数组只有一个元素，而且没有initialValue，或者有initialValue但是array是空的，这个值会直接返回，不会调用callback。
• 给定一个初始的initialValue是最安全的。 如果不给出初始值的话，可能会有多种输出值。
• 求最大最小值的话，使用map&&reduce，并且指定initialValue为Infinity或者-Infinity是最安全的。

不初始设置initialValue vs 初始设置initialValue

let maxCallback = ( acc, cur ) => Math.max( acc.x, cur.x );
let maxCallback2 = ( max, cur ) => Math.max( max, cur );

// 不设置initialValue执行reduce
[ { x: 2 }, { x: 22 }, { x: 42 } ].reduce( maxCallback ); // NaN
[ { x: 2 }, { x: 22 }            ].reduce( maxCallback ); // 22
[ { x: 2 }                       ].reduce( maxCallback ); // { x: 2 }
[                                ].reduce( maxCallback ); // TypeError

// map & reduce指定initialValue为-Infinity是最安全的
[ { x: 22 }, { x: 42 } ].map( el => el.x )
                        .reduce( maxCallback2, -Infinity );

上面这个例子有办法不指定initialValue就返回出最大值吗？怎么改？ 能。reduce的callback return出一个对象即可。

let maxCallback = ( acc, cur ) => ({x: Math.max( acc.x, cur.x )});

// 不设置initialValue执行reduce
[ { x: 2 }, { x: 22 }, { x: 42 } ].reduce( maxCallback ); // {x:42}
[ { x: 2 }, { x: 22 }            ].reduce( maxCallback ); // {x:22}
[ { x: 2 }                       ].reduce( maxCallback ); // { x: 2 }
[                                ].reduce( maxCallback ); // TypeError

reduce()是如何工作的？

假设reduce()方法按照下面的方式调用：

[0, 1, 2, 3, 4].reduce(function(accumulator, currentValue, currentIndex, array) {
  return accumulator + currentValue
})

callback会回调几次？4次。 reduce的返回值是什么？是最后一次callback的return value。 callback详情如下：

可以使用箭头函数：

[0, 1, 2, 3, 4].reduce( (accumulator, currentValue, currentIndex, array) => accumulator + currentValue )

[0, 1, 2, 3, 4].reduce((accumulator, currentValue, currentIndex, array) => {
    return accumulator + currentValue
}, 10)

如果给定一个10作为initialValue，reduce的callback调用详情如下： 最终的返回值为20。

[FrankKai]

实际用途

对一个数组中的元素求和

let total = [ 0, 1, 2, 3 ].reduce(
  ( accumulator, currentValue ) => accumulator + currentValue,
  0
)
// total为6

对对象中的数字求和

如果想让数组中的每个元素都进入迭代，必须设置一个initialValue。

let initialValue = 0
let sum = [{x: 1}, {x: 2}, {x: 3}].reduce(
    (accumulator, currentValue) => accumulator + currentValue.x
    , initialValue
)
console.log(sum) // logs 6

如果想返回对象的形式呢？

let sum = [{x: 1}, {x: 2}, {x: 3}].reduce(
    (accumulator, currentValue) => ({x: accumulator.x + currentValue.x})
)
console.log(sum) // logs {x: 6}

抹平数组中的数组

let flattened = [[0, 1], [2, 3], [4, 5]].reduce(
  ( accumulator, currentValue ) => accumulator.concat(currentValue),
  []
) // [0, 1, 2, 3, 4, 5, 6]

统计数组中元素出现的次数

Object形式

let names = ['Alice', 'Bob', 'Tiff', 'Bruce', 'Alice']
let countedNames = names.reduce(function (allNames, name) { 
  if (name in allNames) {
    allNames[name]++
  }
  else {
    allNames[name] = 1
  }
  return allNames
}, {})
// countedNames is:
// { 'Alice': 2, 'Bob': 1, 'Tiff': 1, 'Bruce': 1 }

Map形式

let names = ['Alice', 'Bob', 'Tiff', 'Bruce', 'Alice']
let countedNames = names.reduce(function (map, name) { 
  if (map.has(name)) {
    map.set(name , map.get(name)+1);
  }
  else {
    map.set(name, 1);
  }
  return  map
}, new Map())
// countedNames is:
// {"Alice" => 2, "Bob" => 1, "Tiff" => 1, "Bruce" => 1}

通过属性分组对象

之前的热力图表格数据其实可以使用reduce计算，可以简化大量的数组forEach，map和filter等等数组遍历。

let people = [
  { name: 'Alice', age: 21 },
  { name: 'Max', age: 20 },
  { name: 'Jane', age: 20 }
];

function groupBy(objectArray, property) {
  return objectArray.reduce((acc, obj)=>{
    let key = obj[property]
    if (!acc[key]) {
      acc[key] = []
    }
    acc[key].push(obj)
    return acc
  }, {})
}

let groupedPeople = groupBy(people, 'age')
// groupedPeople is:
// { 
//   20: [
//     { name: 'Max', age: 20 }, 
//     { name: 'Jane', age: 20 }
//   ], 
//   21: [{ name: 'Alice', age: 21 }] 
// }

使用...和初始值绑定对象数组中包含的数组

抽取数组中的对象中的数组。

// friends - an array of objects 
// where object field "books" is a list of favorite books 
let friends = [{
  name: 'Anna',
  books: ['Bible', 'Harry Potter'],
  age: 21
}, {
  name: 'Bob',
  books: ['War and peace', 'Romeo and Juliet'],
  age: 26
}, {
  name: 'Alice',
  books: ['The Lord of the Rings', 'The Shining'],
  age: 18
}]

// allbooks - list which will contain all friends' books +  
// additional list contained in initialValue
let allbooks = friends.reduce(function(accumulator, currentValue) {
  return [...accumulator, ...currentValue.books]
}, ['Alphabet'])

// allbooks = [
//   'Alphabet', 'Bible', 'Harry Potter', 'War and peace', 
//   'Romeo and Juliet', 'The Lord of the Rings',
//   'The Shining'
// ]

移除数组中的重复项

reduce可以实现类似Set&&Array.form()的方式去重。

Set&&Array.form()去重

let orderedArray = Array.from(new Set(myArray))

reduce去重

let myArray = ['a', 'b', 'a', 'b', 'c', 'e', 'e', 'c', 'd', 'd', 'd', 'd']
let myOrderedArray = myArray.reduce(function (accumulator, currentValue) {
  if (accumulator.indexOf(currentValue) === -1) {
    accumulator.push(currentValue)
  }
  return accumulator
}, [])
console.log(myOrderedArray)

使用.reduce()移除.filter()和.map()

使用map和filter会遍历数组两次，可以用reduce一次遍历即可。

map,filter普通写法

const numbers = [-5, 6, 2, 0,];
const doubledPositiveNumbers = numbers.map((num)=>{if(num>0) return num*2}).filter((num)=>num)
console.log(doubledPositiveNumbers); // [12, 4]

reduce写法

const numbers = [-5, 6, 2, 0,];
const doubledPositiveNumbers = numbers.reduce((accumulator, currentValue) => {
  if (currentValue > 0) {
    const doubled = currentValue * 2;
    accumulator.push(doubled);
  }
  return accumulator;
}, []);
console.log(doubledPositiveNumbers); // [12, 4]

按照序列运行Promise

链式运行Promise，可用于顺序异步队列。

/**
 * Runs promises from array of functions that can return promises
 * in chained manner
 *
 * @param {array} arr - promise arr
 * @return {Object} promise object
 */
function runPromiseInSequence(arr, input) {
  return arr.reduce(
    (promiseChain, currentFunction) => promiseChain.then(currentFunction),
    Promise.resolve(input)
  )
}

// promise function 1
function p1(a) {
  return new Promise((resolve, reject) => {
    resolve(a * 5)
  })
}

// promise function 2
function p2(a) {
  return new Promise((resolve, reject) => {
    resolve(a * 2)
  })
}

// function 3  - will be wrapped in a resolved promise by .then()
function f3(a) {
 return a * 3
}

// promise function 4
function p4(a) {
  return new Promise((resolve, reject) => {
    resolve(a * 4)
  })
}

const promiseArr = [p1, p2, f3, p4]
runPromiseInSequence(promiseArr, 10)
  .then(console.log)   // 1200

管道式组合函数

pipeline式运行函数，可用于流水线性任务。

// Building-blocks to use for composition
const double = x => x + x
const triple = x => 3 * x
const quadruple = x => 4 * x

// Function composition enabling pipe functionality
const pipe = (...functions) => input => functions.reduce(
    (acc, fn) => fn(acc),
    input
)

// Composed functions for multiplication of specific values
const multiply6 = pipe(double, triple)
const multiply9 = pipe(triple, triple)
const multiply16 = pipe(quadruple, quadruple)
const multiply24 = pipe(double, triple, quadruple)

// Usage
multiply6(6)   // 36
multiply9(9)   // 81
multiply16(16) // 256
multiply24(10) // 240

使用reduce写map

这个写法很谜。

if (!Array.prototype.mapUsingReduce) {
  Array.prototype.mapUsingReduce = function(callback, thisArg) {
    return this.reduce(function(mappedArray, currentValue, index, array) {
      mappedArray[index] = callback.call(thisArg, currentValue, index, array)
      return mappedArray
    }, [])
  }
}
[1, 2, , 3].mapUsingReduce(
  (currentValue, index, array) => currentValue + index + array.length
) // [5, 7, , 10]

[FrankKai]

leetcode reduce 解法题目

• 136.只出现一次的数字（easy）
• 202.快乐数（easy）
• 258.各位相加（easy）
• 500.键盘行（easy）

136.只出现一次的数字（easy）

题目：https://leetcode-cn.com/problems/single-number/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/136.Single_Number.js

var singleNumber = function (nums) {
  /**解法5：reduce
   * 性能：80ms 37.1MB
   */
  let countedNums = nums.reduce((acc, cur) => {
    if (!(cur in acc)) {
      acc[cur] = 1;
    } else {
      delete acc[cur];
    }
    return acc;
  }, {});
  return Object.keys(countedNums)[0];
}

202.快乐数（easy）

题目：https://leetcode-cn.com/problems/happy-number/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/202.Happy_Number.js

// 解法二：递归+Set
var isHappy = function(n) {
  if (n == 1) return true;
  var nextNums = arguments[1] || [];
  var nextNumsSet = new Set(nextNums);
  // 通过Set对数组去重，比较size和length的大小
  if (nextNumsSet.size !== nextNums.length) {
    return false;
  }
  function quadratic(num) {
    return Math.pow(parseInt(num), 2);
  }
  var nextNum = -999;

  if (`${n}`.length === 1) {
    // 7 true, 2 false
    nextNum = quadratic(n);
  } else {
    // 19 true, 78 false
    nextNum = `${n}`
      .split("")
      .map(quadratic)
      .reduce((acc, cur) => acc + cur);
  }
  while (nextNum !== 1) {
    nextNums.push(nextNum);
    // 递归
    nextNum = isHappy(nextNum, nextNums);
    return nextNum;
  }
  return nextNum === 1;
};

258.各位相加（easy）

题目：https://leetcode-cn.com/problems/add-digits/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/258.Add_Digits.js

var addDigits = function (num) {
  /**
   * 解法1：递归 reduce
   * 性能：92ms 36.4MB
   */
  let nums = `${num}`.split("").map((item) => BigInt(item));
  let reduce = nums.reduce((acc, cur) => acc + cur);
  if (`${reduce}`.length === 1) {
    return reduce;
  } else {
    return addDigits(reduce);
  }
};

500.键盘行（easy）

题目：https://leetcode-cn.com/problems/keyboard-row/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/500.Keyboard_Row.js

var findWords = function (words) {
/**
     * 解法2: Array Set
     * 性能：60ms 33.9MB
     * 思路：Set优化indexOf
     */
    // 构建字母表
    const lines = [
        ['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'],
        ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'],
        ['z', 'x', 'c', 'v', 'b', 'n', 'm']
    ]
    lines.forEach((line, i, arr) => {
        let reduceArr = line.reduce((acc, cur) => {
            acc.push(cur);
            acc.push(cur.toUpperCase());
            return acc
        }, [])
        arr[i] = new Set(reduceArr)
    })
    // 拆分单词
    const wordsMap = words.map((word) => word.split(""))
    const validWords = [];
    wordsMap.forEach((word) => {
        lines.forEach((line) => {
            let isValid = word.every((char) => line.has(char));
            if (isValid) validWords.push(word.join(""));
        })
    })
    return validWords;
};

[FrankKai]

参考资料： https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce https://github.com/FrankKai/leetcode-js