Node.jsデザインパターン 第2版

9.3

 

CPU

バウンドなタスクの実行

315

9.3.1

 部分和問題の解法

対象として計算量の大きい「部分和問題」を使いましょう。ある整数の集合（あるいは「多重集合」）が、

要素の和がゼロになるような空でない部分集合を含むかどうかを判定する問題です。たとえば、集合

[1, 2, –4, 5, –3]

を与えられた場合、

[1, 2, –3]

と

[2, –4, 5, –3]

がこの条件を満たすことになります。

もっとも単純なアルゴリズムは、すべての大きさの部分集合の可能な組み合わせをチェックするもの

で、計算量は

O

(2

n

)

となり、言い換えれば入力の大きさに従って指数関数的に増加します。つまり要

素

20

個の集合では

1,048,576

個にのぼる組み合わせをチェックする必要があり、我々の仮定をテストす

るのにおあつらえ向きです。もちろん、全部チェックする前に解答が見つかるかもしれませんから、難

易度を上げるために問題を

次のように設定します。「与えられた整数の集合について、合計が指定され

た数になるような要素の組み合わせをすべて求めよ」

それではそのようなアルゴリズムを構築していきましょう。

subsetSum.js

という名前の新たなモ

ジュールを作成します。

SubsetSum

という名前のクラスの作成から始めましょう（

04_cpu_bound

）。

const EventEmitter = require('events').EventEmitter;

class SubsetSum extends EventEmitter ...