从列表中有效地选择N个随机元素（无需数组和更改列表）

Question

如标题所示，我想使用Knuth-Fisher Yates洗牌算法从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

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正在使用代码生成UniformBitmap从https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java

当n

所以我建立了一个函数来结合这两种方法。

Answer 1

假设可以从m中生成n个成对不相交的随机索引，然后在集合中高效地查找它们。如果不需要元素的顺序是随机的，那么可以使用Robert Floyd提出的算法。

Random r = new Random();
Set<Integer> s = new HashSet<Integer>();
for (int j = m - n; j < m; j++) {
    int t = r.nextInt(j);
    s.add(s.contains(t) ? j : t);
}

如果您确实需要顺序是随机的，那么您可以运行Fisher-Yates，在那里，您不使用数组，而是使用一个仅存储键和值不同的映射的HashMap。假设哈希是恒定时间，这两种算法都是渐近最优的（尽管很明显，如果你想随机采样大多数数组，那么有具有更好常数的数据结构）。

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个元素的均匀随机样本。您也可以考虑使用迭代器避免创建结果列表来保存内存，假设在迭代时列表不变。

通过分析，您可以确定转换点，从原始的集合构建方法切换到迭代方法是有意义的。

Answer 3

您可能正在寻找类似Reservoir采样的东西。

从包含第一个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;

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