yoshida_eth0の日記 このページをアンテナに追加 RSSフィード

2010-10-24

Ruby on RailsでMySQL Clusterの使えるようにするプラグインを作ってみた

似たようなプラグインもいくつかあったけど、どれもしっくり来なかったから自分で作った。

その名も「Mysql Cluster Adapter」。

 

eth0jp's activerecord-mysql_cluster_adapter at master - GitHub

http://github.com/eth0jp/activerecord-mysql_cluster_adapter

 

MySQL Cluster Adapterの機能

複数Writableに対応

ただReadOnly機能がないだけだけど。

※マルチマスターレプリケーション対応ではない。

 

クラスタリング・自動復旧

リクエストが来た時にランダムで使うノードを選択する。

もし選択したノードが死んでいたら再接続を試みて、接続出来なかったら次のノードを選択する。

全てのノードが死んでたら500エラー。

 

トランザクション

トランザクションを有効にするために、1つのリクエストでは必ず同じノードに接続するようにする。

そのため、リクエストが送られてからノードが死んだ場合は500エラーをレスポンスする事になる。

 

ユーザビリティ

プラグインを使う人が意識せずに使える。

config/database.ymlが書き方が違うだけで、プログラム側は通常のMySQLアダプタと同じ。

 

設定ファイル

config/database.yml
production:
  adapter: mysql_cluster
  nodes:
    - database: clusterdb
      host: 192.168.1.10
      username: root
      password: pass
      encoding: utf8
    - database: clusterdb
      host: 192.168.1.20
      username: root
      password: pass
      encoding: utf8

development:
  adapter: mysql_cluster
  nodes:
    - database: clusterdb_dev
      host: 192.168.1.10
      username: root
      password: pass
      encoding: utf8
    - database: clusterdb_dev
      host: 192.168.1.20
      username: root
      password: pass
      encoding: utf8

 

インストール

./script/plugin install git://github.com/eth0jp/activerecord-mysql_cluster_adapter.git

 

動作確認バージョン

Ruby 1.8.5

ActiveRecord 2.3.5

 

参考URL

ActiveRecord

ActiveRecordのDBコネクションの接続切れと再接続について。reconnectオプションは危険だなーとかも - odeの開発メモ日記

http://d.hatena.ne.jp/ode/20100809/1281336400

 

データベースに接続できない場合の流れを追ってみた - remind::me

http://d.hatena.ne.jp/kenshoster/20090127/1233041004

 

トランザクション

トランザクション - うなの日記

http://d.hatena.ne.jp/unageanu/20070526/1180148785

 

Ruby on Rails - ActiveRecord - ? ありえるえりあ

http://dev.ariel-networks.com/articles/workshop/rails-activerecord

 

似たようなプラグイン

acts_as_readonlyable

マスタースレーブ構成を想定したプラグイン。

モデルごとにMaster/Slaveを決める。

class Fruit < ActiveRecord::Base
  acts_as_readonlyable :read_only
end

 

Revolution On Rails: [PLUGIN RELEASE] ActsAsReadonlyable

http://revolutiononrails.blogspot.com/2007/04/plugin-release-actsasreadonlyable.html

 

dbのマスタースレーブに対応するためにacts_as_readonlyableを使ってみる - odeの開発メモ日記

http://d.hatena.ne.jp/ode/20090109/1231496360

 

mysql_replication_adapter

マスタースレーブ構成を想定したプラグイン。

SQLごとにMaster/Slaveを決める。

MyModel.find(:all, :use_slave => true)

 

Mysql Replication Adapter | Engineering Rapleaf

http://blog.rapleaf.com/dev/2007/08/12/mysql-replication-adapter/

 

findchris's mysql_replication_adapter at master - GitHub

http://github.com/findchris/mysql_replication_adapter

 

magic_multi_connections

最近のバージョンのRailsでは動かないみたい。

 

Magic Multi-Connections

http://magicmodels.rubyforge.org/magic_multi_connections/

2010-10-19

テントモンをカブテリモンに進化させるプログラムを作ってみた

デジモンアドベンチャー5話「電光!カブテリモン」で光子郎がX-Basic(と思われる言語)でテントモンをカブテリモンに進化させていた。

これが何をするものなのか気になって、JavaScriptに移植してみた。

fractalっていう再帰的関数を定義してあるからどんなかっこいい図が出来るんだろうと期待したけど、拍子抜けだった。

それにしても光子郎、小学4年生でこれは頭良すぎるんじゃないか。

 

今回始めてJavaScriptのPrototypeを弄った。

これは面白い。

図形描画にはHTML5のCanvasを使った。

 

実行結果

Firefox 3.6.10で動作確認。

1から2までのfloat値を入力する。

http://g-storage.appspot.com/share/eth0jp/digimon_evolution.html

 

JavaScript版

function Tentomon() {};
Tentomon.prototype = {
	s : 0,

	evolution : function() {
		this.s = 0;
		while (isNaN(this.s) || this.s<1 || this.s>=2) {
			this.s = parseFloat(prompt("ratio 1 to 2", ""));
		}
		this.s = (this.s - 1) / 10 + 1;
		this.screen(1, 2, 1, 1);
		this.s = Math.sqrt(this.s * this.s - 1);
		var x0 = 100, x1 = 412, y0 = 0, y1 = 0;
		this.fractal(x0, x1, y0, y1);
		this.line(100, 50, 412, 50, 255, 65535);
	},

	fractal : function(x0, x1, y0, y1, sp) {
		var l, r, x2, y2;
		l = Math.sqrt((x1-x0) * (x1-x0) + (y1-y0) * (y1-y0))
		if (l<2 || sp>=0) {
			this.line(x0, y0/3+50, x1, y1/3+50, 255, 65535); return;
		}
		r = Math.random() + Math.random() + Math.random() - 2;
		x2 = (x0+x1)/2 + this.s * (y1-y0) * r;
		y2 = (y0+y1)/2 + this.s * (x1-x0) * r;
		sp = sp + 1;
		this.fractal(x0, x2, y0, y2, sp);
		this.fractal(x2, x1, y2, y1, sp);
	},

	screen : function(size, mode, resolution, graphic) {
		var canvas = document.createElement('canvas');
		var width = 512;
		var height = 512;
		canvas.id = "canvas";
		canvas.setAttribute('width', width + 'px');
		canvas.setAttribute('height', height + 'px');
		canvas.style.cssText = 'position: absolute; top: 0; left: 0; z-index: 100;';
		document.body.appendChild(canvas);
	},

	line : function(x1, y1, x2, y2, p, ls) {
		var canvas = document.getElementById('canvas');
		var context = canvas.getContext('2d');
		context.beginPath();
		context.moveTo(x1, y1);
		context.lineTo(x2, y2);
		context.stroke();
	}
};

window.addEventListener('load', function(){new Tentomon().evolution();}, false);

 

X-Basic

X-Basicやった事ないからもしかしたら間違えてる部分あるかも。

100 /* func sample. coast creation */
110 float s
120 while s<1 or s>=2
130     input "ratio 1 to 2";s
140 endwhile
150 s = (s - 1) / 10 + 1
160 screen 1, 2, 1, 1
170 s = sqr(s * s - 1)
180 float x0 = 100, x1 = 412, y0 = 0, y1 = 0
190 fractal(x0, x1, y0, y1)
200 line(100, 50, 412, 50, 255, 65535)
210 end
220 func fractal(x0:float, x1:float, y0:float, y1:float, sp:int)
230     float l, r, x2, y2
240     l = sqr((x1-x0) * (x1-x0) + (y1-y0) * (y1-y0))
250     if l<2 or sp>=0 then {
260         line(x0, y0/3+50, x1, y1/3+50, 255, 65535) ; return()
270     }
280     r = rnd() + rnd() + rnd() - 2
290     x2 = (x0+x1)/2 + s * (y1-y0) * r
300     y2 = (y0+y1)/2 + s * (x1-x0) * r
310     sp = sp + 1
320     fractal(x0, x2, y0, y2, sp)
330     fractal(x2, x1, y2, y1, sp)
340 endfunc

2010-10-16

rake db:migrateでcreate_tableする時のストレージエンジンを指定するプラグイン作った

データベースをrakeで管理する場合、ストレージエンジンを指定してテーブルを作る時は、いちいちこんなのを書かなきゃいけない。

ちょっとした事なんだけど、非常に面倒くさい。

create_table :table_name, :options => "engine=MyISAM"

 

何かいい方法はないか調べたけど解決策はなさそう。

同じ所で困ってる方がいて、その方の記事が詳しかった。

 

migrateでストレージエンジンを指定 - よかろうもん!

http://d.hatena.ne.jp/interu/20080331/1206977231

 

記事はちょっと古いけど、現在我が家で使ってるActiveRecord 2.3.5もInnoDBをべた書きなのは変わってなかった。

      def create_table(table_name, options = {}) #:nodoc:
        super(table_name, options.reverse_merge(:options => "ENGINE=InnoDB"))
      end

 

で、それを解消するプラグインを作った。

 

出来る事は、

・指定したストレージエンジンをデフォルトとして使う。

・指定したストレージエンジンを強制する。

の2つ。

 

RedmineとかオープンソースのものでMySQL Clusterを使いたい時に、ndbclusterを強制すればいい感じに動く。(かも知れない)

まだRuby on Rails始めてから数週間だけど、なんだか楽しくなってきた。

 

eth0jp's activerecord-engine_spec at master - GitHub

http://github.com/eth0jp/activerecord-engine_spec

 

インストール

確かこんな感じだった気がする。

sudo yum install git
sudo gem install newgem
./script/plugin install git://github.com/eth0jp/activerecord-engine_spec.git

 

設定ファイルサンプル

config/initializersディレクトリの中にファイルを作る。

 

MyISAMをデフォルトのストレージエンジンとして指定する。

create_table呼び出し側でエンジンの指定があった場合は何もしない。

require 'active_record/engine_spec'

ActiveRecord::EngineSpec.engine = :MyISAM
ActiveRecord::EngineSpec.force = false

 

NDB Clusterをストレージエンジンとして使う事を強制する。

create_table呼び出し側でエンジンの指定があっても強制的に上書きする。

require 'active_record/engine_spec'

ActiveRecord::EngineSpec.engine = :ndbcluster
ActiveRecord::EngineSpec.force = true

 

migration実行結果

[root@localhost tmp]# rails testproj
[root@localhost tmp]# cd testproj/
[root@localhost testproj]# ./script/plugin install git://github.com/eth0jp/activerecord-engine_spec.git
[root@localhost testproj]# cat <<-'ENGINE_SPEC' > config/initializers/engine_spec.rb
> require 'active_record/engine_spec'
> ActiveRecord::EngineSpec.engine = :ndbcluster
> ActiveRecord::EngineSpec.force = true
> ENGINE_SPEC
[root@localhost testproj]# vi config/database.yml
[root@localhost testproj]# ./script/generate model test_model
[root@localhost testproj]# rake db:migrate
(in /tmp/testproj)
==  CreateTestModels: migrating ===============================================
-- create_table(:test_models, {:options=>" engine=ndbcluster"})
   -> 0.3325s
==  CreateTestModels: migrated (0.3327s) ======================================

[root@localhost testproj]# mysql -hxxx -uxxx -pxxx xxx
mysql> show create table test_models;
+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table       | Create Table
|
+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| test_models | CREATE TABLE `test_models` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `created_at` datetime DEFAULT NULL,
  `updated_at` datetime DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=ndbcluster DEFAULT CHARSET=utf8 |
+-------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

2010-10-12

ソートアルゴリズムについて調べてみた

結構な量のソートアルゴリズムをやってみた。

ここら辺を参考に。

 

ソート - Wikipedia

http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88

 

ヒープソートは、かなり短くした。

可読性は酷いもんだ。

 

気が向いたら他のアルゴリズムも追記するかも知れない。

 

実行結果

$ php ArraySort.php
array count: 100
sort time: 0.0000970364
----------------------------------------
o bubbleSort                0.0033838749
o cocktailSort              0.0030219555
o oddEvenSort               0.0033051968
o combSort                  0.0007081032
o gnomeSort                 0.0035710335
o quickSort                 0.0007450581
o selectionSort             0.0014488697
o heapSort                  0.0028982162
o smoothSort                0.0220639706
- cartesianTreeSort         0.0000030994
o tournamentSort            0.0256109238
o cycleSort                 0.0067420006
o insertionSort             0.0011010170
o binaryInsertionSort       0.0010468960
o shellSort                 0.0004940033
o treeSort                  0.0109040737
o librarySort               0.0018830299
o patienceSort              0.0018470287
o mergeSort                 0.0016689301
- polyphaseMergeSort        0.0000030994
o strandSort                0.0016798973
o timSort                   0.0216958523
o radixSort                 0.0009479523
o bucketSort                0.0001828671
o countingSort              0.0001790524
o pigeonholeSort            0.0002150536
- burstSort                 0.0000028610
- beadSort                  0.0000030994
- topologicalSort           0.0000019073
o bitonicSort               0.0220050812
o batcherOddEvenMergeSort   0.0182960033
o pancakeSort               0.0044078827
x bogoSort                  0.0032398701
o stoogeSort                0.4778499603

 

ソース

ArraySort.php
<?php

ArraySort::test();


class ArraySort
{
	/* test*/

	public static function test($size=100)
	{
		$arr = array();
		for ($i=0; $i<$size; $i++) {
			$arr[] = mt_rand(0, 100);
		}
		$valid = $arr;

		$b = microtime(1);
		sort($valid, SORT_NUMERIC);
		printf("array count: %d\n", count($arr));
		printf("sort time: %.10f\n", microtime(1) - $b);
		echo "----------------------------------------\n";

		$algos = get_class_methods("ArraySort");
		foreach ($algos as $algo) {
			if (substr($algo, -4)=='Sort') {
				$result = null;
				$bench = microtime(true);
				try {
					$result = ArraySort::$algo($arr);
				} catch (Exception $e) {
				}
				$bench = microtime(true) - $bench;
				$status = $result ? (self::isSorted($result) ? 'o' : 'x') : '-';
				printf("%s %-25s %.10f\n", $status, $algo, $bench);
/*
				if ($status=='x') {
					print_r($result);
				}
*/
			}
		}
	}


	/* 交換ソート */

	// バブルソート
	public static function bubbleSort(array $array)
	{
		$n = count($array) - 1;
		for ($i=0; $i<$n; $i++) {
			for ($j=$n; $i<$j; $j--) {
				if ($array[$j]<$array[$j-1]) {
					list($array[$j], $array[$j-1]) = array($array[$j-1], $array[$j]);
				}
			}
		}
		return $array;
	}

	// シェーカーソート
	public static function cocktailSort(array $array)
	{
		$left = 0;
		$right = count($array) - 1;
		while ($left<$right) {
			for ($i=$left; $i<$right; $i++) {
				if ($array[$i+1]<$array[$i]) {
					list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
					$change = $i;
				}
			}
			$right = $change;
			for ($i=$right; $left<$i; $i--) {
				if ($array[$i]<$array[$i-1]) {
					list($array[$i], $array[$i-1]) = array($array[$i-1], $array[$i]);
					$change = $i;
				}
			}
			$left = $change;
		}
		return $array;
	}

	// 奇偶転置ソート
	public static function oddEvenSort(array $array)
	{
		$flag = true;
		$n = count($array) - 1;
		while ($flag) {
			$flag = false;
			for ($i=0; $i<$n; $i+=2) {
				if ($array[$i+1]<$array[$i]) {
					list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
					$flag = true;
				}
			}
			for ($i=1; $i<$n; $i+=2) {
				if ($array[$i+1]<$array[$i]) {
					list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
					$flag = true;
				}
			}
		}
		return $array;
	}

	// コムソート
	public static function combSort(array $array)
	{
		$count = count($array);
		$h = floor($count / 1.3);
		while (true) {
			$swap = false;
			for ($i=0; $i+$h<$count; $i++) {
				if ($array[$i+$h]<$array[$i]) {
					list($array[$i], $array[$i+$h]) = array($array[$i+$h], $array[$i]);
					$swap = true;
				}
			}
			if ($h==1) {
				if (!$swap) {
					break;
				}
			} else {
				$h = floor($h / 1.3);
			}
		}
		return $array;
	}

	// ノームソート
	public static function gnomeSort(array $array)
	{
		$count = count($array) -1;
		for ($i=0; $i<$count; $i++) {
			if ($array[$i+1]<$array[$i]) {
				list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
				if (0<$i) {
					$i -= 2;
				}
			}
		}
		return $array;
	}

	// クイックソート
	public static function quickSort(array $array)
	{
		$count = count($array);
		if ($count<=1) {
			return $array;
		}
		$pivot = $array[0];
		$left = array();
		$right = array();
		for ($i=1; $i<$count; $i++) {
			if ($array[$i]<=$pivot) {
				$left[] = $array[$i];
			} else {
				$right[] = $array[$i];
			}
		}
		$left = self::quickSort($left);
		$right = self::quickSort($right);
		return array_merge($left, array($pivot), $right);
	}


	/* 選択ソート */

	// 選択ソート
	public static function selectionSort(array $array)
	{
		$count = count($array);
		for ($i=0; $i<$count-1; $i++) {
			$min = $i;
			for ($j=$i+1; $j<$count; $j++) {
				if ($array[$j]<$array[$min]) {
					$min = $j;
				}
			}
			list($array[$i], $array[$min]) = array($array[$min], $array[$i]);
		}
		return $array;
	}

	// ヒープソート
	public static function heapSort(array $array)
	{
		$count = count($array);
		for ($i=0; $i<$count; $i++) {
			$root = floor(($count - $i) / 2) - 1;
			for ($j=$root; 0<=$j; $j--) {
				// 左下
				if ($array[$j*2+1+$i]<$array[$j+$i]) {
					list($array[$j+$i], $array[$j*2+1+$i]) = array($array[$j*2+1+$i], $array[$j+$i]);
				}
				// 右下
				if (isset($array[$j*2+2+$i]) && $array[$j*2+2+$i]<$array[$j+$i]) {
					list($array[$j+$i], $array[$j*2+2+$i]) = array($array[$j*2+2+$i], $array[$j+$i]);
				}
			}
		}
		return $array;
	}

	// スムースソート
	public static function smoothSort(array $array)
	{
		require_once 'SmoothSort.php';
		SmoothSort::sort($array);
		return $array;
	}

	// デカルト木ソート
	public static function cartesianTreeSort(array $array)
	{
		// todo
	}

	// トーナメントソート
	public static function tournamentSort(array $array)
	{
		require_once 'TournamentSort.php';
		TournamentSort::sort($array);
		return $array;
	}

	// サイクルソート
	public static function cycleSort(array $array)
	{
		for ($cycleStart=0; $cycleStart<count($array)-1; $cycleStart++) {
			$item = $array[$cycleStart];

			$pos = $cycleStart;
			for ($i=$cycleStart+1; $i<count($array); $i++) {
				if ($array[$i]<$item) {
					$pos++;
				}
			}

			if ($pos==$cycleStart) {
				continue;
			}

			while ($item==$array[$pos]) {
				$pos++;
			}
			list($array[$pos], $item) = array($item, $array[$pos]);

			while ($pos!=$cycleStart) {
				$pos = $cycleStart;
				for ($i=$cycleStart+1; $i<count($array); $i++) {
					if ($array[$i]<$item) {
						$pos++;
					}
				}
				while ($item==$array[$pos]) {
					$pos++;
				}
				list($array[$pos], $item) = array($item, $array[$pos]);
			}
		}
		return $array;
	}


	/* 挿入ソート */

	// 挿入ソート
	public static function insertionSort(array $array)
	{
		$count = count($array);
		for ($i=1; $i<$count; $i++) {
			$tmp = $array[$i];
			if ($tmp<$array[$i-1]) {
				$j = $i;
				while (0<$j && $tmp<$array[$j-1]) {
					$array[$j] = $array[$j-1];
					$j--;
				}
				$array[$j] = $tmp;
			}
		}
		return $array;
	}

	// 二分挿入ソート
	public static function binaryInsertionSort(array $array)
	{
		$count = count($array);
		for ($i=1; $i<$count; $i++) {
			$tmp = $array[$i];
			$k = self::binarySearchPos($array, $tmp, 0, $i);
			for ($j=$i; $k<$j; $j--) {
				$array[$j] = $array[$j-1];
			}
			$array[$j] = $tmp;
		}
		return $array;
	}

	// シェルソート
	public static function shellSort(array $array)
	{
		static $incs = array(1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1);
		$n = count($array);
		for ($k=0; $k<16; $k++) {
			$h = $incs[$k];
			for ($i=$h; $i<$n; $i++) {
				$v = $array[$i];
				$j = $i;
				while ($h<=$j && $v<$array[$j-$h]) {
					$array[$j] = $array[$j-$h];
					$j = $j-$h;
				}
				$array[$j] = $v;
			}
		}
		return $array;
	}

	// ツリーソート
	public static function treeSort(array $array)
	{
		require_once 'BinaryTree.php';
		$bt = new BinaryTree();
		for ($i=0; $i<count($array); $i++) {
			$bt->add($array[$i]);
		}
		return $bt->traverse();
	}

	// ライブラリソート
	public static function librarySort(array $array)
	{
		$size = 4;
		$libraryElements = array();
		$gapCounter = array();

		if (count($array)<=1) {
			return $array;
		}

		// min_element
		$libraryElements[0] = INF;
		for ($i=0; $i<count($array); $i++) {
			if ($array[$i]<$libraryElements[0]) {
				$libraryElements[0] = $array[$i];
			}
		}
		$gapCounter[0] = false;

		// max_element
		$libraryElements[$size-1] = -INF;
		for ($i=0; $i<count($array); $i++) {
			if ($libraryElements[$size-1]<$array[$i]) {
				$libraryElements[$size-1] = $array[$i];
			}
		}
		$gapCounter[$size-1] = false;

		for ($insertPos=0; $insertPos<count($array); $insertPos++) {
			if (($insertPos & ($insertPos+1)) == 0) {
				$size = (($size - 1) * 2 + 1);

				// resize
				for ($i=0; $i<$size; $i++) {
					if (!isset($libraryElements[$i])) {
						$libraryElements[$i] = 0;
						$gapCounter[$i] = true;
					}
				}

				for ($i=$size-1; 0<=$i; $i--) {
					if ($i%2==0) {
						$libraryElements[$i] = $libraryElements[$i>>1];
						$gapCounter[$i] = $gapCounter[$i>>1];
					} else {
						$gapCounter[$i] = true;
					}
				}
			}

			$left = 0;
			$right = $size-1;
			$leftScanPos = 0;
			$rightScanPos = 0;
			while ($left<=$right) {
				$middle = ($left + $right) >> 1;

				if ($gapCounter[$middle]) {
					$leftScanPos = $middle;
					$rightScanPos = $middle;

					while (true) {
						$leftScanPos--;
						$rightScanPos++;
						if ($left<=$leftScanPos && $gapCounter[$leftScanPos]==false) {
							$middle = $leftScanPos;
							break;
						}
						if ($rightScanPos<=$right && $gapCounter[$rightScanPos]==false) {
							$middle = $rightScanPos;
							break;
						}
						if ($leftScanPos<=$left && $right<=$rightScanPos) {
							break 2;
						}
					}
				}

				if ($libraryElements[$middle]<=$array[$insertPos]) {
					$left = ++$middle;
				} else {
					$right = --$middle;
				}
				$middle = $right;
			}

			if ($gapCounter[$middle]!=true) {
				$leftScanPos = $middle;
				$rightScanPos = $middle;

				while (true) {
					$leftScanPos--;
					$rightScanPos++;
					if (0<=$leftScanPos && $gapCounter[$leftScanPos]) {
						for ($i=$leftScanPos; $i<$middle; $i++) {
							$libraryElements[$i] = $libraryElements[$i+1];
						}
						$gapCounter[$leftScanPos] = false;
						break;
					}
					if ($rightScanPos<$size && $gapCounter[$rightScanPos]) {
						$middle++;
						for ($i=$rightScanPos; $middle<$i; $i--) {
							$libraryElements[$i] = $libraryElements[$i-1];
						}
						$gapCounter[$rightScanPos] = false;
						break;
					}
				}
			}

			$libraryElements[$middle] = $array[$insertPos];
			$gapCounter[$middle] = false;
		}

		$isFirstElement = true;
		$insertPos = 0;
		for ($i=0; $i<$size && $insertPos<count($array); $i++) {
			if ($gapCounter[$i]==false) {
				if ($isFirstElement) {
					$isFirstElement = false;
				} else {
					$array[$insertPos] = $libraryElements[$i];
					$insertPos++;
				}
			}
		}

		return $array;
	}

	// ペイシェンスソート
	public static function patienceSort(array $array)
	{
		$piles = array();

		for ($insertPos=0; $insertPos<count($array); $insertPos++) {
			$middle = 0;
			$left = 0;
			$right = count($piles) - 1;

			while ($left<=$right) {
				$middle = (int)(($left+$right) / 2);
				if ($piles[$middle][count($piles[$middle])-1] < $array[$insertPos]) {
					$left = $middle + 1;
				} else {
					$right = $middle - 1;
				}
			}
			if (count($piles)<=$left) {
				// resize
				$piles[] = array();
			}
			$piles[$left][] = $array[$insertPos];
		}

		for ($insertPos=0; $insertPos<count($array); $insertPos++) {
			$array[$insertPos] = $piles[0][count($piles[0])-1];
			unset($piles[0][count($piles[0])-1]);

			if (count($piles[0])==0) {
				$piles[0] = $piles[count($piles)-1];
				unset($piles[count($piles)-1]);
			}

			$root = 0;
			$minChild = 0;
			while ($root<count($piles)) {
				$child1 = $root * 2 + 1;
				$child2 = $root * 2 + 2;

				if ($child1<count($piles) && $piles[$child1][count($piles[$child1])-1]<$piles[$minChild][count($piles[$minChild])-1]) {
					$minChild = $child1;
				}
				if ($child2<count($piles) && $piles[$child2][count($piles[$child2])-1]<$piles[$minChild][count($piles[$minChild])-1]) {
					$minChild = $child2;
				}
				if ($minChild!=$root) {
					list($piles[$root], $piles[$minChild]) = array($piles[$minChild], $piles[$root]);
					$root = $minChild;
				} else {
					break;
				}
			}
		}
		return $array;
	}


	/* マージソート */

	// マージソート
	public static function mergeSort(array $array)
	{
		if (count($array)<=1) {
			return $array;
		}
		if (count($array)==2) {
			return array(min($array), max($array));
		}
		$array1 = array();
		$array2 = array();
		foreach ($array as $i=>$item) {
			if ($i%2==0) {
				$array1[] = $item;
			} else {
				$array2[] = $item;
			}
		}
		$array1 = self::mergeSort($array1);
		$array2 = self::mergeSort($array2);
		$i1 = 0;
		$i2 = 0;
		$result = array();
		while ($i1<count($array1) || $i2<count($array2)) {
			if ($i1<count($array1) && $i2<count($array2)) {
				if ($array1[$i1]<$array2[$i2]) {
					$result[$i1+$i2] = $array1[$i1];
					$i1++;
				} else {
					$result[$i1+$i2] = $array2[$i2];
					$i2++;
				}
			} else if ($i1<count($array1)) {
				$result[$i1+$i2] = $array1[$i1];
				$i1++;
			} else if ($i2<count($array2)){
				$result[$i1+$i2] = $array2[$i2];
				$i2++;
			}
		}
		return $result;
	}

	// 多層マージソート
	public static function polyphaseMergeSort(array $array)
	{
		// todo
	}

	// ストランドソート
	public static function strandSort(array $array)
	{
		$result = array();

		while (count($array)) {
			$sublist = array();
			$sublist[] = array_shift($array);
			$last = count($sublist) - 1;
			foreach ($array as $i=>$value) {
				if ($sublist[$last]<$value) {
					$sublist[] = $value;
					unset($array[$i]);
					$last++;
				}
			}
			if (0<count($result)) {
				foreach ($sublist as $value) {
					$spliced = false;
					foreach ($result as $i=>$rvalue) {
						if ($value<$rvalue) {
							array_splice($result, $i, 0, $value);
							$spliced = true;
							break;
						}
					}
					if (!$spliced) {
						$result[] = $value;
					}
				}
			} else {
				$result = $sublist;
			}
		}
		return $result;
	}

	// ティムソート
	public static function timSort(array $array)
	{
		require_once 'TimSort.php';
		TimSort::sort($array);
		return $array;
	}


	/* 非比較ソート */

	// 基数ソート
	public static function radixSort(array $array)
	{
		$r = 0;
		for ($i=0; $i<count($array); $i++) {
			if ($r<$array[$i]) {
				$r = $array[$i];
			}
		}
		$rad = array();
		$tmp = array();
		$m = 1;
		$n = count($array);
		while ($m<=$r) {
			for ($i=0; $i<$n; $i++) {
				$rad[$i] = ($array[$i] / $m) % 10;
			}
			$k = 0;
			for ($i=0; $i<=9; $i++) {
				for ($j=0; $j<$n; $j++) {
					if ($rad[$j]==$i) {
						$tmp[$k++] = $array[$j];
					}
				}
			}
			$array = $tmp;
			$m *= 10;
		}
		return $array;
	}

	// バケットソート
	public static function bucketSort(array $array)
	{
		$n = count($array);
		$m = 0;
		for ($i=0; $i<$n; $i++) {
			if ($m<$array[$i]) {
				$m = $array[$i];
			}
		}
		$m++;
		$count = array_fill(0, $m, 0);
		$offset = array_fill(0, $m, 0);
		$result = array();
		for ($i=0; $i<$n; $i++) {
			$count[$array[$i]]++;
		}
		$offset[0] = 0;
		for ($i=1; $i<$m; $i++) {
			$offset[$i] = $offset[$i-1] + $count[$i-1];
		}
		for ($i=0; $i<$n; $i++) {
			$target = $array[$i];
			$result[$offset[$target]] = $target;
			$offset[$target]++;
		}
		return $result;
	}

	// カウンティングソート
	public static function countingSort(array $array)
	{
		$n = count($array);
		$min = $array[0];
		$max = $array[0];
		for ($i=1; $i<$n; $i++) {
			if ($array[$i]<$min) {
				$min = $array[$i];
			} else if ($max<$array[$i]) {
				$max = $array[$i];
			}
		}
		$range = $max - $min + 1;
		$count = array();
		for ($i=0; $i<$range; $i++) {
			$count[$i] = 0;
		}
		for ($i=0; $i<$n; $i++) {
			$count[$array[$i]-$min]++;
		}
		$z = 0;
		for ($i=$min; $i<=$max; $i++) {
			for ($j=0; $j<$count[$i-$min]; $j++) {
				$array[$z++] = $i;
			}
		}
		return $array;
	}

	// 鳩の巣ソート
	public static function pigeonholeSort(array $array)
	{
		if (count($array)<=1) {
			return $arrray;
		}

		$min = $array[0];
		$max = $array[0];
		foreach ($array as $value) {
			if ($value<$min) {
				$min = $value;
			}
			if ($max<$value) {
				$max = $value;
			}
		}

		$tmp = array();
		foreach ($array as $value) {
			if (!isset($tmp[$value-$min])) {
				$tmp[$value-$min] = 0;
			}
			$tmp[$value-$min]++;
		}

		$result = array();
		for ($i=0; $i<=$max-$min; $i++) {
			if (isset($tmp[$i])) {
				while (0 < $tmp[$i]--) {
					$result[] = $i+$min;
				}
			}
		}

		return $result;
	}

	// バーストソート
	public static function burstSort(array $array)
	{
		// todo
	}

	// ビーズソート
	public static function beadSort(array $array)
	{
		// todo
	}


	/* その他 */

	// トポロジカルソート
	public static function topologicalSort(array $array)
	{
		// todo
	}

	// バイトニックソート
	public static function bitonicSort(array $array)
	{
		require_once 'BitonicSort.php';
		BitonicSort::sort($array);
		return $array;
	}

	// バッチャー奇偶マージソート
	public static function batcherOddEvenMergeSort(array $array)
	{
		require_once 'BatcherOddEvenMergeSort.php';
		BatcherOddEvenMergeSort::sort($array);
		return $array;
	}

	// パンケーキソート
	public static function pancakeSort(array $array)
	{
		for ($i=count($array)-1; 0<$i; $i--) {
			$max_index = 0;
			$max = $array[0];
			for ($j=1; $j<=$i; $j++) {
				if ($max < $array[$j]) {
					$max_index = $j;
					$max = $array[$j];
				}
			}

			if ($max_index==$i) {
				continue;
			}

			$new_slice = array();
			if (0<$max_index) {
				$new_slice = array_reverse(array_slice($array, 0, $max_index+1));
				for ($j=0; $j<=$max_index; $j++) {
					$array[$j] = $new_slice[$j];
				}
			}

			$new_slice = array_reverse(array_slice($array, 0, $i+1));
			for ($j=0; $j<=$i; $j++) {
				$array[$j] = $new_slice[$j];
			}
		}
		return $array;
	}


	/* 効果なし ユーモラスソート */

	// ボゴソート
	public static function bogoSort(array $array, $loop=100)
	{
		shuffle($array);
		$loop--;
		if (!self::isSorted($array) && 0<$loop) {
			$array = self::bogoSort($array, $loop);
		}
		return $array;
	}

	// ストゥージソート
	public static function stoogeSort(array $array, $i=0, $j=null)
	{
		if (is_null($j)) {
			$j = count($array) - 1;
		}
		if ($array[$j]<$array[$i]) {
			list($array[$i], $array[$j]) = array($array[$j], $array[$i]);
		}
		if (1<$j-$i) {
			$t = (int)(($j - $i + 1) / 3);
			$array = self::stoogeSort($array, $i, $j-$t);
			$array = self::stoogeSort($array, $i+$t, $j);
			$array = self::stoogeSort($array, $i, $j-$t);
		}
		return $array;
	}


	/* 二分木 */

	// 二分探索 値のindexを返す
	public static function binarySearch(array $array, $value, $left=0, $right=null)
	{
		$pos = self::binarySearchPos($array, $value, $left, $right);
		if (0<$pos && $array[$pos-1]==$value) {
			return $pos-1;
		}
		return null;
	}

	// 二分木探索 値を追加するべき位置を返す
	public static function binarySearchPos(array $array, $value, $left=0, $right=null)
	{
		if (is_null($right)) {
			$right = count($array);
		}
		if ($right<$left) {
			list($left, $right) = array($right, $left);
		}

		while ($left<$right) {
			$middle = (int)(($left + $right) / 2);
			if ($array[$middle]<=$value) {
				$left = $middle + 1;
			} else {
				$right = $middle;
			}
		}
		return $right;
	}


	/* util */

	public static function isSorted(array $array)
	{
		$tmp = -INF;
		for ($i=0; $i<count($array); $i++) {
			if ($array[$i]<$tmp) {
				return false;
			}
			$tmp = $array[$i];
		}
		return true;
	}
}

 

SmoothSort.php
<?php

class SmoothSort
{
	private static $leonardoMemo = array(1, 1);

	public static function leonardo($n)
	{
		if (isset(self::$leonardoMemo[$n]) && self::$leonardoMemo[$n] != 0) {
			return self::$leonardoMemo[$n];
		}
		return self::$leonardoMemo[$n] = self::leonardo($n - 1) + self::leonardo($n - 2) + 1;
	}

	private static function sift(array &$v, $head, $exp)
	{
		$t = $v[$head];
		while (1<$exp) {
			$r = $head - 1;
			$l = $head - 1 - self::leonardo($exp - 2);
			if ($v[$l]<=$t && $v[$r]<=$t) {
				break;
			}
			if ($v[$r]<=$v[$l]) {
				$v[$head] = $v[$l];
				$head = $l;
				$exp -= 1;
			} else {
				$v[$head] = $v[$r];
				$head = $r;
				$exp -= 2;
			}
		}
		$v[$head] = $t;
	}

	private static function arrange(array &$v, $head, $frac, $exp)
	{
		$t = $v[$head];
		while (1<$frac) {
			$next = $head - self::leonardo($exp);
			if ($v[$next]<=$t) {
				break;
			}
			if (1<$exp) {
				$r = $head - 1;
				$l = $head - 1 - self::leonardo($exp - 2);
				if ($v[$next]<=$v[$l] || $v[$next]<=$v[$r]) {
					break;
				}
			}
			$v[$head] = $v[$next];
			$head = $next;
			$trail = self::numberOfTrailingZeros($frac - 1);
			$frac >>= $trail;
			$exp += $trail;
		}
		$v[$head] = $t;
		self::sift($v, $head, $exp);
	}

	public static function sort(array &$v)
	{
		if (count($v)==0) {
			return;
		}
		$head = 0;
		$frac = 0;
		$exp = 0;
		while ($head<count($v)) {
			if (($frac & 3)==3) {
				$frac >>= 2;
				$exp += 2;
			} else if (1<$exp) {
				$frac <<= $exp - 1;
				$exp = 1;
			} else {
				$frac <<= $exp;
				$exp ^= 1;
			}
			$frac++;
			if (0<$exp && count($v)-$head-1<self::leonardo($exp-1)+1) {
				self::arrange($v, $head, $frac, $exp);
			}
			self::sift($v, $head, $exp);
			$head++;
		}
		self::arrange($v, $head - 1, $frac, $exp);
		while (0<$head) {
			$head--;
			if (1<$exp) {
				$frac <<= 2;
				$frac--;
				$exp -= 2;
				self::arrange($v, $head - self::leonardo($exp) - 1, $frac >> 1, $exp+1);
				self::arrange($v, $head - 1, $frac, $exp);
			} else {
				$trail = self::numberOfTrailingZeros($frac - 1);
				$frac >>= $trail;
				$exp += $trail;
			}
		}
	}


	public static function numberOfTrailingZeros($n)
	{
		$i = 0;
		while ($i<=32) {
			if ($n & 1<<$i) {
				return $i;
			}
			$i++;
		}
		return 32;
	}
}

 

TournamentSort.php
<?php

class TournamentNode
{
	public $data;
	public $index;
	public $active;

	public function __construct()
	{
		$this->data = null;
		$this->index = 0;
		$this->active = false;
	}
}


class TournamentSort
{
	private $a;
	private $tree;

	private function __construct(array &$array)
	{
		$this->a =& $array;
		$this->tree = array();
	}

	public static function sort(array &$array)
	{
		$ts = new TournamentSort($array);
		$ts->tournamentSort();
	}

	private function tournamentSort()
	{
		$a =& $this->a;
		$tree =& $this->tree;

		$n = count($a);

		$bottomRowSize = self::justBitSize($n);
		$treeSize = 2 * $bottomRowSize - 1;
		$loadindex = $bottomRowSize - 1;

		for ($i=0; $i<$treeSize; $i++) {
			$tree[] = new TournamentNode();
		}

		$j = 0;
		for ($i=$loadindex; $i<$treeSize; $i++) {
			$tree[$i]->index = $i;
			if ($j<$n) {
				$tree[$i]->active = true;
				$tree[$i]->data = $a[$j];
				$j++;
			} else {
				$tree[$i]->active = false;
			}
		}

		$i = $loadindex;
		while ($i) {
			$j = $i;
			while ($j < 2*$i) {
				if (!$tree[$j+1]->active || $tree[$j]->data < $tree[$j+1]->data) {
					$tree[($j-1)>>1] = $tree[$j];
				} else {
					$tree[($j-1)>>1] = $tree[$j+1];
				}
				$j += 2;
			}
			$i = ($i-1) >> 1;
		}

		for ($i=0; $i<$n-1; $i++) {
			$a[$i] = $tree[0]->data;
			$tree[$tree[0]->index]->active = false;
			$this->updateTree();
		}
		$a[$n-1] = $tree[0]->data;
	}

	private function updateTree()
	{
		$tree =& $this->tree;
		$i = $tree[0]->index;

		if ($i%2==0) {
			$tree[($i-1)>>1] = $tree[$i-1];
		} else {
			$tree[($i-1)>>1] = $tree[$i+1];
		}

		$i = ($i-1) >> 1;
		while ($i) {
			if ($i%2==0) {
				$j = $i - 1;
			} else {
				$j = $i + 1;
			}
			if (!$tree[$i]->active || !$tree[$j]->active) {
				if ($tree[$i]->active) {
					$tree[($i-1)>>1] = $tree[$i];
				} else {
					$tree[($i-1)>>1] = $tree[$j];
				}
			} else {
				if ($tree[$i]->data < $tree[$j]->data) {
					$tree[($i-1)>>1] = $tree[$i];
				} else {
					$tree[($i-1)>>1] = $tree[$j];
				}
			}
			$i = ($i-1) >> 1;
		}
	}

	private static function justBitSize($n)
	{
		$result = 1;
		while (true) {
			if ($n<=$result) {
				return $result;
			}
			$result <<= 1;
		}
	}
}

 

BinaryTree.php
<?php

class BinaryNode
{
	public $data;
	public $left;
	public $right;
	public $dup;

	public function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
		$this->dup = 0;
	}
}


class BinaryTree
{
	private $_root;

	// コンストラクタ
	public function __construct()
	{
		$this->_root = null;
	}

	// 要素を追加
	public function add($data)
	{
		$node = new BinaryNode($data);

		$p =& $this->_root;
		while ($p) {
			// 同じデータが登録済み
			if ($p->data==$data) {
				$p->dup++;
				return true;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}

		$p = $node;
		return true;
	}

	// 要素を削除
	public function delete($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				//  重複数を減らす
				if (0<$p->dup) {
					$p->dup--;
				// ノードを削除
				} else {
					// 左右両方あり
					if ($p->left && $p->right) {
						$p2 =& $p->right;
						while ($p2->left) {
							$p2 =& $p2->left;
						}
						$p2->left = $p->left;
						$p = $p->right;
					// 左あり
					} else if ($p->left) {
						$p = $p->left;
					// 右あり
					} else if ($p->right) {
						$p = $p->right;
					} else {
						$p = null;
					}
				}
				return true;
			}

			// 左へ進む
			if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return false;
	}

	// 要素を検索
	public function search($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				return $p;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return null;
	}

	// 要素を配列で取得
	public function traverse(BinaryNode $p=null)
	{
		if (!$p) {
			$p = $this->_root;
		}
		$result = array();
		if ($p) {
			if ($p->left) {
				$result = array_merge($result, $this->traverse($p->left));
			}
			for ($i=0; $i<=$p->dup; $i++) {
				$result[] = $p->data;
			}
			if ($p->right) {
				$result = array_merge($result, $this->traverse($p->right));
			}
		}
		return $result;
	}
}

 

TimSort.php
<?php

class TimSort
{
	const MIN_MERGE = 32;
	private $a;
	const MIN_GALLOP = 7;
	private $minGallop = 7;
	const INITIAL_TMP_STORAGE_LENGTH = 256;
	private $tmp;
	private $stackSize = 0;
	private $runBase;
	private $runLen;

	private function __construct(array &$a)
	{
		$this->a =& $a;

		$len = count($a);
		$tmpLen = $len < 2 * self::INITIAL_TMP_STORAGE_LENGTH ? $len >> 1 : INITIAL_TMP_STORAGE_LENGTH;
		$this->tmp = array_fill(0, $tmpLen, null);

		$this->runBase = array();
		$this->runLen = array();
	}

	public static function sort(array &$a, $lo=0, $hi=null)
	{
		if (is_null($hi)) {
			$hi = count($a);
		}

		self::rangeCheck(count($a), $lo, $hi);
		$nRemaining  = $hi - $lo;
		if ($nRemaining < 2) {
			return;		// Arrays of size 0 and 1 are always sorted
		}

		// If array is small, do a "mini-TimSort" with no merges
		if ($nRemaining < self::MIN_MERGE) {
			$initRunLen = self::countRunAndMakeAscending($a, $lo, $hi);
			self::binarySort($a, $lo, $hi, $lo + $initRunLen);
			return;
		}

		$ts = new TimSort($a);
		$minRun = self::minRunLength($nRemaining);
		do {
			// Identify next run
			$runLen = self::countRunAndMakeAscending($a, $lo, $hi);

			// If run is short, extend to min(minRun, nRemaining)
			if ($runLen < $minRun) {
				$force = $nRemaining <= $minRun ? $nRemaining : $minRun;
				self::binarySort($a, $lo, $lo + $force, $lo + $runLen);
				$runLen = $force;
			}

			// Push run onto pending-run stack, and maybe merge
			$ts->pushRun($lo, $runLen);
			$ts->mergeCollapse();

			// Advance to find next run
			$lo += $runLen;
			$nRemaining -= $runLen;
		} while ($nRemaining != 0);

		// Merge all remaining runs to complete sort
		if (!($hi==$lo)) {
			throw new Exception("assert lo == hi;");
		}
		$ts->mergeForceCollapse();
		if (!($ts->stackSize==1)) {
			throw new Exception("assert ts.stackSize == 1;");
		}
	}

	private static function binarySort(array &$a, $lo, $hi, $start)
	{
		if (!($lo <= $start && $start <= $hi)) {
			throw new Exception("assert lo <= start && start <= hi;");
		}
		if ($start == $lo) {
			$start++;
		}
		for ( ; $start < $hi; $start++) {
			$pivot = $a[$start];

			// Set left (and right) to the index where a[start] (pivot) belongs
			$left = $lo;
			$right = $start;
			if (!($left <= $right)) {
				throw new Exception("assert left <= right;");
			}

			while ($left < $right) {
				$mid = ($left + $right) >> 1;
				if ($pivot<$a[$mid]) {
					$right = $mid;
				} else {
					$left = $mid + 1;
				}
			}
			if (!($left == $right)) {
				throw new Exception("assert left == right;");
			}

			$n = $start - $left;	// The number of elements to move
			// Switch is just an optimization for arraycopy in default case
			switch($n) {
			case 2:
				$a[$left+2] = $a[$left+1];
			case 1:
				$a[$left+1] = $a[$left];
				break;
			default:
				self::arraycopy($a, $left, $a, $left + 1, $n);
			}
			$a[$left] = $pivot;
		}
	}

	private static function countRunAndMakeAscending(array &$a, $lo, $hi)
	{
		if (!($lo < $hi)) {
			throw new Exception("assert lo < hi;");
		}

		$runHi = $lo + 1;
		if ($runHi == $hi) {
			return 1;
		}

		// Find end of run, and reverse range if descending
		if ($a[$runHi++] < $a[$lo]) {
			while ($runHi < $hi && $a[$runHi] < $a[$runHi - 1]) {
				$runHi++;
			}
			self::reverseRange($a, $lo, $runHi);
		} else {
			while ($runHi < $hi && $a[$runHi] >= $a[$runHi - 1]) {
				$runHi++;
			}
		}
		return $runHi - $lo;
	}

	private static function reverseRange(array &$a, $lo, $hi)
	{
		$hi--;
		while ($lo < $hi) {
			$t = $a[$lo];
			$a[$lo++] = $a[$hi];
			$a[$hi--] = $t;
		}
	}

	private static function minRunLength($n)
	{
		if (!($n >= 0)) {
			throw new Exception("assert n >= 0;");
		}
		$r = 0;		// Becomes 1 if any 1 bits are shifted off
		while ($n >= self::MIN_MERGE) {
			$r |= ($n & 1);
			$n >>= 1;
		}
		return $n +$r;
	}

	private function pushRun($runBase, $runLen)
	{
		$this->runBase[$this->stackSize] = $runBase;
		$this->runLen[$this->stackSize] = $runLen;
		$this->stackSize++;
	}

	private function mergeCollapse()
	{
		while ($this->stackSize > 1) {
			$n = $this->stackSize - 2;
			if ($n > 0 && $this->runLen[$n-1] <= $this->runLen[$n] + $this->runLen[$n+1]) {
				if ($this->runLen[$n - 1] < $this->runLen[$n + 1]) {
					$n--;
				}
				$this->mergeAt($n);
			} else if ($this->runLen[$n] <= $this->runLen[$n + 1]) {
				$this->mergeAt($n);
			} else {
				break;		// Invariant is established
			}
		}
	}

	private function mergeForceCollapse()
	{
		while ($this->stackSize > 1) {
			$n = $this->stackSize - 2;
			if ($n > 0 && $this->runLen[$n - 1] < $this->runLen[$n + 1]) {
				$n--;
			}
			$this->mergeAt($n);
		}
	}

	private function mergeAt($i)
	{
		if (!($this->stackSize >= 2)) {
			throw new Exception("assert stackSize >= 2;");
		}
		if (!($i >= 0)) {
			throw new Exception("assert i >= 0;");
		}
		if (!($i == $this->stackSize - 2 || $i == $this->stackSize - 3)) {
			throw new Exception("assert i == stackSize - 2 || i == stackSize - 3;");
		}

		$base1 = $this->runBase[$i];
		$len1 = $this->runLen[$i];
		$base2 = $this->runBase[$i + 1];
		$len2 = $this->runLen[$i + 1];

		if (!($len1 > 0 && $len2 > 0)) {
			throw new Exception("assert len1 > 0 && len2 > 0;");
		}
		if (!($base1 + $len1 == $base2)) {
			throw new Exception("assert base1 + len1 == base2;");
		}

		$this->runLen[$i] = $len1 + $len2;
		if ($i == $this->stackSize - 3) {
			$this->runBase[$i + 1] = $this->runBase[$i + 2];
			$this->runLen[$i + 1] = $this->runLen[$i + 2];
		}
		$this->stackSize--;

		$k = self::gallopRight($this->a[$base2], $this->a, $base1, $len1, 0);
		if (!($k >= 0)) {
			throw new Exception("assert k >= 0;");
		}
		$base1 += $k;
		$len1 -= $k;
		if ($len1 == 0) {
			return;
		}

		$len2 = self::gallopLeft($this->a[$base1 + $len1 - 1], $this->a, $base2, $len2, $len2 - 1);
		if (!($len2 >= 0)) {
			throw new Exception("assert len2 >= 0;");
		}
		if ($len2 == 0) {
			return;
		}

		// Merge remaining runs, using tmp array with min(len1, len2) elements
		if ($len1 <= $len2) {
			$this->mergeLo($base1, $len1, $base2, $len2);
		} else {
			$this->mergeHi($base1, $len1, $base2, $len2);
		}
	}

	private static function gallopLeft($key, array &$a, $base, $len, $hint)
	{
		if (!($len > 0 && $hint >= 0 && $hint < $len)) {
			throw new Exception("assert len > 0 && hint >= 0 && hint < len;");
		}

		$lastOfs = 0;
		$ofs = 1;
		if ($key > $a[$base + $hint]) {
			$maxOfs = $len - $hint;
			while ($ofs < $maxOfs && $key > $a[$base + $hint + $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to base
			$lastOfs += $hint;
			$ofs += $hint;
		} else {	// key <= a[base + hint]
			// Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
			$maxOfs = $hint + 1;
			while ($ofs < $maxOfs && $key <= $a[$base + $hint - $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to base
			$tmp = $lastOfs;
			$lastOfs = $hint - $ofs;
			$ofs = $hint - $tmp;
		}
		if (!(-1 <= $lastOfs && $lastOfs < $ofs && $ofs <= $len)) {
			throw new Exception("assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;");
		}

		$lastOfs++;
		while ($lastOfs < $ofs) {
			$m = $lastOfs + (($ofs - $lastOfs) >> 1);
			if ($key > $a[$base + $m]) {
				$lastOfs = $m + 1;	// a[base + m] < key
			} else {
				$ofs = $m;			// key <= a[base + m]
			}
		}
		if (!($lastOfs == $ofs)) {
			throw new Exception("assert lastOfs == ofs;");
		}
		return $ofs;
	}

	private static function gallopRight($key, array &$a, $base, $len, $hint)
	{
		if (!($len > 0 && $hint >= 0 && $hint < $len)) {
			throw new Exception("assert len > 0 && hint >= 0 && hint < len;");
		}

		$ofs = 1;
		$lastOfs = 0;
		if ($key < $a[$base + $hint]) {
			// Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
			$maxOfs = $hint + 1;
			while ($ofs < $maxOfs && $key < $a[$base + $hint - $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to b
			$tmp = $lastOfs;
			$lastOfs = $hint - $ofs;
			$ofs = $hint - $tmp;
		} else {	// a[b + hint] <= key
			// Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
			$maxOfs = $len - $hint;
			while ($ofs < $maxOfs && $key >= $a[$base + $hint + $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to b
			$lastOfs += $hint;
			$ofs += $hint;
		}
		if (!(-1 <= $lastOfs && $lastOfs < $ofs && $ofs <= $len)) {
			throw new Exception("assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;");
		}

		$lastOfs++;
		while ($lastOfs < $ofs) {
			$m = $lastOfs + (($ofs - $lastOfs) >> 1);
			if ($key < $a[$base + $m]) {
				$ofs = $m;			// key < a[b + m]
			} else {
				$lastOfs = $m + 1;	// a[b + m] <= key
			}
		}
		if (!($lastOfs == $ofs)) {
			throw new Exception("assert lastOfs == ofs;");		// so a[b + ofs - 1] <= key < a[b + ofs]
		}
		return $ofs;
	}

	private function mergeLo($base1, $len1, $base2, $len2)
	{
		if (!($len1 > 0 && $len2 > 0 && $base1 + $len1 == $base2)) {
			throw new Exception("assert len1 > 0 && len2 > 0 && base1 + len1 == base2;");
		}

		// Copy first run into temp array
		$a =& $this->a;
		$tmp = $this->ensureCapacity($len1);
		self::arraycopy($a, $base1, $tmp, 0, $len1);

		$cursor1 = 0;
		$cursor2 = $base2;
		$dest = $base1;

		// Move first element of second run and deal with degenerate cases
		$a[$dest++] = $a[$cursor2++];
		if (--$len2 == 0) {
			self::arraycopy($tmp, $cursor1, $a, $dest, $len1);
			return;
		}
		if ($len1 == 1) {
			self::arraycopy($a, $cursor2, $a, $dest, $len2);
			$a[$dest + $len2] = $tmp[$cursor1];	// Last elt of run 1 to end of merge
			return;
		}

		$minGallop = $this->minGallop;
		while (true) {
			$count1 = 0; // Number of times in a row that first run won
			$count2 = 0; // Number of times in a row that second run won

			do {
				if (!($len1 > 1 && $len2 > 0)) {
					throw new Exception("assert len1 > 1 && len2 > 0;");
				}
				if ($a[$cursor2] < $tmp[$cursor1]) {
					$a[$dest++] = $a[$cursor2++];
					$count2++;
					$count1 = 0;
					if (--$len2 == 0) {
						break 2;
					}
				} else {
					$a[$dest++] = $tmp[$cursor1++];
					$count1++;
					$count2 = 0;
					if (--$len1 == 1) {
						break 2;
					}
				}
			} while (($count1 | $count2) < $minGallop);

			do {
				if (!($len1 > 1 && $len2 > 0)) {
					throw new Exception("assert len1 > 1 && len2 > 0;");
				}
				$count1 = self::gallopRight($a[$cursor2], $tmp, $cursor1, $len1, 0);
				if ($count1 != 0) {
					self::arraycopy($tmp, $cursor1, $a, $dest, $count1);
					$dest += $count1;
					$cursor1 += $count1;
					$len1 -= $count1;
					if ($len1 <= 1) {	// len1 == 1 || len1 == 0
						break 2;
					}
				}
				$a[$dest++] = $a[$cursor2++];
				if (--$len2 == 0) {
					break 2;
				}
				$count2 = self::gallopLeft($tmp[$cursor1], $a, $cursor2, $len2, 0);
				if ($count2 != 0) {
					self::arraycopy($a, $cursor2, $a, $dest, $count2);
					$dest += $count2;
					$cursor2 += $count2;
					$len2 -= $count2;
					if ($len2 == 0) {
						break 2;
					}
				}
				$a[$dest++] = $tmp[$cursor1++];
				if (--$len1 == 1) {
					break 2;
				}
				$minGallop--;
			} while ($count1 >= self::MIN_GALLOP | $count2 >= self::MIN_GALLOP);
			if ($minGallop < 0) {
				$minGallop = 0;
			}
			$minGallop += 2;	// Penalize for leaving gallop mode
		}
		$this->minGallop = $minGallop < 1 ? 1 : $minGallop;		// Write back to field

		if ($len1 == 1) {
			if (!($len2 > 0)) {
				throw new Exception("assert len2 > 0;");
			}
			self::arraycopy($a, $cursor2, $a, $dest, $len2);
			$a[$dest + $len2] = $tmp[$cursor1];	// Last elt of run 1 to end of merge
		} else if ($len1 == 0) {
			throw new Exception("IllegalArgumentException: Comparison method violates its general contract!");
		} else {
			if (!($len2 == 0)) {
				throw new Exception("assert len2 == 0;");
			}
			if (!($len1 > 1)) {
				throw new Exception("assert len1 > 1;");
			}
			self::arraycopy($tmp, $cursor1, $a, $dest, $len1);
		}
	}

	private function mergeHi($base1, $len1, $base2, $len2)
	{
		if (!($len1 > 0 && $len2 > 0 && $base1 + $len1 == $base2)) {
			throw new Exception("assert len1 > 0 && len2 > 0 && base1 + len1 == base2;");
		}

		// Copy second run into temp array
		$a =& $this->a;
		$tmp = $this->ensureCapacity($len2);
		self::arraycopy($a, $base2, $tmp, 0, $len2);

		$cursor1 = $base1 + $len1 - 1;
		$cursor2 = $len2 - 1;
		$dest = $base2 + $len2 - 1;

		// Move last element of first run and deal with degenerate cases
		$a[$dest--] = $a[$cursor1--];
		if (--$len1 == 0) {
			self::arraycopy($tmp, 0, $a, $dest - ($len2 - 1), $len2);
			return;
		}
		if ($len2 == 1) {
			$dest -= $len1;
			$cursor1 -= $len1;
			self::arraycopy($a, $cursor1 + 1, $a, $dest + 1, $len1);
			$a[$dest] = $tmp[$cursor2];
			return;
		}

		$minGallop = $this->minGallop;
		while (true) {
			$count1 = 0;	// Number of times in a row that first run won
			$count2 = 0;	// Number of times in a row that second run won

			do {
				if (!($len1 > 0 && $len2 > 1)) {
					throw new Exception("assert len1 > 0 && len2 > 1;");
				}
				if ($tmp[$cursor2] < $a[$cursor1]) {
					$a[$dest--] = $a[$cursor1--];
					$count1++;
					$count2 = 0;
					if (--$len1 == 0) {
						break 2;
					}
				} else {
					$a[$dest--] = $tmp[$cursor2--];
					$count2++;
					$count1 = 0;
					if (--$len2 == 1) {
						break 2;
					}
				}
			} while (($count1 | $count2) < $minGallop);

			do {
				if (!($len1 > 0 && $len2 > 1)) {
					throw new Exception("assert len1 > 0 && len2 > 1;");
				}
				$count1 = $len1 - self::gallopRight($tmp[$cursor2], $a, $base1, $len1, $len1 - 1);
				if ($count1 != 0) {
					$dest -= $count1;
					$cursor1 -= $count1;
					$len1 -= $count1;
					self::arraycopy($a, $cursor1 + 1, $a, $dest + 1, $count1);
					if ($len1 ==0) {
						break 2;
					}
				}
				$a[$dest--] = $tmp[$cursor2--];
				if (--$len2 == 1) {
					break 2;
				}

				$count2 = $len2 - self::gallopLeft($a[$cursor1], $tmp, 0, $len2, $len2 - 1);
				if ($count2 != 0) {
					$dest -= $count2;
					$cursor2 -= $count2;
					$len2 -= $count2;
					self::arraycopy($tmp, $cursor2 + 1, $a, $dest + 1, $count2);
					if ($len2 <= 1) {	// len2 == 1 || len2 == 0
						break 2;
					}
				}
				$a[$dest--] = $a[$cursor1--];
				if (--$len1 == 0) {
					break 2;
				}
				$minGallop--;
			} while ($count1 >= self::MIN_GALLOP | $count2 >= self::MIN_GALLOP);
			if ($minGallop < 0) {
				$minGallop = 0;
			}
			$minGallop += 2;	// Penalize for leaving gallop mode
		}
		$this->minGallop = $minGallop < 1 ? 1 : $minGallop;

		if ($len2 == 1) {
			if (!($len1 > 0)) {
				throw new Exception("assert len1 > 0;");
			}
			$dest -= $len1;
			$cursor1 -= $len1;
			self::arraycopy($a, $cursor1 + 1, $a, $dest + 1, $len1);
			$a[$dest] = $tmp[$cursor2];	// Move first elt of run2 to front of merge
		} else if ($len2 ==0) {
			throw new Exception("IllegalArgumentException: Comparison method violates its general contract!");
		} else {
			if (!($len1 == 0)) {
				throw new Exception("assert len1 == 0;");
			}
			if (!($len2 > 0)) {
				throw new Exception("assert len2 > 0;");
			}
			self::arraycopy($tmp, 0, $a, $dest - ($len2 - 1), $len2);
		}
	}

	private function &ensureCapacity($minCapacity)
	{
		if (count($this->tmp) < $minCapacity) {
			$newSize = $minCapacity;
			$newSize |= $newSize >> 1;
			$newSize |= $newSize >> 2;
			$newSize |= $newSize >> 4;
			$newSize |= $newSize >> 8;
			$newSize |= $newSize >> 16;
			$newSize++;

			if ($newSize < 0) {
				$newSize = $minCapacity;
			} else {
				$newSize = min($newSize, count($this->a) >> 1);
			}
			$this->tmp = array_fill(0, $newSize, null);
		}
		return $this->tmp;
	}

	private static function rangeCheck($arrayLen, $fromIndex, $toIndex)
	{
		if ($fromIndex > $toIndex) {
			throw new Exception("IllegalArgumentException: fromIndex(" . $fromIndex . ") > toIndex(" . $toIndex . ")");
		}
		if ($fromIndex < 0) {
			throw new Exception("ArrayIndexOutOfBoundsException: " . $fromIndex);
		}
		if ($toIndex > $arrayLen) {
			throw new Exception("ArrayIndexOutOfBoundsException: " . $toIndex);
		}
	}


	public static function arraycopy(array $from, $from_i, array &$to, $to_i, $n)
	{
		$tmp_arr = array_slice($from, $from_i, $n);
		foreach ($tmp_arr as $tmp_item) {
			$to[$to_i] = $tmp_item;
			$to_i++;
		}
	}
}

 

BitonicSort.php
<?php

class BitonicSort
{
	const ASCENDING = true;
	const DESCENDING = false;

	private $a;
	private $size;

	private function __construct(array &$a)
	{
		$this->a =& $a;
		$this->size = count($a);
	}

	public static function sort(array &$a)
	{
		$org_size = count($a);
		$add_size = self::justBitSize(count($a)) - $org_size;
		while (0<$add_size--) {
			$a[] = INF;
		}
		$bs = new BitonicSort($a);
		$bs->bitonicSort(0, count($a), self::ASCENDING);
		array_splice($a, $org_size);
	}

	private static function justBitSize($n)
	{
		$result = 1;
		while (true) {
			if ($n<=$result) {
				return $result;
			}
			$result <<= 1;
		}
	}

	private function bitonicSort($lo, $n, $dir)
	{
		if (1<$n) {
			$m = $n >> 1;
			$this->bitonicSort($lo, $m, self::ASCENDING);
			$this->bitonicSort($lo+$m, $m, self::DESCENDING);
			$this->bitonicMerge($lo, $n, $dir);
		}
	}

	private function bitonicMerge($lo, $n, $dir)
	{
		if (1<$n) {
			$m = $n >> 1;
			for ($i=$lo; $i<$lo+$m; $i++) {
				$this->compare($i, $i+$m, $dir);
			}
			$this->bitonicMerge($lo, $m, $dir);
			$this->bitonicMerge($lo+$m, $m, $dir);
		}
	}

	private function compare($i, $j, $dir)
	{
		if ($dir==($this->a[$j]<$this->a[$i])) {
			$this->exchange($i, $j);
		}
	}

	private function exchange($i, $j)
	{
		list($this->a[$i], $this->a[$j]) = array($this->a[$j], $this->a[$i]);
	}
}

 

BatcherOddEvenMergeSort.php
<?php

class BatcherOddEvenMergeSort
{
	private $a;

	private function __construct(array &$a)
	{
		$this->a =& $a;
	}

	public static function sort(array &$a)
	{
		$org_size = count($a);
		$add_size = self::justBitSize(count($a)) - $org_size;
		while (0<$add_size--) {
			$a[] = INF;
		}
		$oems = new BatcherOddEvenMergeSort($a);
		$oems->oddEvenMergeSort(0, count($a));
		array_splice($a, $org_size);
	}

	private static function justBitSize($n)
	{
		$result = 1;
		while (true) {
			if ($n<=$result) {
				return $result;
			}
			$result <<= 1;
		}
	}

	private function oddEvenMergeSort($lo, $n)
	{
		if (1<$n) {
			$m = $n >> 1;
			$this->oddEvenMergeSort($lo, $m);
			$this->oddEvenMergeSort($lo+$m, $m);
			$this->oddEvenMerge($lo, $n, 1);
		}
	}

	private function oddEvenMerge($lo, $n, $r)
	{
		$m = $r << 1;
		if ($m<$n) {
			$this->oddEvenMerge($lo, $n, $m);
			$this->oddEvenMerge($lo+$r, $n, $m);
			for ($i=$lo+$r; $i+$r<$lo+$n; $i+=$m) {
				$this->compare($i, $i+$r);
			}
		} else {
			$this->compare($lo, $lo+$r);
		}
	}

	private function compare($i, $j)
	{
		if ($this->a[$j]<$this->a[$i]) {
			$this->exchange($i, $j);
		}
	}

	private function exchange($i, $j)
	{
		list($this->a[$i], $this->a[$j]) = array($this->a[$j], $this->a[$i]);
	}
}

2010-10-05

PHPで二分探索木やってみた

二分木構造で二分探索を行う。

多分こんな感じ。

削除が面倒臭いなぁ。

 

ソース

<?php
class BinaryNode
{
	public $data;
	public $left;
	public $right;

	public function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}


class BinaryTree
{
	private $_root;

	// コンストラクタ
	public function __construct()
	{
		$this->_root = null;
	}

	// 要素を追加
	public function add($data)
	{
		$node = new BinaryNode($data);

		$p =& $this->_root;
		while ($p) {
			// 同じデータが登録済み
			if ($p->data==$data) {
				return false;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}

		$p = $node;
		return true;
	}

	// 要素を削除
	public function delete($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				// 左右両方あり
				if ($p->left && $p->right) {
					$p2 =& $p->right;
					while ($p2->left) {
						$p2 =& $p2->left;
					}
					$p2->left = $p->left;
					$p = $p->right;
				// 左あり
				} else if ($p->left) {
					$p = $p->left;
				// 右あり
				} else if ($p->right) {
					$p = $p->right;
				} else {
					$p = null;
				}
				return true;
			}

			// 左へ進む
			if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return false;
	}

	// 要素を検索
	public function search($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				return $p;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return null;
	}

	// 要素を配列で取得
	public function traverse(BinaryNode $p=null)
	{
		if (!$p) {
			$p = $this->_root;
		}
		$result = array();
		if ($p) {
			if ($p->left) {
				$result = array_merge($result, $this->traverse($p->left));
			}
			$result[] = $p->data;
			if ($p->right) {
				$result = array_merge($result, $this->traverse($p->right));
			}
		}
		return $result;
	}
}

 

参考URL

アルゴリズムとデータ構造編 第17章 二分探索木

http://www.geocities.jp/ky_webid/algorithm/017.html

 

データ構造:二分探索木[1] ― 初期設定、追加、検索

http://tdweb.cssa.chs.nihon-u.ac.jp/ds/ds07.html

 

データ構造:二分探索木[2] ― トラバーサル

http://tdweb.cssa.chs.nihon-u.ac.jp/ds/ds08.html

 

データ構造:二分探索木[3] ― データ要素の削除

http://tdweb.cssa.chs.nihon-u.ac.jp/ds/ds09.html

2010-10-04

PHPのMath関数を再発明してみた

言うまでもなくdankogai氏の1ヶ月位前のブログに触発されて。

普段から使うMath系の関数もあるけど、中で何をやってるのか知らなかったから再発明してみた。

乱数とX進数からX進数へ変換以外の関数は全て。

四角い車輪。

 

極力よく見かける公式とかに合わせた。

速度は気にしない。

Math::atan(1) が一向に収束しないのはどうにかしたいけど、公式をそのまま使うとそうだからとりあえずそれでいい。

 

これ作るのに、2週間位かかった。

数学やったのなんて中学生以来なんじゃないかと。

今までろくに勉強してこなかったのが悔やまれる。

これを作れて、どんな事をやってるのかが知れたからとりあえず満足。

一般教養的な意味でこれを知れたのは有意義だった。

 

Mathクラスと平行して「プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10」もPHPで作ってみてる。

Mathクラスはまぁどうにかなっても、これをPHPで作るのはまずかった。

でも途中まではやってあるから、そのまま完成させる予定。

 

参考にしたページはブックマークしといたつもりだったけど、結構な数が行方不明になってしまった。

 

Math関数の再発明をしてて思った事は、数学は何千年も前から存在するオープンソースプロジェクトみたいだと言う事。

オープンソースというよりはRFCとかそっちのような気もするけど。

昔の人はすごいなぁ、なんて思いつつ、自分もいつか提供する側になりたいなぁ、なんて思いつつ、寝る。

 

再発明した関数一覧

abs

acos

acosh

asin

asinh

atan

atan2

atanh

ceil

cos

cosh

exp

expm1

deg2rad

floor

fmod

hypot

log

log10

log1p

max

min

pi

pow

round

sin

sinh

sqrt

tan

tanh

rad2deg

 

PHP: Math 関数 - Manual

http://php.net/manual/ja/ref.math.php

 

ソース

<?php
class Math
{
	// 絶対値
	public static function abs($a)
	{
		return ($a<0) ? $a * -1 : $a;
	}

	// 逆余弦(アークコサイン)
	public static function acos($x)
	{
		return self::pi() / 2 - self::asin($x);
	}

	// 逆双曲線余弦(アークハイパボリックコサイン)
	public static function acosh($x)
	{
		return self::log($x + self::sqrt($x * $x - 1));
	}

	// 逆正弦(アークサイン)
	public static function asin($x)
	{
		return self::atan($x / self::sqrt(1 - $x * $x));
	}

	// 逆双曲線正弦(アークハイパボリックサイン)
	public static function asinh($x)
	{
		return self::log($x + self::sqrt($x * $x + 1));
	}

	// 逆正接(アークタンジェント)
	public static function atan($a)
	{
		$pi = self::pi();
		$phase = (self::abs($a) / $pi * 2) % 4;
		$x = self::fmod($a, $pi);
		//printf("phrase: %d, a:%f, x: %f\n", $phase, $a, $x);
		if (1<self::abs($x)) {
			//printf("!!! atan abs %f\n", $a);
			return $pi / 2 - self::atan(1 / $a);
		}
		$result = $x;
		$tmp = 1;
		$minus = 1;
		for ($i=1; $result!=$result+$tmp; $i++) {
			$n = $i * 2 + 1;
			$minus *= -1;
			$tmp = self::pow($x, $n) / $n * $minus;
			$result += $tmp;
			//printf("i:%d, a:%d, m:%d, n:%d, t:%.30f, x:%.30f\n", $i, $i*2+1, $minus, $n, $tmp, $result);
		}
		if (2<=$phase) {
			$result *= -1;
		}
		return $result;
	}

	// 2変数のアークタンジェント
	public static function atan2($y, $x)
	{
		$minus_y = 1;
		$minus_x = 1;
		if ($y<0) {
			$y = self::abs($y);
			$minus_y = -1;
		}
		if ($x<0) {
			$x = self::abs($x);
			$minus_x = -1;
		}
		if ($y==0) {
			return 0;
		}
		if ($x==0) {
			return self::pi() / 2 * $minus_y;
		}
		return self::atan($y / $x * $minus_x) * $minus_y;
	}

	// 逆双曲線正接(アークハイパボリックタンジェント)
	public static function atanh($x)
	{
		if (1-$x==0) {
			return INF;
		}
		return self::log((1+$x) / (1-$x)) / 2;
	}

	// 切り上げ
	public static function ceil($a)
	{
		return (int)(((int)$a!=$a) ? ($a<0 ? $a : $a + 1) : $a);
	}

	// 余弦(コサイン)
	public static function cos($x)
	{
		return self::sin($x + self::pi() / 2);
	}

	// 双曲線余弦(ハイパボリックコサイン)
	public static function cosh($x)
	{
		return (Math::exp($x) + Math::exp($x * -1)) / 2;
	}

	// 累乗
	public static function exp($x)
	{
		if (!is_finite($x)) {
			return NAN;
		}
		$tmp = 1;
		$result = 1;
		for ($i=1; $result!=$result+$tmp; $i++) {
			$tmp = $tmp * $x / $i;
			$result += $tmp;
			//printf("x: %f, tmp: %f, result: %f\n", $x, $tmp, $result);
		}
		return $result;
	}

	// exp(number) - 1
	public static function expm1($x)
	{
		return self::exp($x) - 1;
	}

	// 度単位の数値をラジアン単位に変換
	public static function deg2rad($deg)
	{
		return $deg / 180 * self::pi();
	}

	// 切り捨て
	public static function floor($a)
	{
		return (int)(((int)$a!=$a) ? ($a<0 ? $a - 1 : $a) : $a);
	}

	// 剰余
	public static function fmod($x, $y)
	{
		return $x - $y * (int)($x / $y);
	}

	// 直角三角形の斜辺の長さ
	public static function hypot($x, $y)
	{
		return sqrt($x*$x + $y*$y);
	}

	// 自然対数を返す
	public static function log($a, $base=null)
	{
		if (isset($base) && $base<=0) {
			throw new Exception("log(): base must be greater than 0");
		}
		if ($a<=0) {
			return -INF;
		}

		$x = ($a - 1) / ($a + 1);
		$result = 0;
		$tmp = 1;
		for ($i=0; $result!==$result+$tmp; $i++) {
			$tmp = 2 * (1 / (2 * $i + 1)) * self::pow($x, 2 * $i + 1);
			$result += $tmp;
			//printf("%d: %.30f\n", $i, $result);
		}
		//printf("loop: %d\n", $i);

		if (isset($base)) {
			$base = self::log($base);
			if ($base==0) {
				return NAN;
			}
			return $result / $base;
		}
		return $result;
	}

	// 常用対数を返す
	public static function log10($a)
	{
		return self::log($a, 10);
	}

	// log(1 + number)
	public static function log1p($a)
	{
		return self::log(1 + $a);
	}

	// 最大値
	public static function max($a, $b)
	{
		return $a<$b ? $b : $a;
	}

	// 最小値
	public static function min($a, $b)
	{
		return $a<$b ? $a : $b;
	}

	// 円周率
	public static function pi()
	{
		return self::pi_by_gauss();
	}

	// 円周率 ヴィエートの公式
	public static function pi_by_viete()
	{
		$n = self::sqrt(1/2);
		$result = $n;
		//printf("%f\n", $n);
		while ($result!=$result*$n) {
			$n = self::sqrt(1/2 + 1/2 * $n);
			$result *= $n;
			//printf("%f, %.35f\n", $n, $result);
		}
		return 2 / $result;
	}

	// 円周率 モンテカルロ法
	public static function pi_by_montecalro($n=1000)
	{
		$p = 0;
		for ($i=$n; 0<$i; $i--) {
			$x = mt_rand(0, 10000) / 10000;
			$y = mt_rand(0, 10000) / 10000;
			if ($x*$x+$y*$y<=1) {
				$p++;
			}
			//printf("x:%f y:%f\n", $x, $y);
		}
		return $p / $n * 4;
	}

	// 円周率 ガウス=ルジャンドルのアルゴリズム
	public static function pi_by_gauss()
	{
		$a = 1;
		$b = 1 / self::sqrt(2);
		$s = 1;
		$t = 4;
		for ($i=0; $i<3; $i++) {
			$last = $a;
			$a = ($a + $b) / 2;
			$b = self::sqrt($last * $b);
			$s -= $t * ($a - $last) * ($a - $last);
			$t *= 2;
			//printf("%.20f\n", ($a + $b) * ($a + $b) / $s);
		}
		return ($a + $b) * ($a + $b) / $s;
	}

	// 指数表現
	public static function pow($base, $exp)
	{
		if ($base==0) {
			return 0.0;
		}

		// integer
		if (is_int($exp)) {
			$result = 1;
			if ($exp<0) {
				$exp = self::abs($exp);
				$base = 1 / $base;
			}
			while ($exp--) {
				$result *= $base;
			}
			return $result;

		// float
		} else {
			return self::exp(self::log($base) * $exp);
		}
	}

	// 四捨五入
	public static function round($a)
	{
		return self::floor($a + 0.5);
	}

	// 正弦(サイン)
	public static function sin($x)
	{
		$pi = self::pi();
		$phase = (self::abs($x) / $pi * 2) % 4;
		$x = self::fmod($x, $pi);
		//printf("phrase: %d, x: %f\n", $phase, $x);
		$result = $x;
		$tmp = 1;
		$n = 1;
		$minus = 1;
		for ($i=1; $result!=$result+$tmp; $i++) {
			$n *= ($i * 2) * ($i * 2 + 1);
			$minus *= -1;
			$tmp = self::pow($x, $i*2+1) / $n * $minus;
			$result += $tmp;
			//printf("i:%d, a:%d, m:%d, n:%d, x:%f\n", $i, $i*2+1, $minus, $n, $result);
		}
		if (2<=$phase) {
			$result *= -1;
		}
		return $result;
	}

	// 双曲線正弦(ハイパボリックサイン)
	public static function sinh($x)
	{
		return (Math::exp($x) - Math::exp($x * -1)) / 2;
	}

	// 平方根
	public static function sqrt($a)
	{
		return self::sqrt_by_newton($a);
	}

	// 平方根 二分探索
	public static function sqrt_by_binarysearch($a)
	{
		$minus = 1;
		if ($a<0) {
			$minus = -1;
			$a *= -1;
		}
		if ($a==1) {
			return $a * $minus;
		}
		$low = 1;
		$high = $a;
		if ($a<1) {
			$low = $a;
			$high = 1;
		}
		$middle = 0;
		while ($middle*0.000000000000001<$high-$low) {
			$middle = 0.5 * ($low + $high);
			if ($middle * $middle < $a) {
				$low = $middle;
			} else {
				$high = $middle;
			}
			//printf("middle: %f\n", $middle);
		}
		return $middle * $minus;
	}

	// 平方根 ニュートン法
	public static function sqrt_by_newton($a)
	{
		if ($a==0) {
			return 0.0;
		}
		$a = self::abs($a);
		$x = $a;
		//var_dump($x);
		while (true) {
			$last = $x;
			$x = ($x + $a / $x) / 2;
			//var_dump($x);
			if ($last==$x) {
				break;
			}
		}
		return $x;
	}

	// 正接(タンジェント)
	public static function tan($x)
	{
		return self::sin($x) / self::cos($x);
	}

	// 双曲線正接(ハイパボリックタンジェント)
	public static function tanh($x)
	{
		return self::sinh($x) / self::cosh($x);
	}

	// ラジアン単位の数値を度単位に変換
	public static function rad2deg($rad)
	{
		return $rad * 180 / self::pi();
	}
}

 

参考URL

404 Blog Not Found:javascript - Mathを再発明してみた

http://blog.livedoor.jp/dankogai/archives/51518565.html

 

正弦関数 sin(x)をプログラムで実装するにあ?(3) - udongeinの日記

http://d.hatena.ne.jp/udongein/20080725/1216967329

 

AWK Users JP :: 自然対数の計算

http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_227

 

C言語の二分法のプログラムについて | OKWave

http://okwave.jp/qa/q3745693.html

 

三角関数 - Wikipedia

http://ja.wikipedia.org/wiki/%E4%B8%89%E8%A7%92%E9%96%A2%E6%95%B0

 

双曲線関数 - Wikipedia

http://ja.wikipedia.org/wiki/%E5%8F%8C%E6%9B%B2%E7%B7%9A%E9%96%A2%E6%95%B0

 

モンテカルロ法による円周率の計算

http://hp.vector.co.jp/authors/VA014765/pi/montecalro.html

 

指数関数のマクローリン展開

http://www.geocities.jp/yousukehonda_shuzan/calc/japanese/a0402exp.html

 

ケータイ(Vodafone)@らるるのわがまま

http://www.rarul.com/k-tai/java/math/

2010-10-01

NagiosでCPU使用率を調べるプラグインを作ってみた

CPU使用率を調べるプラグインは世の中にいろいろ出回ってるっぽいけど、何が重いかを調べられるのが見つからなかったので、自分で作った。

$SERVICEOUTPUT$がプラグインの出力に置き換えられるっぽいけど、なぜか1行目しかメールで来ない。

Webからはちゃんと全部見れたけど、メールで一覧が見れなきゃ意味ないじゃないか。

 

こんな感じでメールが来る。

***** Nagios *****

Notification Type: RECOVERY

Service: Current CPU
Host: localhost
Address: 127.0.0.1
State: OK

Date/Time: Fri Oct 1 06:07:24 JST 2010

Additional Info:

OK - CPU: 15.0%

 

/usr/lib/nagios/plugins/check_cpu

実行権限も与える。

#!/usr/local/bin/python

from optparse import OptionParser
import sys
import subprocess, re


class Ps:
    ITEMS = {
        'USER' : 0,
        'PID' : 1,
        'CPU' : 2,
        'MEM' : 3,
        'VSZ' : 4,
        'RSS' : 5,
        'TTY' : 6,
        'STAT' : 7,
        'START' : 8,
        'TIME' : 9,
        'COMMAND' : 10,
    }

    def __init__(self):
        self.ps = None

    def load(self):
        cmd = "ps -e aux"
        proc = subprocess.Popen(cmd, shell = True, stdout = subprocess.PIPE, stderr = subprocess.PIPE)
        stdout, stderr = proc.communicate()
        proc.wait()
        self.ps = stdout

    def getTotal(self, item):
        # item index
        index = self.ITEMS.get(item.upper())
        if index is None:
            raise Exception("item is not found: %s" % item)

        # ps load
        if self.ps is None:
            self.load()

        # split
        lines = self.ps.strip().split("\n")
        lines.pop(0)

        # total
        p = re.compile(r'\W+')
        total = 0.0
        for line in lines:
            value = p.split(line)[index]
            total += float(value)
        return total

    def dump(self):
        # ps load
        if self.ps is None:
            self.load()

        return self.ps


# Return status

RETURN_OK = 0
RETURN_WARNING = 1
RETURN_CRITICAL = 2
RETURN_UNKNOWN = 3

RETURN_VALUES = [
    'OK',
    'Warning',
    'Critical',
    'Unknown',
]


# main

def main():
    # parse arguments
    usage = "%prog -w warning_value -c critical_value [-v]"
    parser = OptionParser(usage=usage)
    parser.add_option("-w", "--warning", type="float", dest="warning")
    parser.add_option("-c", "--critical", type="float", dest="critical")
    parser.add_option("-v", "--verbose", action="store_true", dest="verbose", default=False)
    (options, args) = parser.parse_args()
    if options.warning is None or options.critical is None:
        print parser.get_usage(),
        sys.exit(RETURN_UNKNOWN)

    # check cpu
    ps = Ps()
    cpu = ps.getTotal("CPU")

    status = RETURN_OK
    if options.warning <= cpu:
        status = RETURN_WARNING
    if options.critical <= cpu:
        status = RETURN_CRITICAL

    print "%s - CPU: %.1f%%" % (RETURN_VALUES[status], cpu)
    if options.verbose:
        print "\n" + ps.dump()

    sys.exit(status)


if __name__ == "__main__":
    main()

 

/etc/nagios/objects/commands.cfg

以下追加。

# 'check_cpu' command definition
define command{
        command_name check_cpu
        command_line $USER1$/check_cpu -w $ARG1$ -c $ARG2$ -v
}

 

/etc/nagios/objects/localhost.cfg

以下追加。

# Define a service to CPU on the local machine.
define service{
        use                             local-service
        host_name                       localhost
        service_description             Current CPU
        check_command                   check_cpu!50!80
        }

 

追記 2010-10-12 13:25:48

2行目以降は、$LONGSERVICEOUTPUT$で置き換えられた。

 

Nagiosの標準マクロ

http://oss.aspect-sys.co.jp/nagios_jp/macrolist.html