我正在尝试从大小为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。
ArrayList由数组支持，因此修改需要将项目放在一边，在某些情况下甚至可以创建一个全新的数组。
一些可能的方案：
请考虑使用LinkedList或skip-list实现。请注意，在这里，删除一个项目仍然需要O（N）（或跳过列表中的O（logN）），因为它必须找到它。但是，您可以根据已删除的项目数来移动项目。
您可以随意将输入中的项目添加到新的ArrayList中，直到获得所需的项目数。您必须知道您添加了哪些项目，因此以线性方式遍历，并让随机选择器根据您移动的项目有多少步骤。
最简单的解决方案：随机播放整个输入数组，然后选择前M个项目。
这是解决方案＃3的可能代码：
public static List<String> pickNRandom(List<String> lst, int m) {
Collections.shuffle(lst);
return lst.subList(0, n);
}
这里的缺点是它破坏了物品的顺序。您可以通过创建列表的副本作为输入来克服此问题，但这将占用更多内存（暂时）...
每次从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第 - 个元素。
例如，您可以构造一个 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。