java - 在 Java ArrayList 中删除对象 - 耗时

Question

我正在尝试从大小为 7,140,​​000 的 ArrayList 中删除 140,000 个对象。我预计这会花费几秒钟(如果那样的话)，但 Java 每千个对象花费几秒钟。这是我的代码:

     for (int i = list.size(); i > P; i--)
     {
         int size = list.size();

         int index = (int) (Math.random() * size);

         list.remove(index);
     }

注意:P 是我之前设置为 7,000,000 的常数。

循环的目标是从列表中随机删除对象，直到其大小为 7,000,000。

Java 需要这么长时间是因为我从超过 700 万个对象开始吗？过去我从来没有注意到从 ArrayLists 中删除的效率问题。如果有帮助，我会使用 DrJava Beta IDE。

Answer 1

每次从 ArrayList 中删除一个元素时，它都必须将所有具有更大索引的元素向下打乱一个位置。假设您删除了 7M 元素列表的第一个元素 - 然后您还必须移动 6,999,999 个元素。

如果您在循环中执行此操作，则需要 O(n^2)时间，在哪里n是列表的大小。对于 700 万个元素的列表，这会非常慢。

相反，如果您事先知道要删除哪些元素，则可以一次将所有元素向下移动:

int dst = 0;
for (int src = 0; src < list.size(); ++src) {
  if (!toRemove(src)) {
    list.set(dst++, list.get(src));
  }
}
list.subList(dst, list.size()).clear();

哪里toRemove(src)是一些函数，它表示您是否要删除 src -th 元素。

例如，您可以构造一个 BitSet除了P元素集:

BitSet toRemove = new BitSet(list.size());
for (int i = list.size(); i > P; i--) {
  int rand;
  do {
    rand = Math.random() * list.size();
  } while (toRemove.get(rand));
  toRemove.set(rand, true);
}

如果您只是从 7M 元素列表中删除零元素，您仍然需要将所有 6,999,999 个元素向右移动；但任何其他删除都不需要在顶部进行任何更多的转换。这个算法是O(n) ，其中 n 是列表的大小。

---

编辑:您可以选择 P列表中的元素(其中 P <= list.size() )如下所示:

int dst = 0;
Random rand = new Random();
for (int src = 0; dst < P; ++src) {
  if (rand.nextInt(list.size() - src) < (P-dst)) {
    list.set(dst++, list.get(src));
  }
}
list.subList(dst, list.size()).clear();

此策略将以相等的概率 (*) 从列表中选择元素，并且适用于 P 的任何值。 ;它还保留了原始顺序。

---

如果要 sample K带有 N 的列表中的项目没有两次绘制相同元素的项目，有choose(N, K) = N! / (K! * (N-K)!)方法来做到这一点。如果你想以相同的概率从列表中选择所有元素，那么你应该选择这些 c(n,k) 中的任何一个。不同的配置。

当有 k待挑选的元素 n项，您将:

• 选择第一项；然后选择 k-1剩余的元素 n-1项目;或
• 不选择第一项；然后选择k剩余的元素 n-1项目。

为了保证等概率的挑到K元素整体，需要根据组合的个数在两个选项中选择一个从n-1中挑选元素:

                                   #(combinations after taking first item) 
P(take first item) = ------------------------------------------------------------------
                     #(combinations after taking) + #(combinations after not taking)

                   = C(n-1,k-1) / (C(n-1, k-1) + C(n-1, k))

                   = ... working omitted ...

                   = k / n

所以，当你有 k需要从 n 拿走的元素, 你应该拿第一项 k/n的时间。

需要指出的两个有趣案例是:

• 何时k == n , k/n = 1 ，所以你总是取元素。直觉上，如果你必须选择 n n 中的项目，你必须把它们全部拿走。
• 何时k == 0 , k/n = 0 ，所以你永远取元素。直觉上，如果您已经选择了所有 K您的元素，您不需要再拿走。

要实现这一点，您可以简单地生成一个均匀分布的随机数 r在 [0..n) 范围内, 如果 r < k 则从列表中“取出”元素.

就上述实现而言，k = P - dst , 和 n = list.size() - src .