删除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列表的大小在哪里.对于7M元素列表,这将是非常缓慢的.

相反,如果您知道要提前删除哪些元素,则可以在一次传递中将所有元素向下移动:

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; 它还保留了原始订单.

如果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.

Answer 2

ArrayList由数组支持,因此修改需要将项目放在一边,在某些情况下甚至可以创建一个全新的数组.

一些可能的解决方

1. 请考虑使用LinkedList或skip-list实现.请注意,在这里,删除一个项目仍然需要O(N)(或跳过列表中的O(logN)),因为它必须找到它.但是,您可以根据已删除的项目数来移动项目.

2. 您可以随意将输入中的项目放入新的ArrayList中,直到获得所需的项目数.您必须知道您添加了哪些项目,因此以线性方式进行遍历,并根据您移动的项目,使随机选择器有机会执行多少步骤.

3. 最简单的解决方案:随机播放整个输入数组,然后选择前M个项目.

这是解决方案#3的可能代码:

public static List<String> pickNRandom(List<String> lst, int m) {
    Collections.shuffle(lst);
    return lst.subList(0, n);
}

这里的缺点是它破坏了物品的顺序.您可以通过创建列表的副本作为输入来克服此问题,但这会占用更多内存(暂时)...