Scala的並行頻率計算不起作用

Question

我學習Scala從書「斯卡拉不耐煩」工作的練習。請參閱以下問題以及我的答案和代碼。我想知道我的答案是否正確。此外代碼不起作用（所有頻率都是1）。錯誤在哪裏？

Q10：哈利黑客讀取文件到字符串並希望使用 並行採集同時更新上線的 部分信件的頻率。他使用以下代碼：

val frequencies = new scala.collection.mutable.HashMap[Char, Int] 
for (c <- str.par) frequencies(c) = frequencies.getOrElse(c, 0) + 1 

爲什麼這是一個可怕的想法？他怎樣才能真正平行計算 ？

我的回答： 這不是一個好主意，因爲如果2個線程同時更新相同的頻率，結果是不確定的。

我的代碼：

def parFrequency(str: String) = { 
    str.par.aggregate(Map[Char, Int]())((m, c) => { m + (c -> (m.getOrElse(c, 0) + 1)) }, _ ++ _) 
} 

單元測試：

"Method parFrequency" should "return the frequency of each character in a string" in { 
    val freq = parFrequency("harry hacker") 

    freq should have size 8 

    freq('h') should be(2) // fails 
    freq('a') should be(2) 
    freq('r') should be(3) 
    freq('y') should be(1) 
    freq(' ') should be(1) 
    freq('c') should be(1) 
    freq('k') should be(1) 
    freq('e') should be(1) 
} 

編輯： 閱讀this線後，我更新的代碼。現在，如果單獨運行測試，但如果作爲套件運行則失敗。

def parFrequency(str: String) = { 
    val freq = ImmutableHashMap[Char, Int]() 
    str.par.aggregate(freq)((_, c) => ImmutableHashMap(c -> 1), (m1, m2) => m1.merged(m2)({ 
     case ((k, v1), (_, v2)) => (k, v1 + v2) 
    })) 
} 

編輯2： 見下面我的解決方案。

Answer 1

這似乎工作。我喜歡它比這裏提出的其他解決方案更好，因爲：

1. 這是很多比implicit class和略少的代碼比使用getOrElse與foldLeft代碼更少。
2. 它使用API​​中的merged函數來打算做我想要的。

3. 這是我自己的解決方案:)

   def parFrequency(str: String) = { 
       val freq = ImmutableHashMap[Char, Int]() 
       str.par.aggregate(freq)((_, c) => ImmutableHashMap(c -> 1), _.merged(_) { 
       case ((k, v1), (_, v2)) => (k, v1 + v2) 
       }) 
   } 
   

感謝您抽出寶貴時間來幫助我。

Answer 2

++不結合相同的密鑰的值。所以當你合併地圖時，你會得到（對於共享鍵）其中一個值（在這種情況下總是1），而不是值的總和。

這工作：

def parFrequency(str: String) = { 
    str.par.aggregate(Map[Char, Int]())((m, c) => { m + (c -> (m.getOrElse(c, 0) + 1)) }, 
    (a,b) => b.foldLeft(a){case (acc, (k,v))=> acc updated (k, acc.getOrElse(k,0) + v) }) 
} 

val freq = parFrequency("harry hacker") 
//> Map(e -> 1, y -> 1, a -> 2, -> 1, c -> 1, h -> 2, r -> 3, k -> 1) 

的foldLeft迭代的地圖一，更新其它地圖的鍵/值發現。

Answer 3

你麻煩第一種情況下，你自己檢測是++運營商剛剛串聯，下降相同的密鑰的第二occurence。

現在在第二種情況下，你有(_, c) => ImmutableHashMap(c -> 1)，它只是刪除我在seqop階段發現的所有字符。

我的建議是延長Map類型有特殊compination操作，在HashMap像merged工作，並保持在seqop階段從第一例的集：

implicit class MapUnionOps[K, V](m1: Map[K, V]) { 
    def unionWith[V1 >: V](m2: Map[K, V1])(f: (V1, V1) => V1): Map[K, V1] = { 
    val kv1 = m1.filterKeys(!m2.contains(_)) 
    val kv2 = m2.filterKeys(!m1.contains(_)) 
    val common = (m1.keySet & m2.keySet).toSeq map (k => (k, f(m1(k), m2(k)))) 
    (common ++ kv1 ++ kv2).toMap 
    } 
} 

def parFrequency(str: String) = { 
    str.par.aggregate(Map[Char, Int]())((m, c) => {m + (c -> (m.getOrElse(c, 0) + 1))}, (m1, m2) => (m1 unionWith m2)(_ + _)) 
} 

或者你可以使用從保羅的回答fold解決方案，但爲更好的表現爲每個合併選擇較小的地圖遍歷：

implicit class MapUnionOps[K, V](m1: Map[K, V]) { 
    def unionWith(m2: Map[K, V])(f: (V, V) => V): Map[K, V] = 
    if (m2.size > m1.size) m2.unionWith(m1)(f) 
    else m2.foldLeft(m1) { 
     case (acc, (k, v)) => acc + (k -> acc.get(k).fold(v)(f(v, _))) 
    } 
}