通过bitmasking二进制搜索？ [英] Binary searching via bitmasking?

问题描述

我已经使用这个算法，多次到二分查找了 int类型或多头。基本上，从我做起 Long.MinValue 和 Long.MaxValue ，并决定设置位为我日根据我最大化（或最小化）功能的价值定位。在实践中，这真可谓是快（正好63 * 2位操作），更容易code和避免了许多<一href="http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search">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 ith 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 or Long 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 Doubles and Floats?

推荐答案

只要你是位变换（一种流行的消遣方式在某些圈子里）为什么不走一路？我不知道是否有需要获得任何效益，但我认为它实际上使算法更清晰一点。

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二进制搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！