4

以下を実行するための効率的なアルゴリズムを探しています: N 個の項目の配列が与えられた場合、項目が M 個の等しいグループになるように並べ替えます。各グループは並べ替えられていませんが、グループは互いに並べ替えられています (すべての要素)あるグループの要素は、次のグループのどの要素よりも少ない)。

最も簡単な方法は、配列全体をソートすることです。しかし、特にグループの数が項目の総数よりもはるかに少ない場合 (たとえば、100 万の項目を 5 つのグループに分類する場合) は非効率的です。

現在、配列を2つのソートされていないグループにソートし、それをM-1回適用するquickselectアルゴリズム(具体的にはFloyd-Rivestのバリエーション)を使用することに決めました。大幅な改善は、クイック選択に分割統治法を適用することです。最初に配列を 2 つのグループにソートし、次に各半分をソートするというように、M 個のグループが得られるまで続けます。順序付けられていない部分的な並べ替えの問題の一種の一般化。

しかし、私は、この問題に対するより単純で効率的なアプローチがあるかもしれないという直感を持っています。足りないものはありますか？何か案は？これは、 RBush JavaScript ライブラリ(効率的な R* ツリーの実装)での一括挿入のパフォーマンスを向上させるために必要です。

4

1 に答える 1

1

ここに問題の再掲があります。M-1 個のランク付けされた要素を同時に検索し、それらを使用して配列を M 個の並べ替えられていないグループに分割する必要があります。

ランダムなピボットが中央値に近くなるように選択された標準のクイックセレクトから始めて（ランダムなサブサンプルのトリックを実行して推定します）、各ケースで配列を2つに分割し、見つける必要があるランク付けされた要素のリストを分割することをお勧めします2も。現在のグループでランク付けされた要素を見つけるレベルに到達するまで、これを続けます。次に、Floyd-Rivest のクイック選択のバリエーションに切り替えて、実際にその要素を見つけ、現在のグループを 2 つに分割します。その後、クイック選択から戻ると、必要な M グループを簡単につなぎ合わせることができます。

このアプローチの予想実行時間はO(N log(M))、かなり良好な定数です。それよりもはるかに優れているとは思えません。

于 2014-08-31T16:54:47.200 に答える