9

cinからいくつかの線分を読んでいます。各線分は、始点と終点で表されます。2D。XとY。

入力はソートされません。ランダムな順序です。（更新：しかし、最初にXで、次にYでソートする必要があります）

すべてのセグメントを読み取り、それらをベクトルに格納してから、std::sortを呼び出すことができます。一方、空のstd :: setを作成し、到着時に各セグメントを挿入することができます。セットは自動的にソートされた順序を維持します。2つのアプローチのどちらがより効率的ですか？

更新：入力の合計サイズ（セグメント数）は事前にわかっています。

4

4 に答える 4

18

両方のアプローチのパフォーマンスを確実に測定する必要がありますが、局所性の影響とツリー挿入アルゴリズムに隠れている大きな定数のために、に挿入するよりもはるかに高速であるstd::sortとstd::vector想定するのが安全です。また、後続のルックアップと反復が高速になります。std::set

（ただし、std::set挿入と削除/ルックアップ/反復の混合シリーズをサポートするのに適しています。各挿入には平均して線形時間がかかるため、ベクトルでの順序の維持にはコストがかかります。）

于 2013-03-26T13:19:24.417 に答える
11

経験則として、より厳密な保証が提供され、パフォーマンスが低下します。

に挿入すると、挿入のたびstd::setにシーケンスがソートされることが保証されます。

に挿入し、すべての挿入が行われた後に1回std::vector呼び出すと、でのすべての操作が行われた後にシーケンスがソートされることが保証されます。すべての中間挿入中にベクトルをソートする必要はありません。std::sort vector

Astd::vectorはまた、より優れた空間的局所性を示し、必要なメモリ割り当てが少なくて済みます。したがって、このアプローチはより高速であると思いますが、パフォーマンスが重要である場合は、測定vectorするのに十分重要です。

アプリケーションのコードを使用してデータセットの場合に何が速いかを測定する必要がない場合は、どちらが速いかは気にしません。

于 2013-03-26T13:56:05.027 に答える
4

ニーズに適したセマンティクスを持つコンテナーを使用してください。効率は通常、その選択から自動的に続きます。

その後、パフォーマンスのボトルネックが発生した場合は、ベンチマークを実行してください。

于 2013-03-26T13:20:29.480 に答える
4

それは確かに依存しますが、それがstd::setランダムな挿入と削除を目的としていることは確かです。この場合、挿入するだけです。と一緒に行きstd::vectorます。また、おそらくもっと重要なことは、セグメントがいくつあるかを事前に知っている場合は、ベクトルを1回だけ割り当てる必要があり、サイズが2倍になるたびにメモリを再割り当てするわけではありません。

于 2013-03-26T13:27:24.767 に答える