@blog.justoneplanet.info

日々勉強

node.jsでbasic認証を使ってhttps接続する

nodeのバグを踏んだりしてたら4時間かかってしまったのでメモしておく。

■HTTP接続

以下のようにしてHTTPクライアントを生成し、ホストに接続することができる。

var host   = 'www.example.com';
var header = {"Host": host};
var client = http.createClient(
    80,
    host,
    false,
    false
).
client.request(
    "GET",
    "/",
    header
);

createClienetはどうやら廃止される方向らしいので以下のように書きなおす。

var http = require('http');
var host = 'www.example.com';
var req  = http.get(
    {
        "host"  : host,
        "port"  : 80,
        "path"  : "/"
    },
    function(res) {
        console.log("Got response: " + res.statusCode);
    }
);
req.on('error', function(e){
    console.log(e);
})

■Basic認証+HTTP接続

以下のようにしてHTTPクライアントを生成し、ホストに接続することができる。

var username = 'hoge';
var password = 'fuga';
var auth     = 'Basic ' + new Buffer(username + ':' + password).toString('base64');
var host     = 'www.example.com';
var header   = {
    "Host"          : host,
    "Authorization" : auth
};
var client   = http.createClient(
    80,
    host,
    false,
    false
).
client.request(
    "GET",
    "/",
    header
);

createClienetはどうやら廃止される方向らしいので以下のように書きなおす。

var http = require('http');
var host = 'www.example.com';
var req  = http.get(
    {
        "host"  : host,
        "port"  : 80,
        "path"  : "/",
        "auth"  : "username:password"
    },
    function(res) {
        console.log("Got response: " + res.statusCode);
    }
);
req.on('error', function(e){
    console.log(e);
})

■Basic認証+HTTPS接続

失敗例

以下のようにしてHTTPSクライアントを生成しても、ホストに接続することはできない。

var username = 'hoge';
var password = 'fuga';
var auth     = 'Basic ' + new Buffer(username + ':' + password).toString('base64');
var host     = 'www.example.com';
var header   = {
    "Host"          : host,
    "Authorization" : auth
};
var client   = http.createClient(
    443,
    host,
    true,
    false
).
client.request(
    "GET",
    "/",
    header
);

実行してもエラーがでる。

参考

上述のように失敗するのでhttpsモジュールを使う。

■Basic認証+HTTPS接続

以下のようにすることで、HTTPSクライアントでBasic認証を使うことができる。

var https    = require('https');
var host     = 'www.example.com';
var username = 'hoge';
var password = 'fuga';
var auth     = 'Basic ' + new Buffer(username + ':' + password).toString('base64');
var options  = {
    "host"          : host,
    "port"          : 443,
    "path"          : '/',
    "method"        : 'GET',
    "Authorization" : auth
};
var request = https.request(
    options,
    function(response) {
        console.log("statusCode: ", response.statusCode);
        console.log("headers: ", response.headers);
    }
);
request["_headers"]["Authorization"]     = auth;// ...(a)
request["_headerNames"]["Authorization"] = 'Authorization';// ...(b)
request.end();

optionsにAuthorizationをセットするだけではBasic認証が成功しなかった。認証用のヘッダが正しく付加されるように、強引に(a)と(b)を加えた。

参考

■後述

現在のnodeのバージョンでは以下のようにして簡単にhttpsでBasic認証を行うことができた。

var http = require('https');
var host = 'www.example.com';
var req  = http.get(
    {
        "host"  : host,
        "port"  : 443,
        "path"  : "/",
        "auth"  : "username:password"
    },
    function(res) {
        console.log("Got response: " + res.statusCode);
    }
);
req.on('error', function(e){
    console.log(e);
})

参考

Goolge Developer Day 2011のWeb Gameを解いてみる

Extensionとか入れたりするの面倒なので以下のJavaScriptをコンソールに打ち込む。

var ary = [];
for(var i = 0; i < 1024; i++){
    if($('card' + i)){
        $('#card' + i).click();
        ary.push($('#card' + i).css('backgroundColor'));
    }
}
ary.forEach(function(elm, i1, ary){
    for(var i2 = i1 + 1; i2 < ary.length; i2++){
        if(ary[i1] == ary[i2]){
            $('#card' + i1).click();
            $('#card' + i2).click();
        }
    }
});

WebSocket Serverまとめ

Chrome 14からWebSocketプロトコルのバージョンがdraft 10になる。現在、Chrome 13はdraft 76で実装されておりdraft 76とdraft 10は互換性がない。WebSocketを使った既存のサービスは壊れるのでdraft 10で実装されたWebSocketServerを探しときの情報をまとめた。

New WebSocket Protocol: Secure and Extensible

Please note that the new protocol is incompatible with one which Chromium previously supported (draft-ietf-hybi-thewebsocketprotocol-00),
so existing WebSocket-based services may break.
Please upgrade your servers to ones which support HyBi 10.
Existing JavaScript code still works once the protocol version used by the browser and server match.

新しいプロトコルは非互換でなので既存のWebSocketをベースとしたサービスは壊れる。HyBi 10をサポートするようにサーバをアップグレードしてくれ。既存のJavaScriptコードはプロトコルのバージョンが合致すれば動作するだろう。

WebSocket-Node

A WebSocket Draft -08/-09/-10 Implementation for Node.JS

いけちゃうっぽい!broadcastメソッドが存在しないようだが、以下のようにbroadcastメソッドを実装することにした。

var WebSocketServer = require('websocket').server;
WebSocketServer.prototype.broadcastUTF = function(data){
    this.connections.forEach(function(connection, i, ary){
        connection.sendUTF(data);
    });
};

作者の方にも気に入って頂けたようなので近いうちにモジュールに組み込まれるかもしれない。

インストール

npm install websocket

実装

以下のようにしてWebSocketサーバをセットアップした。

/**
 * extend default WebSocketServer for broadcast
 */
var WebSocketServer = require('websocket').server;
WebSocketServer.prototype.broadcastUTF = function(data){
    this.connections.forEach(function(connection, i, ary){
        connection.sendUTF(data);
    });
};

/**
 * websocket server for end users
 */
var server = require('http').createServer(
    function(request, response) {
        console.log((new Date()) + " Received request for " + request.url);
        response.writeHead(404);
        response.end();
    }
);
server.listen(
    eew.env['port'],
    function() {
        console.log((new Date()) + " Server is listening on port 80");
    }
);

wsServer = new WebSocketServer({
    "httpServer"            : server,
    "autoAcceptConnections" : true
});

wsServer.on(
    'connect',
    function(connection){
        console.log((new Date()) + " Connection accepted.");
        connection.sendUTF('{"status" : "accepted"}');
    }
);

broadcastUTFメソッドを自作した以外は殆どサンプルコードと変わらない。

■Support draft-10 (chrome 14-dev+)

node.jsには何種類かWebSocket Serverの実装がある。

This will either be done
via node-websocket-protocol (preferable), or
via some kind of hack to the core of node-websocket-server, which is the route I really don’t want to take.

どうやらプロトコルだけ外に出してモジュール化することで対応する意向らしい。しかし、レスポンスが遅いのが気になる。

Socket IO

hybi10 incompatibility

軽く読んだ限りでは最新の仕様では不具合が発生するようだ。ロングポールなど代替手段が揃っているので有用な選択肢ではある。但し、今回はクライアント側のコードを変更したくないので選択肢から外した。

追記:8/30動作するようになった模様。

pywebsocket

node.js用のモジュールが存在しなければ、他の言語のモジュールで対応するという選択肢も考えた。pywebsocketではdraft-ietf-hybi-thewebsocketprotocol-07まで対応している。

Jetty

Jetty has supported the various WebSocket drafts in the 7.x and 8.x releases.

どうやら最新の実装には対応していないようだ。

■参考

The WebSocket protocol

draft-ietf-hybi-thewebsocketprotocol-10

Comparison table of websocket server implementations.

WebSocketサーバの実装が比較されているが更新されていないっぽい。

■まとめ

バージョンは適宜アップデートされるだろう。node.jsを選んで良かった。

後述

Socket.IOをインストールする

■node.js

以前の記事にも書いたんだけど以下のようにしてインストールできる。

su
yum install openssl-devel gcc-c++ git make
git clone git://github.com/creationix/nvm.git ~/.nvm
source ~/.nvm/nvm.sh
echo "~/.nvm/nvm.sh" >> ~/.bash_profile
echo "nvm use v0.5.0" >> ~/.bash_profile
nvm sync
nvm install v0.5.0
npm install node-base64

でも使い勝手に慣れなくて結局ソースからビルドしてしまったり。

■Socket.IO

以下のコマンドでインストールできる。

npm install socket.io

まぁ、一瞬で終わる。

使ってみる

サーバ側
var io = require('socket.io').listen(80);
io.sockets.on(
    'connection',// 接続された時
    function(socket){// 引数に接続(socket)をセットしてコールバックが実行される
        socket.on(
            'disconnect',
            function () {
                io.sockets.emit('message', 'hogehoge');// 全員にpushされる
            }
        );
    }
);

socketのbroadcastメソッドは接続している以外の全てのクライアントに対してpushされる。

クライアント側

サーバを起動させるとクライアント側で読み込むべきscriptが特定の位置に展開される。楽といえば楽。

<script type="text/javascript" src="http://127.0.0.1:80/socket.io/socket.io.js"></script>
<script type="text/javascript">
var socket = io.connect('http://127.0.0.1:80');
socket.on(
    'message',
    function (data) {
        console.log(data);
    }
);
</script>

JavaScriptでプリム法

重み付き無向グラフの最小全域木を求めるアルゴリズム。任意の辺から始めて全頂点を覆うまで連続的に木の大きさを拡大し、全ての辺の重みの総和が最小となる経路を求める。

■実装

以下のように実装した。

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var v0 = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
v0.appendNeighbor(
    {"vertex" : v1, "weight" : 2},
    {"vertex" : v3, "weight" : 8},
    {"vertex" : v4, "weight" : 4}
);
v1.appendNeighbor(
    {"vertex" : v0, "weight" : 2},
    {"vertex" : v2, "weight" : 3}
);
v2.appendNeighbor(
    {"vertex" : v1, "weight" : 3},
    {"vertex" : v4, "weight" : 1},
    {"vertex" : v3, "weight" : 5}
);
v3.appendNeighbor(
    {"vertex" : v2, "weight" : 5},
    {"vertex" : v4, "weight" : 7},
    {"vertex" : v0, "weight" : 8}
);
v4.appendNeighbor(
    {"vertex" : v2, "weight" : 1},
    {"vertex" : v3, "weight" : 7},
    {"vertex" : v0, "weight" : 4}
);
var V = [v0, v1, v2, v3, v4];

// initialize
var key  = [];
var pred = [];
for(var i = 0; i < V.length; i++){
    key[V[i]['value']]  = Number.POSITIVE_INFINITY;
    pred[V[i]['value']] = -1;
}
key[0] = 0;// 任意の1頂点をスタート地点とするため優先度を0にする
var bh = new BinaryHeap();
for(var i = 0; i < V.length; i++){
    // 頂点を優先度付きキューに格納
    bh.insert(V[i], key[V[i]['value']]);
}

// calc
while(bh.getList().length > 0){
    var u = bh.getPrior();// 優先度で先頭にくる頂点を取り出す
    for(var i = 0; i < u['neighbor'].length; i++){// 経路が存在している頂点でループ
        var neighbor = u['neighbor'][i]['vertex'];
        // 頂点(a)がキューに存在している場合
        if(bh.inQueue(neighbor)){
            var weight = u['neighbor'][i]['weight'];
            // かつ頂点(a)まで距離が前回のループまでに到達した距離よりも短い場合
            if(weight < key[neighbor['value']]){
                pred[neighbor['value']] = u['value'];// 頂点を配列に格納
                key[neighbor['value']]  = weight;// 距離を配列に格納
                bh.changePriority(neighbor, weight);// 優先度を更新(キューの先頭に近づく)
            }
        }
    }
}

// result
console.log("key:");
console.log(key);
console.log("pred:");
console.log(pred);

結果

最小全域木の距離の総和は以下を足した値となる。

0 2 3 5 1

計算時に辿った経路は以下のようになる。

-1 0 1 2 2

優先度付きキュー

以前の記事で使用したコードにメソッドを追記して使用した。

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }

        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * 要素をヒープに追加する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * 要素の優先度を変更する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 * 優先度の高い要素を取得する
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 * ヒープを返す
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

/**
 * BinaryHeap::inQueue
 * ヒープ内で探索
 */
BinaryHeap.prototype.inQueue = function(v){
    var self = this;
    for(var i = 0; i < self._ary.length; i++){
        if(self._ary[i]['elm'] === v){
            return true;
        }
    }
    return false;
}

inQueueメッソドを効率よくできないかな・・・(●´⌓`●)

three.jsを通してWebGLを使う


※Google Chrome以外のブラウザでは正確に表示されない部分があります。

■サンプルコード

サンプルコードを大体そのまま動かしながらコードを理解してみる。

(function(){
    var camera, scene, renderer,
    geometry, material, mesh;
    init();
    animate();
    function init() {
        camera = new THREE.Camera(75, window.innerWidth / window.innerHeight, 1, 10000);
        camera.position.z = 1000;
        scene = new THREE.Scene();
        geometry = new THREE.Cube(200, 200, 200 );
        material = new THREE.MeshBasicMaterial({color: 0xff0000, wireframe: true});
        mesh = new THREE.Mesh(geometry, material);
        scene.addObject(mesh);
        var canvas = document.getElementById('canvas2011030601');
        renderer = new THREE.CanvasRenderer();
        renderer.setSize(canvas.offsetWidth, 300);
        canvas.appendChild(renderer.domElement);
    }
    function animate() {
        // Include examples/js/RequestAnimationFrame.js for cross-browser compatibility.
        requestAnimationFrame(animate);
        render();
    }
    function render() {
        mesh.rotation.x += 0.01;
        mesh.rotation.y += 0.02;
        renderer.render(scene, camera);
    }
})();

CanvasRendererとあるようにどうやら普通にcanvasで描画しているようだ。

■サンプルコード

以下のようにアレンジしてWebGLRendererを使うようにしてみる。

(function(){
    var camera;
    var scene;
    var renderer;
    var mesh;
    // initialize
    (function(){
        camera = new THREE.Camera(75, window.innerWidth / window.innerHeight, 1, 10000);
        camera.position.z = 1000;
        scene = new THREE.Scene();
        mesh = new THREE.Mesh(
            new THREE.Cube(200, 200, 200),
            new THREE.MeshBasicMaterial({
                "color"     : 0xff0000,
                "wireframe" : true
            })
        );
        scene.addObject(mesh);
        var canvas = document.getElementById('canvas2011030602');
        renderer = new THREE.WebGLRenderer();
        renderer.setSize(canvas.offsetWidth, 300);
        canvas.appendChild(renderer.domElement);
    })();
    // animation
    setInterval(
        function(){
            mesh.rotation.x += 0.02;
            renderer.render(scene, camera);
        },
        1000 / 60
    );
});

以下のように表示される。

アンチエイリアスがないのが気になる。 しかしドキュメントが見当たらなかったのでWebGLRenderer.jsを開いてみた。

_antialias = parameters.antialias !== undefined ? parameters.antialias : false,

75行目あたりに上述の記述があるので、以下のようにオプションを指定した。

(function(){
    var camera;
    var scene;
    var renderer;
    var mesh;
    // initialize
    (function(){
        camera = new THREE.Camera(75, window.innerWidth / window.innerHeight, 1, 10000);
        camera.position.z = 1000;
        scene = new THREE.Scene();
        mesh = new THREE.Mesh(
            new THREE.Cube(200, 200, 200),
            new THREE.MeshBasicMaterial({
                "color"     : 0xff0000,
                "wireframe" : true
            })
        );
        scene.addObject(mesh);
        var canvas = document.getElementById('canvas2011030603');
        renderer = new THREE.WebGLRenderer({"antialias" : true});
        renderer.setSize(canvas.offsetWidth, 300);
        canvas.appendChild(renderer.domElement);
    })();
    // animation
    setInterval(
        function(){
            mesh.rotation.x += 0.02;
            renderer.render(scene, camera);
        },
        1000 / 60
    );
});

以下のようにアンチエイリアスがかかった。但し、Firefoxではアンチエイリアスがかからなかった。

meshを以下のように記述することでテクスチャを貼ることができる。

mesh = new THREE.Mesh(
    new THREE.Cube(
        200,
        200,
        200,
        3,
        3,
        3,
        [
            new THREE.MeshBasicMaterial({map: THREE.ImageUtils.loadTexture('/img/lock.png')}), // right
            new THREE.MeshBasicMaterial({map: THREE.ImageUtils.loadTexture('/img/face.png')}), // left
            new THREE.MeshBasicMaterial({map: THREE.ImageUtils.loadTexture('/img/face.png')}), //top
            new THREE.MeshBasicMaterial({map: THREE.ImageUtils.loadTexture('/img/face.png')}), // bottom
            new THREE.MeshBasicMaterial({map: THREE.ImageUtils.loadTexture('/img/face.png')}), // back
            new THREE.MeshBasicMaterial({map: THREE.ImageUtils.loadTexture('/img/face.png')}) // front
        ]
    ),
    new THREE.MeshFaceMaterial()
);

以下のように表示される。

現時点でWebGLに対応しているPCブラウザはGoogle Chrome、Firefoxとなる。残念ながらスマートフォンではandroidのデフォルトのブラウザやMobile SafariでWebGLを見ることはできず、android版のFirefoxでは見ることができる。ちなみにWebGLを使うとMacBookが熱々になる(●´⌓`●)

JavaScriptでフロイドワーシャル法

■実装

以下のように実装した。

//Graph
var vertexes = [
     [null, 2,    null, null, 4],//    vertex 1
     [null, null, 3,    null, null],// vertex 2
     [null, null, null, 5,    1],//    vertex 3
     [8,    null, null, null, null],// vertex 4
     [null, null, null, 4,    null]//  vertex 5
];

// initialize
var dist = [];
var pred = [];
var n    = vertexes.length;
for(var u = 0; u < n; u++){
    dist[u] = [];
    pred[u] = [];
    for(var i = 0; i < n; i++){
        dist[u][i] = Number.POSITIVE_INFINITY;// 経路が存在しない場合は無限
        pred[u][i] = -1;
        if(vertexes[u][i] !== null){
            dist[u][i] = vertexes[u][i];// 元グラフの経路を代入
            pred[u][i] = u;
        }
    }
    dist[u][u] = 0;// 自身に対しては0の距離が存在する
}
console.log('dist:');
console.log(dist);//...(a)

// 計算
for(var k = 0; k < n; k++){
    for(var i = 0; i < n; i++){
        if(dist[i][k] === Number.POSITIVE_INFINITY){
            continue;
        }
        // 任意の頂点まで有限の距離が開いているとき
        // 有限距離 を経由した任意の頂点を選択し
        // そこまでの距離が既に計算したものよりも小さい場合に
        // その値で上書きする
        for(var j = 0; j < n; j++){
            var newLength = dist[i][k];// ik
            newLength += dist[k][j];
            if(newLength < dist[i][j]){
                dist[i][j] = newLength;
                pred[i][j] = pred[k][j];
            }
        }
    }
}

// 結果
console.log("dist:");
console.log(dist);//...(b)

(a)の時、distは以下のようになる。

0 2 Infinity Infinity 4
Infinity 0 3 Infinity Infinity
Infinity Infinity 0 5 1
8 Infinity Infinity 0 Infinity
Infinity Infinity Infinity 4 0

殆ど元グラフと変わらない。結果(b)は、以下のようになる。

0 2 5 8 4
16 0 3 8 4
13 15 0 5 1
8 10 13 0 12
12 14 17 4 0

例えば0→1は距離が2、0→2は距離が5、0→3は距離が8、0→4は距離が4であり、1→0は距離が16である。

経路

終了時のpredは以下のようになる。

-1 0 1 4 0
3 -1 1 2 2
3 0 -1 2 2
3 0 1 -1 0
3 0 1 4 -1

例えば0→1の一つ前の頂点は始点0、0→2の一つ前の頂点は頂点1、0→3の一つ前の頂点は頂点4、0→4の一つ前の頂点は0であり、1→0の場合は頂点3が終点の一つ前である。

■おまけ

ちなみに表は以下のようにして描画した。

document.write('<table border="1" cellpadding="0" cellspacing="0">');
dist.forEach(function(e1, i1, ary1){
	document.write('<tr>');
	e1.forEach(function(e2, i2, ary2){
		document.write('<td>' + e2 + '</td>');
	});
	document.write('</tr>');
});
document.write('</table>');

そろそろJavaScriptでもforEachを使って良い頃だと思う。

JavaScriptでベルマンフォード法

■実装

グラフは以下のようにして実装した。グラフは前回のものと同様だがベルマンフォード法では負の重みも存在しうるので、経路が存在しない部分はnullとした。

// Graph //前回のグラフと同じグラフを使用
var vertexes = [
     [null, 1,    3,    null, null, null],// vertex s
     [null, null, 1,    4,    null, null],// vertex 1
     [null, null, null, 1,    null, null],// vertex 2
     [null, null, null, null, 1,    10],//   vertex 3
     [null, null, null, null, null, 1],//    vertex 4
     [null, null, null, null, null, null] // vertex g
];

// initialize
var dist    = [];
var pred    = [];
for(var i = 0; i < vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
}
dist[0] = 0;// start

// 計算
(function(){
    var n = vertexes.length;
    for(var i = 1; i <= n; i++){
        // i=nの時
        // destinationと自身が同じであるにも関わらず
        // 後述のnewLenの方が短い場合、
        // 負の閉路が存在していることを示す
        failOnUpdate = (i === n);
        leaveEarly   = true;
        for(var u = 0; u < n; u++){
            for(var ci = 0; ci < n; ci++){
                if(vertexes[u][ci] === null){continue;}//経路が存在しない
                var newLen = dist[u] + vertexes[u][ci];//頂点uを経由したciへの距離
                if(newLen < dist[ci]){// 頂点u経由の方が短い場合はアップデートする
                    if(failOnUpdate){
                        throw new Error('Graph has negative cycle');
                    }
                    dist[ci] = newLen;
                    pred[ci] = u;
                    leaveEarly = false;
                }
            }
        }
        if(leaveEarly){
            break;
        }
    }
})();

// 結果表示
console.log("最短経路");
console.log(pred);// [-1, 0, 1, 2, 3, 4]
console.log("最短距離");
console.log(dist);// [0, 1, 2, 3, 4, 5]

但し、上述の場合では負の重みが存在しない。

負の重み

従って以下のデータでテストしてみる。

var vertexes = [
     [null, 1,    3,    null, null, null],// s
     [null, null, 1,    4,    null, null],// 1
     [null, null, null, 1,    null, null],// 2
     [null, null, null, null, 1,    -10],// 3
     [null, null, null, null, null, 1],// 4
     [null, null, null, null, null, null] // g
];

以下のような結果となる。

console.log("最短経路");
console.log(pred);// [-1, 0, 1, 2, 3, 3]
console.log("最短距離");
console.log(dist);// [0, 1, 2, 3, 4, -7]

3→gの距離が4を経由するよりも近くなり、s〜gの重みは-7となった。

負の閉路

以下のように閉路(ループ)で総和が負の値になるような経路を用意する。

var vertexes = [
     [null, -1,   3,    null, null, null],// s
     [null, null, -10,  4,    null, null],// 1
     [5,    null, null, 1,    null, null],// 2
     [null, null, null, null, 1,    -10],// 3
     [null, null, null, null, null, 1],// 4
     [null, null, null, null, null, null] // g
];

以下のようなエラーが発生する。

//Uncaught Error: Graph has negative cycle

ベルマンフォード法は負の重みがあった場合でも処理が可能であるが、総和が0より小さい負の閉路が存在していた場合は使用できない。但し、そのような場合は最短経路自体が意味を成さない。ちなみに密グラフには向かないアルゴリズムであるので、多次元配列(行列)でのグラフ生成は良くないかもしれない。(●´⌓`●)

overflowがscrollの時にアンカーにsmooth scrollできるjQueryプラグインを作ってみた

久しぶりのjQueryでのちょっとしたスクリプト。


■クライアントコード

// a[href="#target"]をクリックすると#targetに#mainがスムーズスクロールする。
$('a[href="#target"]').click(function(e){
    e.preventDefault();
    $('#main').boxScroll($("#target-wrapper"), $('#target'));
});

こんな感じで使う。気が向いたらブラッシュアップする。

緊急地震速報 by Extensionを作ったときの感謝をこめて

「緊急地震速報 by Extension」を作って経験したことなどをまとめました。今回は後編です。前編は会社のブログに書きました。

僕は生産設備を持っていませんので食料をはじめとした物流における支援は難しいのかもしれません。しかしながらシステムエンジニアとして間接的な支援や情報における支援はできます。僕は、天災における「破壊」を修復するのは人々の「生産」と考えるとともに、その「生産」の一部分を担う者として頑張っていきたいと思います。

東北地方太平洋沖地震の後、余震が頻発し緊急地震速報の警告音も頻繁に耳にするようになりました。警告音に焦らされる一方で、本当は落ち着いて揺れに対処しなければならないと思っていました。そこで緊迫感を与えないような緊急地震速報を出せないものかと今回の制作にいたりました。(なので初期バージョンには音がなかったのです)

また、本当は「緊急地震速報 by Chrome Extension」という名前で登録しようとしたのですが「Chrome」というワードは使用ができないので「緊急地震速報 by Extension」という名前になりました。

■プロキシ経由での接続

大きな会社などではプロキシ経由でインターネットに接続するようになっていて配信サーバと接続ができないようでした。

変更前

ポート12001番を使用していました。

var hosts = [
    '123.123.123.123:12001'
];

変更後

ポート443番を使用するように変更しました。

var hosts = [
    '123.123.123.123:443'
];

HTTPSで使用するポートを用いることにより一部の方の接続が可能になりました。

さらに変更後

ポート443番、80、8080番、12001番を使用するように変更しました。

var hosts = [
    '123.123.123.123:443',
    '123.123.123.123:80',
    '123.123.123.123:8080',
    '123.123.123.123:12001'
];

これによって判明したのは1/3〜1/4の利用者の方は443にしか接続できなかった事です。

参考

■マルチバイト文字列のbroadcast

今回、Websocketサーバからbroadcastする際、node-websocket-serverを使用したのですが日本語を正しく送信できませんでした。

解決策

wsServer.broadcast('\\u3092');

こうすることでクライアント側には\u3092という文字列が送信されるようになります。

ちょっとライブラリの中をのぞいてみます。

server.js

broadcastメソッドです。

this.broadcast = function(data) {
    manager.forEach(function(client) {
        clientWrite(client, data);
    });
};

上述のとおりforEachで回してます。clientWriteメソッドも確認します。

function clientWrite(client, data) {
  if (client && client._state === 4) {
    client.write(data, 'utf8');
  }
}

utf8としていされてwriteされています。

manager.js
Manager.prototype.forEach = function(callback, thisArg) {
    var current = this._head;
    while (current !== null) {
        callback.call(thisArg, current.connection);
        current = current._next;
    }
};

this._headは連結リストの先頭の要素のようです。

this._head = client;

clientオブジェクトが入っているようです。

var client = {
    id: connection.id,
    _next: null,
    connection: connection
};

接続IDと接続、次の要素を保持しています。

connection.js
function write(connection, data) {
    debug(connection.id, 'write: ', (new Buffer(data)).inspect());
    if (connection._socket.writable) {
        return connection._socket.write(data, 'binary');
    }
    return false;
}

binaryと指定されていますね。完全に読み切るには少々時間がかかるので適宜更新します。

参考

■正規表現

情報はtwitterのUser Streams API経由で取得していたのですが、ご利用者の方から震度やマグニチュードだけを簡略化して欲しいとの要望がありました。そこで正規表現を使用し文字列を整形して表示することにしました。ところが一部のご利用者には元の文章がそのまま表示されていました。

解決策

以下のようにして日本語をマッチさせるときに16進表現を使用することで解決しました。

var reg = new RegExp('\u9707\u5EA6([3-9]\u5F37*\u5F31*)', 'ig');
text.match(reg);
var scale = RegExp.$1;
// filter : simplify
if(localStorage["simplify"] !== "false"){
    var reg = new RegExp('([0-9]*/[0-9]*/[0-9]*)', 'ig');
    text.match(reg);
    var date = RegExp.$1;

    var reg = new RegExp('([0-9]*\:[0-9]*)', 'ig');
    text.match(reg);
    var time = RegExp.$1;

    var reg = new RegExp('\u30DE\u30B0\u30CB\u30C1\u30E5\u30FC\u30C9([0-9\.]*)', 'ig');
    text.match(reg);
    var magnitude = RegExp.$1;

    var reg = new RegExp('\u3001(.*?)\u306E', 'ig');
    text.match(reg);
    var place = RegExp.$1;

    if(date != '' && time != '' && place != '' && scale != '' && magnitude != ''){
        text = date + " " + time + " " + place + "\n\u9707\u5EA6" + scale + "\n\u30DE\u30B0\u30CB\u30C1\u30E5\u30FC\u30C9" + magnitude;
    }
}

// filter : scale
switch(localStorage["scale"]){
    case "7":
        if(parseInt(scale, 10) < 7){return false;}
        break;
    case "6":
        if(parseInt(scale, 10) < 6){return false;}
        break;
    case "5":
        if(parseInt(scale, 10) < 5){return false;}
        break;
    case "4":
        if(parseInt(scale, 10) < 4){return false;}
        break;
}

ブラウザ側の言語設定は各々異なります。通信時の文字コードを指定しても解決するかもしれません。

■twitterとの接続

node.jsを使い、以下のようなコードでtwitterと接続してます。

var client = http.createClient(
    80,
    "stream.twitter.com",
    false,
    false,
    {
        "username" : "hogehoge",
        "password" : "fugafuga"
    }
);
var request = client.request(
    "GET",
    "/1/statuses/filter.json?follow=123456789",
    {
        "host" : "stream.twitter.com"
    }
);
request.end();
request.on(
    "response",
    function(response){
        //sys.puts("response");
        var chunk = '';
        response.on(
            "data",
            function(data){
                // データ受信処理
            }
        );
        response.on(
            'end',
            function(){
                // twitterから接続を切られた時
            }
        );
    }
);

twitter切断時

実はたまに接続を切られます。切断される可能性を考慮し以下のようなコードを使用してます。

var getRequest = function(){
    var request = client.request(
        "GET",
        "/1/statuses/filter.json?follow=123456789",
        {
            "host" : "stream.twitter.com"
        }
    );
    request.end();
    request.on(
        "response",
        function(response){
            response.on(
                "data",
                function(data){
                    // データ受信処理
                }
            );
            response.on(
                'end',
                function(){
                    // twitterから接続を切られた時
                    r = getRequest();// 再接続
                }
            );
        }
    );
    return request;
}
var r = getRequest();

通信は必ず切れるものと考えてコードを書かなくてはいけませんね。さらに実は以下のようなスクリプトも実行してます。

request.on(
    "response",
    function(response){
        //sys.puts("response");
        var chunk = '';
        response.on(
            "data",
            function(data){
                // データ受信処理
            }
        );
        response.on(
            'end',
            function(){
                // twitterから接続を切られた時
                throw new Error('twitter disconnected me!!');
            }
        );
    }
);

node.jsにおいてcatchできなかったErrorはプロセスを終了させます。従って以下のようなシェルスクリプトと組み合わせてプロセスが終了してないか定期的にチェックし、終了していた場合は再起動することで接続を維持しています。

#!/bin/sh
while true
do
    isAlive=`ps -ef | grep "my-websocket-server.js" | grep -v grep | wc -l`
     if [ $isAlive -ge 1 ]; then
        echo "process is alive"
    else
        node my-websocket-server.js.js
        echo "process is dead"
    fi
    sleep 3
done

■アップデート

拡張機能のアップデートは自動で行われますが、新バージョンを登録してすぐに全ユーザのアップデートが完了するわけではありません。意外にも早く直後にアップデートされる方もいれば、時間がかかる方もいます。1時間で10%程度の方がアップデートされるようです。一方、90%のユーザはアップデート前のクライアントでサーバに接続しますので考慮して更新しなければなりません。

■起動

ちなみにですが以下のコマンドでWebSocketサーバを起動してます。

nohup ./check.sh > log.txt &

接続数を調べるには以下のようなコマンドを使ってます。

lsof -i:12345 | grep "node" | wc -l

■twitterからの文字列

システムの設計の問題にもなりますが、twitterからの文字列が正しくパースできないようなケースが稀にあります。入力は受け手側が意図する形式になるとは限らないということです。

文字列をパースできるように条件分岐する
但し、ブラックリスト方式に近いので未知の正しくない文字列はパース出来ない
データストアを作って保存に対してbroadcastのトリガを引かせる
全てのサーバが正しくパースできなかった事はないので非常に有用だが、失敗する確率はわずかながらある

■サーバ負荷

node.jsの素晴らしさを実感する毎日ですが、接続数が1万数千を超えるとさすがに0.5〜1秒程度遅延します。早く多くの方に届けるべき情報ではあるものの、一方で多くの方が接続すると遅延が生じやすくなります。サーバは個人で賄っているので限度があります。非常に難しい問題です。財閥の末裔だったらデータセンターごと買うのになと思う毎日です。

■まとめ

僕は水や電気の節約には賛成です。しかしながら根拠が不明瞭な自粛ムードには反対です。冒頭で述べました通り、破壊を修復するのは生産であり、手を止めて遠慮する事では無いと思います。何もできることがないと考えた結論の自粛より、いつも通り働き、学び、生活する方が生産的だと僕は考えます。まだまだ対応できていない事ばかりで完璧ではありませんが今後とも宜しくお願いいたします。早く余震が収まるといいですね。(●´⌓`●)

拡張機能への要望

今まで通り@mi_eqbotまでお願いいたします。自分のブログよりも確実にチェックしてます。w

その他開発などへの興味

@mitsuaki_iまでお願いいたします。