用于在Scala中有效选择随机元素的适当集合类型

对于我正在处理的项目，我需要跟踪多达数千个对象。我选择的集合需要支持插入，选择和删除随机元素。我的算法多次执行这些操作中的每一个，所以我想要一个可以在一段时间内完成所有这些操作的集合。用于在Scala中有效选择随机元素的适当集合类型

有没有这样的集合？如果不是，那么现有收藏有哪些折衷？我正在使用Scala 2.9.1。 “随机”，我的意思是数学上/概率上随机的，即，我想用随机或其他适当的生成器从集合中随机选择元素。

来源

2011-11-28 astay13

你的收藏应该能够包含重复？相关元素的顺序是什么？ –

@PeterSchmitz，我不会尝试存储重复项，元素的顺序并不重要，因为我只想随机访问它们。 – astay13

几千件物品并不多，即使是10年前的硬件也没有。 “多次”也是一个模糊的术语。可能每个收藏都适合你。 –

定义“随机”。如果你的意思是索引，那么就没有这样的集合。如果你放弃了“随机元素”的要求，你可以在一定的时间内插入/删除 - 也就是说，你有非常量的元素将被删除或将作为插入点。或者你可以不断的查询而不需要不断的插入/删除。

最符合要求的集合是Vector，它为这些操作提供O(log n)。

另一方面，如果您有要查找或删除的元素，请选择HashMap。这不是恰恰恒定的时间，但它是一个公平的近似值。只要确保你有一个很好的散列函数。

来源

2011-11-28 14:30:40

看我上面的编辑 – astay13

直到最近我还以为因为'Vector'是一个'IndexedSeq'，它就像一个不可变的数组，但实际上它是一棵树。这有助于解释其性能特征。完整的矢量描述在这里：http://www.scala-lang.org/docu/files/collections-api/collections_15.html –

我认为'HashMap'是我所需要的。谢谢！ – astay13

作为一个起点，请看The Scala 2.8 Collections API，尤其是Performance Characteristics。

来源

2011-11-28 09:00:01

用于在Scala中有效选择随机元素的适当集合类型

回答

相关问题