PHPでセッションの有効期限を設定する
session.gc_maxlifetime
TrackBack URL :
Comments (0)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)
TrackBack URL :
Comments (0)root宛のメールを他のユーザに転送する
以下のコマンドで設定ファイルを編集する。
vi /etc/aliases
以下の記述を
#root:marc
以下のように変更すると、hogeユーザ（hoge@ドメイン）にroot宛のメールがすべて転送される。
root:hoge
ファイルの編集が終わったら忘れずに以下のコマンドを実行する。
postalias hash:/etc/aliases
設定ファイルにはメールアドレスを記述することもできるようだ。
TrackBack URL :
Comments (0)sshのポートを変更する
ロシアや中国のサーバから不正ログインを試みるアクセスが多いので変更することをお勧めする。
■設定
ファイアーウォールの変更
変更する予定のポートを開いておくこと。もし間違えた場合はサーバまで出向いて直接設定を修正するハメになる。
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
■アクセス
再起動したらターミナルを閉じないで、新しくターミナルを起動し設定したポートでアクセスできることを確認してから元々開いていた方のターミナルを閉じる事。もし、新しい設定で接続できない場合は、元々開いていた方のターミナルで設定を修正する。
TrackBack URL :
Comments (0)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単語が衝突する。
TrackBack URL :
Comments (0)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)となる
TrackBack URL :
Comments (0)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)
- 探索が成功した場合に要素を先頭や最後尾に移動させることにより、複数回の探索時の性能をあげられる可能性がある
TrackBack URL :
Comments (0)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]]
// 衝突が起こると挿入ソートの回数が増えて性能が低下する
■特性
- 高速ハッシュ関数を使って、要素が一様に分割できる必要がある
TrackBack URL :
Comments (0)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)である
TrackBack URL :
Comments (0)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)となる
- 要素を頻繁に入れ替える
- 安定整列ではない
TrackBack URL :
Comments (0)