从java元素列表中选择java元素（无需更改）

Question

正如在标题中，我想使用Knuth Fisher-Yates shuffle算法从列表中选择N个随机元素，但不使用列表。整理并更改列表。以下是我目前的代码：

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;
}

它使用列表。toArray（）创建新数组以避免修改原始列表。然而，我现在的问题是，我的列表可能非常大，可能有100万个元素。然后列出清单。toArray（）太慢了。我的n可能在100万到100万之间。当n很小时（比如说2），函数非常有效，因为它仍然需要执行列表。toArray（）获取包含100万个元素的列表

有人能帮助改进上述代码，使其在处理大型列表时更高效吗。谢谢

在这里，我假设Knuth Fisher-Yates shuffle是从列表中选择n个随机元素的最佳算法。我说得对吗？如果有比Knuth Fisher-Yates shuffle更好的算法来完成这项工作，在速度和结果质量方面（保证真正的随机性），我将非常高兴

更新：

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

当从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储层取样方法更快

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

Answer 1

总结长王的最新消息如果你想要超过250000件物品，请使用amit的答案。否则使用^{}，如图所示

NOTE: The result is always in the original order as well

public static <T> List<T> getNRandomElements(int n, List<T> list) {
    List<T> subList = new ArrayList<>(n);
    int[] ids = generateUniformBitmap(n, list.size());
    for (int id : ids) {
        subList.add(list.get(id));
    }
    return subList;
}

// https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java
private static int[] generateUniformBitmap(int num, int max) {
    if (num > max) {
        DebugUtil.e("Can't generate n ints");
    }
    int[] ans = new int[num];
    if (num == max) {
        for (int k = 0; k < num; ++k) {
            ans[k] = k;
        }
        return ans;
    }
    BitSet bs = new BitSet(max);
    int cardinality = 0;
    Random random = new Random();
    while (cardinality < num) {
        int v = random.nextInt(max);
        if (!bs.get(v)) {
            bs.set(v);
            cardinality += 1;
        }
    }
    int pos = 0;
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
        ans[pos] = i;
        pos += 1;
    }
    return ans;
}

如果你想让它们随机化，我使用：

public static <T> List<T> getNRandomShuffledElements(int n, List<T> list) {
    List<T> randomElements = getNRandomElements(n, list);
    Collections.shuffle(randomElements);
    return randomElements;
}

Answer 2

你可能正在寻找类似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;

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