30個の実数のソート済み配列があります。数値は均等に分散されます。この配列内の数値を検索したい。現在、線形探索アルゴリズムを使用しています。アプリケーションのパフォーマンスを向上させるには、より優れた検索アルゴリズムを使用する必要があります。どの検索アルゴリズムを使用するか、またはどのような基準で「最適な」アルゴリズムを選択するか?
前もって感謝します!
30個の実数のソート済み配列があります。数値は均等に分散されます。この配列内の数値を検索したい。現在、線形探索アルゴリズムを使用しています。アプリケーションのパフォーマンスを向上させるには、より優れた検索アルゴリズムを使用する必要があります。どの検索アルゴリズムを使用するか、またはどのような基準で「最適な」アルゴリズムを選択するか?
前もって感謝します!
最速のものを確立するには、いくつかのタイミングを実行する必要があります。これは、プラットフォーム、プログラミング言語、CPU アーキテクチャ、使用しているデータなどによって異なる場合があります。また、プロファイラーを使用するか、独自のタイミング呼び出しを挿入して、プログラム全体でタイミングを実行する価値があります。
C++ でどの手法が最速かをテストするために、単純なテスト プログラムを実行してパフォーマンスを比較しました。
std::find
ソートされていない配列 ( )、O(n) に対する線形検索std::lower_bound
)、O(log n)、並べ替えられたデータの線形検索は、一致が見つかるとすぐに停止するため、探している要素が配列内にある場合、予想されるコストは、並べ替えられていない配列の線形検索の半分になります。私のテスト プログラムでは、検索したケースの半分が配列に含まれていなかったため、このコストは、並べ替えられていないデータの線形検索のコストの約 75% になると予想されます。もちろん、配列を頻繁にソートする必要がある場合、配列をソートすると実行時間が大幅に長くなります!
下のグラフでは、
少なくともこの場合、n=30 の場合、どの手法を選択するかはあまりありません。また、プロファイリングで実際にパフォーマンスのボトルネックがあることが示されない限り、シンプルなルールに従うのが最善かもしれません。並べ替えられたデータが必要ない場合は、並べ替えられていないデータに対して線形検索を実行するだけで、並べ替えられたデータを持つという追加の制約がなくなります (または、並べ替えが合理的な制約である場合は、並べ替えられたデータに対して線形検索を実行します)。
数値がソートされている場合は、バイナリ検索を使用する必要があります。O(n)
Linear Search( )と比較して、O(log n)
時間内に検索します
それが 30 のプリミティブ型の配列である場合、線形検索は間違いなく最良の選択です。
Hash の場合: C++ でプログラミングしている場合は、C++ Container "Set" を使用できます。または、存在する要素をマークする必要があるジョブに単に配列を使用できます。検索するには、その要素のフラグが設定されているか設定解除されているかを確認するだけです!
まず第一に、検索が本当にボトルネックになっていると確信していますか? コードを作成する前にスケジュールを最適化してください。本当に価値のある部分を最適化していることを確認してください。より単純で時間がかかることに気付くと、すぐに驚くかもしれません。確認するためにプロファイリングをお勧めします。C++ を使用している場合は、通常、 VerySleepyがその仕事をしてくれます。
ここで、検索が実際にボトルネックを表していることに気付いた場合は、コメントで提案されているように (C++std::binary_search
から<algorithm>
)、バイナリ検索に切り替えることができます。hast tableのコンテナーを切り替えることもできますが、これはニーズと状況によって異なります。
プロファイル、ベンチマーク、状況に最適なものを選択してください。