乱数の順位付けのアルゴリズム

質問

[0,1]の範囲で乱数を1000個、配列に発生させて、小さいもの100個を選び出すアルゴリズムということを考えます（知りたいのは数値と配列番号、むしろ配列番号が大事）。まず想定できるのはソートですが、それにもいろんなものがあり、クイックソート、バブルソートなどが挙げられます。ソートのアルゴリズムは既に開発されつくしたのかもしれませんが、どのようになっているでしょうか。一番高速な（かつ間違いない）な方法が１つあればそれを採用したいのですが。
そして１つ厄介なのですが、そのトップ100個以外の900個はソートする必要がないということです。私が考えているアルゴリズムは、
１．既に100個の選ばれていると仮定（初期はすべて１）
２．新しい1個が来たとき、100個の最低値よりも小さいなら考慮の対象なのだから最低値を交換してその100個でソートする。そうでない場合は何もしない。
３．次の新しい1個を調べて、項目２をする。
４．発生させた1000個でそれを繰り返す。
このアルゴリズムだと100個のソートを何百回かぐらいやることになります。
これをするぐらいだったら1000個のソートを1回やればいいということになるでしょうか（不必要な残りの900個もソートされてしまう）。あるいはその1回の1000個のソートの中でやる必要のない処理を排除する工夫があるかもしれません。

問題が難しくなく、素人っぽくコード化できると思いますが、その分、非効率なところも放置されそうなので高速化できるコードの書き方があったら教えて頂きたいのですが。コードというよりアイディアだけ説明していただいても助かります。実際はフォートランになると思いますが。よろしくお願いします。

回答No.8

akayoroshi

クイックソートのアルゴリズムを使う。ピボットを任意に選んでそれ以下のものとそれより大きいものの2つのグループに分ける。ピボットに選んだ値が100番目よりも前にきたら、前半のグループと後半のグループをそれぞれ再帰的にソートする。100番目以降になっていたら、前半のグループだけを再帰的にソートする。これでできるのだが、ソートの途中でグループの大きさが100以下になっていたら挿入ソートを使うほうが速いかもしれない。

回答No.6

f272

> このような組み込み関数の仕様について正式な仕様説明ってどこかに出ているでしょうか。

本当に調べるのなら
JIS X 3001-1　プログラム言語Fortran—第1部：基底言語
JIS X 3001-2　プログラム言語Fortran—第2部：可変長文字列
またはISO/IEC 1539-1:1997やISO/IEC 1539-2:2000を見ることになるんでしょうが，実際にはネットで適当に調べれば十分なことがほとんどです。

> maxloc(r100, 1)の２つの目の引数1の意味が分かりませんでした。

ここでr100は2次元配列です。このうちの1番目の次元について，r100の最大の値をもっている最初の要素の位置を調べるのです。
結果は元の配列がn次元のときには，(n-1)次元の配列になります。
たとえば
B=[1 3 -9]
__[2 2 6]
のとき
MAXLOC(B,1)=[2 1 2]
MAXLOC(B,2)=[2 3]
となります。

> 組み込み関数の部分はもちろん最適化されており精度・速度ともプロレベルに設定されているということですね。

そう信じていますが...

回答No.5

AsarKingChang

f272さんども！
フォートランはわからなかったので＾＾
アルゴリズムしか紹介できませんでしたんで。助かりました＾＾

もし、データが、
一つ当たり10個以上（カラム）あり、その中のデータ１～データ１０として、
データ「５」の値でソートせよだと。またアルゴリズムは変わりますよ。
こうなると、1回のソートで10個のデータが移動対象になるので、
この場合はまた、違うアルゴリズムを使いますが。

今回は、シリアライズデータなので、これで十分かな～と
思ってますが。

回答No.4

f272

面白そうなので書いてみた。アイディアはAsarKingChangさんと同じですが，ソートはしていません。10000回実行させても1秒はかかりません。

program skmsk1941093
implicit none
real :: t1, t2
integer,parameter :: n1 = 100
integer,parameter :: n2 = 1000
real :: rr(n2,2), r100(n1,2)
integer :: i, j, itask, jj(2)

call cpu_time(t1)　　　!時間計測
do itask = 1, 10000 !時間を稼ぐため10000回実行する

call random_number(rr)
do i = 1, n2
rr(i,2) = i
end do
!ここまででrr(:,1)に値を格納。rr(:,2)はインデックス

r100 = rr(1:n1,:)
jj = maxloc(r100, 1)

do i = n1+1, n2
if (rr(i,1) < r100(jj(1),1)) then
r100(jj(1),1) = rr(i,1)
r100(jj(1),2) = i
jj = maxloc(r100, 1)
end if
end do

end do
call cpu_time(t2)　　　!時間計測

! --- output
do i = 1, n1
print "(f10.4,f10.0)", r100(i,1), r100(i,2)
end do
print *, "cpu time:", t2-t1, "seconds."
end program skmsk1941093

お礼

ソース例まで頂き、回答ありがとうございます。この質問をする前に、fortran95の組み込み関数としてmaxloc, maxvalなどが提供されていることに気づきませんでした。これがあるのとないのではだいぶ違うように思います。このような組み込み関数の仕様について正式な仕様説明ってどこかに出ているでしょうか。
maxloc(r100, 1)の２つの目の引数1の意味が分かりませんでした。私設ガイドブックのようなものの説明ではランクがどうの、と書いてあるのですが、配列の中で最大となる場所の配列番号というシンプルな意味しか読め取れなかったのですが。組み込み関数の部分はもちろん最適化されており精度・速度ともプロレベルに設定されているということですね。もう作ってあるライブラリを組み合わせて仕事していくpythonのようなものでもいいかなと思いますが。

回答No.3

AsarKingChang

>後段のご指摘の”40番目に入りそうだったら”というのはどのように判定するのでしょうか。
new_val=???;
for (i=0;i<100;i++) {
if (new_val<data[i]) {
/* 小さい順に並んでいるわけなので、それよりも小さいという事は、
　今回格納が必要だという証拠で、さらに、この時の「i」の位置が
　新規で挿入される位置 */
}
}

5 6 7 8 9 10 とテーブルに入っているとき、新しい値として「6'」が来たら。
index=0 6'<5 NG
index=1 6'<6 NG
index=2 6'<7 OK
となり、3番目の値（インデックスの2番）に挿入する。
「5 6」の2個はそのままで、そのあとに新しいほうの「6'」を入れる。
「5 6」+「6'」
その後、もともとのテーブルの「末尾を削除した物」を結合
「5 6」+「6'」+「789」
なので、７８９がシフト対象のテーブルという事。
総移動数は「5 6 7 8 9 10」の長さ6セット　－　ヒットした位置2　＝　4個
（1個減ったように見えるのは、最後の1個を捨てるため）
これで、どうでしょうか？

なお、実際に作るときは、後方シフトで作ってくださいね。
12345
12345
この場合、「５から１に向かって」です。
「１から5に向かって」やると、
data[1]=data[0]; の時点で、次のターンがdata[0]のクローンになるので、
全部のインデックスが、data[0]で埋め尽くされます。（やれば意味が分かります）

回答No.2

AsarKingChang

>101個目以降は、100番目（配列99）を下回る値か？チェックして、
>下回るならソートして格納。
>ソート結果が101件になるので、101件目を捨てる。
ごめ。これちっと不要だわ。
data[99]=new_val;
sort();
いきなり100番目を上書きしてもいいや。少なくとも事前に100番目より小さいか？聞いているんだから、ソート後、元の100番が必ず101になることは
やる前からわかってることだから。100件ソートだけでいいね。

本気で高速化するならもともとソートはほぼいらない。
計算上40番に入りそう？だったら、
0～39：新しい値：40～100（100番を捨てるだけ）
とシフトするだけでいいわけだから。
配列の中身を、右側（大きい側）に動かすだけの、サブルーチン1個
作って、どの位置からシフトすればいいの？
というパラメタを持たせるだけで、終わるよ。

この場合、平均ストレス値は100/2=50となる。
（0番だと、100回シフトだが、100番なら0回シフトなので）
確率上、約半分の作業量になるから。
さらに、入り口で、100番（99番の配列）をチェックしてるので、
1000/100＝10％が格納されると推測。

ある円盤の1点からの移動は右回転でも左回転でも、
反対側から戻るのが一番遅いが、1週回ることはない。。
って理屈と同じね。

お礼

回答ありがとうございます。前段はよくわかりました。100個のソートは100番目（配列で言うと９９：交代要員）を指定するためだけに使うわけですね。

後段のご指摘の”40番目に入りそうだったら”というのはどのように判定するのでしょうか。また、このアルゴリズムは結果として問題ないものになるでしょうか。動的プログラミングのように真値に至らない可能性が残るということはないでしょうか。
　今回、高速化というのも大事でして、本当の目的は空間に浮遊している数多くの粒子の相互作用をみるためのものですが、全数総当たり調査などできないので、ある粒子について調査する粒子を100個ぐらい決めておいてそれだけに対して操作をするというものです。つまり近い距離のものを100個ぐらい抽出しておくということです。初めに決めたものだけをやるというのは問題なので時々、チェックするわけですが、それを高速化したいと思っています。それが最終目標なので高速化は重要なのです。

回答No.1

AsarKingChang

>２．新しい1個が来たとき、100個の最低値よりも小さいなら考慮の対象なのだから最低値を交換してその100個でソートする。そうでない場合は何もしない。

ここが、逆！
「最大値」より大きいならにすればOK

1000個のランダム値の最初の1個・・・例として0.5としてみます。
0.5が入ってくるー＞100個以内は無条件格納。
（この格納はソートなしで先頭からまともにいれてOK）
という感じ。
100個までは素直に入るが、この時点ではソートする必要はない。

100個たまったら、一度ソート
なので、最初の100個入ったか？のカウントのためのindex変数を1個使うほうが
効率は良いだろう。

101個目以降は、100番目（配列99）を下回る値か？チェックして、
下回るならソートして格納。
ソート結果が101件になるので、101件目を捨てる。

後は、1000個までどんどんつっこむ！
（別に何個でもいい、どうせ先の100個より大きい値は入り口で無視されるため）
そうすることで、不要なソートはなくなる。
（ついでに、1000個格納する必要もないのでメモリも食わない）

要するに、今の配列に入る値なのか？を問うことで不要な計算をなくすというやり方。
ソートが小さい順である指定なので、逆に言えば、配列の末尾は
「その中で一番大きい値」だということが証明されているので、
その、末尾と比較を1度するだけで、入り口時点で、蹴ってしまえる。

という方式です。

お礼

回答ありがとうございます。すでに出来上がっている100個のグループに対して新値がぶつけられたとき、交代するかどうかを調べるわけですが、最大値（交代要員）を探しておけばよいということになりますかね。その交代要員と新値を比べて新値が小さいなら交代要員と交代するということで、交代したら次の交代要員を探すときに100個のソートをするということですね。fortran95でやろうと思っているのですが、その組み込み関数に配列中の最大値とその配列番号を返す関数があることがわかりました。その関数があるとソートしなくてもいいということになりそうです。高速で動作してくれる関数なのかどうかが重要かもですが。