Javascript で塗り分け問題を解いてみる (4)

前回で総当たり方式についてコードを一般化出来たところで、今度はこれに枝刈りを導入して動作の効率化を図る。

枝刈りというのは、要は全てのタイルの色を設定した後で全ての条件に合致するかを判断するのではなく、1枚ずつタイルの色を設定しながら、現時点で条件を満たさないことが判明したらその先の試行をやめて違う組み合わせを試すというものになる。

そのためには、それぞれの条件に対して判断に必要なタイルを明記する必要がある。

        var Colors = ['red', 'blue', 'green', 'yellow'];
        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            { require: [tile1, tile2], func: function() { return tile1.selected != tile2.selected; } },
            { require: [tile1, tile3], func: function() { return tile1.selected != tile3.selected; } },
            { require: [tile1, tile4], func: function() { return tile1.selected != tile4.selected; } },
            { require: [tile1, tile5], func: function() { return tile1.selected != tile5.selected; } },
            { require: [tile2, tile3], func: function() { return tile2.selected != tile3.selected; } },
            { require: [tile3, tile5], func: function() { return tile3.selected != tile5.selected; } },
            { require: [tile4, tile5], func: function() { return tile4.selected != tile5.selected; } },
            { require: [tile4, tile2], func: function() { return tile4.selected != tile2.selected; } }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

各条件を判定するときには、require で示されたタイルの色が設定されているかをチェックして、設定されていない場合は undefined を返すようにする。

        function checkOne(question, cond) {
            var i;
            for(i = 0; i < cond.require.length; i++) {
                if(cond.require[i].selected === undefined) {
                    return undefined;
                }
            }
            return cond.func();
        }

あとは、
複数の条件のうち、一つでも条件を満たさない場合はその先の試行は行わない。
全ての条件を満たせばそれが回答の一つになる。
それ以外(undefinedが混じる場合)は次のタイルの色を設定してもう一度条件を確認する。
というのを行っていけばよい。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                result = check(question, conditions);
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.selected; }));
                }
            });
            question[iter].selected = undefined;
            return answer;
        }

        function check(question, conditions) {
            var i,
                tmp,
                result = true;
            for(i = 0; i < conditions.length; i++) {
                tmp = checkOne(question, conditions[i]);
                if(tmp === false) return false;
                else if(tmp === undefined) result = undefined;
            }
            return result;
        }

こうすれば、メンテナンス性を維持しつつも、枝刈りにより高速に処理が出来る。

check や checkOne の戻り値をチェックして処理内容を変えるところなんかは、関数型言語で勉強したモナド的なやり方を導入するともう少しスマートに書けそうな気がするのだが、一からモナドを設計するのは自分の脳みそじゃ無理そうだ。

塗り分け問題を JavaScript で書いてみた結論としては、

　　prologで良いじゃん

の一言に尽きる。

というか、prolog 向きの問題だと言うことはハナからわかっていたが、JavaScript で書いたらもう少しオブジェクト指向的なアプローチが出来るかなと思って色々試行錯誤してみたのたが、結局は一般化しようとしたら prolog っぽい書き方をするのが一番良いよねということになってしまった。
強いて言えば、require と selected をもう少しスマートに表現できるようにしたかったなぁ。

まあ、こんなことは先人たちがさんざん試してるので今更なんだろうが、勉強には良いよね。

Javascript で塗り分け問題を解いてみる (3)

前回は効率性を重視するあまりメンテナンス性がおろそかになってしまった。
メンテナンス性を良くするために、解き方はもとの総当たりに戻すとして、一旦命題を整理してみる。

今回の命題を言葉で書くと
「タイル1～5までの5枚のタイルがある」
「それぞれのタイルには赤、青、緑、黄のどれかの色が塗られる」
「"条件"に合致するタイルの色の組み合わせは何か」
のということになる。

これをそのままコードで書くとこのように書ける。

        var Colors = ['red', 'blue', 'green', 'yellow'];

        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            function() { return tile1.selected != tile2.selected; },
            function() { return tile1.selected != tile3.selected; },
            function() { return tile1.selected != tile4.selected; },
            function() { return tile1.selected != tile5.selected; },
            function() { return tile2.selected != tile3.selected; },
            function() { return tile3.selected != tile5.selected; },
            function() { return tile4.selected != tile5.selected; },
            function() { return tile4.selected != tile2.selected; }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

命題をコードで書けるのなら、それをそのまま解けば良い。

        function solve(question, conditions, iter) {
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) {
                if(conditions.every(function(condition) { return condition(); })) {
                    return [question.map(function(tile) { return tile.selected; })];
                }
                return [];
            }
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                answer = answer.concat(solve(question, conditions, iter+1));
            });
            return answer;
        }

        var Answer = solve(Question, Conditions);

さらっと無茶なことをやっているようにも見えるが、実際は question で与えられた tile1 ～ tile5 に対して再起を使って candidate の全ての組み合わせを総当たりで試しているだけ。

こうしてしまえば、タイルの数が増えようが、条件が変わろうが容易に対応できる。

Javascript で塗り分け問題を解いてみる (2)

前回の続き。

さすがに総当たりだと単純すぎるので、いわゆる枝刈りして余計な試行を削っていく。

var colors = ['red', 'blue', 'green', 'yellow'];

colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        if(tile1 != tile2) {
            colors.forEach(function(tile3) {
                if(tile1 != tile3 && tile2 != tile3) {
                    colors.forEach(function(tile4) {
                        if(tile1 != tile4 && tile3 != tile4) {
                            colors.forEach(function(tile5) {
                                if(tile1 != tile5 && tile4 != tile5 && tile2 != tile5) {
                                    document.write(tile1+', '
                                        +tile2+', '
                                        +tile3+', '
                                        +tile4+', '
                                        +tile5+'<br>');
                                }
                            });
                        }
                    });
                }
            });
        }
    });
});

たしかにこれで速くはなるのだが、いかんせんメンテナンス性がすこぶる悪い。
タイルを一枚増やしたり、条件を変更しようとするとあっちゃこっちゃ変えなくちゃならない。

Javascript で塗り分け問題を解いてみる (1)

以前なんかで見かけて、暇があったら勉強がてら JavaScript で書いてみようと思っていたプログラム。
いわゆる塗り分け問題で、細かいところは覚えていないが、とりあえず適当に下のような5枚のタイルを同じ色が隣接しないように赤青黄緑の4色で塗り分ける問題を解いてみる。

まずは何も考えずに愚直に書くとこうなる

var colors = ['red', 'blue', 'green', 'yellow'];

var i, j, k, l, m;
var tile1, tile2, tile3, tile4, tile5;
for(i = 0; i < colors.length; i++) {
    tile1 = colors[i];
    for(j = 0; j < colors.length; j++) {
        tile2 = colors[j];
        for(k = 0; k < colors.length; k++) {
            tile3 = colors[k];
            for(l = 0; l < colors.length; l++) {
                tile4 = colors[l];
                for(m = 0; m < colors.length; m++) {
                    tile5 = colors[m];
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                }
            }
        }
    }
}

これでも解けることは解けるが、タイル数(N)が増えると試行回数が4(色数)のN乗で増えていくので、こんなんを大学の専攻のレポートで提出したら確実に赤点食らうだろう。

蛇足だが、forEachを使うと若干シンプルに書ける。

var colors = ['red', 'blue', 'green', 'yellow'];
var begin = Date.now();
colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        colors.forEach(function(tile3) {
            colors.forEach(function(tile4) {
                colors.forEach(function(tile5) {
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                });
            });
        });
    });
});

もっとも、シンプルに書けるだけで中身は変わらないので、まともにしようと思ったら工夫が必要になる。

GUI と DVFS

最近のプロセッサなら大抵は動作電圧と動作周波数を変更する機能が付いている。
OS は負荷が低いときは CPU の電圧と周波数を落とすことで消費電力を抑えることが出来る。
ってのが教科書的な DVFS の概略。

スマートフォンの場合は、何もせずにホーム画面を表示しているだけだと裏で何か処理をしていない限り基本的には何も処理していないので、負荷が一番低い＝動作周波数が一番低い状態にある。

この状態で指で画面を横にスワイプすると、スワイプのアニメーション処理が走るため一気に負荷が上昇する。
最近の周波数マネージャがどうなっているか知らないが、一昔前の OS の周波数制御は非常に単純だったので、負荷が閾値を超えたら動作周波数と電圧を一段階上げて、それでもまだ負荷が高ければもう一段階あげて・・・とやっていくため、周波数が上がりきるまでに時間がかかっていた。

といっても影響があるのは最初の１～２フレーム程度なのだが、これが触ったときのちょっとした引っかかりの一因になる。
しかも、皮肉なことに周波数変更の刻みが細かい高価なプロセッサほどこれによる遅延が大きく、逆に中華製の安価なプロセッサの方が変更回数が少ない分、周波数の上がりが早くて、うまくはまると中華製の安価タブレットの方が下手な国産高級タブよりもタッチの反応が良かったりするケースもあった。

もともと GUI のような応答性重視で短時間で終わるような処理ってのは DVFS との相性は良くない。
とはいえ、制御工学で言うところのインパルス応答性の改善ってのと根っこは同じでやりようはあると思うので、最近の OS ならだいぶマシになっているはず、だと思う、と信じたい。
（個人的には本気でレスポンスを良くしたければ周波数を細かく設定できるようにするよりも、周波数は2段階だけで、その代わり周波数の切り替えを早くして、短時間でもやることが無ければ最低周波数、ちょっとでも処理するときは最大周波数と言った具合に on/off をこまめに切り替えられる方に注力した方が良いと思ってるんだが）

で、最近オクタコアなる CPUコア を8個も搭載したあほみたいなプロセッサが出てきた。といっても8個同時に使えるわけでは無く、いわゆる Big-Little とかいう技術で内部的には4コアの低速なプロセッサと4コアの高速なプロセッサが入っていて、軽い処理なら低速だが消費電力の少ない方のプロセッサで、重い処理の場合は消費電力は大きいが高速なプロセッサでといった具合に状況に応じて適した方を切り替えて使うそうだ。

さて、これで GUI 処理を行ったらどうなるだろうか。
先ほどのようにただ画面を表示しているだけの状態ならおそらく低速なプロセッサを最低周波数で動かすようにするのが普通だ。そこからスワイプにより一気に負荷が上昇すると、昔のアホな周波数制御なら一段階ずつ周波数を上げていくことになる。所詮GUIなんてたいしたことはやらないので、低速なプロセッサで最大値まで周波数を上げたところで負荷が落ち着いてくれれば良いが、まだ負荷が高ければ今度は高速な方のプロセッサに切り替わる羽目になる。メーカー曰くプロセッサの切り替えは高速に出来るそうだが、普通に考えるとそれでも周波数を切り替えるよりは遙かに時間がかかるだろうから、こんなことをやられると GUI の応答性能的にはグッダグダになることが容易に予想できる。

いくらでも回避方法はあると思うが、この手のやつは原因を見極めずに小手先の対応を積み重ねていくとどんどんドツボにはまってくで、その辺最近のはどうなってんだろうかと、最近出たオクタコア搭載スマフォがいまいちだという話を聞いてちょっと気になった。

Atom の remote-ftp が動かない

最近 Atom ってエディタが流行ってるので、職場でも Sublime から乗り換えてみた。

Sublime の時に重宝していた SFTP と同等のことが remote-ftp で出来るって言うんで早速導入してみたが、"Error: Timed out while waiting for handshake" ってエラーが出て動かない。

ググってもなかなか情報が無いのでソースコード見たりサーバーのログ見たりと色々と試行錯誤した結果、コンフィグファイルの connTimeout を 99999 に設定したら無事に繋がった。

どうも接続タイムアウトのデフォルト(10000、10秒?)が短すぎたらしいのだが、それなら一言 "Connection timeout" って言ってくれればすぐにわかったんだがなー
（とはいえ、このメッセージ出してるのはSSHのライブラリの方なので remote-ftp の作者さんに非は無いのかもしれんが）

ただまあ、社内ネットで接続に10秒以上かかるってのも変な話だし、サーバー側のログ見るとSSHの認証は通ってるっぽいし、普通にSSHでログインしている感覚からするとあれに10秒もかかっているように思えんし、なんかどっかで変なバグでも踏んでんのかな

Mongoose の autoreconnect が動かない

やったことのメモ

Mongoose には自動再接続の機能があるらしいのだが思ったように動かない。

とりあえず connection の connected, disconnected, reconnected イベントを拾ってログを出すようにしてみたら、１回目の再接続時はきちんと disconnected → connected のイベントが出ていたが、2回目以降は disconnected は発生せずに reconnected だけ発生していた。

さらにややこしいのが一度でもデータベースに save をするとどのイベントも発生しなくなる（厳密には拾い方が変わるのかもしれんが）。readyState も変わらないのでどうしようも無い。

こちらのイベント処理が悪いのかと思って、autoreconnect を信じて全てのイベント処理を外してみても駄目。

バグなのか仕様なのか自分の使い方が悪いのかはわからんが、色々試行錯誤した結果以下のように save のコールバックで失敗した書き込みをキューイングして再接続させるようにしたらうまく動いた。

mongoose.connect(dbURI);

// 送信失敗したデータを溜めるためのキュー
var instQueue = [];
var connecting = false;

function saveInst(inst) {
  inst.save( function(err) {
    if(err) {
      console.log('save failed');
      instQueue.push(inst);
      if(connecting) {
        connecting = true;
        mongoose.connect(dbURI, function(err) {
          connecting = false;
          // 接続に成功したら溜まっているキューを save
          if(!err && instQueue.length > 0) {
            saveInst(instQueue.shift());
          }
        });
      }
    } else {
      console.log('saved');
      // キューが溜まっていれば残りも save
      if(instQueue.length > 0) {
        saveInst(instQueue.shift());
      }
    }
}

connect 中にもう一回 connect するとエラーになるので connecting フラグを使って多重コネクトを行わないように管理していたが、自前でフラグを作らずに readyState を見ても良かったかもしれない。

今回は定期的に吐かれるログを保存するためのスクリプトだったので接続に失敗してもキューに突っ込んでおいて次回リトライできるが、そうでない場合は setTimeout 等を使って手動で connection を何度もリトライする必要が出てくる。

でもそれホントは autoreconnect の仕組みがやってくれるはずなんだよね・・・