PHPでセッションの有効期限を設定する

投稿日時: 2010 年 10 月 31 日投稿者: admin

session.gc_maxlifetime

JavaScriptでマージソート

投稿日時: 2010 年 10 月 30 日投稿者: admin

返信

■実装

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)

root宛のメールを他のユーザに転送する

投稿日時: 2010 年 10 月 30 日投稿者: admin

返信

以下のコマンドで設定ファイルを編集する。

vi /etc/aliases

以下の記述を

#root:marc

以下のように変更すると、hogeユーザ（hoge@ドメイン）にroot宛のメールがすべて転送される。

root:hoge

ファイルの編集が終わったら忘れずに以下のコマンドを実行する。

postalias hash:/etc/aliases

設定ファイルにはメールアドレスを記述することもできるようだ。

sshのポートを変更する

投稿日時: 2010 年 10 月 30 日投稿者: admin

返信

ロシアや中国のサーバから不正ログインを試みるアクセスが多いので変更することをお勧めする。

■設定

ファイアーウォールの変更

変更する予定のポートを開いておくこと。もし間違えた場合はサーバまで出向いて直接設定を修正するハメになる。

system-config-securitylevel-tui

別解

以下のコマンドでiptablesを直接編集する。

vi /etc/sysconfig/iptables

以下のラインを

-A RH-Firewall-1-INPUT -m state --state NEW -m tcp -p tcp --dport 22 -j ACCEPT

以下のように編集する。

-A RH-Firewall-1-INPUT -m state --state NEW -m tcp -p tcp --dport 2022 -j ACCEPT

以下のコマンドでおiptablesを再起動する。

/etc/init.d/iptables restart

ちなみにstatusで現在の設定を確認できる。

/etc/init.d/iptables status

但し、system-config-securitylevel側に変更は反映されないので注意が必要。

設定ファイルの変更

以下のコマンドを実行し設定ファイルを編集する。

vi /etc/ssh/sshd_config

以下のラインを

Port 22

以下のように編集する。

Port 2022

sshdの再起動

以下のコマンドを実行してsshdを再起動する。

/etc/rc.d/init.d/sshd restart

■アクセス

再起動したらターミナルを閉じないで、新しくターミナルを起動し設定したポートでアクセスできることを確認してから元々開いていた方のターミナルを閉じる事。もし、新しい設定で接続できない場合は、元々開いていた方のターミナルで設定を修正する。

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

投稿日時: 2010 年 10 月 29 日投稿者: admin

返信

■実装

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で二分探索

投稿日時: 2010 年 10 月 29 日投稿者: admin

返信

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

■実装

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でシーケンシャル探索

投稿日時: 2010 年 10 月 29 日投稿者: admin

返信

■実装

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

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でバケツソート

投稿日時: 2010 年 10 月 27 日投稿者: admin

返信

■実装

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で数え上げソート

投稿日時: 2010 年 10 月 27 日投稿者: admin

返信

データが取り得る値の範囲が分かっている場合、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でヒープソート

投稿日時: 2010 年 10 月 26 日投稿者: admin

返信

■実装

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)となる
要素を頻繁に入れ替える
安定整列ではない

@blog.justoneplanet.info

日々勉強

月別アーカイブ: 2010年10月

PHPでセッションの有効期限を設定する

JavaScriptでマージソート

■実装

■特性

root宛のメールを他のユーザに転送する

sshのポートを変更する

■設定

ファイアーウォールの変更

別解

設定ファイルの変更

sshdの再起動

■アクセス

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

■実装

■特性

■ポイント

■参考

JavaScriptで二分探索

■実装

■特性

JavaScriptでシーケンシャル探索

■実装

■特性

JavaScriptでバケツソート

■実装

■特性

JavaScriptで数え上げソート

■実装

■特性

JavaScriptでヒープソート

■実装

■特性