4

我经常*发现自己需要一个具有以下属性的数据结构：

  • 可以用 O(n) 中的 n 个对象数组初始化。
  • 可以在 O(1) 中获得一个随机元素，在此操作之后，将拾取的元素从结构中删除。（无需更换）
  • 可以在 O(p) 中撤消 p '不替换的拾取'操作
  • 可以从 O(log(n)) 中的结构中删除特定对象（例如通过 id）
  • 可以在 O(n) 中获取当前结构中的对象数组。

其他操作（例如插入）的复杂性（甚至可能性）并不重要。除了复杂性之外，它对于少量的 n 也应该是有效的。

谁能给我实施这种结构的指导方针？我目前实现了一个具有上述所有属性的结构，除了元素的选取需要 O(d) 和 d 过去选取的数量（因为我明确检查它是否“尚未选取”）。我可以找出允许在 O(1) 中选择的结构，但这些结构至少在其他操作之一上具有更高的复杂性。

顺便说一句：请注意，上面的 O(1) 意味着复杂性与#earlier 选择的元素无关，也与总的#elements 无关。

*在蒙特卡罗算法中（从 n 个元素的“集合”中迭代选择 p 个随机元素）。

4

4 回答 4

2

HashMap 的插入和删除复杂度为 O(1)。您指定了很多操作，但所有这些操作都只是插入、删除和遍历：

可以用 O(n) 中的 n 个对象数组初始化。

n * O(1) 插入。HashMap 没问题

可以在 O(1) 中获得一个随机元素，在此操作之后，将拾取的元素从结构中删除。（无需更换）

这是唯一需要 O(n) 的操作。

可以在 O(p) 中撤消 p '不替换的拾取'操作

这是一个插入操作：O(1)。

可以从 O(log(n)) 中的结构中删除特定对象（例如通过 id）

O(1)。

可以在 O(n) 中获取当前结构中的对象数组。

你可以在 O(n) 中遍历一个 HashMap

编辑：在 O(n) 中选取随机元素的示例：

HashMap map ....
int randomIntFromZeroToYouHashMapSize = ...
Collection collection = map.values();
Object[] values = collection.toArray();
values[randomIntFromZeroToYouHashMapSize];
于 2011-07-01T00:29:52.553 回答
1

一个数组（或ArrayList）被分为“picked”和“unpicked”怎么样？您跟踪边界的位置，并选择，在边界下方生成一个随机索引，然后（因为您不关心顺序）将该索引处的项目与最后一个未选择的项目交换，并减少边界. 要取消选择，您只需增加边界。

更新：忘记了 O(log(n)) 删除。HashMap不过，如果您将一个ID 保存到索引中，这并不难，只是有点内存开销。

如果您在网上四处寻找，您会发现各种IndexedHashSet实现或多或少都遵循这个原则——一个数组或ArrayList加上一个HashMap.

（不过，如果存在，我希望看到更优雅的解决方案。）

更新 2：嗯......或者如果您必须重新复制数组或移动它们，实际删除是否再次变为 O(n)？

于 2011-07-01T01:10:58.900 回答
1

这是我对使用Collections.shuffle()on an的分析ArrayList：

  • ✔ 可以在 O(n) 中使用包含 n 个对象的数组进行初始化。

    是的，尽管除非事先知道 n，否则成本是摊销的。

  • ✔ 可以在 O(1) 中获得一个随机元素，在此操作之后，将拾取的元素从结构中删除，无需替换。

    是的，选择洗牌数组中的最后一个元素；subList()用剩余元素中的一个替换数组。

  • ✔ 可以在 O(p) 中撤消 p '无需替换的拾取'操作。

    是的，通过 将元素附加到此列表的末尾add()。

  • ❍ 可以从 O(log(n)) 中的结构中删除特定对象（例如通过 id）。

    不，它看起来像 O(n)。

  • ✔ 可以在 O(n) 中获得当前结构中的对象数组。

    是的，使用toArray()看起来很合理。

于 2011-07-01T02:18:37.713 回答
1

好的，与0verbose的答案相同，只需简单修复即可获得 O(1) 随机查找。创建一个存储相同 n 个对象的数组。现在，在 HashMap 中，存储对。例如，假设您的对象（为简单起见为字符串）是：

{"abc" , "def", "ghi"}

创建一个

List<String> array = ArrayList<String>("abc","def","ghi")

使用以下值创建一个 HashMap 映射：

for (int i = 0; i < array.size(); i++) 
{
    map.put(array[i],i);
}

O(1) 随机查找很容易通过选择数组中的任何索引来实现。出现的唯一并发症是删除对象时。为此，请执行以下操作：

  1. 在 中查找对象map。获取它的数组索引。让我们称这个索引i( map.get(i)) - O(1)

  2. 将 array[i] 与 array[size of array - 1] 交换（数组中的最后一个元素）。将数组的大小减少 1（因为现在少了一个） - O(1)

  3. i在map(map.put(array[i], i))中的数组位置更新新对象的索引- O(1)

我为 java 和 cpp 符号的混合道歉，希望这会有所帮助

于 2011-07-01T03:47:38.430 回答