median
大き目の配列から中間値(median)を得る必要があり,単に sort してから中心の値を得る方法と,Modifind アルゴリズム (Hoare C.A.R (1971) CACM 14: 39- の FIND アルゴリズムを改良したもの) 及び Floyd R.W. and Rivest R.L. (1975) CACM 18: 173- の方法を,それぞれ Java で試してみた.

Modifind 法や F&R 法の解説や Rexx での実装例が
http://www.geocities.com/zabrodskyvlada/3alg.html
にあり,参考になった.Google のソースコード検索も役立った.

sort 法では, JRE の java.util.Arrays.sort() を用いた(条件が悪い場合を考慮した quicksort )ため,平均計算量は O(N * log(N)) である. Modifind 法 と F&R 法 は O(N) らしい. N は要素数.

手元の環境(JDK 1.5, Athlon64 3500+)では,およそ 10 k 要素の場合, sort 法は数秒, O(N) の方法ではその 1/10 くらいを要した.また, 100 M 要素くらいまで Modifind 法 が F&R 法より若干速かった.もっと大きくなると逆転するかもしれない. Modifind 法は F&R 法の半分以下の行数(30 行程)で書けることもあり,ひとまず Modifind 法を用いることにした.

一様乱数からなる double 配列からの median 算出時間
b0095474_113734.gif

[PR]
by edogawadai_bio | 2007-08-11 01:02 | comp
<< 7階スピニングディスク CLS... emacs + skk での変換待ち >>