performance - 頻繁に挿入ソートされるリストにアイテムを挿入する

Question

頻繁に挿入ソートされるリストがあります。挿入ソートがしなければならない作業を最小限に抑えるために、このリストに追加するのに適した位置 (最後以外) はありますか?

Answer 1

あなたの質問は意味がありません。リストが挿入ソートされているか (つまり、定義により最後に追加できないことを意味します。要素は、それが属する場所に配置されます。それ以外の場合、リストはソートされません)。

多くの要素を追加する必要がある場合、最善の解決策は、リストを複製し、すべての要素を追加し、新しいリストを一度ソートしてから、最初のリストを複製で置き換えることです。

[編集] コメントへの返信: いくつかの追加を行った後、次のソートされた挿入を行う前に、リストをソートする必要があります。したがって、問題は、ソートされた挿入をより安価にする方法ではなく、追加とソートされた挿入の間のソートです。

答えは、ほとんどのソート アルゴリズムは、部分的にソートされたリストでうまく機能するということです。質問する必要があるのは、どのような並べ替えアルゴリズムが使用されているか、どのようなプロパティがあるか、そして最も重要なのは、なぜ気にする必要があるかということです。

最後の質問は、実際の数値に基づいていない限り、最適化を行う前にパフォーマンスを測定する必要があることを意味します.

並べ替えに戻ります。Java は、クイックソートのバージョンを使用してコレクションをソートします。クイックソートはピボット要素を選択してコレクションを分割します。この選択は、アルゴリズムのパフォーマンスにとって重要です。最高のパフォーマンスを得るには、ピボット要素を結果の中央にある要素にできるだけ近づける必要があります。通常、クイックソートは現在のパーティションの中間の要素をピボット要素として使用します。また、クイックソートは小さなインデックスでリストの処理を開始します。

そのため、新しい要素を最後に追加すると、パフォーマンスが向上しない場合があります。ピボット要素の選択には影響しませんが、クイックソートは、並べ替えられたすべての要素を既にチェックした後、新しい要素を調べます。真ん中に新しい要素を追加すると、ピボットの選択に影響を与えますが、それがパフォーマンスに影響を与えるかどうかはわかりません. 私の本能的な推測では、クイックソートがパーティションの途中でソートされた要素を見つけた場合、ピボット要素の方が優れていると思います。

そのため、最初に新しい要素を追加する必要があります。このように、クイックソートは通常、完全なピボット要素を見つけ (リストの中央がソートされるため)、最初に新しい要素を選択します。欠点は、挿入ごとに配列全体をコピーする必要があることです。これを回避するには 2 つの方法があります。b) 2 番目の ArrayList を使用し、すべての新しい要素をその中に入れてから、 を使用できますaddAll()。この場合、Java は内部でいくつかの最適化を行い、既存の要素を 1 回だけ移動します。

[EDIT2] あなたの質問を完全に誤解しました。アルゴリズム挿入 sortの場合、最適な場所はおそらく中間のどこかです。これにより、リスト全体で要素を移動する必要がある可能性が半分になります。しかし、100% 確信があるわけではないので、これを確認するためにいくつかの小さなテストを作成することをお勧めします。