右クリックから一発で素材SWCが生成できるFlashDevelopプラグイン作った

cats

[FlashDevelop Assets Packager Plugin]


前置き

だいぶ昔ですが、Flash開発での素材管理についてこんな話題がありました。

「Flash 開発の議論 – あなたは Embed 派、SWC 派、Load 派? – Togetter」

Flash開発者にとって素材管理は悩ましい問題です。

タイムライン中心でFlashを作る場合は、Adobe Flash Professionalの素材管理機能をそのまま使えばいいので、問題になるのはFlashDevelop, FlashBuilder, FDTなどのエディタを使ってコードをガリガリ書いてFlashの開発をする場合です。

いろんな管理方法がありますが、それぞれにメリット、デメリットがあります。

自分が知っている主な方法は5種類です。

これまでの素材管理方法

Flash Professionalを使わない方法

① 素材1つ1つをLoaderで読み込み (ひとつづつLoad派)
例: 「FlashゲームPG講座 For AS3.0【ファイルの読み込みについて】」

② 素材1つ1つを[Embed()]タグで埋め込み (ひとつづつEmbed派)
例: 「Flash ActionScript3で画像を表示する ≪ Walk on apps.」

○ メリット

  • 有料ソフトウェアが要らない
  • 素材の変更がすぐ反映される

× デメリット

  • 素材一つ一つのパスやコードを書かないといけない。

Flash Professionalを使う方法

③素材をSWC化して、ライブラリとして使う。(SWC派)
例: 「SWCを利用したFlash制作の分業ワークフロー:FlashとFlash Builder連携開発 | デベロッパーセンター」

④素材をSWF化して、Loaderで読み込み。(SWF Load派)
例:「Flex で別 SWF のシンボルをロードする方法あれこれ – 俺の成長日記」

⑤素材をSWF化して、[Embed()]タグで埋め込み。(SWF Embed派)
例:「馬鹿全 – Flex と Flash CS3 の ハイブリッド SWF について」

○ メリット

  • コードの記述量が減らせる
  • フォントの範囲指定とか、ファイルの圧縮とかの管理機能がついてくる

× デメリット

  • Flash Proが高い(CS6は定価で84000円)
  • Flash Proが重い
  • 素材を編集した際の再設定がめんどくさい
  • 複数の開発ツールをまたぐので、敷居が高い

自分がよく使ってるのは③です。ただ、Adobe Flash Professionalが必要というのはかなりのネックになります。素材変更するごとにいちいち設定しなおしてパブリッシュするのメンドクサイですし、Flash Proが入ってないところで編集したい場合もあります。とはいえ、この中では一番楽なのでFlash Pro持ってる人はこの素材管理をしてる人が多いと思います。


…でもさ、Flash Proを使わなくてもさ、Embedの記述なんて自動化できるし、SWCの生成だってFlex SDKで出来るんだよね。この際、FlashDevelopのプラグインでも作っちゃった方が楽なんじゃねーの?

ってことで作りました。

FlashDevelop + Assets Packager Pluginでラクラク素材管理

Assets Packager PluginはFlashDevelop4用のプラグインです。

特徴

  • フォルダを、右クリックですぐ使える
  • [Embed]タグを記述したAS3ファイル、SWC、SWFが一発で生成
  • ディレクトリ構造とファイル名がそのままパッケージ名とクラス名に(普通のAS3ファイルといっしょ!)
  • png、gif、jpgをBitmapDataとして埋め込み
  • otf、ttf、ttc、dfontをFontとして埋め込み
  • mp3をSoundとして埋め込み
  • svg、svgzをSpriteとして埋め込み。(v1.5から)
  • as、mxmlはそのままのコードを埋め込み。(v1.2から)
  • txt、xml、swfなどその他すべてのフォーマットはByteArrayとして埋め込み
  • フォントファイルを、右クリック>>[フォントの設定]で埋め込む文字の指定が可能
  • Haxeでも使用可。生成されたSWFを-swf-libで指定。

2分ちょっとでわかる。Assets Packagerのインストール法と使い方。

インストール法はSourceForgeから.fdzダウンロードしてきて、ダブルクリックするだけです。

基本的な使い方

素材を放りこんだフォルダをFlashDevelopのプロジェクトマネージャー上で右クリック>>[素材をパッケージ]を選択するだけで、libフォルダ内に[Embed]を記述したAS3、SWC、SWFの3種類のファイルが一度に生成されます。

例えば、assetsフォルダ内に以下の4つのファイルを置いてパッケージ化した場合

  • assets/image/Background.png
  • assets/sound/SoundEffect.mp3
  • assets/font/Pixcell.ttf
  • assets/text/HelloWorld.txt

次の4つのクラスが自動で生成されます。

  • assets.image.Background (BitmapData)
  • assets.sound.SoundEffect (Sound)
  • assets.font.Pixcell (Font)
  • assets.text.HelloWorld (ByteArray)

これらを利用するためにどのようなコードを書けばいいかはサンプルコードを用意してあります。

SourceForgeでexample.zipをダウンロードしてください。

基本的には、生成されたAS3ファイルかSWCの参照を追加して各クラスをnewするだけです。それぞれ、BitmapData、Sound、Font、ByteArrayとして使うことが出来ます。

package {
	import assets.text.HelloWorld;
	import assets.font.Pixcell;
	import assets.image.Background;
	import assets.sound.SoundEffect;
	import flash.display.*;
	import flash.events.*;
	import flash.media.Sound;
	import flash.text.*;
	import flash.utils.ByteArray;
	
	[SWF(width=480,height=360)]
	public class EmbedTest extends Sprite {
			
		function EmbedTest() {
			//Font(ttf)
			var font:Font = new Pixcell();
			var tf:TextField = new TextField();
			tf.autoSize = "left";
			tf.embedFonts = true;
			tf.selectable = false;
			tf.defaultTextFormat = new TextFormat( font.fontName, 48 );
			
			//ByteArray(txt)
			tf.text = (new HelloWorld() as ByteArray).toString();
			tf.height = tf.textHeight;
			tf.x = (stage.stageWidth - tf.width) / 2;
			tf.y = (stage.stageHeight - tf.height) / 2;
			addChild( tf );
			
			//BitmapData(png)
			var g:Graphics = graphics;
			g.beginBitmapFill( new Background() );
			g.drawRect( 0, 0, stage.stageWidth, stage.stageHeight );
			
			//Sound(mp3)
			stage.addEventListener( 
				MouseEvent.CLICK, 
				function( e:Event ):void { new SoundEffect().play(); }
			);
		}
	}
}

結果:[example.swf]

フォントの設定

さらに、フォントファイル(ttf,otf,dfont)を右クリック>>[フォントの設定]をクリックでフォントの埋め込み範囲やフォント名に関する設定を行えます。

フォント_small

詳細設定

他のプラグインと同じようにツール>>環境設定>>AssetsPackagerから各種設定が行えます。
ここで拡張子の設定、各出力のオン/オフ切り替え、出力フォルダの指定ができます。

ライセンス

MITライセンスです。

更新履歴

2013/05/13 v1.5.0
– 拡張子設定”Sprite Extentions”,”MovieClip Extentions”を追加
– ‘.svg’,’.svgz’をSpriteとして対応
2013/04/13 v1.4.0
– 拡張子設定”Bitmap Extentions”を追加
– 拡張子’ttc’をフォントとして対応
– フォント設定に”太字”,”イタリック”を追加。
2013/03/18 v1.3.0
– 設定にcompcのコンパイラオプションを追加。
– コンパイル前のファイル名チェックを追加。
– ファイル名のマルチバイト文字に対応。
2013/03/16 v1.2.2
– 大文字の拡張子が無視されていたのを修正。
2013/03/15 v1.2.0
– .as,.mxmlのファイルをクラスとして埋め込まれるように設定。
– さらに、詳細設定で無視されるファイルの拡張子が指定可能に。
2013/03/14 v1.1.2
-C:以外のボリュームのプロジェクトで使用した際のエラーを修正。

迷路で眺める探索アルゴリズム

CodeVS2.0(サイト:http://codevs.jp/ 予選の連鎖動画:http://www.nicovideo.jp/watch/sm19873888)の復習をかねてこんなFlashを作りました。



迷路で眺める探索アルゴリズム(Search algorithm visualize)

さまざまなアルゴリズムを使って、迷路探索を行います。
使ったのは基本的な探索アルゴリズム8種とオリジナルのアルゴリズム2種です。

まずは迷路の見方について。

  • 青色(): Sがスタート、Gがゴール
  • 白色(): 未探索のマス
  • 灰色(): 探索済みのマス
  • 赤色(): 探索により発見されて、リストに保持されているの分岐点
  • 橙色(): 枝刈りにより、リストから削除された分岐点
  • マスに書いてある数字は、リスト内のマスにゴールに近い順に順位を付けたものです
    (間違い制限探索のみ異なるので後で解説)

つぎに操作方法について。

  • 左上のコンボボックス[…|+]でから眺めるアルゴリズムを選ぶ
  • [new]で新しい迷路に更新
  • [new]の左隣のチェックボックスで、2種類の迷路(分岐が多いor少ない)を切り替える
  • [speed]のスライドバーで再生速度を選択

さらにFlash下部のデータの読み方です。

  • 探索回数は迷路内で移動した回数です(灰,赤,橙マスの合計数と同じ)。計算時間(CPU Time)に直結します
  • 分岐数は、現在の探索中リストに追加されているマス(赤)の数です。メモリの使用量に直結します

各アルゴリズムの解説

深さ優先探索(Depth-first search)

深さ優先探索 – Wikipedia

ひたすら一本の道を突き進み、行き止まりがあったら、1つ前の未探索の分岐点に戻って再びその道を突き進む探索法。

特徴

  • 知識なし(評価関数を使用しない)
  • 探索範囲が有限の場合は完全(解を必ず見つけられる)。
  • ただし、探索範囲が無限の場合は不完全。
  • 省メモリ

ただし無限に広いフィールドで探索を行うと、ゴールが近くにあっても見逃してしまいゴールを見つけられない場合があります。

幅優先探索(Breadth-first search)

幅優先探索 – Wikipedia

現在までに見つかってる分岐すべてを一回、一回伸ばしていく探索法。

特徴

  • 知識なし(評価関数を使用しない)
  • 完全(解を必ず見つけられる)
  • 探索範囲が無限でも完全
  • 並列化しやすい

一般的には深さ優先探索よりメモリを大量に使う探索ですが、今回ような迷路探索は分岐が少なく行き止まりが多いので深さ優先探索よりも省メモリな探索になってます。

反復深化深さ優先探索(Iterative deeping depth-first search)

反復深化深さ優先探索 – Wikipedia

深さ制限を設けて深さ優先探索を行い、ゴールが見つからなかった場合は深さ制限をゆるめて再度探索する探索法。

特徴

  • 知識なし
  • 完全
  • 探索範囲が無限でも完全
  • 省メモリ

深さ優先探索の省メモリ性をそのままに、無限に広いフィールドでも使えるようにした探索法です。
ただし省メモリな実装を行うと同じ探索を繰り返し行うことになるので、探索時間が長くなります。
また、省メモリでない実装を行うと、幅優先探索と同等のメモリ消費になります。

知識あり探索と知識なし探索

反復深化深さ優先探索は一般的には知識なし探索です。知識なし探索とは評価関数の使わない探索法のことで、この迷路探索の場合ゴールの位置も分からずに盲目的に探索するような手法です。ただし、今回のFlashでは知識あり探索として、反復深化深さ優先探索をおこないました。

ここから先、すべての探索法は知識あり探索ですが、これらすべてで評価関数に現在値とゴールのマンハッタン距離を利用しています。

 マンハッタン距離を使うとゴールまで到達するのに絶対に必要な深さというのがわかります。例えば、スタートからゴールまでの距離が15マスあった場合、最低15回は枝を伸ばさなければゴールに到達できません。これにより、絶対にゴールに到達できない深さ制限というのが分かります。さらにこれにいくらかのマージン(デフォルトでは4)を上乗せした値を深さ制限に使って探索を行うことで計算量を減らしています。

山登り法(Hill climbing)

山登り法 – Wikipedia

ゴールに近い方向へとひたすら進んでいき、行き止まりがあったらそこで断念する探索法。

特徴

  • 知識あり(評価関数を使う)
  • 不完全
  • 省メモリ

今回の迷路探索ではすぐに行き止まりに突っ込むので、あまり使えません。

最良優先探索(Best-first search)

最良優先探索 – Wikipedia

すべての枝を保持して、それらの分岐の中から一番ゴールに近いものを選んで伸ばしいく探索法。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存

今回の迷路の条件と評価関数では、完全な探索方法としては最速になるはずです。

間違い制限探索(Limited discrepancy search)

始めに山登り法で探索を行い、解が見つからなかった場合は1回だけ最良では無い方向に行くことを許容して再び探索を行う。それでも見つからなければ、間違った方向へと進める回数(discrepancy)をさらに増やして探索を繰り返す手法。

注:この探索の赤マスに書かれた数字はそのルートの間違い数(discrepancy)です。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存
  • 省メモリ

反復深化と同様、繰り返し同じ探索を行うことになるため探索に時間がかかります。
ただし、評価関数によっては、省メモリ性、完全性、速度を併せ持つ非常に強力な探索方法となります。

幅優先ビームサーチ(Breadth-first beam search)

幅優先と同じ手順で探索を行い、分岐のリストが事前に決めておいた数(ビーム幅)より長くなった場合に、評価値の悪い枝を枝刈りする。

特徴

  • 知識あり
  • 不完全
  • 並列化しやすい
  • ビーム幅が1の時、山登り法と同じ。
  • ビーム幅が∞(無限)の時、幅優先探索と同じ。

最良優先ビームサーチ(Best-first beam search)

Beam Search – Wikibooks

最良優先と同じ手順で探索を行い、分岐のリストが事前に決めておいた数(ビーム幅)より長くなった場合に、評価値の悪い枝を枝刈りする。

特徴

  • 知識あり
  • 不完全
  • ビーム幅が1の時、山登り法と同じ。
  • ビーム幅が∞(無限)の時、最良優先探索と同じ。

ここまでがある程度知名度のある基本的なアルゴリズムで、次からがオリジナルの探索アルゴリズムになります。

優良優先探索(good-first search)

最良優先探索をより一般化した探索。1度に伸ばす枝の数を、1つに限らず複数にまで拡張した。
例えば、1度に伸ばす枝の数(優先幅)を3に設定した場合、保持されてる枝のうち良い枝から順に3つを延長する操作を繰り返す。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存
  • 優先幅が∞の時、幅優先探索と同じ
  • 優先幅が1の時、最良優先探索と同じ

二重制限探索(Double limit search, Good-first beam search)

優良優先探索にビームサーチを適用したもの。優先幅とビーム幅両方による制限を行う。

ただし、(優先幅)≦(ビーム幅)となる。

特徴

  • 知識あり
  • 不完全
  • 並列化しやすい
  • 優先幅、ビーム幅が共に∞の時、幅優先探索と同じ
  • 優先幅、ビーム幅が共に1の時、山登り法と同じ
  • 優先幅が1、ビーム幅が∞の時、最良優先探索と同じ
  • 優先幅とビーム幅が同じ時、幅優先探索ビームサーチと同じ
  • 優先幅が1の時、最良優先ビームサーチと同じ
  • ビーム幅が∞の時、優良優先探索と同じ

余談

 ここで紹介したアルゴリズムは各種アルゴリズムは迷路だけではなくて、15パズルや、codevsのような落ち物パズル、ソリティアのようなゲームの探索にも利用可能です。
 さらに、一工夫加えればチェスやオセロの様な対戦ゲームで利用することも出来ます。一見、ビームサーチは対戦ゲームでは使えないに見えますが、各手がどの程度良い手かではなく、各手がどの程度打たれやすいのか(この値は評価関数から算出できる)を考えてそれを基準に枝刈りを行えば、ビームサーチと同じような探索が可能です。

 ちなみにcodevsで使った探索法は幅優先ビームサーチでした。幅優先ビームサーチは実装も簡単で、評価関数を作る際にステップ数が異なる盤面の比較を気にする必要もありません。
 ただ一般的な場合でお勧めの探索法は二重制限探索です。実装の簡単さは幅優先ビームサーチとほぼ同じで、一度実装すればパラメータを変更するだけで、幅優先ビームサーチにしたり、最良優先ビームサーチにしたり、幅優先探索と最良優先探索の中間的な性質の探索にしたりできます。また、今回のような最良優先探索有利の課題に対してマルチコアで挑む場合、優先幅をコア数に合わせることで最良優先探索より高速な探索を行うことも可能になります。

あと、迷路生成アルゴリズムは古くて新しい自動迷路生成アルゴリズム – ガジェット通信を参考にクラスタリングアルゴリズムと穴掘り法を使用しました。

※追記:2017/05/27 wonderfl閉鎖によりリンク切れのため「How wonderfl!」へのリンクの差し替えをおこないました

マージソートで速度比較【C#, C++, Java, PHP vs. Haxe】

 最近はWindowsアプリケーションの制作にC#を使ってるんですが、Haxe/C++ってどうなのよ、C++と比べてどのくらいの速さなのよ?ってことが気になったので速度比較しました。つかったのは、マージソートです。理由は先日のCODE VS 2.0(http://codevs.jp/)で配列操作がボトルネックになってるように見えたからです。

マージソートって何?って人もいると思うのでちょっと紹介。

右上のrandomを押したあと、左上でMargeを選択してみましょう。
このような方法で数字の大小を比較して、順番に並べるのがマージソートです。

速度比較用コード

Haxe

package;

class Main {
    static inline var SIZE = 1000000;
    
	static function main() {
		var start = getTime();
        var arr = new Array<Int>();
		
		//Neko,PHP,Java,C#は初めに領域確保。これをやらないと配列を伸ばすごとに時間がかかる。
		#if (neko || php || java || cs)
		arr[SIZE - 1] = 0;
		#end
		
		for( i in 0...SIZE ){ arr[i] = SIZE - i; }
        margeSort( arr );
        var time:Int = Math.round(getTime() - start);
		trace( time + "ms" );
	}
     
    public static function margeSort( arr:Array<Int> ){
        var l   = arr.length;
        var tmp = new Array<Int>();
		
		#if (neko || php || java || cs)
		tmp[SIZE - 1] = 0;
		#end
		
        var i = 1;
        while( i < l ) {
            var j = 0;
            while( true ){
                var l0 = j + i;
                if( l0 >= l )    break;
                 
                var l1 = l0 + i;
                if( l1 > l ) l1 = l;
                 
                var p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0;
                 
                while ( true ){
                    if( val0 <= val1 ){
                        tmp[ tp++ ] = val0;
                        if( ++p0 == l0 ) break;
                        val0 = arr[ p0 ];
                    }else{
                        tmp[ tp++ ] = val1;
                        if( ++p1 == l1 ){
                            var tl = l0 - p0;
                            copyArray( arr, p0, arr, l1 - tl, tl );
                            break;
                        }
                        val1 = arr[ p1 ];
                    }
                }
                copyArray( tmp, 0, arr, j, tp );
                j = l1;
            }
            i <<= 1;
        }
    }
     
    public static inline function copyArray( source:Array<Dynamic>, sourceIndex:Int, target:Array<Dynamic>, targetIndex:Int, length:Int ) {
        var i = length;
        while( --i >= 0 ) target[targetIndex + i] = source[sourceIndex + i];
    }
	
	public static inline function getTime() {
		#if (flash || js || cs)
		return Date.now().getTime();
		#else
		return Sys.time() * 1000;
		#end
	}
}

 関数の頭にinlineと付けるだけでインライン展開できるのがポイント。Haxeから出力されたC++では、copyArrayの関数自体は消えてなくなり、中身のループが呼び出し位置に展開された形になります。

 あと、配列の長さが指定できないのが特徴で、PHP, Neko, C#, Javaに出力する際は注意が必要になります。これらの言語を選択した場合、配列の長さを伸びるごとに配列の長さに比例した時間が取られてしまいます。あらかじめ配列を伸ばしておいてから数値を代入しましょう。

 せっかくなので、JavaScript, AIR, NekoVM, PHP, C++, C#, Javaに出力しました。上のコードでこれらすべての言語に対応してます。

C#

using System;
using System.Diagnostics;

namespace SpeedTest{
	class Program{
		public const int SIZE = 1000000;
		
		public static void Main(string[] args){
			var sw = new Stopwatch();
			sw.Start();
			
			int[] arr = new int[ SIZE ];
			for( int i = 0; i < SIZE; i++ ){
				arr[i] = SIZE - i;
			}
			MargeSort( arr );
			
			Console.WriteLine( sw.ElapsedMilliseconds + "ms" );
			Console.ReadKey(true);
		}
		
		//小さい順にソート
		public static void MargeSort( int[] arr ){
			int 	l 	= arr.Length;
			int[] 	tmp	= new int[l];
			
			for( int i = 1; i < l; i <<= 1 ){
				for( int j = 0, l0, l1; ; j = l1 ){
					l0 = j + i;
					if( l0 >= l )	break;
					
					l1 = l0 + i;
					if( l1 > l )	l1 = l;
					
					int p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0;
					
					while( true ){
						if( val0 <= val1 ){
							tmp[ tp++ ] = val0;
							if( ++p0 == l0 ) break;
							val0 = arr[ p0 ];
						}else{
							tmp[ tp++ ] = val1;
							if( ++p1 == l1 ){
								int tl = l0 - p0;
								var targetIndex = l1 - tl;
								var i1 = tl;
								while(--i1 >= 0) {
									arr[targetIndex + i1] = arr[p0 + i1];
								}
								
								break;
							}
							val1 = arr[ p1 ];
						}
					}
					
					{
						var i1 = tp;
						while(--i1 >= 0) {
							arr[j + i1] = tmp[i1];
						}
					}
				}
			}
		}
	}
}

 copyArrayの部分はループに変更しています。普段ならそんなめんどくさいことやらないでArray.Copy()を使ってますが、Array.Copy()使うと50msくらい遅くなります。

C++

#include <iostream>
#include <time.h>

using namespace std;
int SIZE = 1000000;

void margeSort( int* arr, int l ){
    int* 	tmp	= new int[l];

    for( int i = 1; i < l; i <<= 1 ){
        for( int j = 0, l0, l1; ; j = l1 ){
            l0 = j + i;
            if( l0 >= l )	break;

            l1 = l0 + i;
            if( l1 > l )	l1 = l;

            int p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0;

            while( true ){
                if( val0 <= val1 ){
                    tmp[ tp++ ] = val0;
                    if( ++p0 == l0 ) break;
                    val0 = arr[ p0 ];
                }else{
                    tmp[ tp++ ] = val1;
                    if( ++p1 == l1 ){
                        int tl = l0 - p0;
                        int targetIndex = l1 - tl;
                        int i1 = tl;
                        while(--i1 >= 0) {
                            arr[targetIndex + i1] = arr[p0 + i1];
                        }
                        break;
                    }
                    val1 = arr[ p1 ];
                }
            }
            {
                int i1 = tp;
                while(--i1 >= 0) {
                    arr[j + i1] = tmp[i1];
                }
            }
        }
    }
}

int main() {
    int start = clock();
    
    int* arr = new int[SIZE];
    for( int i = 0; i < SIZE; i++ ){ arr[i] = SIZE - i; }
    margeSort( arr, SIZE );
    
    std::cout << (clock() - start) << "ms\n";
    return 0;
}

 C++は苦手です。やりようによってはまだまだ高速化できるのかもしれませんが、わからないのでできません。C#のコードをなるべくそのまま移植しました。

Java

public class Main {
    public static final int SIZE = 1000000;
	
    public static void main(String[] args) {
        // TODO code application logic here
        long start = System.currentTimeMillis();
        int[] arr = new int[ SIZE ];
        for( int i = 0; i < SIZE; i++ ){
            arr[i] = SIZE - i;
        }
        margeSort( arr );
        
        System.out.println( (System.currentTimeMillis() - start) + "ms" );
    }

    //小さい順にソート
    public static void margeSort( int[] arr ){
        int 	l 	= arr.length;
        int[] 	tmp	= new int[l];

        for( int i = 1; i < l; i <<= 1 ){
            for( int j = 0, l0, l1; ; j = l1 ){
                l0 = j + i;
                if( l0 >= l )	break;

                l1 = l0 + i;
                if( l1 > l )	l1 = l;

                int p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0;

                while( true ){
                    if( val0 <= val1 ){
                        tmp[ tp++ ] = val0;
                        if( ++p0 == l0 ) break;
                        val0 = arr[ p0 ];
                    }else{
                        tmp[ tp++ ] = val1;
                        if( ++p1 == l1 ){
                            int tl = l0 - p0;
                            System.arraycopy( arr, p0, arr, l1 - tl, tl );
                            break;
                        }
                        val1 = arr[ p1 ];
                    }
                }
                System.arraycopy( tmp, 0, arr, j, tp );
            }
        }
    }
}

 C#のコードをほぼそのまま移植しました。こうやって見るとほんとC#にそっくりです。配列のコピーはループよりSystem.arraycopy()のが高速でした。

PHP

<?php
function margeSort($arr) {
	$l = count($arr);
	$tmp = array();
	for ($i = 1; $i < $l; $i <<= 1) {
		$j = 0;
		while(true) {
			$l0 = $j + $i;
			if($l0 >= $l) { break; }
			$l1 = $l0 + $i;
			if($l1 > $l) { $l1 = $l; }
			$p0 = $j; $p1 = $l0; $val0 = $arr[$p0]; $val1 = $arr[$p1]; $tp = 0;
			while(true) {
				if($val0 <= $val1) {
					$tmp[$tp++] = $val0;
					if(++$p0 === $l0) {
						break;
					}
					$val0 = $arr[$p0];
				} else {
					$tmp[$tp++] = $val1;
					if(++$p1 === $l1) {
						$tl = $l0 - $p0;
						$targetIndex = $l1 - $tl;
						$i1 = $tl;
						while(--$i1 >= 0) {
							$arr[$targetIndex + $i1] = $arr[$p0 + $i1];
						}
						break;
					}
					$val1 = $arr[$p1];
				}
			}
			{
				$i1 = $tp;
				while(--$i1 >= 0) {	$arr[$j + $i1] = $tmp[$i1]; }
			}
			$j = $l1;
		}
	}
}

define( "SIZE", 1000000 );
$start = microtime(true) * 1000;
$arr = array();
$_g = 0;
while($_g < SIZE) {
	$i = $_g++;
	$arr[$i] = SIZE - $i;
}
margeSort($arr);
$time = floor(microtime(true) * 1000 - $start);
echo $time."ms";
?>

Haxe/PHPがあまりにもかわいそうな結果だったので、PHPも書きました。こっちのがいくらかマシです。

結果

速い順です。

言語 時間[ms] C++との比較
C++ 37
C# 72 1.95倍
Java 74 2倍
Haxe/C++ 119 3.22倍
Haxe/JS [Node.js] 274 7.41倍
Haxe/C# 501 13.5倍
Haxe/AIR 744 24倍
Haxe/Java 1155 31.2倍
Haxe/Neko 4282 116倍
PHP 19853 537倍
Haxe/PHP 132853 3590倍

 やはりC++が高速。続いて、C#,Javaがほぼ同じ。ちょっと遅れてHaxe/C++。

 Haxe/C++とC#で結構な差があるように見えますが、先述のArray.Copy()でひっくり返りかねない差なので、C#,Java,Haxe/C++は同じくらいのレベルと考えていいと思います。個人的にC++はあまり使いたくないので、速さが必要なプログラムはこの3つのどれかで作ることになるでしょうか。

 Haxeはマージソートくらいだと他言語に簡単に移植できるのがいいですね。ついでなので他の言語への移植もしてみましたが、Haxe/JSはかなり健闘しました。Node.jsって遅いイメージがあったんですが、かなり高速らしいです。

 Haxe/AIRは、まあ普通という感じです。AS3で書いてもこのへんになる気がします。
 
 Haxe/C#、Haxe/Javaはベータ版ということもありまだ洗練されていないように見えます。これからに期待。
 
 Haxe/Nekoも遅いですね。Node.jsの方がはるかに速いです。
 
 PHPが遅いのは当然の結果ですね。C++の500倍遅かろうとPHPは良い言語ですし…。そもそも、PHPで速度が必要なプログラム書くこと自体が間違ってますし…。HTML生成できて、JSON出力できて、データベース操作できて、exec()でコマンド実行出来れば、それだけでPHPは価値があると思いますね。

 Haxe/PHPはさらに遅いです。PHPはただでさえ遅いのに配列に独自のクラスをつかってるので、無駄な関数呼び出しが発生してるようでした。Haxe/PHPはPHPの良い部分も死んでる(HTMLに直接書き込めない、1ページに1プロジェクト必要など)気がするので、自分が使う機会はなさそうです。

 ともあれ、Haxe/C++, Haxe/JS, Haxe/Flash(AIR)はかなり実用的だと思います。これだけできれば、モバイルでも、ブラウザでも、サーバーサイドでも、PCネイティブでも使えるので、プラットフォームと使える言語がマッチしなくて困ることはほぼ無さそうです。

 Haxeに興味を持った人はとりあえず公式サイト(http://haxe.org/?lang=jp)にどうぞ。

使った環境について

Windows 7 Home Premium 64-bit
Intel(R) Core(TM) i5-2430M
メモリ: 4G

Haxe 2.10, cygwin gcc 3.4.4(C++), .NET Framework 4.5(C#) 4.0(Haxe/C#), Visual Studio 2010(Haxe/C++), node.js 0.8.11, AIR 3.4, neko vm 1.8.2, php 5.3.10