对于我正在处理的项目,我需要跟踪多达数千个对象。我选择的集合需要支持插入,选择和删除随机元素。我的算法多次执行这些操作中的每一个,所以我想要一个可以在一段时间内完成所有这些操作的集合。用于在Scala中有效选择随机元素的适当集合类型
有没有这样的集合?如果不是,那么现有收藏有哪些折衷?我正在使用Scala 2.9.1。 “随机”,我的意思是数学上/概率上随机的,即,我想用随机或其他适当的生成器从集合中随机选择元素。
对于我正在处理的项目,我需要跟踪多达数千个对象。我选择的集合需要支持插入,选择和删除随机元素。我的算法多次执行这些操作中的每一个,所以我想要一个可以在一段时间内完成所有这些操作的集合。用于在Scala中有效选择随机元素的适当集合类型
有没有这样的集合?如果不是,那么现有收藏有哪些折衷?我正在使用Scala 2.9.1。 “随机”,我的意思是数学上/概率上随机的,即,我想用随机或其他适当的生成器从集合中随机选择元素。
定义“随机”。如果你的意思是索引,那么就没有这样的集合。如果你放弃了“随机元素”的要求,你可以在一定的时间内插入/删除 - 也就是说,你有非常量的元素将被删除或将作为插入点。或者你可以不断的查询而不需要不断的插入/删除。
最符合要求的集合是Vector
,它为这些操作提供O(log n)
。
另一方面,如果您有要查找或删除的元素,请选择HashMap
。这不是恰恰恒定的时间,但它是一个公平的近似值。只要确保你有一个很好的散列函数。
作为一个起点,请看The Scala 2.8 Collections API,尤其是Performance Characteristics
。
你的收藏应该能够包含重复?相关元素的顺序是什么? –
@PeterSchmitz,我不会尝试存储重复项,元素的顺序并不重要,因为我只想随机访问它们。 – astay13
几千件物品并不多,即使是10年前的硬件也没有。 “多次”也是一个模糊的术语。可能每个收藏都适合你。 –