问题标签 [bisect]

我编写了代码来了解在搜索列表中的元素时哪个更快。原来是平分的。我不明白二分算法的复杂性是什么，它是否使用 Van Emde Boas 树？

参考： http ://docs.python.org/library/bisect.html

我有一个整数列表，我想编写一个函数来返回一个范围内的数字子集。NumbersWithinRange(list, interval) 函数名之类的东西......

IE，

也许我忘了在结果中再写一个数字，但这就是我的想法......

该列表的长度可以达到 10/20 百万，范围通常为几百个。

关于如何使用 python 有效地做到这一点的任何建议 - 我正在考虑使用 bisect。

谢谢。

我在尝试使用git-bisect来查找 jquery git 存储库中的特定更改时遇到了一个奇怪的问题： bisect 命令似乎创建了阻止 bisect 进程继续进行的修改文件。这些是我首先运行的命令：

此时我得到输出：

但是现在，当我运行时git status，输出是：

四个文件显示为已修改。如果我然后运行git bisect bad，我会收到一条错误消息，指出我的本地更改将被结帐覆盖。

我做错了什么或误解了它的git-bisect工作原理吗？此问题的任何解决方法？谢谢！

rebaseif mercurial 扩展在拉取时自动执行 rebase 的过程，前提是合并可以自动完成而没有冲突。（如果有需要手动解决的冲突，它不会变基，让您准备好手动合并两个分支。）当开发人员在代码的不同部分工作时，这会简化和线性化历史记录，尽管任何变基都会抛出当开发人员工作时，会删除一些有关世界状态的信息。我倾向于同意这样的论点和这个在一般情况下，rebase 不是一个好主意，但我发现 rebase-if 哲学对非冲突情况很有吸引力。我对此持谨慎态度，尽管我知道当代码的不同部分发生更改时仍然存在逻辑错误的风险（并且rebaseif 扩展的作者已经觉得这是一个坏主意。..）

我最近经历了一个复杂而痛苦的 bisect，我认为在我们的存储库中有大量的短分支合并是 bisect 没有实现其隐含的 O(lg n) 承诺的主要原因。我发现自己需要多次运行“bisect --extend”，以将范围扩展到合并之外，一次通过几个变更集，基本上使 bisect O(n)。我还发现跟踪平分线的进展情况以及了解到目前为止我获得的信息非常复杂，因为在查看存储库的图表时我无法遵循分支。

是否有更好的方法来使用 bisect（以及查看和理解修订历史），或者如果我们在开发中更多地使用 rebase，这个过程会更顺利，我是对的。或者，您能否帮助我更具体地理解在非冲突情况下使用 rebase 可能会出现什么问题：是否足以引起应该避免的问题？

因为我认为 rebaseif 匹配更典型的 git 工作流程，所以我更一般地标记了这个（不仅仅是 mercurial）：git 用户可能已经看到了陷阱。

可能的重复：
使用二等分搜索来确定

我已经发布了其他线程，但它没有收到答案，因此我试图提供我的一些工作以更清楚地说明。

我需要使用二分法来确定每月还款额，以便准确地在一年内还清债务。

这是一些代码：

但是，我收到的答案很离谱：298222.173851

我的朋友告诉我正确答案是：29157.09

这比我的要低很多......我想问题在于舍入（我还没有这样做）并在每次循环后保留平衡并在余额超过 0 时重置它。我不知道如何尝试这个问题请帮助某人:)

我试图弄清楚如何使用平分搜索来查找：

每月还款以清除贷款金额

• 月利率=（年利率）/12
• 月供下限=余额/12
• 月供上限 = (余额 x (1 + 月利率)12) / 12

目前我有：

任何对我出错的地方的帮助将不胜感激。

如果 bisect 范围包括多个分支，hg bisect 的搜索是如何工作的。它是否有效地将每个子分支一分为二（我认为这将是低效的）？

例如，感激地借用这个相关问题的答案中的图表，如果二等分首先到达“好”右侧分支上的变更集 7 会怎样。

然后它会看起来只在 7 到 12 之间，错过我们关心的真正的第一坏吗？（因此使用“哑”数字顺序）或者它是否足够聪明以使用完整的地形并知道第一个坏可能在右侧分支上低于 7，或者仍然可能在左侧分支上的任何位置。

我的问题的目的是（a）只是为了更好地理解算法，以及（b）理解我是否可以自由地扩展我的初始平分范围，而无需认真考虑我去哪个分支。我一直处于高分支平分情况，每次测试后它一直要求我扩展到下一次合并之外，因此整个过程基本上是 O(n)。我想知道我是否可以将第一个“好”标记扔回一些合并巢而不考虑太多，以及这是否会节省时间并给出正确的结果。

我一直在 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修复该错误的修订版：

但这行不通：

一些好的转速不是坏转速的祖先。
git bisect 在这种情况下无法正常工作。
也许你误会了好转速和坏转速？

有什么提示可以克服这个吗？我错过了文档中的某些内容吗？

我真的相信在一个问题上进行一次提交是一种很好的做法。我确定我在“最佳实践”之类的文章中某处读过它。

因此，我的工作流程如下：

• 对于一个新问题，我使用git checkout -b new-issue.
• 将所有更改提交给它。有时这涉及大量提交。
• 完成后，我squash将提交并将rebase它们放入当前的主题分支。
• 如果出现问题，我可以git revert提交，找到错误，修复它，然后将新补丁提交到主题分支。我不会更改远程存储库的历史记录。

但是今天，我很惊讶地听到以下工作流程：

• 为新问题创建新分支。
• 将一切都投入其中。
• 用于merge --no-ff将问题分支与主题分支合并（因此我们将拥有我们可以的“合并提交” revert）。
• 如果出现问题，我们可以使用它git bisect来查找错误。

根据第一种方法，我们将拥有一个干净的 git 历史记录，并且不知道开发期间使用的开销分支。

根据第二种方法，我们将有一个非常混乱的历史，只有一个问题有很多丑陋的、不必要的合并和提交。但是，我们可以使用它git bisect来查找错误。（也许这更适合重构？）

• 您认为这两种方法的优缺点是什么？

• 您使用哪种方法，为什么？

• 在实践中，你真的习惯于git bisect寻找错误吗？（我没有……）