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を起こす。