-1

私は何時間もこのコードを理解しようとして失敗しました。私は自分のバージョンのビーズソートアルゴリズムを書きましたが、それはとても遅いです。これがなぜこれほど速く動作するのかを理解したいと思います。ビーズソートアルゴリズムに関する情報は次のとおりです。http：
//demonstrations.wolfram.com/ExtendedBeadSort/
このアルゴリズムがどのように機能するかを理解するのを手伝っていただけませんか。

#include <iostream>
#include <vector>

using std::cout;
using std::vector;

void distribute(int dist, vector<int> &List) {
    //*beads* go down into different buckets using gravity (addition).
    if (dist > List.size() )
        List.resize(dist); //resize if too big for current vector

    for (int i=0; i < dist; i++)
        List[i]++;
}

vector<int> beadSort(int *myints, int n) {
    vector<int> list, list2, fifth (myints, myints + n);
    cout << "sakums\n";
    cout << myints<< "\n";
 //   for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) cout << " " << *it << "\n";
    cout << "beigas\n";

    cout << "#1 Beads falling down: ";
    for (int i=0; i < fifth.size(); i++)
        distribute (fifth[i], list);
    cout << '\n';

    cout << "\nBeads on their sides: ";
    for (int i=0; i < list.size(); i++)
        cout << " " << list[i];
    cout << '\n';

    //second part

    cout << "#2 Beads right side up: ";
    for (int i=0; i < list.size(); i++)
        distribute (list[i], list2);
    cout << '\n';

    return list2;
}

int main() {
    int myints[] = {734,3,1,24,324,324,32,432,42,3,4,1,1};
    vector<int> sorted = beadSort(myints, sizeof(myints)/sizeof(int));
    cout << "Sorted list/array";
    for(unsigned int i=0; i<sorted.size(); i++)
        cout << sorted[i] << ' ';
    system("PAUSE");
    return 0;
}
4

2 に答える 2

1

その私の実装！私は、rosettacode で見られる C++ のビーズ ソートの最初の作成者です。

アルゴリズムが非常に遅い理由は、この並べ替えには 3 つの主要な速度低下の問題があるためです。分散が O(S) を実行するたびに、ベクトルの潜在的なサイズ変更を処理します。これはまた、各「極」 O(S)+O(S) または O(2S) の下に数値を 1 つずつ実際に追加し、これを n 回実行することと組み合わされます。ここで、n はソートされる数値 O(n )+O(2S)。ほとんどの場合、S はまだ大きいので、アルゴリズムは O(S) のままです。

公平を期すために、パフォーマンスを向上させるために必要なのは、誰かが私のコードのより良い実装と冗長性の低いバージョンを作成することだけです。このアルゴリズムをこの方法で作成したのは、ビーズの並べ替えに慣れていない人にできるだけ簡単に紹介できるようにするためです。

さらに詳しく知りたい場合は、ビーズソートの wiki ページも確認してください。

于 2013-05-02T20:03:06.377 に答える
0

配布のしくみにより、次のようになります。

他の数字はそれぞれ、スロットに「ビーズ」を提供します。13 個の数字があるため、スロット 1 が最初のパスを終了すると、スロット 1 には 13 個が含まれます。

ビーズを「列」に「分散」します。つまり、横に印刷すると、最大数の 734 スロットになります。

配布が再度実行されると、列を合計して「ビーズ」を下にシフトします。最大要素に応じて、いくつかの追加を実行します * 数値の数とメモリ割り当て

于 2012-12-04T23:21:32.660 に答える