2

30個の実数のソート済み配列があります。数値は均等に分散されます。この配列内の数値を検索したい。現在、線形探索アルゴリズムを使用しています。アプリケーションのパフォーマンスを向上させるには、より優れた検索アルゴリズムを使用する必要があります。どの検索アルゴリズムを使用するか、またはどのような基準で「最適な」アルゴリズムを選択するか?

前もって感謝します！

4

6 に答える 6

2

最速のものを確立するには、いくつかのタイミングを実行する必要があります。これは、プラットフォーム、プログラミング言語、CPU アーキテクチャ、使用しているデータなどによって異なる場合があります。また、プロファイラーを使用するか、独自のタイミング呼び出しを挿入して、プログラム全体でタイミングを実行する価値があります。

C++ でどの手法が最速かをテストするために、単純なテスト プログラムを実行してパフォーマンスを比較しました。

  1. std::findソートされていない配列 ( )、O(n) に対する線形検索
  2. ソートされたデータのバイナリ チョップ ( を使用std::lower_bound)、O(log n)、
  3. ソートされたデータの線形検索 O(n)。

並べ替えられたデータの線形検索は、一致が見つかるとすぐに停止するため、探している要素が配列内にある場合、予想されるコストは、並べ替えられていない配列の線形検索の半分になります。私のテスト プログラムでは、検索したケースの半分が配列に含まれていなかったため、このコストは、並べ替えられていないデータの線形検索のコストの約 75% になると予想されます。もちろん、配列を頻繁にソートする必要がある場合、配列をソートすると実行時間が大幅に長くなります!

下のグラフでは、

  • 赤い円は、ソートされていない配列での二分探索と線形探索のコストの比率です。
  • 黒い円は、並べ替えられたデータに対する線形検索のコストと並べ替えられていないデータの比率です。

ここに画像の説明を入力

少なくともこの場合、n=30 の場合、どの手法を選択するかはあまりありません。また、プロファイリングで実際にパフォーマンスのボトルネックがあることが示されない限り、シンプルなルールに従うのが最善かもしれません。並べ替えられたデータが必要ない場合は、並べ替えられていないデータに対して線形検索を実行するだけで、並べ替えられたデータを持つという追加の制約がなくなります (または、並べ替えが合理的な制約である場合は、並べ替えられたデータに対して線形検索を実行します)。

于 2013-06-14T12:55:16.433 に答える
1

数値がソートされている場合は、バイナリ検索を使用する必要があります。O(n)Linear Search( )と比較して、O(log n)時間内に検索します

于 2013-06-14T10:32:58.947 に答える
1

それが 30 のプリミティブ型の配列である場合、線形検索は間違いなく最良の選択です。

于 2013-06-14T10:36:18.260 に答える
1
  1. 入力数値の範囲がわからない場合は、バイナリ検索を使用できます。または配列が実際にソートされている場合。
  2. 数値の範囲を知っている場合。ハッシュはより良いオプションでなければなりません。

Hash の場合: C++ でプログラミングしている場合は、C++ Container "Set" を使用できます。または、存在する要素をマークする必要があるジョブに単に配列を使用できます。検索するには、その要素のフラグが設定されているか設定解除されているかを確認するだけです!

于 2013-06-14T10:41:08.323 に答える
1

まず第一に、検索が本当にボトルネックになっていると確信していますか? コードを作成する前にスケジュールを最適化してください。本当に価値のある部分を最適化していることを確認してください。より単純で時間がかかることに気付くと、すぐに驚くかもしれません。確認するためにプロファイリングをお勧めします。C++ を使用している場合は、通常、 VerySleepyがその仕事をしてくれます。

ここで、検索が実際にボトルネックを表していることに気付いた場合は、コメントで提案されているように (C++std::binary_searchから<algorithm>)、バイナリ検索に切り替えることができます。hast tableのコンテナーを切り替えることもできますが、これはニーズと状況によって異なります。

プロファイル、ベンチマーク、状況に最適なものを選択してください。

于 2013-06-14T10:33:21.937 に答える