reduce で積を計算｜コードで実践

reduce で積を計算

このレッスンで分かること

計算量は配列を 1 周するだけなので O(n) です

map と filter の次に覚えるべき関数型ツールが reduce です

reduce は次の 2 つを受け取ります

reduce で積を計算とは

配列の全要素を reduce (畳み込み) で 1 つの値にまとめる。配列の積を計算する関数を実装し、関数型の畳み込みの概念を理解する。

map と filter の次に覚えるべき関数型ツールが reduce です。日本語では 畳み込み とも呼ばれ、配列の全要素を 1 つの値にまとめる 操作を意味します。和 積 最大値 最小値 文字列の連結 カウント など、多くの集計処理が reduce ひとつで表現できます。

本レッスンでは「整数配列を受け取り、全要素の積を返す」関数を reduce の考え方で実装します。空配列の場合は 1 を返します (乗法の単位元 が 1 だから)。

reduce は 初期値 + 各要素を蓄積する関数 の 2 つを与えれば、どんな集計でも書ける万能ツール。

reduce の動き

reduce は次の 2 つを受け取ります。

初期値 (accumulator の初期値)
関数 (accumulator と現在の要素を受け取り、新しい accumulator を返す)

たとえば [1, 2, 3, 4] の 積 を計算する場合は、初期値 1、関数 (acc, n) => acc * n を渡します。動作は次のように進みます。

diagram (will load when visible)

図のポイント (テキスト併記)

各ステップで accumulator が更新され、最後の値 24 が戻り値になります

各ステップで accumulator が更新され、最後の値 24 が戻り値になります。

Python での実装

Python には functools.reduce がありますが、ここでは原理を見せるために for ループで書きます。

Python

def product(nums):
    result = 1
    for n in nums:
        result *= n
    return result

functools.reduce(lambda acc, n: acc * n, nums, 1) と書いても同じ結果です。初期値 1 を忘れずに渡すこと。空配列のときに 1 を返してくれるのは初期値があるからです。

JavaScript での実装

JavaScript

function product(nums) {
  return nums.reduce((acc, n) => acc * n, 1);
}

JS の Array.prototype.reduce は標準装備です。第 2 引数の 1 が初期値で、これを書かないと空配列のときにエラーになります。

和との対応

和 を求めるなら初期値 0、関数 (acc, n) => acc + n を使います。初期値は演算の単位元 を選ぶのが基本。加法なら 0、乗法なら 1、最大値なら -Infinity、最小値なら Infinity です。畳み込み の世界では、この 単位元 の選択がきれいに揃います。

reduce の初期値は その演算の単位元 を選ぶ。和なら 0、積なら 1。これを覚えれば応用が利く。

計算量と注意点

計算量は配列を 1 周するだけなので O(n) です。ただし 積はあっという間にオーバーフローする 点に注意。[10, 10, 10, 10, 10] で 10^5、要素が 20 個もあれば 32bit 整数を超えます。Python は任意精度なので大丈夫ですが、Java の int や Go の int32 だと簡単にオーバーフローします。本レッスンではテストケースを小さい値に絞っているので問題ありませんが、実用では BigInteger や int64 を使うのが安全です。

Python

# functools 版
from functools import reduce
result = reduce(lambda acc, n: acc * n, [1, 2, 3, 4], 1)

早期終了の工夫

配列に 0 が含まれている場合、結果は必ず 0 になります。これを使うと 0 を見つけた瞬間にループを抜ける という最適化が可能です。

Python

def product(nums):
    result = 1
    for n in nums:
        if n == 0:
            return 0
        result *= n
    return result

ただし、純粋な reduce パラダイムでは早期終了が書きにくいというデメリットもあります。関数型一辺倒 ではなく、状況に応じて for ループを選ぶ柔軟性も大切です。

map / filter / reduce の関係

面白いことに、map と filter はどちらも reduce で実装できます。map は「結果配列に変換した値を追加していく reduce」、filter は「条件を満たすときだけ追加していく reduce」です。reduce はもっとも汎用性が高く、三種の神器の親玉 という位置づけです。

reduce は 汎用集計の親玉。map と filter も reduce の特殊形と捉えられる。

よくある間違い

1 つ目は 初期値を忘れる ことです。JS の reduce は初期値なしだと配列の先頭要素を初期値にしてしまい、空配列ではエラーになります。2 つ目は 空配列で 0 を返す こと。乗法の単位元は 1 なので、空配列でも 1 を返すのが数学的に整合します。3 つ目は オーバーフロー を考えない実装。値が大きくなる可能性がある場合は型を意識する。

やってみよう

関数を sum に書き換え、和 を返すようにしてみる。初期値を 0 に、演算を + に変えるだけ。
配列の 最大値 を reduce で書いてみる。初期値は -Infinity (JS) や float("-inf") (Python)。
reduce を使って文字列配列を連結してみる。初期値は "" で関数は (acc, s) => acc + s。

reduce が書ければ、for で書く集計処理の 9 割は短く書ける。map filter reduce の三種の神器を 自然に組み合わせる のが関数型の入り口。

よくある質問

Q. reduce はどんなときに使うべきですか？

A. 合計・最大値・グルーピングなど、配列を 1 つの値や別の構造にまとめたいときに有効です。単純な合計なら sum / Array.prototype.reduce((a,b)=>a+b,0) で OK ですが、複雑なロジックでは for ループの方が読みやすいこともあります。

Q. 初期値は省略しても良いですか？

A. 省略すると配列の先頭要素が初期値になり、空配列のときに TypeError になります。明示的に 0 や [] を渡しておくと安全で、型推論にも優しくなります。可読性と安全性の両面から初期値は付ける派が多数です。

Q. reduce でオブジェクトを作るには？

A. items.reduce((acc, x) => ({ ...acc, [x.id]: x }), {}) のように初期値に {} を渡し、各反復で展開構文を使います。要素数が多い場合は scatter で性能劣化するため、acc[x.id] = x; return acc; のように mutate する形も検討してください。

次のレッスン

次は 関数合成 で、配列の全要素を reduce (畳み込み) で 1 つの値にまとめるを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

reduce で積の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. reduce で積とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

reduce で積を計算