ストリーミングされたデータをソートされたリストに読み込む

Question

一般的に、最悪の場合の複雑さO（N * log（N））で実行される任意のデータに対して「よりスマートな」比較ソートが行われます。

私の質問は、コレクションを並べ替えるのではなく、データのストリームを並べ替えるように求められた場合です。つまり、値は私たちに一つずつ与えられ、次に来るものは示されません（データが有効/範囲内であることを除いて）。直観的には、すべてを集めて後でソートする（ポーカーハンドを仕分けした後にソートする）のではなく、ポーカーハンドを1つずつピックアップするようなデータをソートする方が優れていると考えるかもしれません。これは事実ですか？

収集と並べ替えはO（N + N * log（N））= O（N * log（N））となります。しかし、それが来るようにソートすると、O（N * K）です。ここで、Kは、適切なインデックス+要素を挿入する時間を見つけるための時間です。 Kの値はデータ構造の選択に依存するため、これは事を複雑にします。配列はインデックスを見つける上で優れていますが、要素を挿入する時間が無駄です。リンクリストは簡単に挿入できますが、バイナリ検索でインデックスを見つけることはできません。

この問題に関する完全なディスカッションはありますか？いつどのような方法を使うべきですか？しばらく毎回ソートするのが望ましい中間戦略かもしれませんか？

Answer 1

Balanced tree sortがO(N log N)であり、要素が追加されている間にソートされた順序でリストが維持されます。

Answer 2

絶対にありません！

最初に、ストリーミングデータをソートすることができれば、すべてのデータをO(N)に受け入れるだけで、それを自分にストリームし、より高速な方法でソートすることができます。私。すべてのデータからストリームへの削減を実行することができます。つまり、それを高速化することはできません。

第二に、あなたが実際にO(N^2)時に実行される挿入ソートを、記述している（すなわちO(NK)のあなたの説明は正しかったが、Kは、Nのではなく関数で一定でない）それを見つけるためにO(N)時間がかかる可能性があるため、適切なインデックス。あなたはそれをバイナリの挿入ソートに改善することができますが、それはO(NlogN)で実行されます（リンクリストを使用していると仮定すると、配列はバイナリ最適化でもO(N^2)になります）。

おそらく一般的な原則に言及する価値があります。比較モデルを使用している間は（ソートしているデータに関する重要な情報はほとんどありません）、ソートアルゴリズムは最高でO(NlogN)になります。私。このモデルのソートアルゴリズムの最悪の場合の実行時間はomega(NlogN)です。これは仮説ではなく、定理です。したがって、（同じ前提のもとで）何かをより早く見つけることは不可能です。

Answer 3

ストリームのタイミングが比較的遅い場合は、最後の要素が到着した時点で、完全にソートされたリスト（最後の要素を引いたもの）を取得します。次に、 O（log n）完全バイナリソートでないバイナリ検索サイクル O（n log n）が残っています。潜在的には、他のソートアルゴリズムで頭角を現し始めているため、パフォーマンスの向上が認められます。

ストリームからのデータの管理、キューイング、および抽出は、まったく別の問題であり、あなたの意図に反する可能性があります。 1つまたは2つの要素をストリームするのとほぼ同じ時間に完全なデータセットを並べ替えることができないかぎり、ストリーミング部分をコーディングするのが良いと思わない限り、これをお勧めしません。

Answer 4

ヒープソートを使用すると、ツリーソートはツリー構造を格納するために追加の領域が必要なため、大量のデータセット、つまり大量のデータが正しく動作しません。