2006-03-18

sort algorithm part4

ぷよぷよフィーバーのβ trial期間が終了しちゃったなり by d金魚

ぷよぷよフィーバーのβ trialが終了したのでPC版を購入したいと思っています。

既にぷよぷよフィーバーの２がコンシューマ機の方では発売されているらしいです。

PSとかPS2とかゲームキューブとかXBOXとかでぷよぷよをやりたい方はここをクリック

2006-03-18

flash sort最速の設定

Program ProgramIdiom

http://d.hatena.ne.jp/studiokingyo/20060303
にて
Misty氏（http://rainer.blog7.fc2.com/）にflash sortなるものを紹介していただいたのだが…
http://d.hatena.ne.jp/studiokingyo/20060303#p2
のように結果は散々だったものの
設定や条件を変えると
http://d.hatena.ne.jp/studiokingyo/20060303#p3
のように最速になる事が分かった。

Cの実装（http://www.neubert.net/Flacodes/FLACodes.html#Sprung3）の
flashsort(a,n,m,ctr)の最速条件を以下に示したいと思う。

浮動小数点データの配列である。(float,double,long double等)
データ長はある程度長い（512k個の要素数を持った配列くらい byte単位にすると 4194304byteほど）
double配列の要素数に対して4096分の1のサイズのTHRESHOLD
THRESHOLDの2倍のCLASS_SIZE
mはTHRESHOLDと同じサイズ
データの範囲は一様にrandomである(追記)*1
再帰呼び出しにならない(追記)(再帰呼び出し毎にメモリを確保するような実装なので遅い…)

関係性をC言語で表すと



const size_t element_size = 1024 * (512);/* == n */

const int THRESHOLD = element_size / 4096 ;

const CLASS_SIZE = THRESHOLD * 2;     /* minimum value for m */

const int m_value = THRESHOLD;

この設定でquicksort(クイックソート)(STLPortのstd::sort)より速くなる。
皆さんも試して見てはいかがかな？
えーっと希望でしたらソースアップしましょうか？（でも、自分で書いたソースじゃないし…なんかライセンス系がよく分からないので気が引ける。）

*1:一様にランダムでないとflashsortはstack over flowを起こす。

2006-03-18

O(n)!!? flash sort祭りリンク集

『増補改訂版Java言語で学ぶデザインパターン入門マルチスレッド編』無料プレゼント

self

『増補改訂版Java言語で学ぶデザインパターン入門マルチスレッド編』無料プレゼント
に応募しました。
http://d.hatena.ne.jp/hyuki/20060316
当たるとイイナ＾＾
皆さんもトラばって応募してみよう！！

2006-03-18

flashsortベンチマークソフト公開

Program software news 追記

flashsortの最速条件が環境依存かどうかを調べるために公開したflashsortをベンチマークするツールです。
http://www.dkut.flnet.org/test.html
からダウンロードできます。
結果はブログに書いてトラックバック送ってもらったりコメントに残してもらうと非常に嬉しいです。
皆様、どうか協力していただけないでしょうか？m(_ _)m