問題タブ [binary-search]

リスト/タプルでバイナリ検索を実行し、見つかった場合はアイテムの位置を返し、そうでない場合は「False」(-1、なしなど) を返すライブラリ関数はありますか?

bisect モジュールで関数 bisect_left/right を見つけましたが、項目がリストにない場合でも位置を返します。それは意図した使用法ではまったく問題ありませんが、アイテムがリストにあるかどうかを知りたいだけです(何も挿入したくない)。

その位置にある項目が検索対象のものと等しいかどうかを使用しbisect_leftて確認することを考えましたが、それは面倒なようです (また、その数がリスト内の最大数よりも大きくなる可能性があるかどうかの境界チェックも行う必要があります)。もっと良い方法があれば、私はそれについて知りたいです。

編集これが必要な理由を明確にするために：辞書がこれに非常に適していることは承知していますが、メモリ消費をできるだけ低く抑えようとしています。私の意図する使用法は、一種の双方向ルックアップ テーブルです。テーブルに値のリストがあり、インデックスに基づいて値にアクセスできる必要があります。また、値がリストにない場合は、特定の値または None のインデックスを見つけられるようにしたいと考えています。

これには辞書を使用するのが最も速い方法ですが、メモリ要件が (約) 2 倍になります。

Python ライブラリで何かを見落としている可能性があると考えて、この質問をしていました。Moeが提案したように、私は自分のコードを書かなければならないようです。

著者から毎日新しい本を手渡されると想像してみてください。本は進行中の作業です。彼は自分が何を変更または追加したかを教えてくれません。

あなたの仕事は、変更と追加を特定し、これらのみを出版社 (毎日本全体を読む時間がない) に渡すことです。

この問題を解決するために、本は 100 万行の ASCII テキストで構成され、拡大しています (実際には MySQL バックアップ ファイル)。

私の現在のアイデアは、各行 (1k 文字) の安全なハッシュ (たとえば SHA256) を作成し、それを HD に保存することです。ハッシュは 32 バイトしかないため、ファイルは 32MB しかありません。

次に、明日次のファイルを取得すると、1 行ずつ調べて、各行の新しいハッシュを作成し、それを前日のハッシュと比較します。

プロセスが終了すると、翌日のためにハッシュ ファイルが上書きされます。

比較は、文字列比較 ( > < オペランド) の二分探索法を使用します。これにより、平均 4 回の反復で結果が返されます。

私はまだ btree インデックス ソリューションをコーディングしていませんが、これにどのように取り組みますか?

配列だけを使用してバイナリ検索を実装するにはどうすればよいですか?

キーとレコード番号の間にインデックスがあるキー レコード ルックアップを作成しています。これはキーでソートされます。速度の最適化のために私が持っているものよりもこれをうまく行う方法はありますか?

オブジェクトの静的セット (一度読み込まれるとほとんど変更されないという意味での静的) が与えられた場合、最適なパフォーマンスで繰り返し同時ルックアップが必要な場合、HashMapカスタム コンパレータを使用したバイナリ検索を使用する配列と、どちらが優れているでしょうか?

答えはオブジェクトまたは構造体型の関数ですか? ハッシュおよび/または等価関数のパフォーマンス? ハッシュの一意性? リストサイズ？ Hashsetサイズ/セットサイズ?

私が検討しているセットのサイズは、500k から 10m の範囲です (その情報が役立つ場合)。

私は C# の答えを探していますが、真の数学的答えは言語にはないと思うので、そのタグは含めません。ただし、C# 固有の注意事項がある場合は、その情報が必要です。

私はノード構造体を持っています

ソートされたベクトルで。

ベクトルのバイナリ検索を実行して要素を見つけるアルゴリズムに関数があるかどうか疑問に思っています。

I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_search in the standard library's <algorithm> header, but I need it to return the iterator that points at the result, not a simple boolean telling me if the element exists.

(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)

My main concern here is that I need the speed of a binary search, so although I can find the data with other algorithms, as mentioned below, I want to take advantage of the fact that my data is sorted to get the benefits of a binary search, not a linear search.

so far lower_bound and upper_bound fail if the datum is missing:

Note: I'm also fine using an algorithm that doesn't belong to the std namespace as long as its compatible with containers. Like, say, boost::binary_search.

5000 個の整数のソート済み配列があります。ランダムな整数が配列のメンバーであるかどうかは、どのくらいの速さでわかりますか? 一般的な答えとしては、C と Ruby がいいでしょう。

配列値の形式は次のとおりです。

ここでc、1 から 5000 までの任意の整数を指定できます。

例えば：

二分探索は見た目よりも実装が難しいです。「二分探索の基本的な考え方は比較的単純ですが、詳細は驚くほどトリッキーになる可能性があります…」—ドナルドクヌース。

新しいバイナリ検索の実装に導入される可能性が最も高いバグはどれですか？

第一に、私はプログラマーではなく、プログラミングやアルゴリズムを学んだことがありません。実際には、ほとんど awk または ruby​​ で、いくつかの bash をプログラムする必要があります。

今日のタスクでは、プレーン テキスト ファイルに巨大なデータ セット (浮動小数点数) があり、1 つのレコード/行があり、セットのすべての数値の合計がありますが、数値の一部 ( 1 つ) は負ですが、ファイルには表示されません (要素が負の場合は符号がありません)。

しかし、私はそれ/それらを見つけなければなりません：最初に正しい合計を計算しました（ ですべての数字を追加してawk）、それらの符号は気にしませんでした。ここで、元の合計 (記号を考慮したもの) と新しい合計の差がわかりました。しかし、差分/2 のようにまったく同じ合計を持つデータセットのすべてのサブセットを見つける必要があります。

例えば：

これで、1+2+3+4+5 - ORIG SUM: 15-5=10 の差を計算できます。10/2 = 5 なので、合計が 5 になるすべてのサブセット、つまり [1,4]、[2,3]、[5] を見つける必要があります。

それを行う適切な方法はありますか？私は awk、ruby、シェル スクリプトを好みますが、python と perl の両方を使用できます (外部ライブラリをインストールする権利がないため、外部ライブラリを頻繁に使用する必要はありません)。

前もって感謝します。