如标题所述,我想使用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时,蓄水池抽样方法更快。
因此,我构建了一个结合这两种方法的函数。