学会reduce函数

Array 中有几个很实用的函数,比如 each, map, filter, find, some 等,这些我们平时的业务实现中会经常用到,而有一个 reduce 函数可能经常被忽视。

简单介绍

可直接参考MDN: Array.prototype.reduce

简单来说就是这样的函数形式

1
2
3
4
[].reduce(function (accumulator, currentValue, currentIndex, array) {
// do something
return accumulator;
}, initialValueOfAccumulator);

在迭代函数中会接收一个accumulator,在 reduce 开始时可以为它设置初始值(即上面的initialValueOfAccumulator)。在迭代中做的事情就是把处理后的结果追加到accumulator上再将其返回,这样就使得accumulator在迭代中依次传递(第0次的结果会传给第1次,第1次的结果传递给第2次,…),所有的处理结果都汇聚在accumulator上。最后 reduce 函数的返回值就是最终的accumulator值。

map-reduce 关系

MapReduce 是在分布式中提出的计算方法,我看过两篇解释简单又清晰的文章,可供参考

js 中也有mapreduce函数,用它俩也能实现 MapReduce,区别是 js 没有分布式计算的支持。这里简单示意下 word count 程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 一些列文章,数组中每个元素相当于一篇文章的完整字符串
var articles = [
'This is an example of word count.',
'This is an example of word count.',
'todo...'
];
articles.map(function (content) {
// 将每篇文章的字符串都切成单词数组,如果需要预处理(比如剔除某些助动词)也在这时处理
var words = content.replace(/[^\w\s]/g, '').split(/\s+/);
// 统计该篇文章的 word count
var countMap = words.reduce(function (accumulator, word) {
accumulator[word] = (accumulator[word] || 0) + 1;
return accumulator;
}, {});
// 返回每篇文章的单词统计
return countMap;
}).reduce(function (stats, countMap) {
// 将每篇文章的统计结果合并起来
for (var word in countMap) {
stats[word] = (stats[word] || 0) + countMap[word];
}
return stats;
}, {});

运用场景举例

1. 数组扁平化

题目:将形如 [[0, 1], [2, 3, 4], [5]] 的数组转成扁平结构的一维数组 [0, 1, 2, 3, 4, 5]

用 reduce 实现的话代码就很简单

1
2
3
[[0, 1], [2, 3, 4], [5]].reduce(function (flatten, item) {
return flatten.concat(item);
}, []);

现在考虑一下:如果输入的数组可能嵌套多层呢?形如 [[0, [1]], [2, [3, 4]], [[[5]]]] 且嵌套的深度我们无法预知

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 对多维数组的 flatten
var flatten = function (array) {
// 如果当前 array 已经是基础类型了,就转成1维数组
if (array instanceof Array === false) {
return [array];
}
// 临时空间,它的每个成员都要保证是1维数组
var tmps = [];
for (var i in array) {
tmps.push(flatten(array[i]));
}
// 利用 reduce 函数可以将形如 [[a], [b, c]] 的数组扁平化成1维数组
return tmps.reduce(function (res, item) {
return res.concat(item);
}, []);
};
flatten([0, 1, 2, 3, 4, 5]);
flatten([0, [1], [2, 3], 4, 5]);
flatten([[0, [1]], [[2], [3]], [[4, 5]]]);
flatten([[[0, 1]], [2, [3, 4]], [[[5]]]]);

如果需要从右向左的顺序 flatten 处理,则可使用 reduceRight 代替 reduce

当然,这个多维数组的例子有点刻意使用 reduce 的感觉,只要使用递归,其中 reduce 可以用 tmps = tmps.concat(flatten(array[i])) 代替。

顺便附上 flatten 函数的 underscore 实现版本(非递归实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Internal implementation of a recursive `flatten` function.
var flatten = function(input, shallow, strict, output) {
output = output || [];
var idx = output.length;
for (var i = 0, length = getLength(input); i < length; i++) {
var value = input[i];
if (isArrayLike(value) && (_.isArray(value) || _.isArguments(value))) {
// Flatten current level of array or arguments object.
if (shallow) {
var j = 0, len = value.length;
while (j < len) output[idx++] = value[j++];
} else {
flatten(value, shallow, strict, output);
idx = output.length;
}
} else if (!strict) {
output[idx++] = value;
}
}
return output;
}

2. 统计节点标签数

另一个实用例子是统计一个页面中所有的节点数,利用 document.getElementsByTagName('*') 可取出所有节点的 HTMLCollection,再配合 map 和 reduce 函数就可轻松统计出各 tagName 的数目。

1
2
3
4
5
6
7
8
Array.prototype.slice.call(document.getElementsByTagName('*'))
.map(function (el) {
return el.tagName;
})
.reduce(function (total, tag) {
total[tag] = (total[tag] || 0) + 1;
return total;
}, {});

reduce 内部实现

根据 reduce 函数的定义,可以简单这样实现(仅供学习使用)

1
2
3
4
5
6
Array.prototype.reduce = function (iterator, accumulator) {
for (var i = 0; i < this.length; i++) {
accumulator = iterator(accumulator, this[i], i, this);
}
return accumulator;
}

reduce 函数是 es5 中的标准,从 MDN 上抄了一份 Polyfill(可用于生产环境)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Production steps of ECMA-262, Edition 5, 15.4.4.21
// Reference: http://es5.github.io/#x15.4.4.21
// https://tc39.github.io/ecma262/#sec-array.prototype.reduce
if (!Array.prototype.reduce) {
Object.defineProperty(Array.prototype, 'reduce', {
value: function(callback /*, initialValue*/) {
if (this === null) {
throw new TypeError( 'Array.prototype.reduce ' +
'called on null or undefined' );
}
if (typeof callback !== 'function') {
throw new TypeError( callback +
' is not a function');
}
// 1. Let O be ? ToObject(this value).
var o = (Objectthis);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// Steps 3, 4, 5, 6, 7
var k = 0;
var value;
if (arguments.length >= 2) {
value = arguments[1];
} else {
while (k < len && !(k in o)) {
k++;
}
// 3. If len is 0 and initialValue is not present,
// throw a TypeError exception.
if (k >= len) {
throw new TypeError( 'Reduce of empty array ' +
'with no initial value' );
}
value = o[k++];
}
// 8. Repeat, while k < len
while (k < len) {
// a. Let Pk be ! ToString(k).
// b. Let kPresent be ? HasProperty(O, Pk).
// c. If kPresent is true, then
// i. Let kValue be ? Get(O, Pk).
// ii. Let accumulator be ? Call(
// callbackfn, undefined,
// « accumulator, kValue, k, O »).
if (k in o) {
value = callback(value, o[k], k, o);
}
// d. Increase k by 1.
k++;
}
// 9. Return accumulator.
return value;
}
});
}