4

私は現在、データの配列の下半分にある値を取得しようとしています。この配列は、最初はソートされていません。

これから：

{4,6,9,3,8,5}

これに：

{3,4,5,6,9,8} or {3,4,5}

簡単な解決策は、（クイックソートを使用して）配列を並べ替えてから、並べ替えられた配列の前半に格納されている値のみを使用することです。ただし、クイックソートと最も効率的なソートアルゴリズムでは、最初の50％しか必要ないのに配列全体がソートされるため、これはリソースの無駄のように思われます。このプロジェクトではパフォーマンスが問題になることに注意してください。

完全なソートがO（n log n）であり、最下位の要素が見つかった後に停止するソートがO（n）であることを知っているので、n / 2*nの複雑さを持つ単純なアルゴリズムを簡単に構築できます。最低50％。しかし、それは完全なクイックソートよりも本当に優れていますか？

明確にするために、配列内の値の下半分のみが必要な場合に使用するのに最適な並べ替えは何でしょうか。50％が小さければ（1％のように）、最下位の要素を順次検索するのがもちろん最速の解決策ですが、クイックソートよりも遅くなるのは何％ですか？

私はC++でコーディングし、ベクトルを使用していますが、この質問はかなり一般的なはずです。

4

5 に答える 5

11 
#include <algorithm>
std::partial_sort(start, middle, end);
于 2012-08-09T16:22:18.003 に答える
4

下半分を並べ替える必要がない場合は、を使用しますstd::nth_element。下半分を並べ替える必要があり、ベクトルに含まれる要素が100,000未満の場合は、を使用しstd::partial_sortます。ベクトルが大きい場合は、を使用std::nth_elementしてベクトルを下半分と上半分に分割し、std::qsort下半分で使用します。CentOSとg++4.4.3を実行しているIntelXeonX5570 @ 2.93GHzでこれを確認し、この回答の最後にタイミングを示します。std::nth_elementスコット・マイヤーズと他の人々は、それに続くことが大きなベクトルstd::qsortよりもはるかに速くなる可能性があることを驚くべきことに気づきました。std::partial_sort

http://www.velocityreviews.com/forums/t745258-nth_element-sort-versus-partial_sort.html

値の下半分だけが必要で、それらをソートする必要がない場合std::nth_elementは、最速です（複雑さは線形です）。

http://www.cplusplus.com/reference/algorithm/nth_element/

// nth_element example (modified to partition into lower/upper halves)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    vector<int> myvector;
    vector<int>::iterator it;

    // set some values:
    for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

    random_shuffle (myvector.begin(), myvector.end());

    // using default comparison (operator <):
    nth_element (myvector.begin(), myvector.begin()+myvector.size()/2, myvector.end());

    // print out content:
    cout << "myvector contains:";
    for (it=myvector.begin(); it!=myvector.end(); ++it)
        cout << " " << *it;

    cout << endl;

    return 0;
}

CentOSを実行し、g++4.4.3を使用しているIntelXeonX5570 @ 2.93GHzで、次の時間を測定します。データから明らかなように、std::nth_element線形std::partial_sortですべてのサイズよりも高速であり、Nが10億要素の場合は94倍高速です。

N =       1000 nth_element   0.0000082 sec
N =       1000 nth + qsort   0.0001114 sec
N =       1000 partial_sort  0.0000438 sec

N =      10000 nth_element   0.0000592 sec
N =      10000 nth + qsort   0.0005639 sec
N =      10000 partial_sort  0.0005271 sec

N =     100000 nth_element   0.00095 sec
N =     100000 nth + qsort   0.00683 sec
N =     100000 partial_sort  0.00697 sec

N =    1000000 nth_element   0.0086 sec
N =    1000000 nth + qsort   0.0831 sec
N =    1000000 partial_sort  0.1227 sec

N =   10000000 nth_element   0.0700 sec
N =   10000000 nth + qsort   0.9307 sec
N =   10000000 partial_sort  2.7006 sec

N =  100000000 nth_element   0.8147 sec
N =  100000000 nth + qsort  10.7602 sec
N =  100000000 partial_sort 56.7105 sec

N = 1000000000 nth_element   10.055 sec
N = 1000000000 nth + qsort  123.703 sec
N = 1000000000 partial_sort 947.949 sec
于 2012-08-09T16:32:11.417 に答える
0

部分的なクイックソートを実行できると確信しています。配列の少なくとも半分をソートした後、アルゴリズムを停止してください。視覚的な表現については、こちらをご覧ください。

最悪の場合、配列全体がソートされ、最良の場合の半分がソートされます。

于 2012-08-09T16:37:14.203 に答える
0

この問題に対して、時間計算量がO（log N）未満のアルゴリズムはあり得ないと思います。しかし、平均的な場合、これは強化される可能性があります。

以下のように、この特定のユースケースのクイックソートアルゴリズムを微調整できます。

クイックソートは、パーティションと呼ばれる内部アルゴリズムで構成されています。このアルゴリズムは、左側の値がピボットより小さく、右側の値がピボットより大きくなるように、中央にピボット要素を持つ2つに配列を分割します。 。

したがって、問題は、ピボットの両側に同じ数の要素を持つように配列を分割する問題になります。

次のアルゴリズムが機能するはずです。これにより、配列が2つに分割され、配列の下半分の要素の要素が中央値より小さくなり、上半分の要素の要素が中央値より大きくなります。

void split_the_array(int[] array, int a, int b, int m)
{
    p = partition(array, a, b)
    if (p == m) return;
    if (p < m) split_the_array(p+1, b, m)
    else       split_the_array(a, p-1, m)
}

この関数を次のように呼び出します

split_the_array(arr, 0, len(arr), len(arr) / 2)

関数の実行後、（len（arr）/ 2）の左側のすべての要素はそれより小さく、右側の要素はそれより大きくする必要があります。

パーティションのアルゴリズムを簡単に取得できるはずです。

于 2012-08-09T16:38:04.820 に答える
0

基数ソートですべてをソートできます。クイックソートよりも高速な場合があります。部分的な並べ替えよりも速いかどうかはわかりません。限られた範囲の数値（たとえば32ビット表現）をソートする必要がある場合に便利です。これは 私が少し前に作成した実装です
。編集：この基数ソートの実装はさらに高速であるようです。

于 2012-08-09T19:22:33.477 に答える