我有一个二进制搜索循环,它在执行路径中被多次命中。
分析器显示搜索的除法部分(根据搜索范围的高和低索引查找中间索引)实际上是搜索成本最高的部分,大约是 4 倍。
(我认为)对于有效的二分搜索来说,找到精确的中间值并不重要,只是靠近中间的一个值,在任何一个方向上都没有偏差。
是否有一种比特旋转算法可以用mid = (low + high) / 2
更快的东西代替?
编辑:语言是 C#,但等效的位操作在任何语言中都有效(尽管它可能对性能没有好处),这就是我关闭 C# 标记的原因。
我有一个二进制搜索循环,它在执行路径中被多次命中。
分析器显示搜索的除法部分(根据搜索范围的高和低索引查找中间索引)实际上是搜索成本最高的部分,大约是 4 倍。
(我认为)对于有效的二分搜索来说,找到精确的中间值并不重要,只是靠近中间的一个值,在任何一个方向上都没有偏差。
是否有一种比特旋转算法可以用mid = (low + high) / 2
更快的东西代替?
编辑:语言是 C#,但等效的位操作在任何语言中都有效(尽管它可能对性能没有好处),这就是我关闭 C# 标记的原因。
这是一个不受溢出问题影响的平均值的 bit-hack 版本:
unsigned int average (unsigned int x, unsigned int y)
{
return (x&y)+((x^y)>>1);
}
int mid = (low + high) >>> 1;
请注意,当整数溢出成为问题时,使用“(low + high) / 2”进行中点计算将无法正常工作。
您可以使用位移并克服可能的溢出问题:
low + ((high-low) >> 1)
但是我必须承认,我希望现代编译器和解释器将除以 2(或除以任何其他恒定的 2 幂)作为位移位,所以不确定它是否真的有帮助 - 试试看。
为了进一步扩展 Nils 的答案,Richard Schroeppel发明了这个。
http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23
第 23 项(施罗佩尔):
(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B)。
(A + B)/2 = ((A XOR B) + 2(A AND B))/2
= (A XOR B)/2 + (A AND B)
= (A XOR B)>>1 + (A AND B)
avg(x,y){return((x^y)>>1)+(x&y);}
(A AND B) + (A OR B) = A + B
因为A AND B
给出了两个共享的(在 A 和 B 之间)幂的总和,A OR B
给出了共享的和不共享的,因此:
(A AND B) + (A OR B) =
(sum of shared powers of two) +
((sum of shared powers of two) + (sum of unshared powers of two)) =
(sum of shared powers of two) +
((sum of shared powers of two) + (sum of powers of two of A only) +
(sum of powers of two of B only)) =
((sum of shared powers of two) + (sum of powers of two of A only)) +
((sum of shared powers of two) + (sum of powers of two of B only))
= A + B.
A XOR B
给出 A 和 B 之间不同的那些位的映射。因此,
A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only).
因此:
2(A AND B) + (A XOR B) =
((sum of shared powers of two) + (sum of powers of two of A only)) +
((sum of shared powers of two) + (sum of powers of two of B only))
= A + B.
如果我没记错的话,在某些情况下,使用数组的确切中间实际上可能会更慢。解决方案是随机选择一分为二数组的索引。确定数组中位数的算法同样如此。
我不记得确切的细节,但我记得在 iTunes 上的MIT 算法系列的第 6 讲中听过。
尝试低 + ((高 - 低) / 2))。这应该有效,因为您只取两个数字的平均值。如果二进制搜索列表相当大,这将减少算法所花费的时间,因为高 - 低远小于高 + 低。