scala - 如何有效地从 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

警告 此答案仅供实验使用。对于实际项目，您可能应该使用自己的集合类型。

所以我在 HashSet source 中做了一些研究而且我认为几乎没有机会以某种方式提取最有值(value)的内部结构 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) 运行得更好。当前版本的复杂度应为 O(ln(n))，与 immutable.HashSet 的任何操作一样。

另一个警告 - HashSet 的私有(private)结构不是 scala 标准库 API 的一部分，因此它可能会更改任何版本导致此代码错误(尽管自 2.8 以来它没有更改)