ホーム > ニュース > 分位数ルーチン開発

分位数(quantile)を高速に求める新ルーチン開発!

NAG数値計算ライブラリの次期バージョンに追加

NAG数値計算ライブラリの次期バージョンには分位数を高速に求めるルーチンが追加されます。

高速分位数計算

分位数とはその値の下に指定された割合のデータが含まれる事を示す値です。 良く使われる分位数の1つに中央値がありますが、この値は、データを小さい順に並べて そのちょうど真ん中を示す値です。NAGの言い方では0.5(50%)quantileとなります。

同様にパーセンタイル(percentile)は0.01 quantile, 0.02 quantile, ...となります。

NAGではある金融機関より「非常に大きなデータから高速に分位数(quantile)を求めたい」との要望を受け この新しいルーチンの研究開発を行いました。一般的な方法としてはまず与えられたデータを小さい順に 並べ替えて、希望の位置から値を求めますが、この場合データが多くなればなるほど、並べ替え(ソート)の時間が 多大になってきます。

これに応えNAGのコラボレーターである、Oxford大学の教授Mike Giles氏が部分的なクイックソートアルゴリズムを開発しました。 このアルゴリズムは、NAGライブラリにすでに含まれているクイックソートルーチンをベースに開発がなされました。 その結果非常に効率的な計算ルーチンが新たにできあがりました。効率的な理由は、分位数を求める際に部分的な並べ替えが 必要で、すべてを並べ替える必要がないことをアルゴリズム化した点があげられます。

以下のグラフは既存のQuick Sortルーチン(M01CAF)と、新たに開発されたルーチン(G01AMF)の 比較を行ったものです。

新しいルーチンはNAG数値計算ライブラリの次期バージョン(Mark22)に含まれます。

Results matter. Trust NAG.

Privacy Policy | Trademarks