-1

そのため、クイックソート用のバージョンを実装しましたが、最適な方法で実行したかどうかはわかりません. 並べ替えているベクトルの要素は 3D ポイントです。配列を分割すると、"if(level == 1), if(level == 2), etc" と表示されることに気付くでしょう。これは、クイックソートを呼び出すタイミングに応じて、x、y、または z 座標のいずれかになるためです。ポイントのソートの基礎です。

私のコードは以下です。アルゴリズムをテストしたところ、ポイントが正しくソートされているように見えますが、特に呼び出す必要があるため、期待したほど速く実行されないため、多くのオーバーヘッドまたは何かが発生する可能性があるように感じますこの並べ替え関数は、500,000 要素もの配列を何度も並べ替えます。

ソートアルゴリズムを改善/クリーンアップ/スピードアップするためにできることはありますか?

std::vector<Point> SortPoints(std::vector<Point> points, int level)
{
    if(points.size() <= 1) return points;
    std::vector<Point> s1, s2;
    size_t index = ((float)rand()/RAND_MAX)*(points.size()-1);
    Point pivot = points[index];
    points.erase(points.begin() + index);
    size_t size = points.size();
    for(int i = 0; i < size; i++)
    {
        if(level == 1)
        {
            if(points[i].pos.x <= pivot.pos.x) s1.push_back(points[i]);
            else s2.push_back(photons[i]);
        } else if(level == 2)
        {
            if(points[i].pos.y <= pivot.pos.y) s1.push_back(points[i]);
            else s2.push_back(photons[i]);
        } else if(level == 3)
        {
            if(points[i].pos.z <= pivot.pos.z) s1.push_back(points[i]);
            else s2.push_back(photons[i]);
        }
    }
    if(s1.size() == 0) return Concatenate(s1, pivot, s2); 
    else if(s2.size() == 0) return Concatenate(s1, pivot, s2);
    else return Concatenate(SortPoints(s1, level), pivot, SortPoints(s2, level)); 
}

std::vector<Point> Concatenate(std::vector<Point> s1, 
                                       Point p, std::vector<Point> s2)
{  
    std::vector<Point> result;
    result.reserve(s1.size()+s2.size()+1);
    result.insert(result.end(), s1.begin(), s1.end());
    result.push_back(p);
    result.insert(result.end(), s2.begin(), s2.end());
    return result;
}
4

2 に答える 2

2

あなたの主な問題は、パーティション分割時にコピーを作成していることです。舞台裏で多くのメモリ割り当てとコピーが行われています。

より速くしたい場合は、その場で並べ替える必要があります (そして、巨大なベクトルを値で渡さないでください)。

これがクイックソートを実装する演習でない限りstd::sort、カスタム比較関数を使用する必要があります。

于 2012-12-05T06:39:13.327 に答える
1

したがって、ここにいくつかの観察があります。

  • 他の人が指摘したように、std 実装をベンチマークとして使用することを検討する必要があります。
  • ベクトルを継続的に成長させて再割り当てするのではなく、ソートするベクトルを事前に予約することができます。
  • ベクトルからピボットを消去するのではなく、ループ内でピボットをスキップする方がよい場合があります。ベクトルからピボットを消去すると、大量のデータのコピーが必要になる可能性があるためです。
  • データを新しいベクトルにコピーして連結することを気にせず、その場で並べ替えることができませんでした。
  • おそらく、無作為に行うよりも適切なピボットを選択できます (特に、データが事前に並べ替えられている場合)。
  • Point の実装を変更して、if() を使用する代わりに xyz のインデックスを作成できるようにすることができます。

本質的に、これは非常に単純な実装のように思えます。おそらく、事前に提供されたバージョンを打ち負かすために、かなりの作業を行い、独自のデータに関する専門知識を利用する必要があります。

于 2012-12-05T07:14:41.753 に答える