9

非常に基本的な質問がありますが、これは「すべてのCPUティックがカウントされる」という状況にあります（これは、スーパーコンピューターで使用されるより大きなアルゴリズムの一部です）。

問題は非常に単純です。unsignedlonglongint番号とその元のインデックスのリストを並べ替える最速の方法は何ですか？（最初は、unsigned long long int番号は完全にランダムな順序です。）

Example :
Before
Numbers: 32 91 11 72
Indexes: 0 1 2 3
After
Numbers: 11 32 72 91
Indexes: 2 0 3 1

「最速の方法」とは、次のことを意味します。使用するアルゴリズム：std :: sort、C qsort、またはWebで利用可能な別のソートアルゴリズム？使用するコンテナ（C配列、std :: vector、std :: map ...）？インデックスを同時にソートする方法（構造体、std :: pair、std :: map ...を使用）？

並べ替える要素はいくつですか？->通常は4Goの数字

4

8 に答える 8

16

明らかな出発点は、operator<定義された構造体です。

struct data { 
    unsigned long long int number;
    size_t index;
};

struct by_number { 
    bool operator()(data const &left, data const &right) { 
        return left.number < right.number;
    }
};

...そして、データを保持するための std::vector :

 std::vector<data> items;

並べ替えをstd::sort行うには:

 std::sort(items.begin(), items.end(), by_number());

単純な事実として、通常のコンテナー (など) は十分に効率的であり、それらを使用してもコードの効率が大幅に低下することはありません。一部の部分を別の方法で書くことでより良い結果が得られるかもしれませんが、同じくらい簡単に悪い結果になる可能性があります。堅実で読みやすいものから始めて、テストします。時期尚早に最適化 (しようと) しないでください。

編集: もちろん C++11 では、代わりにラムダ式を使用できます。

std::sort(items.begin(), items.end(), 
          [](data const &a, data const &b) { return a.number < b.number; });

これは通常、書くのに少し便利です。読みやすさは依存します--このような単純なものの場合、かなり読みやすいと思いますsort ... by_numberが、それは比較演算子に付ける名前に(大きく)依存します。ラムダを使用すると、実際の並べ替え基準が見つけやすくなるため、コードを読みやすくするために慎重に名前を選択する必要はありません。

于 2012-04-23T20:45:58.323 に答える
5

std::pair and std::sort fit your requirements ideally: if you put the value into the pair.first and the index in pair.second, you can simply call a sort on a vector of pairs, like this:

// This is your original data. It does not need to be in a vector
vector<long> orig;
orig.push_back(10);
orig.push_back(3);
orig.push_back(6);
orig.push_back(11);
orig.push_back(2);
orig.push_back(19);
orig.push_back(7);
// This is a vector of {value,index} pairs
vector<pair<long,size_t> > vp;
vp.reserve(orig.size());
for (size_t i = 0 ; i != orig.size() ; i++) {
    vp.push_back(make_pair(orig[i], i));
}
// Sorting will put lower values ahead of larger ones,
// resolving ties using the original index
sort(vp.begin(), vp.end());
for (size_t i = 0 ; i != vp.size() ; i++) {
    cout << vp[i].first << " " << vp[i].second << endl;
}
于 2012-04-23T20:51:28.980 に答える
3

次のように、数値とインデックスを分離してから、単にインデックスを並べ替えるだけの価値があるかもしれません。

#include <vector>
#include <algorithm>
#include <iostream>

void PrintElements(const std::vector<unsigned long long>& numbers, const std::vector<size_t>& indexes) {

    std::cout << "\tNumbers:";
    for (auto i = indexes.begin(); i != indexes.end(); ++i)
        std::cout << '\t' << numbers[*i];
    std::cout << std::endl;

    std::cout << "\tIndexes:";
    for (auto i = indexes.begin(); i != indexes.end(); ++i)
        std::cout << '\t' << *i;
    std::cout << std::endl;

}

int main() {

    std::vector<unsigned long long> numbers;
    std::vector<size_t> indexes;

    numbers.reserve(4); // An overkill for this few elements, but important for billions.
    numbers.push_back(32);
    numbers.push_back(91);
    numbers.push_back(11);
    numbers.push_back(72);

    indexes.reserve(numbers.capacity());
    indexes.push_back(0);
    indexes.push_back(1);
    indexes.push_back(2);
    indexes.push_back(3);

    std::cout << "BEFORE:" << std::endl;
    PrintElements(numbers, indexes);

    std::sort(
        indexes.begin(),
        indexes.end(),
        [&numbers](size_t i1, size_t i2) {
            return numbers[i1] < numbers[i2];
        }
    );

    std::cout << "AFTER:" << std::endl;
    PrintElements(numbers, indexes);

    return EXIT_SUCCESS;

}

これは以下を出力します:

BEFORE:
        Numbers:        32      91      11      72
        Indexes:        0       1       2       3
AFTER:
        Numbers:        11      32      72      91
        Indexes:        2       0       3       1

アイデアは、並べ替えられる要素が小さいため、並べ替え中にすばやく移動できるということです。ただし、最近の CPU では、numbersキャッシュへの間接アクセスの影響により、これらの利点が台無しになる可能性があるため、使用する最終的な決定を下す前に、現実的な量のデータでベンチマークを行うことをお勧めします。

于 2012-04-23T23:02:45.720 に答える
3

std::sortqsortインダイレクションがなく、重要な操作をインライン化できるため、古いものよりも高速であることが証明されています。

の実装はstd::sort高度に最適化されており、打ち負かすのは難しいですが、不可能ではありません。データが固定長で短い場合、基数ソートの方が高速であることがわかる場合があります。Timsortは比較的新しく、Python に良い結果をもたらしました。

インデックス配列を値配列とは別に保持することもできますが、余分なレベルの間接化がスピード キラーになることが証明されると思います。それらを構造体またはstd::pair.

速度が重要なアプリケーションと同様に、実際の実装をいくつか試して比較し、どれが最速かを確認する必要があります。

于 2012-04-23T20:53:59.910 に答える
1

これはスーパーコンピューターで使用されますか？

その場合、並列ソートアルゴリズムを調べることをお勧めします。これは、大きなデータセットを並べ替える場合にのみ意味がありますが、必要な場合の勝利はかなりのものです。

于 2012-04-23T21:54:29.637 に答える
1

とを使用std::vectorしstd::sortます。これにより、最速のソート方法が提供されるはずです。元のインデックスを見つけるには、構造体を作成します。

struct A {
    int num;
    int index;
}

次に、構造体の数値を比較するソート用の独自の比較述語を作成します。

struct Predicate {
    bool operator()(const A first, const A second) {
        return first.num < second.num;
    }
}

std::sort(vec.begin(), vec.end(), Predicate())

于 2012-04-23T20:43:34.413 に答える
1 
struct SomeValue
{
    unsigned long long val;
    size_t index;
    bool operator<(const SomeValue& rhs)const
    { 
       return val < rhs.val;
    }
}

 #include <algorithm>
 std::vector<SomeValue> somevec;
 //fill it...
 std::sort(somevec.begin(),somevec.end());
于 2012-04-23T20:45:49.623 に答える
0

これは興味深い読み物になるかもしれません。私は STL のソートから始めて、できればそれを改善しようとしました。このスーパー コンピューターで C++11 コンパイラ (gcc4.7 など) にアクセスできるかどうかはわかりませんが、std::futures と std::threads を使用した std::sort をお勧めします。保守可能な方法で問題を並列化することに関しては、そこに少し道があります。

std::sort と qsort を比較する別の質問があります。

最後に、並列アルゴリズムのパフォーマンスを比較する Dobb 博士の記事があります。

于 2012-04-23T22:45:08.943 に答える