从List中有效地选择N个随机元素(不使用toArray并更改列表)

Question

在标题中,我想使用Knuth-Fisher-Yates shuffle算法从List中选择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)时,该函数非常低效,因为它仍然需要list.toArray()获得100万个元素的列表.

有人可以帮助改进上面的代码,使其在处理大型列表时更有效.谢谢.

在这里,我假设Knuth-Fisher-Yates shuffle是从列表中选择n个随机元素的最佳算法.我对吗？如果有其他算法比Knuth-Fisher-Yates shuffle更好地完成结果的速度和质量(保证真正的随机性),我将非常高兴.

更新:

以下是我的一些测试结果:

当从1000000个元素中选择n时.

当n <1000000/4时,通过使用Daniel Lemire的Bitmap函数首先选择n random 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使用代码generateUniformBitmap从https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java

当n> 1000000/4时,储层采样方法更快.

所以我构建了一个结合这两种方法的函数.

Answer 1

你可能正在寻找像Resorvoir Sampling这样的东西.

从包含第一个k元素的初始数组开始,并使用具有降低概率的新元素对其进行修改:

java喜欢伪代码:

E[] r = new E[k]; //not really, cannot create an array of generic type, but just pseudo code
int i = 0;
for (E e : list) {
   //assign first k elements:
   if (i < k) { r[i++] = e; continue; }
   //add current element with decreasing probability:
   j = random(i++) + 1; //a number from 1 to i inclusive
   if (j <= k) r[j] = e;
}
return r;

这需要对数据进行单次传递,每次迭代都需要非常便宜的操作,并且空间消耗与所需的输出大小成线性关系.

Answer 2

如果n与列表的长度相比非常小,则取一组空的int并继续添加随机索引,直到该集合具有正确的大小.

如果n与列表的长度相当,则执行相同操作,但随后返回列表中没有集合中索引的项目.

在中间位置,您可以遍历列表,并根据您看到的项目数量以及已经返回的项目随机选择项目.在伪代码中,如果你想要来自N的k项:

for i = 0 to N-1
    if random(N-i) < k
        add item[i] to the result
        k -= 1
    end
end

这里random(x)返回0(包括)和x(不包括)之间的随机数.

这产生了k个元素的均匀随机样本.您还可以考虑使用迭代器来避免构建结果列表以节省内存,假设列表在迭代时保持不变.

通过分析,您可以确定从朴素的集合构建方法切换到迭代方法的转换点.