@blog.justoneplanet.info

日々勉強

JavaScriptで深さ優先探索

■実装

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

■特性

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

二分木と二分探索木

意思の疎通が上手くいかなかったりするので、ちゃんと区別したい。で記事にした。゜(´□`。)°゜

■二分木(binary tree)

各ノードの子要素が2以下で通常は左と右と呼ばれる。

var BT = function(value){
    var self = this;
    self._left  = null;
    self._right = null;
    self.value = value;
    self.appendChild = function(child, location){
        if(location === 'left' && self._left === null){
            self._left = child;
            return true;
        }
        else if(location === 'right' && self._right === null){
            self._right = child;
            return true;
        }
        else{
            return false;
        }
    }
}

// test code
var root  = new BT(5);
var leaf1 = new BT(7);
var leaf2 = new BT(2);
var leaf3 = new BT(10);
var leaf4 = new BT(6);
var leaf5 = new BT(1);
var leaf6 = new BT(8);

root.appendChild(leaf1, 'left');
root.appendChild(leaf2, 'right');

leaf1.appendChild(leaf3, 'left');
leaf1.appendChild(leaf4, 'right');
leaf2.appendChild(leaf5, 'left');
leaf2.appendChild(leaf6, 'right');

console.log(root);
console.log(JSON.stringify(root));

■二分探索木(binary search tree)

二分木の一種だが要素の大小に『left < parent < right』という順序が成立する。

var BST = function(value){
    var self = this;
    self._left  = null;
    self._right = null;
    self.value = value;
    self.appendChild = function(child){
        if(child.value < self.value){
            if(self._left){
                self._left.appendChild(child);
            }
            else{
                self._left = child;
            }
        }
        else{
            if(self._right){
                self._right.appendChild(child);
            }
            else{
                self._right = child;
            }
        }
    }
}

// test code
var root  = new BST(5);
var leaf1 = new BST(7);
var leaf2 = new BST(2);
var leaf3 = new BST(10);
var leaf4 = new BST(6);
var leaf5 = new BST(1);
var leaf6 = new BST(8);

root.appendChild(leaf1);
root.appendChild(leaf2);
root.appendChild(leaf3);
root.appendChild(leaf4);
root.appendChild(leaf5);
root.appendChild(leaf6);

console.log(root);
console.log(JSON.stringify(root));

つまり要素の大小関係に基づいて位置が決まるのがbinary search treeであって、binary treeではないよね。ちなみに以前はめんどいから配列で実装した。配列で実現することも可能だが、木が平衡でない場合に無駄な空きができてしまう。

■文献

まぁ、色々読んだほうが早いかもしれん。

Binary tree

Binary trees are commonly used to implement binary search trees and binary heaps.

Binary search tree

In computer science, a binary search tree (BST) or ordered binary tree is a node-based binary tree data structure which has the following properties:[1]

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

アルゴリズムクイックリファレンス(p143)

二分探索木Tは、順序特性を持つ、すなわちキーによって識別される節点の有限集合となる。節点集合は空でなければ、根節点(root node)nrを含む。節点nは、2つの二分探索木TlとTrとを持ち、節点nのキーをkとしたら、Tlのすべてのキーが≦kで、Trのすべてのキーが≧kであるという性質を保持する。この性質は、二分探索木の性質(binary-search-tree property)と呼ばれる(Cormen et al., 2001)。

■canvas

つーかさ、console.logで確認するのめんどいよね!そういうわけでcanvasで表示させます。

var BST = function(value){
    var self = this;
    self._left  = null;
    self._right = null;
    self.value = value;
    
    /**
     * appendChild
     * @param {Object} child
     */
    self.appendChild = function(child){
        if(child.value < self.value){
            if(self._left){
                self._left.appendChild(child);
            }
            else{
                self._left = child;
            }
        }
        else{
            if(self._right){
                self._right.appendChild(child);
            }
            else{
                self._right = child;
            }
        }
    }
    
    /**
     * draw
     * @param {Object} context
     * @param {int} left
     * @param {int} top
     * @param {int} center
     * @param {int} depth
     */
    self.draw = function(context, left, top, center, depth){
        if(self._left !== null){
            var cl = left - (center / Math.pow(2, depth + 1));
            var ct = top + 50
            context.fillStyle = 'black';
            context.beginPath();
            context.moveTo(left, top);
            context.lineTo(cl, ct);
            context.stroke();
            var lp = self._left.draw(context, cl, ct, center, depth + 1);
        }
        if(self._right !== null){
            var cl = left + (center / Math.pow(2, depth + 1));
            var ct = top + 50
            context.fillStyle = 'black';
            context.beginPath();
            context.moveTo(left, top);
            context.lineTo(cl, ct);
            context.stroke();
            var lp = self._right.draw(context, cl, ct, center, depth + 1);
        }
        context.fillStyle = 'red';
        context.beginPath();
        context.arc(left, top, 10, 0, Math.PI * 2, false);
        context.fill();
        
        context.font = "15px Arial bold";
        context.textAlign = "center";
        context.textBaseline = "middle";
        context.fillStyle = 'white';
        context.fillText(self.value, left, top, 30);
        return {"left" : left, "top" : top};
    }
}

// test code
var root  = new BST(5);
root.appendChild(new BST(7));
root.appendChild(new BST(2));
root.appendChild(new BST(10));
root.appendChild(new BST(6));
root.appendChild(new BST(1));
root.appendChild(new BST(8));
root.appendChild(new BST(12));
root.appendChild(new BST(11));
root.appendChild(new BST(9));
root.appendChild(new BST(4));
root.draw(document.getElementById("canvas").getContext('2d'), 200, 50, 200, 0);

おや、まぁ、なんと素敵なことでしょう!(o゚▽゚)♡

JavaScriptで二分探索木

二分探索木とは二分木と同じ構造で、左の子<親<右の子となっているものですな。

■二分探索木に対する挿入

以下のようにして、二分探索木(Binary Search Tree)に対する挿入を実装してみた。linked listで再現したほうがイメージしやすい気もするがコード量は増えるので配列を使用した。

Array.prototype.bpush = function(elm){
    var ary  = this;
    var push = function(elm, key){
        if(!ary[key]){
            ary[key] = elm;
        }
        else{
            if(elm < ary[key]){// left child
                push(elm, 2 * key + 1);
            }
            else{// right child
                push(elm, 2 * key + 2);
            }
        }
    }
    push(elm, 0);
}

var bst = [];
bst.bpush(5);
bst.bpush(7);
bst.bpush(8);
bst.bpush(3);
console.log(bst);// [5, 3, 7, undefined, undefined, undefined, 8]// ex1

var bst = [];
bst.bpush(7);
bst.bpush(2);
bst.bpush(5);
bst.bpush(1);
console.log(bst);// [7, 2, undefined, 1, 5]// ex2

var bst = [];
bst.bpush(1);
bst.bpush(2);
bst.bpush(3);
bst.bpush(4);
console.log(bst);// [1, undefined, 2, undefined, undefined, undefined, 3, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 4]// ex3

ソート済みの配列を格納した場合、上述ex3に見られるように線形リストとなり下述の探索性能が下がる。

■探索

上述で生成した二分探索木を探索するアルゴリズムを実装した。

Array.prototype.bpush = function(elm){
    var ary  = this;
    var push = function(elm, key){
        if(!ary[key]){
            ary[key] = elm;
        }
        else{
            if(elm < ary[key]){// left child
                push(elm, 2 * key + 1);
            }
            else{// right child
                push(elm, 2 * key + 2);
            }
        }
    }
    push(elm, 0);
}

Array.prototype.bsearch = function(elm){
    var ary    = this;
    var search = function(elm, key){
        if(!ary[key]){
            return -1;
        }
        if(elm === ary[key]){
            return key;
        }
        else{
            if(elm < ary[key]){
                return search(elm, 2 * key + 1);
            }
            else{
                return search(elm, 2 * key + 2);
            }
        }
    }
    return search(elm, 0);
}

var bst = [];
bst.bpush(5);
bst.bpush(7);
bst.bpush(8);
bst.bpush(3);
console.log(bst);// [5, 3, 7, undefined, undefined, undefined, 8]
console.log(bst.bsearch(3));// 1

var bst = [];
bst.bpush(7);
bst.bpush(2);
bst.bpush(5);
bst.bpush(1);
console.log(bst);// [7, 2, undefined, 1, 5]
console.log(bst.bsearch(3));// -1

var bst = [];
bst.bpush(1);
bst.bpush(2);
bst.bpush(3);
bst.bpush(4);
console.log(bst);// [1, undefined, 2, undefined, undefined, undefined, 3, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 4]
console.log(bst.bsearch(3));// 6

まぁこんな感じ。前述の通りex3は線形リストのシーケンシャル探索と同じとなり性能が低下する。従って、要素の挿入と削除に対して、ツリーの平衡を維持するようなロジックを導入する必要がある。代表的なものとして赤黒木などがある。

■特性

  • 最悪時の計算コストはO(n)。平均時はO(log n)となる

JavaScriptでマージソート

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * msort
 * @param {Object} ary
 */
var msort = function(ary){
    if(ary.length < 2){
        return ary;
    }
    else{
        var l = msort(ary.splice(0, ary.length >>> 1));// 配列の左半分
        var r = msort(ary.splice(0));// 残りの部分配列
        console.log(l.toString());
        console.log(r.toString());
        // 以下の部分でマージする
        while(!(l.length < 1 && r.length < 1)){
            if(!l[0]){
                ary.push(r.shift());
            }
            else if(!r[0]){
                ary.push(l.shift());
            }
            else if(l[0] < r[0]){// 小さい方をpush
                ary.push(l.shift());
            }
            else{
                ary.push(r.shift());
            }
        }
        console.log(ary.toString());
        console.log('===============');
        return ary.concat(l, r);
    }
}


msort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

  • 最悪時の計算量はO(n log n)
  • 安定ソート
  • 平均時性能はO(n log n)

JavaScriptでハッシュに基づいた探索

■実装

var a =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19];

/**
 * hash
 * ハッシュ関数
 * 解説用に衝突しやすい関数を使用
 * @param {int} x
 */
var hash = function(x){
    return x % 5;// tableのサイズを5とした(=メモリに応じたサイズ)
}

/**
 * setTable
 * 要素のハッシュ値をキーにした配列に変換
 * @param {Array} ary
 */
var setTable = function(ary){
    var table = [];
    for(var i = 0; i < a.length; i++){
        var key = hash(a[i]);
        if(!table[key]){// 衝突した場合
            table[key] = [];// 通常は連結リストを使用するが簡略化のため配列を使用
            table[key].push(a[i]);// (要素の追加・削除の用途が多いので)
        }
        else{
            table[key].push(a[i]);
        }
    }
    return table;
}

/**
 * search
 * 探索用関数
 * @param {Array} table
 * @param {int} elm
 */
var search = function(table, elm){
    var key = hash(elm);// 要素のハッシュ値を求めてハッシュテーブルから探索する
    if(table[key]){
        for(var i = 0; i < table[key].length; i++){
            if(table[key][i] === elm){
                return true;
            }
        }
        return false;
    }
    else{
        return false;
    }
};


var table = setTable(a);
console.log(JSON.stringify(table));// [[0,5,10,15],[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19]]
console.log(search(table, 6));// true
console.log(search(table, 39));// false

■特性

  • 最良時と平均時の計算コストはO(1)
  • 最悪時は全ての要素のハッシュ値が衝突した場合で線形時間の探索が必要になりO(n)

■ポイント

  • ハッシュ関数には性能が良く衝突が少ないものを使う
  • 衝突は起こるものとして考える

■参考

文字列のハッシュ値の計算として以下のようなものもあるらしい。

var key = function(str){
    var hash = 0;
    for(var i = 0; i < str.length; i++){
        hash += Math.pow(31, str.length - i - 1) * str[i].charCodeAt(0);
    }
    return hash;
}

しかし上述の関数でも20万語を通すと衝突が発生し、最大で7単語が衝突する。

JavaScriptで二分探索

集団が予め整列されている時の探索。

■実装

var a =  [0, 3, 6, 9, 12, 15, 18, 21, 24, 27];


var search = function(ary, elm){
    low  = 0;
    high = ary.length - 1;
    while(low <= high){
        var i = Math.floor((low + high) / 2);
        if(ary[i] === elm){
            return i;
        }
        else if(ary[i] > elm){
            high = i - 1;
        }
        else{
            low = i + 1;
        }
    }
    return -1;
};


console.log(a.toString());
console.log(search(a, 6));

■特性

  • 電話帳や名簿など予め整列された集合に対して有用である
  • 最良時にO(1)、平均と最悪時の計算コストはO(log n)となる

JavaScriptでシーケンシャル探索

■実装

まぁ、簡単すぎるけど一応書いておく。

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}


var search = function(ary, elm){
    for(var i = 0; i < ary.length; i++){
        if(ary[i] === elm){
            return i;
        }
    }
    return -1;
};


console.log(a.toString());
console.log(search(a, 5));

■特性

  • 整列していない要素の少ない配列に対して有効
  • 殆どの場合で-1を返すような場合、違ったアルゴリズムを検討するべき
  • 最良時は配列の先頭に要素がある場合で計算量はO(1)
  • 最悪時は配列の最後尾に要素がある場合で計算量はO(n)
  • 平均すると配列の中央まで探索することになり計算量はO(n)
  • 探索が成功した場合に要素を先頭や最後尾に移動させることにより、複数回の探索時の性能をあげられる可能性がある

JavaScriptでバケツソート

■実装

var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
array = a.concat();


/**
 * bucketSort
 * @param {array} ary
 */
var bucketSort = function(ary){
    var hash = function(value){
        return Math.floor(value / 3);
    }// hash関数
    
    var bucket = [];
    for(var i = 0; i < ary.length; i++){
        if(!bucket[hash(ary[i])]){
            bucket[hash(ary[i])] = [ary[i]];
        }
        else{
            bucket[hash(ary[i])].push(ary[i]);
        }
    }// bucket配列に格納(各bucketは配列となっている)
    console.log(JSON.stringify(bucket));
    
    // 衝突したbucket内で挿入ソート
    for(var i = 0; i < bucket.length; i++){
        for(var i2 = 1; i2 < bucket[i].length; i2++){
            var value = bucket[i][i2];
            for(var i3 = i2 - 1; i3 >= 0; i3--){
                if(value <= bucket[i][i3]){
                    bucket[i][i3 + 1] = bucket[i][i3];
                }
                else{
                    break;
                }
            }
            bucket[i][i3 + 1] = value;
        }
    }
    console.log(JSON.stringify(bucket));
    
    // bucketの先頭の要素から取り出し、元の配列を上書きする
    var store = 0;
    for(var i = 0; i < bucket.length; i++){
        if(bucket[i]){
            for(var i2 = 0; i2 < bucket[i].length; i2++){
                ary[store++] = bucket[i][i2];
            }
        }
    }
}


bucketSort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());
// ハッシュ関数と要素の分布によって衝突することもある
// 以下がハッシュ関数に対して理想的な分布だった場合
// var a = [15, 21, 9, 27, 3, 12, 18, 24, 6, 0];
// [[0],[3],[6],[9],[12],[15],[18],[21],[24],[27]]
// 以下が衝突が起こった場合
// var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
// [[0,1,2],[3,4,5],[6,7,8],[9]]
// 衝突が起こると挿入ソートの回数が増えて性能が低下する

■特性

  • 高速ハッシュ関数を使って、要素が一様に分割できる必要がある

JavaScriptで数え上げソート

データが取り得る値の範囲が分かっている場合、O(n log n)の限界を超えて、O(n)の計算量でソートできる。

■実装

var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
array = a.concat();


/**
 * countingSort
 * @param {array} ary
 * @param {int} max
 */
var countingSort = function(ary, max){
    var bucket = [];
    for(var i = 0; i <= max; i++){
        bucket.push(0);
    }// バケツの準備
    for(var i = 0; i < ary.length; i++){
        bucket[ary[i]]++;
    }// i番目の要素に与えられた配列の要素値iの出現回数が記録される
    
    var store = 0;
    for(var i = 0; i <= max; i++){
        while(bucket[i]-- > 0){
            ary[store++] = i;
        }
    }// 出現回数に応じて元の配列を上書きする
}


countingSort(a, 9);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());
//before : 5,7,3,9,1,4,6,8,2,0
//after  : 0,1,2,3,4,5,6,7,8,9

■特性

  • 要素の値に重複があっても良い
  • 要素の値が取り得る最大値が分からなくてはならない
  • 計算量はO(n)である

JavaScriptでヒープソート

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * swap
 * @param {array} ary
 * @param {int} x
 * @param {int} y
 */
var swap = function(ary, x, y){
    console.log(ary.toString());
    var a = ary[x];
    var b = ary[y];
    ary[x] = b;
    ary[y] = a;
    console.log(ary.toString());
    console.log('---');
    return true;
}

/**
 * heapify
 * 3要素を比較し最も大きい要素を親とする
 * @param {array} ary
 * @param {int} i
 * @param {max} max
 */
var heapify = function(ary, i, max){
    var l = 2 * i + 1;
    var r = 2 * i + 2;
    var li = 0;
    if(l < max && ary[l] > ary[i]){
        li = l;
    }
    else{
        li = i;
    }
    if(r < max && ary[r] > ary[li]){
        li = r;
    }
    if(li !== i){
        swap(ary, i, li);// 比較した3要素の最大値を親に移動…(a)
        heapify(ary, li, max);
        /*(a)によりiの子孫(孫以下)のノードでヒープが崩れた可能性がある*/
        /*従って、aryのヒープ特性を保持するため、leaf方向に向けて再帰でheapify*/
    }
}

/**
 * buildHeap
 * 子を持つ要素のうち最も大きいインデックスを持つ要素より前をheapifyする
 * @param {array} ary
 */
var buildHeap = function(ary){
    for(var i = Math.floor(ary.length / 2) - 1; i >= 0; i--){
        heapify(ary, i, n);
    }
}

/**
 * hsort
 * @param {array} ary
 */
var hsort = function(ary){
    buildHeap(ary);// 初期のヒープ構造を生成
    for(var i = ary.length - 1; i > 0; i--){
        swap(ary, 0, i);// 先頭の最大値と最後尾の要素をswap
        heapify(ary, 0, i);// 最後尾の要素を除いてヒープ構造を再構築
    }
}


hsort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

  • データの出現順序による計算量の変化が小さく、計算量はO(n log n)となる
  • 要素を頻繁に入れ替える
  • 安定整列ではない