@blog.justoneplanet.info

以下のようなコードを考える。

var sys = require('sys');

var dog = {
    "pochi" : 16,
    "john"  : 10
};
var getDogAge = function(name){
    return dog[name];
}

sys.puts('pochi is ' + getDogAge('pochi') + ' years old.');

以下のようにモジュール化すると非常にすっきりする。

■モジュール側

以下のように記述する。ちなみにgetメソッドなどは予約されていて使用できないようだ。

var dog = {
    "pochi" : 16,
    "john"  : 10
};
exports.getAge = function(name){
    return dog[name];
}

クライアント側から使用するメソッドやプロパティはexportオブジェクトのプロパティとする。それ以外のグローバル空間にある変数や関数はクライアント側からは見えず、プライベート扱いとなる。

■クライアント側

以下のようにして使用する。

var sys = require('sys');
var dog = require('./dog.js');
sys.puts('pochi is ' + dog.getAge('pochi') + ' years old.');

また以下のようにした場合は

var Dog = function(name){
    var self = this;
    self.name = name;
    self.cry = function(){
        sys.puts(self.name);
    }
}
module.exports = Dog

以下のように使用することができる。

var Dog = require('./dog.js');
var dog = new Dog();

すっきり。簡単。(●´ω｀●)

■参考

• Modules

■pywebsocket単体で動作させる

draft75

vi /home/pywebsocket-0.5.2/src/mod_pywebsocket/standalone.py

以下の部分を

parser.add_option('--allow-draft75', dest='allow_draft75',
                      action='store_true', default=False,
                      help='Allow draft 75 handshake')

以下のように変更する。

parser.add_option('--allow-draft75', dest='allow_draft75',
                      action='store_true', default=True,
                      help='Allow draft 75 handshake')

起動

python /home/pywebsocket-0.5.2/src/mod_pywebsocket/standalone.py -p 8800 -d /home/pywebsocket-0.5.2/src/example

WebSocketで8800ポートにアクセスする。(●´ω｀●)

■apacheモジュールとして動作させる

http-devel

yum install http-devel

mod_python

wget http://archive.apache.org/dist/httpd/modpython/mod_python-3.3.1.tgz
tar xvzf mod_python-3.3.1.tgz
cd mod_python-3.3.1
./configure –with-apxs=/usr/sbin/apxs –with-python=/usr/bin/python
make
make install

設定

vi /etc/httpd/conf.d/python.conf

以下の記述の下に

LoadModule python_module modules/mod_python.so

以下の記述を付加する。

AddHandler mod_python .py

mod_pywebsocket

wget http://pywebsocket.googlecode.com/files/mod_pywebsocket-0.5.2.tar.gz
tar xvzf mod_pywebsocket-0.5.2
cd pywebsocket-0.5.2/src
python setup.py build
python setup.py install

設定

vi /etc/httpd/conf.d/python_mod_pywebsocket.conf

以下を記述する。

<IfModule python_module>
    PythonPath "sys.path+['/usr/lib/python2.4/site-packages/']"
    PythonOption mod_pywebsocket.handler_root /var/www/html/wsh
    PythonHeaderParserHandler mod_pywebsocket.headerparserhandler
    PythonOption mod_pywebsocket.allow_draft75 On
</IfModule>

/etc/init.d/httpd restart

起動

cp /home/pywebsocket-0.5.2/src/example/echo_wsh.py /var/www/html/wsh/

WebSocketクライアントで/echoにアクセスする。(●´ω｀●)

■ベンチマーク

正確性は微妙だが100クライアントからの接続でのロードアベレージは、「node : pywebsoket(standalone) : pywebsoket(apache) = 0.15 : 0.25 : 0.8」となった。最初の2つの差は微妙だったが、Apacheモジュールとして動作させた時のリソースの消費量は明らかに大きいようだ。

どうやら環境によっては以下のエラーが出る。

../base64.cc:138: error: 'malloc' was not declared in this scope
../base64.cc:141: error: 'free' was not declared in this scope

■解決策

ソースをダウンロードしbase64.ccに以下のラインを追加する。

#import <stdlib.h>

その後、以下のコマンドでインストールする。

npm install dir/

最後のスラッシュは必要なかったかもしれない。

HTML5の要素の一つとして新しくaudio要素が加わった。このaudio要素を使用することでプラグインを使用することなく音源を再生することができる。(●´ω｀●)

■HTML

以下のようにしてaudio要素を使用できる。

<audio src="http://upload.wikimedia.org/wikipedia/commons/0/03/262Hz.ogg" controls></audio>

また以下のようにしてaudio要素に対応していないブラウザに対しての表示を行うことができる。

<audio src="http://upload.wikimedia.org/wikipedia/commons/0/03/262Hz.ogg" controls>
最新のブラウザを使ってくれよな
</audio>

以下のような表示となる。

ogg形式に対応していないブラウザ用にmp3の音源を使用してみた。

PCブラウザの対応状況

Chrome 9

両方再生可能だ

Firefox 3.6

MP3形式の音源が再生できない

IE 9

MP3形式のみ再生が可能

スマートフォンブラウザの対応状況

iPhone4のsafari

audio要素を理解できるが、ogg形式の音源を再生することはできず、MP3は再生することができた

android 2.1・2.2

audio要素を理解することができなかった。androidのOpera mobileでも再生することはできない

android 3.0

エミュレータ上ではあるが両方再生可能

androidのブラウザには本当に頑張ってほしい限りだ。(☍﹏⁰)

■JavaScript

以下のようにJavaScriptだけで音源を再生することもできる。

var audio = new Audio('http://upload.wikimedia.org/wikipedia/commons/0/03/262Hz.ogg');
audio.play();

再生時間の表示

以下のようにして再生時間を表示することができる。

var audio = new Audio('http://upload.wikimedia.org/wikipedia/commons/0/03/262Hz.ogg');
audio.addEventListener(
    'timeupdate',
    function(){
        document.getElementById('content').innerHTML = audio.currentTime;
    },
    false
);
audio.play();

以下のようにaudio要素をcreateElementした場合、そのオブジェクトに対して上述と同様のメソッドが使用できる。

var audio = document.createElement('audio');
audio.setAttribute('src', 'http://upload.wikimedia.org/wikipedia/commons/0/03/262Hz.ogg');
audio.setAttribute('controls', 'true');
document.getElementById('content').appendChild(audio);
audio.play();

■参考

audio – MDC Doc Center

前回の記事では、生成するグラフが疎であったので連結リストを使用した。密グラフ向けに行列でも実装した。

■実装

// Graph //（密ではないが）前回のグラフと同じグラフを使用
var Vertexes = [
             [0, 1, 3, 0, 0, 0],// s
             [0, 0, 1, 4, 0, 0],// 1
             [0, 0, 0, 1, 0, 0],// 2
             [0, 0, 0, 0, 1,10],// 3
             [0, 0, 0, 0, 0, 1],// 4
             [0, 0, 0, 0, 0, 0] // g
];

// initialize
var dist    = [];
var pred    = [];
var visited = [];
for(var i = 0; i < Vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
    visited[i] = false;// 訪問を記録する
}
dist[0] = 0;// start

// search
var dijkstraMX = function(){
    var getMin = function(){
        var tmp = Number.POSITIVE_INFINITY;
        for(var i = 0; i < Vertexes.length; i++){
            if(visited[i] === false && dist[i] < tmp){
                tmp = i;
            }
        }
        if(tmp === Number.POSITIVE_INFINITY){
            tmp = null;
        }
        return tmp;
    }

    while(true){
        var u = getMin();// 未訪問の中でスタートから最小の距離の頂点
        // 「sから辿れない頂点しか残っていない場合」「未訪問が無い場合」はループ終了
        if(dist[u] === Number.POSITIVE_INFINITY || u === null){break;}
        visited[u] = true;
        for(var i = 0; i < Vertexes[u].length; i++){
            if(Vertexes[u][i] > 0){// 辺が存在している
                var neighbor  = i;//隣接点(a)
                var weight    = Vertexes[u][i];// (a)との辺の重み
                var newLength = dist[u] + weight;// (b)
                // 現在セットされている、スタート地点から隣接点までの距離が
                // 新しい経路での値より大きい時
                if(newLength < dist[neighbor]){
                    dist[neighbor] = newLength;
                    pred[neighbor] = u;
                }
            }
        }
    }
}
dijkstraMX();

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

// 最短距離
console.log(dist);// [0, 1, 2, 3, 4, 5]

グラフが疎である場合、行列を使用すると殆どの空間が0で埋められるので勿体無いね。

つまずいた部分があったのでメモっておく。φ(-ω-。`)。

■ダウンロード

eclipse downloadsのJavaScript版をダウンロードした。

■プラグイン

JsTestDriverを使用する。

まず、「ヘルプ ＞ 新規ソフトウェアのインストール ＞ 有効なソフトウェア・サイト」を選択し、フィルタに「http://js-test-driver.googlecode.com/svn/update/」と入力する。

次に、一覧にパッケージが表示されるので、バージョンが新しいものを選択しインストールする。

■使用方法

用意するファイルは3ファイルである。以下のサンプルソースはドキュメントのコードを使用させていただいた。

projectdir/src/Greeter.js

myapp = {};
myapp.Greeter = function(){ };
myapp.Greeter.prototype.greet = function(name){
    return "Hello " + name + "!";
};

projectdir/src/GreeterTest.js

テストコードである。

GreeterTest = TestCase("GreeterTest");

GreeterTest.prototype.testGreet = function(){
    var greeter = new myapp.Greeter();
    assertEquals("Hello World!", greeter.greet("World"));
};

projectdir/jsTestDriver.conf

クラスのディレクトリとテストコードのディレクトリを設定している感じだ。

server: http://localhost:42442

load:
  - src/*.js
  - src-test/*.js

どうやらプロジェクトルートに置く必要があるようだ。また、ファイル内のパスは注意して正しく記述する必要がある、

ビューの表示

「ウィンドウ ＞ ビューの表示 ＞ その他」を選択し、JavaScriptの中からJsTestDriverを選択すると表示される。

設定1

「ウィンドウ ＞ 設定 ＞ Js Test Driver」を選択し、各ブラウザのexeファイルと関連付ける。要はパスを通すって感じだ。

設定2

プロジェクトを選択した状態で、「実行 ＞ 実行の構成」を選択したら、「実行 ＞ Js Test Driver Test ＞ 新規構成」を選択し、以下のように入力する。

project

projectdir

Conf File

jsTestDriver.conf

実行

JsTestDriverビューの「サーバーを始動」のボタンを押し、テストするブラウザのボタンを押す。するとブラウザが立ち上がるので、ビューに戻り「return last configuration」をクリックするとテストが実行される。

優先度つきキューを使用したダイクストラ法をJavaScriptで実装した。

■実装

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.dist     = Number.POSITIVE_INFINITY;// もしくは十分に大きい値とか
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var g  = new Vertex(5);

// set up connections
// 単純化のためループや往路を除去した
s.appendNeighbor(
    {"weight" : 1, "vertex" : v1},
    {"weight" : 3, "vertex" : v2}
);
v1.appendNeighbor(
    {"weight" : 1, "vertex" : v2},
    {"weight" : 4, "vertex" : v3}
);
v2.appendNeighbor(
    {"weight" : 1, "vertex" : v3}
);
v3.appendNeighbor(
    {"weight" : 1, "vertex" : v4},
    {"weight" : 10, "vertex" : g}
);
v4.appendNeighbor(
    {"weight" : 1, "vertex" : g}
);
g.appendNeighbor(
);

// initialize
var vertexes = [s, v1, v2, v3, v4, g];
var pred     = [];
var pq       = new BinaryHeap();// sからの距離が短い頂点順の優先度つきキュー
s.dist = 0;
for(var i = 0; i < vertexes.length; i++){// キューの生成
    pred[i] = -1;
    pq.insert(vertexes[i], vertexes[i].dist);
}

// search
var dijkstraPQ = function(){
    while(pq.getList().length > 0){
        var u = pq.getPrior();// スタートからの距離が近い頂点を取得しcurrent頂点とする
        for(var i = 0; i < u.neighbor.length; i++){
            var neighbor  = u.neighbor[i].vertex;
            var weight    = u.neighbor[i].weight;// 隣接点の距離...(a)
            var newLength = u.dist + weight;// current頂点のsからの距離と(a)を加算...(b)
            // (b) < visitした時の距離の場合
            // キューを更新し、最短経路も更新する
            if(newLength < neighbor.dist){
                pq.changePriority(neighbor, newLength);
                neighbor.dist = newLength;
                pred[neighbor.value] = u.value;
            }
        }
    }
}
dijkstraPQ();

// 最短経路
console.log(pred);// [-1, 0, 1, 2, 3, 4]
// g<-v4<-v3-<v2<-v1<-s

// 最短距離
console.log(g.dist);// 5

任意の頂点に対して一つ前の頂点とその時の距離が分かる。

■特性

• 辺の重みは0より大きい値
• 重みの和が0より小さい閉路が存在すると無限ループする可能性がある

/**
 * 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;
}

Cの場合は以下のようにして、二分ヒープを使用することができるらしい。

#include "BinaryHeap.h"

■実装

しかし、JavaScriptには二分ヒープのようなデータ構造が存在しないので、以下のように自力で実装する。

/**
 * 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;
}

// test code
var pq = new BinaryHeap();
pq.insert('pochi', 0);
pq.insert('son', 4);
pq.insert('mike', 10);
pq.insert('father', 1);
pq.insert('mother', 2);
console.log(pq.getList());

優先度つきキューに使用したいので、ヒープソートのコードを変更し最小ヒープとした。使用方法は以下のとおりである。

二分ヒープの生成

var pq = new BinaryHeap();

要素の追加

pq.insert(elm, priority);

優先度の変更

pq.changePriority(elm, priority);

最優先要素の取得

var elm = pq.getPrior();

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

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var v5 = new Vertex(5);
var v6 = new Vertex(6);
var v7 = new Vertex(7);
var v8 = new Vertex(8);
var g  = new Vertex(9);
s.appendNeighbor(v1, v4);
v1.appendNeighbor(s, v2);
v2.appendNeighbor(v1, v3);
v3.appendNeighbor(v2, v4, g);
v4.appendNeighbor(v3, v5, s);
v5.appendNeighbor(v4);
v6.appendNeighbor(v7);
v7.appendNeighbor(v6);
g.appendNeighbor(v3);
var vertexes = [s, v1, v2, v3, v4, v5, v6, v7, v8, g];

// initialize
var pred       = [];
var distance   = [];
var queue = [];
var counter    = 0;
for(var i = 0; i < vertexes.length; i++){
    pred[vertexes[i].value]       = -1;
    distance[vertexes[i].value]   = -1;
}

// search
s.state = 1;
distance[s.value] = 0;
queue.push(s);
var breadthFirstSearch = function(){
    while(queue.length > 0){
        var vertex = queue.shift();// 処理する頂点
        for(var i = 0; i < vertex.neighbor.length; i++){// 隣接点全てに対して
            var n = vertex.neighbor[i];
            if(vertex.neighbor[i].state === 0){
                distance[n.value] = distance[vertex.value] + 1;// 処理中の頂点+1の距離
                pred[n.value]     = vertex.value;// 処理中の頂点の値
                n.state           = 1;// visitした記録
                queue.push(n);// 隣接点をキューに入れる
            }
        }
        vertex.state = 2;// 処理し終わった記録
    }
}
breadthFirstSearch();

// 1つ前の節点の値
console.log(pred);// [-1, 0, 1, 4, 0, 4, -1, -1, -1, 3]

// 各節点のスタートからの距離
console.log(distance);// [0, 1, 2, 2, 1, 2, -1, -1, -1, 3]

console.log(vertexes);

スタート地点から全体に探索菌が同速度で広がっていくイメージだね。

■特性

• 無向グラフでも有向グラフでも機能する
• 重みでなくステップ数での最短距離を求めることができる
• 節点をQueueに蓄えるので巨大グラフでは巨大なストレージが必要となる
• スタートから辿れない頂点は基本的には訪問しない

■実装

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

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var v5 = new Vertex(5);
var v6 = new Vertex(6);
var v7 = new Vertex(7);
var v8 = new Vertex(8);
var g  = new Vertex(9);

// set up connections
s.appendNeighbor(v1, v4);
v1.appendNeighbor(s, v2);
v2.appendNeighbor(v1, v3);
v3.appendNeighbor(v2, v4, g);
v4.appendNeighbor(v3, v5, s);
v5.appendNeighbor(v4);
v6.appendNeighbor(v7);
v7.appendNeighbor(v6);
g.appendNeighbor(v3);
var vertexes = [s, v1, v2, v3, v4, v5, v6, v7, v8, g];

// initialize
var pred       = [];
var discovered = [];
var finished   = [];
var counter    = 0;
for(var i = 0; i < vertexes.length; i++){
    pred[vertexes[i].value]       = -1;
    discovered[vertexes[i].value] = -1;
    finished[vertexes[i].value]   = -1;
}

/**
 * depthFirstSearch
 * @param array vertexes
 */
var depthFirstSearch = function(vertexes){
    depthFirstVisit(s);// start地点から探索
    // 以下の処理でstart地点から辿れない頂点を探索
    for(var i = 0; i < vertexes.length; i++){
        if(vertexes[i].state === 0){
            depthFirstVisit(vertexes[i]);
        }
    }
} 

/**
 * depthFirstVisit
 * @param Vertex vertex
 */
var depthFirstVisit = function(vertex){
    vertex.state = 1;// 探索した事を記録（再帰処理部分で自身を再訪しないように）
    discovered[vertex] = ++counter;
    // 以下の処理で隣接点を探索
    for(var i = 0; i < vertex.neighbor.length; i++){
        if(vertex.neighbor[i].state === 0){
            pred[vertex.neighbor[i].value] = vertex.value;
            depthFirstVisit(vertex.neighbor[i]);
        }
    }
    vertex.state = 2;// 全ての隣接点を探索した事を記録
    finished[vertex.value] = ++counter;
}
depthFirstSearch(vertexes);

// 1つ前の節点の値
console.log(pred);// [-1, 0, 1, 2, 3, 4, -1, 6, -1, 3]
// g<-3(v3)<-2(v2)<-1(v1)<-0(s)

// 発見したときのカウンタの値
console.log(discovered);// [1, 2, 3, 4, 5, 6, 15, 16, 19, 9]

// 探索し終えたときのカウンタの値
console.log(finished);// [14, 13, 12, 11, 8, 7, 18, 17, 20, 10]

console.log(vertexes);

■特性

• グラフ全体を見通して経路を生成することはできず、求められる経路は最短経路ではない
• 無向グラフでも有向グラフでも機能する
• グラフ探索において情報蓄積量が最小