我正在尝试从一个大小为7,140,000的ArrayList中删除140,000个对象。我认为这应该只需要几秒钟（如果需要的话），但实际上Java每删除1000个对象需要花费好几秒钟。以下是我的代码：
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花费这么长时间是因为我从7百万个对象开始吗？ 我以前从ArrayList中删除时从未注意到这个效率问题。 如果有帮助的话，我使用DrJava Beta IDE。
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 个元素。
例如，您可以构造一个只设置了除 P 元素之外所有元素的 BitSet：
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);
}
如果您只是从一个700万元素列表中删除零元素，则仍然需要将所有6999999个元素向右移动；但是任何其他的删除都不需要再进行额外的移动。这个算法的时间复杂度为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 的值；它还保持了原始顺序。
如果你想从一个有 N 个项目的列表中随机选出 K 个项目而不重复，有 choose(N, K) = N! / (K! * (N-K)!) 种方法可以实现。如果你想要以相等的概率选择所有元素，则应该选择这些 c(n,k) 种不同的配置之一。
当还剩下 k 个项目可供选择时，你可以：
n-1 个项目中选择 k-1 个项目；或者n-1 个项目中选择 k 个项目。为了确保整体上选择这 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
public static List<String> pickNRandom(List<String> lst, int m) {
Collections.shuffle(lst);
return lst.subList(0, n);
}
这里的缺点是它破坏了项目的顺序。您可以通过将列表作为输入创建副本来克服此问题，但这将占用更多内存（暂时）...