如标题所述，我想使用Knuth-Fisher-Yates随机置乱算法从列表中选择N个随机元素，但不使用List.toArray并且不改变列表。以下是我的当前代码：
public List<E> getNElements(List<E> list, Integer n) {
List<E> rtn = null;
if (list != null && n != null && n > 0) {
int lSize = list.size();
if (lSize > n) {
rtn = new ArrayList<E>(n);
E[] es = (E[]) list.toArray();
//Knuth-Fisher-Yates shuffle algorithm
for (int i = es.length - 1; i > es.length - n - 1; i--) {
int iRand = rand.nextInt(i + 1);
E eRand = es[iRand];
es[iRand] = es[i];
//This is not necessary here as we do not really need the final shuffle result.
//es[i] = eRand;
rtn.add(eRand);
}
} else if (lSize == n) {
rtn = new ArrayList<E>(n);
rtn.addAll(list);
} else {
log("list.size < nSub! ", lSize, n);
}
}
return rtn;
}
为了避免修改原始列表，它使用list.toArray()创建一个新数组。然而，我的问题现在是，我的列表可能非常大，可以有100万个元素。那么list.toArray()太慢了。当n从1到100万时，函数的效率很低，特别是当n很小（比如2）时，它仍然需要对100万个元素的列表执行list.toArray()。
是否有人能帮助改进上述代码，使其在处理大型列表时更有效？谢谢。
在这里，我假设Knuth-Fisher-Yates随机置乱算法是从列表中选择n个随机元素的最佳算法。我是正确的吗？如果在速度和结果质量（保证真正随机）方面有比Knuth-Fisher-Yates随机置乱算法更好的其他算法，则我将非常高兴。
更新：
以下是我一些测试结果：
当从1000000个元素中选择n时。
当n < 1000000/4时，通过使用Daniel Lemire的位图函数来选择n个随机id，然后使用这些id获取元素是最快的方法：
public List<E> getNElementsBitSet(List<E> list, int n) {
List<E> rtn = new ArrayList<E>(n);
int[] ids = genNBitSet(n, 0, list.size());
for (int i = 0; i < ids.length; i++) {
rtn.add(list.get(ids[i]));
}
return rtn;
}
genNBitSet使用了来自https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java的generateUniformBitmap代码。
当n大于1000000/4时，蓄水池抽样方法更快。
因此，我构建了一个结合这两种方法的函数。