Scalaのバイナリベクトルのハミング距離

Question

バイナリベクトルのハミング距離を高速に実装したいと考えています。 Array[Int]より高速ではあるが、そうではないと考えて、Array[Byte]でテストしました。 誰かがこの行動を私に説明したり、より良い実装について助言したりすることができます。

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レジスタが良く、単一のバイトよりも、今日で4バイトのシーケンスに対処するために装備されています。

上記はちょうど私の推測ですが、それにあなたの家を賭けてはいけません。より高速な実装については

、あなたのユースケースは、単一のナノ秒の問題は、あなたが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 
} 

これがすべきあなたの実装より平均して数百倍高速です。