Scala 中二进制向量的汉明距离

Question

我想在二进制向量上快速实现汉明距离。我在 Array[Byte] 而不是 Array[Int] 上测试了它，认为它会更快，但事实并非如此。如果有人可以向我解释这种行为 and/or 建议我更好地实施。

def hammingDistanceI(v1:Array[Int], v2:Array[Int]) = {
  v1.zip(v2).count{case(a,b) => a!=b}
}
def hammingDistanceB(v1:Array[Byte], v2:Array[Byte]) = {
  v1.zip(v2).count{case(a,b) => a!=b} 
}

def speedMeasureByte(v:Array[Byte], nbIte:Int) = {
  val t0 = System.nanoTime
  for(i<-0 to nbIte-1) hammingDistanceB(v,v)
  val t1 = System.nanoTime
  (t1-t0)/1000000
}

def speedMeasureInt(v:Array[Int], nbIte:Int) = {
  val t0 = System.nanoTime
  for(i<-0 to nbIte-1) hammingDistanceI(v,v)
  val t1 = System.nanoTime
  (t1-t0)/1000000
}

val v1Int = Array.fill(100)(Random.nextInt(2))
val v1Byte = v1Int.map(_.toByte)

val (tInt, tByte) = (speedMeasureInt(v1Int,1000000),
                     speedMeasureByte(v1Byte,1000000))

// tInt = 1636 ms
// tByte = 3307 ms

Answer 1

我不确定为什么字节实现比另一个慢，但怀疑它与实现方式有关 != - cpu 寄存器更适合处理四字节现在的序列比单字节。

以上只是我的猜测，不要赌你的房子。

至于更快的实现，如果您的用例是这样的，其中单个纳秒很重要，您将不得不放弃 scala 集合的优雅并坚持使用旧的好循环：

 def hd(a: Array[Int], b: Array[Int]) { 
   var c = 0
   var i = 0
   while(i < a.length) { c += a(i)^b(i); i+=1 }
   c
 }

这应该比您的实施平均快几百倍。

Scala 中二进制向量的汉明距离

Hamming Distance on binary Vector in Scala

scala

hamming-distance