algorithm - 二分探索ではなく線形探索を選択する場所

Question

インターネットを検索した後、線形検索が二分検索よりも望ましい包括的な一連の状況を見つけたということに満足することができませんでした。

私は基本的に、（業界で見られるような一般的なプログラミングの観点から）アドバイスの比較的明確なリストを編集できるかどうか疑問に思っています。あるいは、この件に関して言うべきことはすべて実際に私が見たことを確認できれば幸いです。

Answer 1

おそらく、決定的なリストを作成することはできません。たとえば、.NET で並べ替えられたリストを検索して、しばらく前にいくつかのテストを行いました。整数のソートされたリストでは、項目数が 13 の場合、二分探索は逐次検索よりも高速であることが判明しました。文字列のソートされたリストでは、その数は 8 でした。さらに小さい。

異なる言語またはランタイム ライブラリを使用して同じテストを実行すると、異なる数値が得られます。メモリアクセスハードウェアや、おそらくその他のハードウェアに関する考慮事項にも依存する可能性があります。

シーケンシャル サーチはバイナリ サーチよりもはるかに単純であるため、複雑さが軽減されるため、小さなリストでは大きな利点が得られるというのが従来の通念でした (おそらく今でもそうです)。今日の真実は、CPU 速度とメモリ アクセスが非常に高速であるため、リストが非常に小さい場合にのみ、順次検索の単純さが問題になるということです。

せいぜい、特定のデータ型を比較す​​るときに、特定のハードウェア上の 1 つのランタイム構成に適用される決定的な一連のルールを考え出すことができます。環境を変更したり、データ型を変更したりした場合は、テストを作成してベンチマークをやり直す必要があります。