まあ、集合って言っても実態は通常配列またはﾘｽﾄです。
つまり、AとBはどちらもDを表すオブジェクトの配列またはﾘｽﾄです。
ある条件、というくらいだから、その条件で「より条件に近いか遠いか」、つまり大小を比較できるわけです。従って何も上位n個に限った話ではなく、別に下位n個だって昇順か降順かの違いだからどっちでも好きに読み替えてください。
求めかたその1: 全部Aをソートして、上位からdをn個取り出してBにコピーする。
→まあ、あまり他人には見せないほうがいいと思います。多分「膨大な」という形容詞を見落としています。
求め方その2: とりあえずAからn個まではdをコピーしてBを作成し、以後はBにAからdを1つ追加して、Bをソートして、Bから最下位のデータを除いて常にn個になるようにする。
→いくら優秀なソートアルゴリズムでも平均O(n log n)の計算量が必要になるのに、それをAの件数-n回やるなんて豪快ですねえ。但し、もしこんなコードを書いて見せて誰も指摘してくれないのなら、あなたは相当嫌われています。
求め方その3: Aからdを1つ取り出し、Bに挿入すべき位置を二分探索法で探索し、その位置にdを挿入する。
→この際、Bは配列(動的でも静的でも同じ)である必要があります。理由は後述します。
Bを線形探索すると計算量はO(N)、対して二分探索法の計算量はO(log N)で圧倒的に高速です。但し、n個目末尾以外への挿入にO(N)の計算量がかかります。挿入位置以後の要素を、一番最後の要素を除いてひとつづつ後ろにずらす必要があるからです(Bへの追加数がまだn個に達していない、またはn個目だった場合は挿入ではなく代入すればいいので計算量はO(1)。n個目以上だったら何もしないので配列操作に対する計算量はゼロ)。
一方、Bが連結ﾘｽﾄの場合は二分探索法はBの要素をランダムアクセスする必要がありますが、連結ﾘｽﾄのn番目の要素を参照するためには線形探索が必要で、O(N)の計算量が必要となるため、最初から線形探索を用いて挿入位置を探索したほうがマシです。但し、連結ﾘｽﾄの挿入の計算量はO(1)のため、Aから取り出すdのほとんどがBでの上位争いするような場合には連結ﾘｽﾄのほうが有利となります。とはいえ、一般的には探索する計算量のほうがはるかに多いでしょう。
というわけで、求め方その3をお勧めします。
※O(N)とかO(1)とかO(n log n)ってなんだよ!意味わかんねーよ!!という方へ:
以下をご提案しますのでご検討ください。
1.「計算量 ｸﾞﾗﾌ」で画像検索してみる。(計算量が直感的につかめます)
2.「ランダウの記号」、または「オーダー記法」で検索して引っかかった記事を軒並み読む。
3.分からないものはそのままそっとしておける、大人な選択ができる自分を大切にする。
まあ、これだけで記事を終わらせて納得するような人はそもそもこんな記事読みませんよね。
具体的に「dをBに挿入すべき位置を二分探索法で探索」するとはどういうことなんだ、と叱られてしまいます。
まず二分探索法とは何か、なんて解説なんか誰も求めてないのでしません。
まあ、こんな感じです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | int BinarySearch( D d /* Aから1つ取り出したもの */, D[] B /* 文中のB配列への参照 */ ) { int searchBoundTop = 0; /* B配列の先頭要素のindex */ int searchBoundBottom = B.length - 1;/* B配列の最後の要素のindex */ int middle = 0; /* 上記2変数の真ん中 */ while ( searchBoundTop <= searchBoundBottom ) { middle = ( searchBoundTop + searchBoundBottom ) / 2; int result = Cmp( B[ middle ], d ); /* ソート用比較関数と同じもの */ if ( result == 0 ) { return middle; } else if ( result < 0 ) { searchBoundTop = middle + 1; } else { searchBoundBottom = middle - 1; } } return ~searchBoundTop; } |
この関数の戻り値が挿入すべき位置を示します。
戻り値が0以上だった場合、すでにdがBに存在していますので、Bで等価のdの重複が必要ならBのその位置に挿入してください。
戻り値が0未満だったら、dがBにまだ存在していないことを示すと同時に、1の補数でdのBへの挿入位置を示しています。
1の補数ってこの処理系じゃ使えねえよ、という人は21行目からチルダ(~)を除いてください。0を含む正数しか返ってこなくなります。但し、等価のdがBに既に存在していたかどうかはわからなくなります。
dが既存かわかんないんじゃ困るという場合は
return -( searchBoundTop + 1 );に書き換えるとかすればsearchBoundTopの1の補数表現と同等の値が得られます。
もっとも、そんな処理系だったら中央値を計算する際に2で割ってる時点でもうこの関数は動かなくなります。小数点以下切り捨ての処理の追加が必要になるでしょう。
面白い例だとjavascriptは内部表現が32ビット整数だった場合はNOT演算は上記同様チルダ(~)で同等の処理が行えますが、いずれにせよ中央値の計算が例えば(1+2)/2だった場合、答えが1ではなく1.5となるので浮動小数しか扱えない処理系のように明示的にMath.floor()が必要になるでしょう。
なお二分探索法のライブラリはほとんどどんな言語にもあると思いますが、見つからない場合は常に-1やNULLを返すような仕様のライブラリもあります。
まあ、なんだかんだ言って二分探索法は応用が利くので覚えておいて損はありません。
以上、お読みいただきありがとうございました。
ところで、C#のジェネリック型のListって、時々勘違いされておいでの方がいますが、あれは中身はﾘｽﾄではなく動的配列です。
メンバ関数にBinarySearch()が用意されていて、さっきご紹介した関数と全く同じ値が得られます。が、C#のようなゴージャスな処理系ならHashSetやSortedList等、ライブラリがとても充実しているのでList.BinarySearchを使わなくても選り取り見取りです。
0 件のコメント:
コメントを投稿