爲什麼在這個特定代碼中的Map查找花費了如此長的時間？

我有以下數據結構：爲什麼在這個特定代碼中的Map查找花費了如此長的時間？

val set: scala.collection.immutable.Set[String] = ... 
val test1: scala.collection.immutable.Map[String,scala.collection.immutable.Set[String]] = ... 
val test2: Array[scala.collection.immutable.Set[String]] = ...

set包含約60000 entires。 test1有兩個條目（「一個」和「兩個」），並且每個條目類似於set。 test2與test1類似，但是鍵是0和1。

運行test1.get("one").get.contains("somestring")需要很長時間（約1秒），但運行test2(0).contains("somestring")是非常快的。

我不太明白爲什麼會有這麼大的差異。有任何想法嗎？

來源

2013-12-18 Mark Goldenstein

如果你認爲地圖有「one」作爲鍵入，那麼你應該調用'test1（「one」）。contains（「somestring」）' – Kigyo

@Kigyo感謝你的提示，它絕對看起來更好。然而，'apply'方法與我測試中的'get'方法具有相同的性能。 –

像其他人一樣說：我們需要更多關於您的代碼的信息。 – Kigyo

問題是我在現有的地圖上使用mapValues來生成新的地圖。我認爲mapValues的作用與map類似，但實際上mapValues只在現有的地圖上創建一個視圖，而不是新的地圖。

來源

2013-12-18 13:38:14

此：

test2(0)

運行非常快，因爲它是一個數組，它知道究竟在何處0是，地圖必須找到「一」鍵，然後再獲取的它的對。

來源

2013-12-18 12:46:23

很明顯，Array比Map快，問題在於爲什麼Map極其緩慢，即使它只有兩個條目。在包含60,000個條目的Set中，所花費的時間比包含的查找要多得多。 –

你如何評估這個？我無法使用System.currentTimeInMillis（）來測量運行map（「one」）的時間。它始終爲零。 –

@弗拉維安他說他看到**一秒**差異。只有兩個鍵最壞的情況是在一個散列桶內進行兩次比較，操作的數量可以忽略不計。 –

運行這段代碼生成一些藏品像你提到的：

import scala.collection.mutable.{HashSet, HashMap} 
import scala.util.Random 

def genSet(count: Int = 100 * 1000, stringSize: Int = 10): Set[String] = { 
    val set = new HashSet[String] 
    set.sizeHint(count) 

    for(i <- 1 to count) { 
    set.add(i.toString) 
    } 

    set.toSet 
} 

def genSetMap(count: Int = 2, keySize: Int = 10) 
      (f: => Set[String]): Map[String, Set[String]] = { 
    val map = new HashMap[String, Set[String]] 
    map.sizeHint(count) 

    for(i <- 1 to count) { 
    map.put(i.toString, genSet()) 
    } 

    map.toMap 
}

下面的測試，使用每一套100.000元，仍然運行瞬間：

val map = genSetMap(2, 10){ genSet(100*1000) } 
map("2").contains("99999") // res2: Boolean = true

所以我懷疑有一些特殊性在你的實際代碼導致它不會生成一個集合，但一些其他中間集合沒有快速搜索。你能提供一個更具體的例子，你看到的行爲與實際的代碼？

來源

2013-12-18 13:15:42 danielkza

感謝您的貢獻，您是對的，問題出在代碼中，而不是問題的一部分。我使用的Map是使用'mapValues'方法創建的，它只在舊的Map上創建一個View，而不是一個新的地圖。 –

爲什麼在這個特定代碼中的Map查找花費了如此長的時間？

回答

相關問題