如何高效地從Scala不可變HashSet中選擇一個隨機元素

Question

我有一個scala.collection.immutable.HashSet，我想從中隨機選擇一個元素。

我可以像這樣的擴展方法解決這個問題：

implicit class HashSetExtensions[T](h: HashSet[T]) { 
    def nextRandomElement(): Option[T] = { 
    val list = h.toList 
    list match { 
     case null | Nil => None 
     case _ => Some (list (Random.nextInt (list.length))) 
    } 
    } 
} 

...但轉換到一個列表將是緩慢的。什麼是最有效的解決方案？

Answer 1

由於size是O(1)上HashSet，並iterator儘可能懶，我覺得這個解決辦法是比較有效：

implicit class RichHashSet[T](val h: HashSet[T]) extends AnyVal { 
    def nextRandom: Option[T] = Some(h.size) collect { 
     case size if size > 0 => h.iterator.drop(Random.nextInt(size)).next 
    } 
} 

如果你正在試圖讓你可以使用效率的每一盎司這裏使用的是match而不是更簡潔的Some/collect成語。

你可以看看mutable HashSet執行看到size方法。在那裏定義的iterator方法基本上只在FlatHashTable上調用iterator。如果您正在使用這些方法，則這些方法的相同基本效率適用於immutable HashSet。作爲比較，您可以看到HashSet上的toList實現在TraversableOnce上的類型層次結構的所有方向上，並使用了可能效率較低的更原始元素，並且（當然）必須迭代整個集合才能生成List。如果您是將整個集合轉換成Traversable集合，你應該使用Array或Vector具有恆定的時間查找。

你可能也注意到，沒有什麼特別的上述方法有關HashSet，你可以豐富Set[T]相反，如果你願意的選擇（雖然就沒有保證，這將是對其他Set實現高效的課程）。

作爲一個側面說明，對於擴展方法實現豐富的類時，你應該總是考慮通過擴展AnyVal暗示它們，用戶定義的值類。您可以閱讀有關docs和this answer中的一些優點和限制。

Answer 2

警告這個答案是唯一的實驗使用。對於真正的項目你可能應該使用自己的集合類型。

所以我在HashSet source做了一些研究，我認爲很少有機會在不違反封裝的情況下提取最有價值的class HashTrieSet的內部結構。

我沒有想出這個代碼，這是延長Ben Reich's solution：

package scala.collection 

import scala.collection.immutable.HashSet 
import scala.util.Random 

package object random { 
    implicit class HashSetRandom[T](set: HashSet[T]) { 
    def randomElem: Option[T] = set match { 
     case trie: HashSet.HashTrieSet[T] => { 
     trie.elems(Random.nextInt(trie.elems.length)).randomElem 
     } 
     case _ => Some(set.size) collect { 
     case size if size > 0 => set.iterator.drop(Random.nextInt(size)).next 
     } 
    } 
    } 
} 

文件應在src/scala/collection/random文件夾中的某處創建

注意scala.collection包 - 這件事情使得HashTrieSet的elems部分可見。這只是我能想到的解決方案，它可以比O(n)更好地運行。當前版本的複雜程度應該爲immutable.HashSet的任何操作。

另一個警告 - 的HashSet私人結構不Scala的標準庫API的一部分，所以它可以改變任何版本進行這項代碼錯誤（儘管它並沒有因爲2.8改變）