問題タブ [binary-search]

すべてのプログラマーは、二分探索がデータの順序付けられたリストを検索する優れた高速な方法であると教えられています。二分探索を使用したおもちゃの教科書の例はたくさんありますが、実際のプログラミングではどうでしょうか: 二分探索は実際のプログラムのどこで使用されるのでしょうか?

Javascript でテキスト ファイル内の特定のキーに対してディスク ベースのバイナリ検索を行う方法はありますか? テキスト ファイルが大きすぎてメモリにロードできませんが、キー値で並べ替えられています。特に、Javascript で Perl のSearch::Dict機能を模倣する方法を探しています。

たとえば、ファイル foo.txt がある場合:

look(c,foo.txt)c 5バイナリ検索を実行し、ファイルを直線的にトラバースしないことにより、行 ' ' を返す必要があります。

線形検索と二分検索の違いは何ですか？

私はPerlプログラムをJavaに移植するのに苦労しており、Javaを学びながら進んでいます。元のプログラムの中心的なコンポーネントは、バイナリ検索を使用して+500 GBのソートされたテキストファイルで文字列プレフィックスルックアップを実行するPerlモジュールです（基本的に、ファイルの中央のバイトオフセットを「シーク」し、最も近い改行にバックトラックし、比較します）検索文字列の行プレフィックス、そのバイトオフセットの半分/ 2倍に「シーク」し、見つかるまで繰り返します...）

私はいくつかのデータベースソリューションを試しましたが、このサイズのデータ​​セットを使用した場合のルックアップ速度でこれに勝るものはありません。そのような機能を実装する既存のJavaライブラリを知っていますか？それができない場合、ランダムアクセスがテキストファイルを読み取る慣用的なサンプルコードを教えていただけますか？

または、新しい（？）Java I / Oライブラリに精通していませんが、500 GBのテキストファイルをメモリマップして（メモリに余裕のある64ビットマシンを使用しています）、バイナリを実行するオプションはありますか？メモリマップトバイト配列を検索しますか？この問題や同様の問題についてあなたが共有しなければならない経験を聞いて非常に興味があります。

Windows イベント ログで特定のセキュリティ イベントをキャプチャするログ解析サービスを開発しています。私の最初の考えは、Microsoft のLogParserを使用することでしたが、事前にわかっている特定のインスタンス/イベント ID を選択する以外の機能は探していません。

いくつかのベンチマークの後、EventLog.EntriesMicrosoft の LogParser にクエリを実行するよりも、.NET コレクション全体を反復処理する方が 3 倍以上高速にデータを取得できることがわかりました。

最終的に、プルされるデータは SQL Server データベースに保存されます。このサービスは毎日この作業を行うため、エントリの重複を避けたいと考えてEventLog.Entriesいます。データベースにまだ存在しないコレクション内の次のエントリを見つける方法が必要です。最初のエントリが見つかったら、データベースへの挿入を開始できます。

データベースの最新のDATETIMEタイムスタンプ フィールドを使用してこのエントリを検索し、それをコレクションTimeWritten内のアイテムのプロパティと比較するバイナリ検索を作成しようとしていました。EventLog.Entriesこれはできますが、この検索を実行するための組み込みメソッドが既にあるかどうか疑問に思っていますか?

コラム 2 (「AHA! アルゴリズム」) の「プログラミング パール」では、ソートやツリー トラバーサルなどのさまざまなプロセスでバイナリ検索がどのように役立つかについて説明しています。ただし、バイナリ検索は「プログラムのデバッグ」で使用できると述べています。誰かがこれがどのように行われるか説明してもらえますか?

次の表があるとします。

:key のフィールドによるバイナリ検索用に行が最適に格納されるようにするにはどうすればよいですか?

また、バイナリ検索が使用されていることを確認するにはどうすればよいですか?

オブジェクトを使用して ArrayList にバイナリ検索を実装する方法はありますか? この例では、ArrayList はフィールド「id」でソートされます。

「User getUserById( ArrayList users, int userid )」は、バイナリ検索を使用して指定された ID を持つユーザーを返す必要がある場合、どのように見えますか? これは可能ですか？

簡単な質問-IList<T>メソッドを自分で記述せずに、また組み込みのバイナリ検索サポートを備えたタイプにデータをコピーせずに、どのようにバイナリ検索を実行するかを考えます。私の現在の状況は次のとおりです。

• List<T>.BinarySearch()のメンバーではありませんIList<T>
• に相当するArrayList.Adapter()方法はありませんList<T>
• IList<T>から継承しないためIList、使用ArrayList.Adapter()できません

ビルトインメソッドでは不可能だと思う傾向がありますが、そのような基本的なメソッドがBCL/FCLに欠けているとは信じられません。

それが不可能な場合、誰が最短、最速、最も賢い、または最も美しい二分探索の実装を提供できIList<T>ますか？

アップデート

二分探索を使用する前にリストをソートする必要があることは誰もが知っているので、そうだと推測できます。しかし、私はそれがソートと同じ問題であると思います（しかし検証しませんでした）-どのようにソートしますIList<T>か？

結論

の組み込みの二分探索はないようですIList<T>。LINQメソッドを使用First()して検索と並べ替えを行うことができますが、パフォーマンスが低下する可能性があります。OrderBy()（拡張メソッドとして）自分で実装するのが最善のようです。