#二分查找 #鲁棒 #错误 #过程中 # #有向无环图 #范围

bin+lib robust-binary-search

鲁棒二分查找提供了一个对搜索过程中错误具有鲁棒性的二分查找实现。

2 个版本

0.1.1 2020 年 10 月 24 日
0.1.0 2020 年 10 月 24 日

#1872算法


用于 robust-git-bisect

Apache-2.0

105KB
2.5K SLoC

鲁棒二分查找

鲁棒二分查找提供了一个对搜索过程中错误具有鲁棒性的二分查找实现。换句话说,如果比较函数有时返回不正确的结果,本项目中的搜索仍然会收敛到正确的解决方案。

此算法借鉴了 Karp 和 Kleinberg 在 ""Noisy binary search and its applications" by Karp and Kleinberg" 中的乘法权重算法,并进行了调整以使其确定性,然后扩展以支持有向无环图。

用法

请参阅 AutoSearcher 以在线性范围内进行二分查找,以及 AutoCompressedDAGSearcher 以在图中进行二分查找。

如果您正在寻找 git bisect 的替代品,请参阅使用此库的 robust-git-bisect 包。

性能

此代码针对最小化执行的测试次数(即迭代次数)进行了优化,并不一定是搜索算法本身的 CPU 时间,因此如果测试是确定性的,则可能比普通二分查找慢。

线性算法(SearcherAutoSearcher)每迭代一次大约需要 O(log N) 的时间。图算法(CompressedDAGSearcherAutoCompressedDAGSearcher)每迭代一次大约需要 O(segments) 的时间。

依赖项

~3–11MB
~103K SLoC