0

STL を使用する C++ では、2 つの操作のどちらが大きな個別の数値をソートするのに CPU 時間が少なくて済みますか。

  • 要素をセットにプッシュする
  • 要素をベクトルに格納し、sort() 関数を呼び出しますか?
4

1 に答える 1

6

1回限りの操作の場合は、std::vectorその後に。を使用しstd::sortます。

漸近的な複雑さに関する限り、2つの解決策は同等である必要があります。セットへの挿入はO（log（n））であり、N個の要素に対してこれを行うため、O（N log（N））（証明）になります。

一方、ベクトルへの挿入（事前にサイズがわかっている場合）はO（N）であり、並べ替えはO（N log（N））であるため、グローバルにはO（N log（N））になります。

ただし、ベクトルには1回限りの割り当てが必要です（または、最終的なサイズがわからない場合は、通常の実装ではO（log（N））再割り当てで最終的なサイズに達する必要があります）。一方、セットをRBツリーとして実装する場合は、ノードごとに割り当てが必要です。つまり、アロケータをN回呼び出す必要があります。つまり、PODコンテナ内のアロケータ呼び出しは、おそらく次のいずれかになります。ボトルネック。また、ツリーは通常、キャッシュの局所性が少なく、より多くのメモリを使用するため、このオーバーヘッドはすべてパフォーマンスを低下させる可能性があります。

また、big-O表記は関数の時間依存性を示しますが、乗法定数を非表示にします。私の言葉を信じないでください、しかし、N * setの挿入は、各要素に対して行うすべての余分な簿記のために、最後に単一のソートよりも多くの費用がかかるとほぼ確信しています（ツリーの挿入には多くの場合、いくつかが必要ですRBツリーのプロパティを復元するために作業します）。

一方、データ構造を並べ替えておく必要がある場合（新しいデータがによって来る）、通常はセットが正しい解決策です。

しかし、いつものように、疑わしいプロファイルの場合。

于 2013-02-28T02:47:23.150 に答える