1

私は一連のオブジェクト (約 20) を定義するルーチンを持っていJetます<。それらがソートされた後、私は最も低い2つを取ります。これを行うための迅速な方法は何ですか？これまでに考えたオプション：

  1. boost::ptr_vector<Jet>組み込みの を使用し.sort()、最初の 2 つを取得し、
  2. boost::ptr_list<Jet>、使用.sort()、最初の 2 つを取る
  3. 上記のようにリストを使用しますが、ソートするのではなく、 を使用max_elementして要素を削除し、再度実行します。

次の理由から、使用std::vector<Jet>が最悪のオプションになると思います。ランダムアクセスは必要ありません。ソートはオブジェクトをメモリ内で移動します。を呼び出したときにオブジェクトがコピーされますpush_back(Jet)。std::list<Jet>コピーが必要なため、 anは よりも悪いと思いboost::ptr_list<Jet>ます。max_elementさらに、リスト全体をソートするよりも 2 回取得する方が高速であると想定します。

私の論理は健全ですか？パフォーマンスの違いは重要ですか？私が考えていない他のオプションはありますか？

4

3 に答える 3

3

オブジェクトの代わりにポインターを保存する方が高速であるという点で、あなたの仮定の1つは正しいです。

ただし、最小の 2 つの要素のみが必要な場合は、何も並べ替える必要はありません。vector最初の 2 つの要素を取り、 orの要素を反復処理してlist、小さい要素を保持します。

于 2012-04-26T21:24:49.057 に答える
2

これを正確に行うための標準ライブラリアルゴリズムがあります。

std::vector<Jet> v;
// populate v
std::partial_sort(v.begin(), v.begin() + 2, v.end());

v[0]が最小の要素になりv[1]、2 番目に小さい要素になりました。残りの要素は順不同です。後者にもランダム アクセス イテレータがあるため、std::vector<>で置き換えることができます。std::deque<>

(私がリンクしたページに記載されている複雑さは正しくないことに注意してください。C++11 §25.4.1.3 では、複雑さは(last - first) * log(middle - first).)

于 2012-04-26T23:27:00.913 に答える
1

最低 2 つのオブジェクトが必要な場合は、O(N) 時間で実行される独自の検索関数を作成できます。ソートの使用は O(N log N) 時間です。

于 2012-04-26T21:24:34.687 に答える