海明距離二進制向量在斯卡拉

我想有一個快速執行海明距離二進制向量。我在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

來源

2016-11-19 KyBe

我看到它的方式......你在冷靜的jvm上運行你的測量。首先預熱jvm，然後查看數字。 –

我不知道爲什麼字節實現比其他慢，但是懷疑它與!=的實現方式做 - 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 
}

這應該平均比實施要快數百倍。

來源

2016-11-19 13:22:19 Dima

謝謝你的實現，將進程速度提高30倍。我還使用Array [Byte]對其進行了測試，但對於Byte而言，增益大約爲5％，而不是Int。 – KyBe

30似乎並不令人印象深刻。在我的基準測試中，它快了大約300倍。 – Dima

我不知道爲什麼，但經過新的測試後，我得到了500倍的改進。最好使用Vector而不是Array或其他類型的結構？ – KyBe

海明距離二進制向量在斯卡拉

回答

相關問題