(cache)JavaScriptで配列の最大値・最小値求めるならreduceで

JavaScriptでMath.max.applyやMath.maxに対してのスプレッド構文が使えなかった時にreduceを使って最大値を求めた時のメモです。なぜ使えなかったのかもメモで残しておきます。

reduceで配列の最大値を求める

let target = [1,2,3,4,5,6,7,8];

//reduce+条件演算子を使用
console.log(target.reduce((a,b)=>a>b?a:b));

//reduce+Math.maxを使用
console.log(target.reduce((a,b)=>Math.max(a,b)));

想像はつくと思うんですが最小値を求めるなら以下のような感じになります。

reduceで配列の最小値を求める

let target = [1,2,3,4,5,6,7,8];

//reduce+条件演算子を使用
console.log(target.reduce((a,b)=>a<b?a:b));

//reduce+Math.minを使用
console.log(target.reduce((a,b)=>Math.min(a,b)));

参考までによく見かけるMath.max.applyとスプレッド構文で最大値を求める方法です。

Math.max.applyとスプレッド構文で配列の最大値を求める

let target = [1,2,3,4,5,6,7,8];

//Math.max.applyを使用
console.log(Math.max.apply(null,target));

//スプレッド構文を使用（ES2015(ES6)で使用可）
console.log(Math.max(...target));

Math.max.applyやスプレッド構文が使えなかったケース

実際に私が遭遇したMath.max.apply（Math.maxに対してのスプレッド構文も含む）が使えなかったケースです。

その1. 配列が大きめだった時

Math.max.applyやスプレッド構文で使用できる配列の大きさには制限があるようで、それを超えてしまう場合は使うことができないようです。私は画像処理するプログラムを書いている時、試しに480x360くらいの画像を処理しようとしたらMaximum call stack size exceededエラーとなったことで、そのことを知りました。

私の環境では13万くらい（以下のサンプルなら125,683以上）でエラーとなりましたが、環境によってはその倍近くいけるものもあるようで、実行環境によって制限が異なることがあるため注意が必要です。

大きめの配列

let target = [];
for(let i=0;i<130000;i++) {
    target.push(Math.random())
}
let max = Math.max.apply(null, target);//又はMath.max(...target)
console.log(max);

大きめの配列の実行結果

$ node large_array_max.js 
large_array_max.js:6
let max = Math.max.apply(null, target)
                   ^

RangeError: Maximum call stack size exceeded
    at Object.<anonymous> (/home/large_array_max.js:6:20)
    at Module._compile (module.js:652:30)
    at Object.Module._extensions..js (module.js:663:10)
    at Module.load (module.js:565:32)
    at tryModuleLoad (module.js:505:12)
    at Function.Module._load (module.js:497:3)
    at Function.Module.runMain (module.js:693:10)
    at startup (bootstrap_node.js:191:16)
    at bootstrap_node.js:612:3

その2. 欲しいのが最大値じゃなかった時

ちょっと分かりにくいですがよくあるケースだと思います。例えば以下のようなデータがあって最大値（つまり最高年齢）ではなく「最高年齢の「人」」や「最高年齢の「人の名前」」を取得したい場合とかです。

名前	年齢
Aさん	10
Bさん	20
Cさん	30
Dさん	40
Eさん	50

reduceを使った場合は以下のような感じで、最大値を求めるプログラムとほとんど同じように書けます。

reduceを使ったサンプル

let target = [
  {name:"Aさん", age:10},
  {name:"Bさん", age:20},
  {name:"Cさん", age:30},
  {name:"Dさん", age:40},
  {name:"Eさん", age:50}
]

//最高年齢の人を表示
console.log(target.reduce((a,b)=>a.age>b.age?a:b));

//名前だけ表示したい場合
console.log(target.reduce((a,b)=>a.age>b.age?a:b).name);

Math.max.applyやスプレッド構文では実現できないので、もしreduceを使わないで書くとするなら以下のような感じになるんじゃないかと思います。

reduceを使わない

let target = [
    {name:"Aさん", age:10},
    {name:"Bさん", age:20},
    {name:"Cさん", age:30},
    {name:"Dさん", age:40},
    {name:"Eさん", age:50}
]

let max = null;
for (const o of target) {
    if (!max || o.age > max.age) max = o
}
console.log(max);
console.log(max.name);

速度について

reduceだと配列ぐるぐる回しているんだから遅くて、Math.max.applyやスプレッド構文は関数使っているから速いようなイメージがあったのでちょっと測定してみました。環境はLubuntu16.04(64bit)でnodejsはv8.11.3です。

環境

$ uname -a
Linux it 4.4.0-128-generic #154-Ubuntu SMP Fri May 25 14:15:18 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ node -v
v8.11.3

まずは大きめの配列（10万）を作成しJSON形式で保存します。本当はもっと大きい配列の方が差が出やすいと思うのですがMath.max.applyとスプレッド構文で扱える数の制約のためこの数としました。

配列を作成

"use strict"

let target = []
for(let n=0;n<100000;n++) {
    target.push(Math.random())
}
//JSON形式で保存
let fs = require('fs');
fs.writeFileSync('test_array.json', JSON.stringify(target));

測定プログラムです。先ほど作成した配列から最大値を求める処理を100回繰り返します。

測定プログラム（reduceを使った場合）

"use strict"

let target = require("./test_array.json");
let max;
for(let n=0;n<100;n++) {
    max = target.reduce((a,b)=>a>b?a:b);
}
console.log(max)

測定プログラム（reduce+Math.maxを使った場合）

"use strict"

let target = require("./test_array.json");
let max;
for(let n=0;n<100;n++) {
    max = target.reduce((a,b)=>Math.max(a,b));
}
console.log(max)

測定プログラム（Math.max.applyを使った場合）

"use strict"

let target = require("./test_array.json");
let max;
for(let n=0;n<100;n++) {
    max = Math.max.apply(null, target)
}
console.log(max)

測定プログラム（スプレッド構文を使った場合）

"use strict"

let target = require("./test_array.json");
let max;
for(let n=0;n<100;n++) {
    max = Math.max(...target)
}
console.log(max)

結果は以下のとおりです。今回の環境下ではreduceで条件演算子を使ったものが一番速い結果になりました。しかし配列の中身が全て整数の場合だと差がほとんどなくなったり、環境が違えばMath.maxの方が速い場合もあるようです。どちらが速いとかは一言では言えないかなっていうのが私の感想です。

結果

$ time node test_reduce.js
0.9999991287922751

real    0m0.428s
user    0m0.392s
sys 0m0.029s

$ time node test_reduce_math_max.js
0.9999991287922751

real    0m0.788s
user    0m0.693s
sys 0m0.056s


$ time node test_math_max_apply.js
0.9999991287922751

real    0m2.047s
user    0m2.198s
sys 0m0.338s

$ time node test_spred.js
0.9999991287922751

real    0m2.202s
user    0m2.119s
sys 0m0.400s

ちなみに速度を重視するなら以下のようなアルゴリズムの教科書に出てきそうなプログラムを書いた方が高速になるようです。reduceが速いかMath.max.applyが速いかって競うことに意味があるんだろうかって考えさせられます。

測定プログラム（while+ifを使った場合）

"use strict"

let target = require("./test_array.json");
let i;
let max;
for(let n=0;n<100;n++) {
  i = target.length;
  max = -Infinity;
  while (i--) {
    if (target[i] > max) { max = target[i] }
  }
}
console.log(max);

結果

$ time node test_while_if.js
0.9999744004750859

real    0m0.152s
user    0m0.136s
sys 0m0.012s