用於在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中有效選擇隨機元素的適當集合類型

回答

相關問題