algorithm - アイテムを挿入した後、または並べ替えられたリストに追加した後にリストを並べ替える方が速いですか

Question

並べ替えられたリストがある場合 (並べ替えのクイック並べ替えなど)、追加する値がたくさんある場合は、並べ替えを一時停止して最後に追加してから並べ替えるか、バイナリチョップを使用してアイテムを正しく配置する方がよいでしょうか。それらを追加します。アイテムがランダムな場合、またはすでに多かれ少なかれ順序付けられている場合、違いはありますか?

score 46 · Accepted Answer

リストを最初から効果的に作成するのに十分なアイテムを追加すると、後でリストを並べ替えることでパフォーマンスを向上させることができます。

アイテムがほぼ正常である場合は、増分更新と定期的な並べ替えの両方を微調整してそれを利用できますが、率直に言って、通常は問題を起こす価値はありません。（また、予期しない順序でアルゴリズムに時間がかからないようにするなどの点にも注意する必要があります。qvnaiveクイックソート）

インクリメンタル更新と通常のリストソートはどちらもO（N log N）ですが、後ですべてをソートするより良い定数係数を取得できます（ここでは、インクリメンタル更新がOよりも速くリストアイテムにアクセスできるように、補助的なデータ構造があると想定しています。（N）...）。一般的に、インクリメンタル更新では常に完全な順序を維持する必要があるため、一度に並べ替えると、増分で順序を維持するよりも設計の自由度が高くなりますが、一括並べ替えではそうではありません。

他に何もないとしても、高度に最適化されたバルクソートがたくさんあることを忘れないでください。

score 27 · Accepted Answer

通常、 heapを使用する方がはるかに優れています。つまり、プッシャーとピッカーの間で順序を維持するためのコストを分割します。両方の操作は、他のほとんどのソリューションと同様に、O(n log n) ではなく O(log n) です。

score 11 · Accepted Answer

まとめて追加する場合は、マージソートを使用できます。追加するアイテムのリストを並べ替えてから、両方のリストからコピーし、アイテムを比較して次にコピーするアイテムを決定します。宛先配列のサイズを変更し、最後から逆方向に作業する場合は、その場でコピーすることもできます。

このソリューションの効率は O(n+m) + O(m log m) です。ここで、n は元のリストのサイズ、m は挿入されるアイテムの数です。

編集：この回答は愛されていないので、C ++サンプルコードで肉付けしたいと思いました。並べ替えられたリストは、配列ではなくリンクされたリストに保持されていると思います。これにより、アルゴリズムがマージではなく挿入のように見えますが、原理は同じです。

// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
    std::sort(itemstoadd.begin(), itemstoadd.end());
    std::list<T>::iterator listposition = sortedlist.begin();
    std::vector<T>::iterator nextnewitem = itemstoadd.begin();
    while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
    {
        if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
            sortedlist.insert(listposition, *nextnewitem++);
        else
            ++listposition;
    }
}

score 4 · Accepted Answer

テストしてみましょう！:)

私はクイックソートを試しましたが、ほとんどソートされている配列をクイックソートでソートするのは...まあ、あまり良い考えではありません。私は修正したものを試し、7要素で切り取り、そのために挿入ソートを使用しました. それにしてもひどい出来。マージソートに切り替えました。ソートには大量のメモリが必要になる場合があります (インプレースではありません) が、パフォーマンスはソートされた配列の方がはるかに優れており、ランダムな配列ではほぼ同じです (最初のソートは両方でほぼ同じ時間を要し、クイックソートはわずかに高速でした) ）。

これはすでに 1 つのことを示しています。質問に対する答えは、使用する並べ替えアルゴリズムに大きく依存します。ほとんどソートされたリストでパフォーマンスが低下する場合は、最後に追加してから再ソートするよりも、正しい位置に挿入する方がはるかに高速です。リストが巨大な場合、大量の外部メモリが必要になる可能性があるため、マージソートはオプションではない場合があります。ところで、私はカスタムのマージソート実装を使用しました。これは、単純な実装に対して外部ストレージの 1/2 のみを使用します (配列サイズ自体と同じ量の外部ストレージが必要です)。

マージソートがオプションではなく、クイックソートも確実にオプションではない場合、最良の代替手段はおそらくヒープソートです。

私の結果は次のとおりです。新しい要素を最後に単純に追加してから配列を再ソートすると、正しい位置に挿入するよりも数倍速くなりました。ただし、最初の配列には 10 mio 要素 (並べ替え済み) があり、別の mio (並べ替えなし) を追加していました。したがって、10 mio の配列に 10 個の要素を追加する場合、それらを正しく挿入すると、すべてを再ソートするよりもはるかに高速になります。したがって、質問に対する答えは、最初の (並べ替えられた) 配列の大きさと、それに追加する新しい要素の数にも依存します。

score 4 · Accepted Answer

原則として、リストをソートするよりもツリーを作成する方が高速です。ツリー挿入は挿入ごとに O(log(n)) であり、全体として O(n log(n)) になります。O(n log(n))でソート。

そのため、Java には (List の TreeSet、TreeList、ArrayList、および LinkedList 実装に加えて) TreeMap があります。

TreeSet は、オブジェクトの比較順序で物事を保持します。キーは Comparable インターフェースによって定義されます。
LinkedList は、物事を挿入順に保持します。
ArrayList はより多くのメモリを使用し、一部の操作ではより高速です。
同様に、TreeMap を使用すると、キーで並べ替える必要がなくなります。マップは、挿入中にキーの順序で構築され、常に並べ替えられた順序で維持されます。

ただし、何らかの理由で、TreeSet の Java 実装は、ArrayList と並べ替えを使用するよりもかなり遅くなります。

[なぜ劇的に遅くなるかを推測するのは難しいですが、そうです。データを1回通過するだけで、わずかに速くなるはずです。この種のことは、多くの場合、メモリ管理のコストがアルゴリズム分析よりも優先されます。]

score 1 · Accepted Answer

ソートされたリストへのアイテムの挿入には、O(n)時間ではなくO(log n)時間がかかります。あなたは時間をかけて、それを置く場所を見つけなければなりませんO(log n)。しかし、その後、すべての要素をシフトする必要があります-O(n)時間がかかります。したがって、並べ替えを維持しながら挿入するのはですがO(n ^ 2)、すべてを挿入してから並べ替えるのはO(n log n)です。

O(n log n)ソートの実装によっては、挿入の数がリストのサイズよりもはるかに少ない場合よりもさらに良くなる可能性があります。しかし、そうであれば、どちらの方法でも構いません。

したがって、挿入の数が多い場合は、すべて挿入してソリューションをソートします。そうでない場合は、おそらく問題になりません。

score 1 · Accepted Answer

ほぼ同じです。ソートされたリストに項目を挿入するのは O(log N) であり、リスト内のすべての要素に対してこれを行う (したがってリストを構築する) のは O(N log N) であり、これはクイックソート (またはマージソート) の速度です。これはこのアプローチに近いです)。

代わりにそれらを前に挿入すると、O(1) になりますが、後でクイックソートを行うと、O(N log N) になります。

少し高速になる可能性があるため、最初のアプローチを使用します。リストの初期サイズ N が、挿入する要素の数 X よりもはるかに大きい場合、挿入方法は O(X log N) になります。リストの先頭に挿入した後のソートは O(N log N) です。N=0 の場合 (つまり、リストは最初は空です)、ソートされた順序での挿入の速度、またはその後のソートの速度は同じです。

score 1 · Accepted Answer

リストが a) 既にソートされていて、b) 本質的に動的である場合、ソートされたリストへの挿入は常に高速である必要があります (適切な場所 (O(n)) を見つけて挿入 (O(1)))。

ただし、リストが静的な場合は、リストの残りの部分をシャッフルする必要があります (O(n) で適切な場所を見つけ、O(n) で下にスライドさせます)。

いずれにせよ、ソートされたリスト (または二分探索木のようなもの) への挿入はより高速になるはずです。

O(n) + O(n) は常に O(N log n) よりも高速である必要があります。

score 1 · Accepted Answer

大まかに言えば、並べ替えは反復検索と考えることができるため、これは非常に単純な問題です。順序付けられた配列、リスト、またはツリーに要素を挿入する場合は、要素を挿入するポイントを検索する必要があります。次に、うまくいけば低コストでそれを入れます。したがって、並べ替えアルゴリズムは、一連のものを取り、1 つずつ適切な位置を検索して挿入するものと考えることができます。したがって、挿入ソート (O(n* n)) は反復線形検索 (O(n)) です。ツリー、ヒープ、マージ、基数、クイックソート (O(n*log(n))) は、反復二分探索 (O(log(n))) と考えることができます。基礎となる検索が順序付けられたハッシュテーブルのように O(1) である場合、O(n) ソートを行うことができます。(この例は、52 ビンに投げて 52 枚のカードをソートすることです。)

したがって、あなたの質問に対する答えは、一度に 1 つずつ挿入するのと、保存してから並べ替えるのとでは、大きな違いはありません。もちろん、対処しなければならない一定の要因がある可能性があり、それらは重要な場合があります。

もちろん、n が 10 のように小さい場合、全体の議論はばかげています。

score 0 · Accepted Answer

それらを前に追加してから、基数ソートを使用する必要があります。これが最適なはずです

http://en.wikipedia.org/wiki/Radix_sort#Efficiency

score 0 · Accepted Answer

（あなたが話しているリストが C# のようなものでList<T>ある場合。）多くの値を持つソートされたリストにいくつかの値を正しい位置に追加すると、必要な操作が少なくなります。ただし、追加する値の数が多くなると、さらに多くの値が必要になります。

リストではなく、より適切なデータ構造を使用することをお勧めします。たとえば、二分木のように。挿入時間が最小限のソートされたデータ構造。

score -1 · Accepted Answer

これが .NET で項目が整数の場合は、それらを辞書に追加する方が迅速です (または、.Net 3.0 以降を使用している場合は、重複を失うことを気にしない場合は HashSet を使用します)。これにより、自動の並べ替えが可能になります。

文字列も同じように機能すると思います。このように O(1) の挿入と並べ替えを行うことができるのは素晴らしいことです。

score -2 · Accepted Answer

ソートされたリストにアイテムを挿入するのは O(log n) ですが、リストをソートするのは O(n log N) です。これは、最初にソートしてから挿入する方が常に良いことを示唆しています

ただし、大きな 'O' はアイテム数による速度のスケーリングにのみ関係することを思い出してください。アプリケーションにとって、中間の挿入は高価である可能性があり (たとえば、ベクトルの場合)、後で追加して並べ替える方がよい場合があります。

algorithm - アイテムを挿入した後、または並べ替えられたリストに追加した後にリストを並べ替える方が速いですか

13 に答える 13

Related

Reference