Node.jsを競技プログラミングの知識を使って6時間くらいで理解する

概要

Node.jsが面白い言語構造をしているっぽかったので勉強しました。その過程で、割と競技プログラミングの経験が役に立ったので共有します。僕はC++ネイティブなので、かなり違うマインドセットが必要でした。C++をやっている人は、恐らくこの記事のような理解を介すことになるでしょう。

ほんま初心者なので、間違ってたら言ってください。電脳世界を汚さないためにも。

理解のために使ったサンプルプログラムはこちら

はむこのNode.jsの理解

「入力Aに対して、出力Bを返す」というオンラインクエリを$q$個、シングルスレッドで最低限の遅延で大量に処理したい。そのためには、関数 $f: S \rightarrow T$ を「Sを入力したらTを返す」という通常の関数で実装するのは不適切である。なぜなら、関数fがブロッキングI/Oを必要とする場合、CPUのアイドルタイムが発生するからである。CPUのアイドルタイムを少なくするために、ノンブロッキングI/Oを基本としたシステムを組みたい。このようなシステムをC++で組む場合、どうすればよいだろうか?

一般にノンブロッキングI/Oでは当然、結果が返ってくるかはわからないので次の処理ができないはずだ。最悪、例外が投げられてくることもある。したがって、関数に「まだ準備出来ていないデータ」が入力される可能性があり、従来型の関数の範疇を超える。

どうすればよいか?関数 $f : S \rightarrow T$ はもはや通常の関数ではなく、$S$を入力したら$T$を出力するという「約束=プロミス(Promise)」を基本単位とする。プロミス$y = f(x_1, ..., x_n)$を考える。プロミス$f$が$y$を計算するためには、全ての$x_i$が「準備完了である」必要がある。ノンブロッキングI/Oを前提としているため、常には準備完了ではない。しかしいつかは、全てのデータ$x_i$が準備完了となるはずである。このときはじめてプロミス$f$は具体的に$y$を計算する。そして、$y$の準備完了を待っている他のプロミスが、計算を始めるための糧となるのである。

ここで、プロミスが$m$個あることを想定しよう。このようなシステムを組むためには、プロミス$f_i$全てを常に監視し続けなければならないことが理解できるはずだ。なぜならば、プロミス$f_i$が依存する全変数について、「準備完了である」フラグが立っていることを検証しなければプロミス$f_i$の中にプログラムポインタを入れてよいかがわからないからである。ここで、プロミスを全て突っ込んだsetを想定し、未完了のプロミスがある限り全プロミスの引数の準備完了フラグを監視し続けるループを回し続けることを考えよう。

大局的にはループを回し続けているだけが、局所的な視点に立ってみよう。すなわちプロミス側の立場に立ってみると、高速に監視ループが回っているため、非常に短期間で自分にプログラムポインタが回ってくる。したがって、変数が準備完了になったというイベントは、ほぼタイムロスなく検知することができる。このことから、「変数が準備完了になったら関数を具体的に計算し、後段のプロミスにデータを渡す」(これをresolveという)ということを保証するだけで良いことがわかる。

系全体には、イベントドリブンに入力が与えられる。その入力に対応する目的の計算結果を求めるために、プロミスのネットワークを設計しなければいけない。ネットワークはグラフ構造としてモデル化できることを考えよう。グラフ構造の辺はデータ$x_i$であり、辺はプロミス$f$とみなす。このようなプロミスのグラフ構造は、計算が停止するために依存関係はループしてはいけない。すなわち、プロミスが成すグラフ構造はDAGを成す(プロミスDAGと呼ぼう)。

プロミスDAGにおいて、プロミスの結果が色々な場所で使われうることを考えると、全ての頂点は多入次数多出次数を持つ。では、多入次数・多出次数のグラフ構築を行うためのプログラムのシンタックスはなんだろうか?

プロミスDAGとnode.jsのasync/await

プロミスの定義

async function echoNumber(n) { console.log(n + "#number"); return n; } |
// console.log(echoNumber(2)); // 何か出力されるけどこれはバグ!この時点でプロミスが解消されているとは限らない。 |

通常の関数のように定義する。注意すべきことは、この関数を呼ぶだけではPromiseオブジェクトが返ってくるだけで、準備完了かどうかは不明であり、動作は不明となることである!

プロミスDAGの結果をメインループで取得

プロミスDAGはただのイベントドリブンに結果を計算するが、その出力をどうするかはプロミスの空間に限られている。出力結果をそのままクライアントに送り返せばそれで終わりだから、メインループのプログラムポインタと無関係でありえるからである。

しかし、これではデバッグも何もできたものではないので、プロミスの出力をメインループで取得するシンタックスを考えよう。結論、これは以下のようにthen関数で無名関数を与えることでできる。この無名関数には、プロミスが準備完了になったときに入る。無名関数の引数は1つであり、プロミスがresolveした値を受け取ることができる。

async function echoNumber(n) { console.log(n + "#number"); return n; } |
echoNumber(3).then(v=>{console.log(v);}); // asyncはプロミスを返すので、thenで簡易async関数内awaitができる。 |

多入次数プロミス

以下のようにすることで、固定入次数のプロミスを組める。awaitは、その後のものを準備完了にするという意味である。ここで、plusの3つはDAG上で完全に並列した形になっている。(この実装はあまりよくなくて、twoの計算にoneの計算が依存した形になっている)

    async function plus(x, y) { return x + y; }
    async function multiplyTwo(n) { return n * 2; }
    async function exec() {
        var one = plus(0, 1);
        var two = plus(0, 2);
        var three = plus(0, 3);
        one = await multiplyTwo(await one);
        two = await multiplyTwo(await two);
        three = await multiplyTwo(await three);
        return one + two + three;
        console.log(one + two + three + "#test 2");
    }
    exec().then(v=>{console.log(v + "#test 2"); });

多出次数プロミス

awaitした値を複数のプロミスの引数に突っ込めば良い。

まとめ

Node.jsはDAG構築ゲー

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.