c++ - ベクトルがソートされているかどうかを確認する最適なアルゴリズム

Question

std::vectoraがソートされていることを確認する最良の方法は何でしょうか? それをチェックするループよりも速いものはありますv[i]<=v[i+1]か？イテレータを使用すると、より高速/クリーンになりますか? それとも、実際にはsort毎回呼び出すほうがよいのでしょうか (ただし、「v は既にソートされています」というケースは非常に一般的です)。

ベクトルには POD (通常はfloats、場合によっては sdoubleとs) のみが含まれていると安全に想定できintます。

ベクトルのサイズは重要ですが (通常は数千のアイテム)、極端ではありません (ギガバイトサイズではありません)。

直後にベクトルをソートする場合もありますが、ソートしない場合もあります (これはアルゴリズムのエラーケースです)。
可能な限り、フラグ「IsSorted」を既に使用しています。

score 28 · Accepted Answer

v[i]<=v[i+1] をチェックするループよりも速いものはありますか?

いいえ。

これを頻繁に確認したい場合は、False で始まる「ソート済み」フラグを保持し、アイテムが追加されるたびに False に設定され、設定するメンバー関数 sort() を追加するラッパークラスを作成することをお勧めします。ソート後にフラグを True にします。

score 22 · Accepted Answer

22

最良の方法は次を使用することstd::is_sortedです：

is_sorted(v.begin(), v.end())

:-)

于 2008-11-04T15:07:40.033 に答える

score 16 · Accepted Answer

複数の CPU コアを考慮する

これは、プラットフォームとベクター内のアイテムの数によって異なります。最適なものを見つけるには、ベンチマークを実行する必要があります。

答えることはできません: v[i]<=v[i+1] をチェックするループよりも速いものはありますか?
なしで。

なぜなら... 最近のコンピューターには複数の CPU/コア/ハイパースレッディングが搭載されているからです。そのため、チェック作業を複数のスレッドに分割することで、コンピューターの並列処理を利用する方がはるかに高速である可能性があります。そのため、各 CPU は小さな範囲を並行してチェックできます。

自分で実装するのではなく、ライブラリ関数を介してこれを行うのがおそらく最善です。ライブラリの新しいバージョンは、並列処理を利用します。そのため、std::sort を使用すると、STL の新しい実装に対してビルドするときに、心配することなく操作が並行して行われることがわかるでしょう。すでにこれを行うSTLのバージョンがすぐに利用できるかどうかはわかりませんが、ライブラリ関数に固執する価値があるので、そうするバージョンにアップグレードするときに、変更を加える必要なくこの最適化が行われます。 .

score 12 · Accepted Answer

12

std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()

于 2009-05-20T22:26:21.600 に答える

score 6 · Accepted Answer

もちろん、私はあなたの問題ドメインについて何も知らないので、私が言っていることが関係ない場合は無視してください。vector<T>最良の選択ではないかもしれません。

score 5 · Accepted Answer

v[i]<=v[i+1] をチェックするループよりも速いものはありますか?

値がソートされているかどうかを確認する必要があるため、ベクトルを変更しているときに自分で変更を追跡するか、すでにソートされているデータ構造を使用しない限り、O(n) より速くなることはありません。

それとも、実際には毎回 sort を呼び出すほうがよいのでしょうか (ただし、「v は既にソートされています」というケースは非常に一般的です)。

リストがすでにソートされている場合 (およびピボットが正しく選択されていない場合)、クイックソートの最悪のケースの動作が発生することに注意してください。このような動作を回避するには、代わりに std::stable_sort をチェックアウトすることをお勧めします。

score 2 · Accepted Answer

2

C ++-11には、<algorithm>にis_sortedが含まれています。

于 2013-02-10T08:34:19.870 に答える

score 2 · Accepted Answer

リストがソート済みに非常に近いと予想している場合は、挿入ソートの変更を試みると有益な場合があります。リストがすでにソートされている場合は、1 つのパスだけが実行され、その旨が通知されます。リストがほぼソートされている場合は、非常に迅速にソートされます。リストがソートされていない場合は、何回かスワップした後にソートを解除し、クイックソート (または stable_sort) に切り替えます。

score 1 · Accepted Answer

v[i]<=v[i+1] をチェックするループよりも速いものはありますか?

いいえ。

ただし、ベクトルをソートするかどうかを決定するためにチェックを実行する場合、正しいソートアルゴリズム、つまり std::stable_sort ではなく std::sort を使用する場合は、常にソートする方がよい場合があります。

score 0 · Accepted Answer

並べ替えを確認するには、すべての項目を確認する必要があります。したがって、 v[i]<=v[i+1] は最速のチェックです。

score 0 · Accepted Answer

C++ 標準ライブラリの実装にアルゴリズム is_sorted() が含まれている場合は、これが最適なオプションです。

score 0 · Accepted Answer

アイテムを挿入するときにバイナリ検索を使用して挿入ポイントを見つけた場合、順序付けされていないことはありません。

score 0 · Accepted Answer

他の人が指摘したように、ソートされた状態を決定する述語は O(n) です。しかし、ソートされたフラグについての言及から、次のようなものが必要ないのではないかと思います。

アプリケーションの基本ライブラリには、メンバーシップを照会できるコンテナクラスが含まれています。ここに簡単なスケッチがあります：

class ObjList {
public:
    ObjList() {};
    ~ObjList() {};

    bool isMember(const Item *);
    void add(const Item *, bool sort = false);

private:

    unsigned int last_sorted_d;

    bool sorted_d;
    unsigned int count_d;
    Item *store_d;
};

isMember()は、要素のソートされた範囲でバイナリ検索を使用し、次にソートされた範囲の後の項目の線形検索を使用します。挿入は、プログラマーの選択に応じて、アイテムの並べ替えをトリガーすることもトリガーしないこともできます。たとえば、タイトなループで何千ものアイテムを追加することを認識している場合は、最後の挿入までソートしないでください。

上記は単なるスケッチであり、ストアはポインターの配列よりも複雑ですが、アイデアは理解できます。

c++ - ベクトルがソートされているかどうかを確認する最適なアルゴリズム

13 に答える 13

Related

Reference