ニアソートアルゴリズム-いつ使用しますか？

Question

私は時々Webをブラウズし、面白いアルゴリズムとデータ構造を探して、私のbagに入れます。 1年前、ソフトヒープデータ構造に出会い、ほぼ並べ替えについて学習しました。

この背後にある考え方は、ソートアルゴリズムが少しごまかしているという事実に耐えることができれば、比較ベースのソートのO（n log n）障壁を破ることができるということです。ほぼソートされたリストを取得しますが、同様にいくつかのエラーを抱えて生きる必要があります。

テスト環境でアルゴリズムをいじりましたが、それらの使用法を見つけることができませんでした。

それで質問：実際にソートの近くで誰かが使ったことはありますか？その場合、どのような種類のアプリケーションですか？ソートに近いことが正しいことであるユースケースを考えられますか？

Answer 1

「貪欲」な人がたくさんいます定期的にセットの最小値を選択するヒューリスティック。貪欲なヒューリスティックは完全ではないため、最小値を選択しても、最終的な最良の答えが得られるとは限りません。実際、 GRASP メタヒューリスティックでは、複数の最終結果を得るために、意図的にランダムエラーを導入します。ソリューションと最適なものを選択します。その場合、速度と引き換えにソートルーチンに何らかのエラーを導入することは良いトレードオフになります。

Answer 2

これは完全な飛行推測ですが、「関連性」という固有の主観を考慮して、検索結果を並べ替える際の手段として、完全に並べ替えられているかどうかは関係ありません。推奨事項についても同じことが言えます。アルゴリズムのその他すべての部分がO（n）であるように何らかの形で調整できる場合は、ソートを回避することを検討できます。

最悪の場合、「ほぼ並べ替え済み」ということにも注意してください。データは、「ほぼ並べ替えられた」という直感的な考えの1つに当てはまりません。これは、データの反転が少ないことです。これは、データにO（n）反転のみがある場合、挿入ソートまたはカクテルソート（双方向バブルソート）を使用してO（n）時間でソートを終了できるためです。したがって、O（n）時間で（比較を使用して）完全に未ソートからこのポイントに到達することはできません。そのため、データの大部分のサブセットがソートされ、残りが散在するアプリケーションを探しています。すべての要素が正しい位置に近いことを必要とするアプリケーションではではありません。

Answer 3

ここで推測するだけですが、私が想像することの1つは、データベースクエリの最適化です。

SQLなどの宣言型言語のデータベースクエリは、「実行計画」と呼ばれる段階的なプログラムに変換する必要があります。通常、1つのSQLクエリは、多数のこのような実行プランに変換できます。これらの実行プランはすべて同じ結果になりますが、パフォーマンスは大きく異なります。クエリオプティマイザーは、最速のもの、または少なくとも高速のものを見つける必要があります。

コストベースのクエリオプティマイザーには、特定のプランの実行時間を推定するために使用する「コスト関数」があります。徹底的なオプティマイザーは、すべての可能なプラン（「すべての可能な」という値に対して）を実行し、最速のプランを選択します。複雑なクエリの場合、可能なプランの数が非常に多く、最適化時間が非常に長くなる可能性があります（データベースで検索を開始する前に！）ため、網羅的でないオプティマイザーもあります。彼らは、おそらくどのプランを選択するかのランダムな要素を使って、いくつかのプランだけを見ています。通常、多数の「良い」が存在するため、これは機能します。最適なプランを見つけることはそれほど重要ではないかもしれません-2秒を見つけるのに数分間の最適化が必要な場合、最適な2秒プランの代わりに5秒プランを選択することをお勧めします計画。

いくつかの最適化アルゴリズムは、「有望」のソートされたキューを使用します。 （部分）計画。絶対に最適な計画を見つけてもそれが本当に重要でない場合は、ほとんどソートされたキューを使用できますか？

別のアイデア（私はまだ推測中です）は、特定のプロセスまたはスレッドが厳密に数ミリ秒後にタイムスロットを取得する場合、重要ではない可能性があるタイムシェアリングシステムのプロセスまたはスレッドのスケジューラです優先度でソート。

Answer 4

ニアソートの一般的なアプリケーションは、人間がペアワイズ比較を行っており、多くの質問をする必要がない場合です。

ペアワイズ比較でソートしたいアイテムがたくさんあるとします。順序が正確ではないことを受け入れる場合は、必要な比較の数を大幅に減らすことができます。たとえば、優先するアイテムが一番上にある限り、隣接するアイテムが長い間スワップされていてもかまいません。

Answer 5

どこでも

1. あなたは速く反応するはずです
2. クライアントに正確な動作を約束していません
3. ただし、内部的にはいくつかのルールがあります

使用できます。 「それほど厳しくない」はどうですかルールベースの優先度キュー？それはどこで役立ちますか？たぶんスレッド/プロセス/リソースのスケジューリング。スレッド/プロセススケジューリングでは、1つのスレッドが最初、2番目、または最後に行くことを実際に約束していませんが、一般的には、全員にチャンスを与えたいと考えています。あなたはそれが先制的で、優先順位が付けられ、真っ白になるように、緩いルールを実施したいかもしれません。

リソーススケジュールの例は、ピザの配達や人への本の配送などに対応します。確定的な結果が予想される場所では使用できませんが、実生活では物事がそれほど確定的ではない/予測可能。

Answer 6

O（n log n）はすでにかなり高速です。誰もがほぼ並べ替えアルゴリズムを使用して開始するとは思わない。完全なソートを行うコードから始めます（選択したプログラミング言語は nearsort 関数ではなく sort 関数を提供する可能性が高いため）、そして経験的に発見したとき並べ替えに時間がかかりすぎると、データを完全に並べ替える必要があるかどうかを疑問に思うようになります。

基本的に、ソートがプログラムの重大なボトルネックであることを最初に発見しない限り、ニアソートの使用を検討することはありません。