问题描述
我已经使用这个算法,多次到二分查找了 int类型
或多头
。基本上,从我做起 Long.MinValue
和 Long.MaxValue
,并决定设置位为我
日根据我最大化(或最小化)功能的价值定位。在实践中,这真可谓是快(正好63 * 2位操作),更容易code和避免了许多gotchas传统的二进制搜索实现。
I have used this algorithm many times to binary search over Ints
or Longs
. Basically, I start from Long.MinValue
and Long.MaxValue
and decide to set the bit at i
th position depending on the value of the function I am maximizing (or minimizing). In practice, this turns out to be faster (exactly 63*2 bitwise operations) and easier to code and avoids the many gotchas of traditional binary search implementations.
下面是我在斯卡拉算法:
Here is my algorithm in Scala:
/**
* @return Some(x) such that x is the largest number for which f(x) is true
* If no such x is found, return None
*/
def bitBinSearch(f: Long => Boolean): Option[Long] = {
var n = 1L << 63
var p = 0L
for (i <- 62 to 0 by -1) {
val t = 1L << i
if (f(n + t)) n += t
if (f(p + t)) p += t
}
if (f(p)) Some(p) else if (f(n)) Some(n) else None
}
我有3个问题:
I have 3 questions:
-
这是什么算法叫文学?当然,我不能这样做的发明者 - 但是,我没有发现任何东西,当我试图使用Google的二进制搜索+位掩码/反复的各种组合。我一直在亲自把它称为bitBinSearch。我没有看到文章将超过二分查找了一个
诠释
或龙
站点在哪里,这将是该提出来了琐碎写。
What is this algorithm called in literature? Surely, I can't be the inventor of this - but, I did not find anything when I tried googling for various combinations of binary-search + bit-masking/toggling. I have been personally calling it "bitBinSearch". I have not seen this mentioned at all in articles going over binary search over an
Int
orLong
domain where this would be trivial to write.
可以在code改进/缩短呢?现在,我跟踪了消极和积极的解决方案,在 N
和 P
。任何聪明的方式,我可以把它们合并成单一的变量?下面是一些测试用例: http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c 你回答问题之前
Can the code be improved/shortened in anyway? Right now I keep track of the negative and positive solutions in n
and p
. Any clever way I can merge them into single variable? Here are some sample test cases: http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c before you attempt an answer
是否有可与双击
s到工作的一个版本,浮动
S'
Is there a version that can be made to work with Double
s and Float
s?
推荐答案
只要你是位变换(一种流行的消遣方式在某些圈子里)为什么不走一路?我不知道是否有需要获得任何效益,但我认为它实际上使算法更清晰一点。
As long as you're bit-twiddling (a popular pastime in some circles) why not go all the way? I don't know if there's any efficiency to be gained, but I think it actually makes the algorithm a little clearer.
def bitBinSearch(f: Long => Boolean): Option[Long] = {
var n = Long.MinValue
var p = 0L
var t = n >>> 1
while (t > 0) {
if ( f(n|t) ) n |= t
if ( f(p|t) ) p |= t
t >>= 1
}
List(p,n).find(f)
}
当然,如果你去递归可以消除这些讨厌的 VAR
秒。
import scala.annotation.tailrec
@tailrec
def bitBinSearch( f: Long => Boolean
, n: Long = Long.MinValue
, p: Long = 0L
, t: Long = Long.MinValue >>> 1 ): Option[Long] = {
if (t > 0) bitBinSearch(f
, if (f(n|t)) n|t else n
, if (f(p|t)) p|t else p
, t >> 1
)
else List(p,n).find(f)
}
此外,可能不是更有效,但也许更多的斯卡拉似的。
Again, probably not more efficient, but perhaps a bit more Scala-like.
更新
您的评论对智力/长了我想知道,如果一个函数可以做到这一切。
Your comment about Int/Long got me wondering if one function could do it all.
在旅行下来一些死角我终于想出了这个(这是奇怪的是,居然pretty的接近你原来的code)。
After traveling down a few dead-ends I finally came up with this (which is, oddly, actually pretty close to your original code).
import Integral.Implicits._
import Ordering.Implicits._
def bitBinSearch[I](f: I => Boolean)(implicit ev:Integral[I]): Option[I] = {
def topBit(x: I = ev.one):I = if (x+x < ev.zero) x else topBit(x+x)
var t:I = topBit()
var p:I = ev.zero
var n:I = t+t
while (t > ev.zero) {
if ( f(p+t) ) p += t
if ( f(n+t) ) n += t
t /= (ev.one+ev.one)
}
List(p,n).find(f)
}
这通过下面的测试。
assert(bitBinSearch[Byte] (_ <= 0) == Some(0))
assert(bitBinSearch[Byte] (_ <= 1) == Some(1))
assert(bitBinSearch[Byte] (_ <= -1) == Some(-1))
assert(bitBinSearch[Byte] (_ <= 100) == Some(100))
assert(bitBinSearch[Byte] (_ <= -100) == Some(-100))
assert(bitBinSearch[Short](_ <= 10000) == Some(10000))
assert(bitBinSearch[Short](_ <= -10000) == Some(-10000))
assert(bitBinSearch[Int] (_ <= Int.MinValue) == Some(Int.MinValue))
assert(bitBinSearch[Int] (_ <= Int.MaxValue) == Some(Int.MaxValue))
assert(bitBinSearch[Long] (_ <= Long.MinValue) == Some(Long.MinValue))
assert(bitBinSearch[Long] (_ <= Long.MaxValue) == Some(Long.MaxValue))
assert(bitBinSearch[Long] (_ < Long.MinValue) == None)
这篇关于通过bitmasking二进制搜索?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!