ma38su.sourceforge.jp

いい加減、sourceforgeでブログを書くのもなぁと思いまして、ma38su.orgへ移転することにしました。

しばらくはこのままこちらのページも保存しておくつもりですが、基本的に今後の更新は行なわない方針で考えています。

WordPressのテーマ、wp.Vicunaの拡張テーマ、プラグインについては、ma38su.org - wp.Vicuna Ext.で更新していくつもりです。

A new english pages is ready in http://ma38su.org/en/.

Gmailがロックされた。なにあの仕様？多分、容量オーバのファイルを添付しようとして失敗したけど本文書いてたのをほってたら、Firefoxが勝手に何度もアップロードしなおしてて（でも再アップロードするようなコードを書いてるのはGoogle!）、いつの間にか、不正利用としてロックされた。。。

ありえん。。。POPでメールを引っ張れたし、ほとんど転送で使ってるからさほど害はないけどさ。。。

もう解除されてた。けど、怖いな。

あー、行く用意しな。。。

この間、ぶらーっと観に行ってきた。あんまり期待してなかったものの話にも演技にも引き込まれてしまった。津川雅彦って落語家やっけとか思ったくらい。いやー、いい映画をみたって気分で帰れた。いやーよかった。この間の1000000YEN Girlも結構よかったけど、それ以上か。

そういえば、デトロイト・メタル・シティは、30分前から立ち見になってたけど、おもろいんかな？

最近、わざわざ映画館までいくのは、映画だけを観る時間を求めてるからのような気がする。

最近、sourceforge.jpにアクセス拒否されてるみたい。困った困った。

ASにもJavaのコレクションフレームワークみたいなのを実装してくれないものかなと思いつつ気分転換に書いてたのをせっかくなので晒す。

package org.ma38su.util
{
	/**
	 * ヒープを実装したクラスです。
	 * コンストラクタに比較関数を定義することで、自由に要素の順序を定義することができます。
	 * 比較関数の引数は2、戻り値は、intでもNumberでも比較できる型であればかまいません。
	 * 比較関数の戻り値が0のとき、要素は等しいと判断され、
	 * 0より大きいとき、1番目の引数よりも、2番目の引数が小さいとされ、
	 * 0より大きいとき、1番目の引数よりも、2番目の引数が大きいとされます。
         * @author ma38su
	 */
	public class Heap
	{
		/**
		 * ソートされるオブジェクト
		 */
		private var entries:Array;

		/**
		 * 要素間の比較をする関数
		 */
		private var comparator:Function;

		/**
		 * ヒープのコンストラクタ
		 * @param comparator 比較関数
		 */
		public function Heap(compareFunction:Function=null) {
			entries = new Array();
			entries.push(null);
			this.comparator = compareFunction;
		}

		/**
		 * @param entry 挿入する要素
		 */
		public function add(entry:Object):void {
			entries.push(entry);
			fixUp(entries.length - 1);
		}

		/**
		 * 入れ替える
		 * @param index1
		 * @param index2
		 */
		private function swap(index1:uint, index2:uint):void {
			var tmp:Object = entries[index1];
			entries[index1] = entries[index2];
			entries[index2] = tmp;
		}

		/**
		 * ヒープの先頭（根）の要素を削除して取り出す
		 * @return ヒープの先頭の要素
		 */
		public function poll():Object {
			if (entries.size == 0) {
				return null;
			}
			var entry:Object = entries[1];
			if (entries.length > 2) {
				entries[1] = entries.pop();
			} else if (entries.length == 2){
				entries.pop();
			}
			if (entries.length > 2) {
				fixDown(1);
			}
			return entry;
		}

		/**
		 * 削除せずにヒープの先頭（根）の要素を取り出す
		 * @return ヒープの先頭の要素
		 */
		public function peek():Object {
			return entries[1];
		}

		/**
		 * 子との状態の比較、必要に応じて移動
		 * @param index 比較する要素の添字
		 */
		private function fixDown(index:uint):void {
			var son:uint;
			while ((son = index << 1) < entries.length) {
				var nson:uint = son + 1;
				if (comparator ==  null) {
					if (nson < entries.length && entries[son] > entries[nson]) {
						son = nson;
					}
					if (entries[index] <= entries[son]) {
						break;
					}
				} else {
					if (nson < entries.length
								&& comparator.call(null, entries[son], entries[nson]) > 0) {
						son = nson;
					}
					if (comparator.call(null, entries[index], entries[son]) <= 0) {
						break;
					}
				}
				swap(index, son);
				index = son;
			}
		}

		/**
		 * 親との状態を比較、必要に応じて移動
		 * @param index 比較する要素の添字
		 */
		private function fixUp(index:uint):void {
			var parent:uint;
			while ((parent = index >> 1) > 0) {
				if (comparator == null) {
					if (entries[index] >= entries[parent]) {
						break;
					}
				} else {
					if (comparator.call(null, entries[index], entries[parent]) >= 0) {
						break;
					}
				}
				swap(index, parent);
				index = parent;
			}
		}

		/**
		 * ヒープが空かどうかの確認
		 * @return ヒープに空ならtrueを返す
		 */
		public function isEmpty():Boolean {
			return entries.length <= 1;
		}

		/**
		 * ヒープの要素数を返す関数
		 * @return ヒープの要素数
		 */
		public function size():uint {
			return entries.length - 1;
		}
	}
}

あー、一応ラクダの本とか、アルパカの本とかもちょこちょこ目を通してますよ。

JavaのKD-treeをActionScriptに書き直して、k近傍探索を実装してみた。

Continue reading