Расстояние Хэмминга на бинарном векторе в Scala

Question

Я хотел бы иметь быструю реализацию расстояния Хемминга на двоичных векторах. Я проверил это на Array[Byte] скорее, чем Array[Int] думая, что это будет быстрее, но это не так. Если кто-то может объяснить мне это поведение и / или посоветовать мне лучшую реализацию.

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

Я не уверен, почему реализация байтов медленнее, чем другие, но подозреваю, что это связано с тем, как != Реализация - регистры процессора лучше оснащены для работы с четырехбайтовыми последовательностями в настоящее время, чем с одиночными байтами.

Вышесказанное - только мое предположение, но не ставьте на это свой дом.

Что касается более быстрой реализации, если ваш вариант использования таков, где важны отдельные наносекунды, вам придется отказаться от элегантности коллекций 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
 }

В среднем это должно быть в несколько сотен раз быстрее, чем ваша реализация.