問題タブ [bisect]

リスト内の要素を検索する場合、どちらが高速かを理解するためのコードを作成しました。それは二等分であることが判明しました。私が理解していないのは、バイセクトアルゴリズムの複雑さであり、Van Emde Boasツリーを使用していますか？

参照： http ：//docs.python.org/library/bisect.html

整数のリストがあり、範囲内の数値のサブセットを返す関数を作成したいと考えています。NumbersWithinRange(list, interval) 関数名のようなもの...

すなわち、

結果にもう 1 つ数字を書き忘れたかもしれませんが、それがアイデアです...

リストの長さは 10/20 百万にもなり、範囲は通常数 100 です。

Pythonで効率的に行う方法に関する提案-私はbisectを使用することを考えていました.

ありがとう。

jquery git リポジトリで特定の変更を見つけようとしたときに、奇妙な問題に遭遇しましたgit-bisect。bisect コマンドは、bisect プロセスの続行を妨げる変更されたファイルを作成するようです。最初に実行したコマンドは次のとおりです。

どの時点で出力が得られます：

しかし、今、実行するgit statusと、出力は次のようになります。

4 つのファイルが変更済みとして表示されます。次に を実行するgit bisect badと、ローカルの変更がチェックアウトによって上書きされるというエラーが表示されます。

私は何か間違ったことをしているのですか、それとも仕組みを誤解してgit-bisectいますか? この問題の回避策はありますか? ありがとう！

rebaseif Mercurial拡張機能は、プル時に、競合なしでマージを自動的に実行できる場合にのみ、リベースを実行するプロセスを自動化します。（手動で解決する競合がある場合、リベースは行われないため、2つのブランチを手動でマージする準備が整います。）これにより、開発者がコードのさまざまな部分で作業しているときに履歴が単純化および線形化されますが、リベースはスローされます。開発者が作業を行っていたときの世界の状態に関する情報を削除します。私はこのような議論に同意する傾向があります一般的なケースでは、リベースは良い考えではありませんが、リベース-哲学が競合しない場合に魅力的である場合、私はリベースを見つけます。コードのさまざまな部分で変更が発生した場合、ロジックエラーのリスクがまだあることを理解していますが、私はそれについて気を配っています（そして、rebaseif拡張機能の作成者はそれが悪い考えだと感じるようになりました。）

私は最近、複雑で苦痛なバイセクトを経験しました。リポジトリに短いブランチのマージが多数あることが、バイセクトが暗黙のO（lg n）の約束を果たせなかった主な理由だと思います。マージを超えて範囲を拡張するために、「bisect --extend」を何度も実行する必要があることに気付きました。一度にいくつかのチェンジセットを実行して、基本的にbisect O（n）を作成します。また、リポジトリのグラフを見ると分岐を追跡できなかったため、バイセクトがどのように進んでいるかを追跡し、これまでに取得した情報を理解するのは非常に複雑でした。

bisectを使用する（そして改訂履歴を見て理解する）より良い方法はありますか、それとも開発でrebaseifをもっと使用していれば、プロセスはよりスムーズだったでしょう。または、競合していない場合にリベースを使用すると何がうまくいかないのかをより具体的に理解するのに役立ちますか？問題を引き起こす可能性があり、回避する必要がありますか？

rebaseifはより一般的なgitワークフローに一致すると思うので、これをより一般的に（Mercurialだけでなく）タグ付けしています。gitユーザーは落とし穴を見たことがあるかもしれません。

重複の可能性:
二分探索を使用して決定する

他のスレッドを投稿しましたが、回答が得られなかったので、より明確にするために私の仕事の一部を提供しようとしています.

ちょうど1年で借金を完済するには、二分法を使って毎月の支払いを決定する必要があります。

ここにいくつかのコードがあります：

しかし、私は非常に離れた答えを受け取ります: 298222.173851

私の友人は、正解は : 29157.09 だと教えてくれました。

これは私よりもはるかに低いです...問題は、丸め(まだ行っていません)と、ループのたびにバランスを維持し、バランスが0を超えている場合はリセットすることにあると思います。この問題を試みる方法がわかりませんそして、誰かを助けてください:)

二分検索を使用して見つける方法を見つけようとしています:

ローン金額を清算するための毎月の支払い

• 月利 = (年利) / 12
• 毎月の支払い下限 = 残高 / 12
• 月々のお支払い上限額＝（残高×（1＋月々の金利）12）÷12

現時点で私は持っています：

私が間違っているところへの助けをいただければ幸いです。

bisect 範囲に複数の分岐が含まれる場合、hg bisect の検索はどのように機能しますか。各サブブランチを効果的に二分していますか (非効率的だと思います)。

たとえば、感謝の気持ちを込めて、この関連する質問への回答から図を借りると、バイセクトが最初に「適切な」右側のブランチの変更セット 7 に到達した場合はどうなるでしょうか。

それでは、7 から 12 の間だけに見えて、私たちが気にかけている真のファーストバッドを見逃してしまうのでしょうか? （したがって、「ばかげた」番号順を使用します）または完全な地形を使用して、最初の悪い点が右側の分岐で7未満である可能性があるか、左側の分岐のどこかにある可能性があることを知るのに十分賢いですか.

私の質問の目的は、(a) アルゴリズムをよりよく理解することと、(b) どのブランチに行くかを真剣に考えずに最初の bisect 範囲を自由に拡張できるかどうかを理解することです。私は、すべてのテストの後に、次のマージを超えて拡張するように求められ続けたため、手順全体が本質的に O(n) であった、高分岐の bisect 状況にありました。最初の「良い」マーカーを、あまり考えずにマージのネストを過ぎて投げることができるかどうか、そしてそれが時間を節約して正しい結果をもたらすかどうか疑問に思っています。

コードの自動生成されたパフォーマンスデータをperf.txtに保存しています。コードを改善するたびに、perf.txtを新しいパフォーマンスデータで上書きするスクリプトを実行します。次に、perf.txtをコミットします。

振り返ってみると、perf.txtの上書きは骨の折れる間違いでした。そして今、私はいくつかの分析/プロットを私の改善のグラフにしたいのですが、できません。もちろん、古いperf.txtファイルはまだコミット履歴に残っています。それらを取得する簡単な方法はありますか？理想的には、perf〜1.txt、perf〜2.txtなどをタイムスタンプとともに新しいディレクトリに配置したいと思います。

あるいは、git-bisectのようにコミット履歴（たとえば、git next perf.txt）を単純に「再生」できれば、直線的にも機能します。

私は次の問題を抱えています：

• のバージョンは正常にmaster動作します
• 前の最後のタグのバージョンmaster（たとえばlast）にはバグがあります
• 同僚は、lastその特定のバグに対する彼の改訂のためのパッチを必要としています

わかった。git bisectバグを修正したリビジョンを友人に聞いてみましょう。

しかし、それはうまくいきません：

いくつかの良い回転は悪い回転の祖先ではありません。
この場合、gitbisectは正しく機能しません。
多分あなたは良い回転と悪い回転を間違えますか？

これを克服するためのヒントはありますか？ドキュメントで何かを見逃しましたか？

1 つの課題に対して 1 つのコミットを行うことは、良い習慣であると心から信じています。「ベスト プラクティス」などの記事のどこかで読んだはずです。

そのため、私のワークフローは次のとおりです。

• 新しい問題については、新しいローカル ブランチを作成しgit checkout -b new-issueます。
• すべての変更をそれにコミットします。これには、多くのコミットが含まれることがあります。
• 完了したらsquash、コミットし、rebaseそれらを現在のテーマ別ブランチに入れます。
• 何か問題が発生した場合はgit revert、コミットしてバグを見つけて修正し、新しいパッチをテーマ ブランチにコミットできます。リモート リポジトリの履歴は変更しません。

しかし、今日、次のワークフローを聞いて驚きました。

• 新しい問題の新しいブランチを作成します。
• それにすべてをコミットします。
• 課題ブランチをテーマ ブランチとマージするために使用merge --no-ffします (そのため、「マージ コミット」が可能になりますrevert)。
• 何か問題が発生した場合はgit bisect、バグを見つけるために使用できます。

最初のアプローチによると、クリーンな git 履歴があり、開発中に使用されるオーバーヘッド ブランチについてはわかりません。

2 番目のアプローチによれば、非常に厄介な履歴が残り、たった 1 つの課題に対して多くの醜く不必要なマージとコミットが行われます。ただし、git bisectバグを見つけるために使用できます。(おそらく、これはリファクタリングに適していますか?)

• 両方のアプローチについて、どのような長所と短所がありますか?

• どのアプローチを使用し、その理由は何ですか?

• 実際に、実際にgit bisectバグを見つけることに慣れていますか? （私はそうではありません…）