在java中选择N个随机不同的int的高效方法？

Question

我目前正在寻找最好的方法,因此在n个int中选择x个唯一的int.它会像Random.nextInt(range)多次一样,但它永远不应该选择两次相同的int.如果它发生x > n那么结果将只包含n个int

我试图自己做这个,我目前基于Fisher/Yates shuffle这样做:

private static final Random R   = new Random();

public static int[] distinctRandoms(int nb, int max) {
    int[] all = new int[max];
    for (int i = 0; i < all.length; i++) {
        all[i] = i;
    }
    if (max <= nb) {
        return all;
    }
    int index;
    int[] result = new int[nb];

    for (int j = 0, k = all.length - 1; k > 0 && j < nb; k--, j++) {
        index = R.nextInt(k + 1);
        result[j] = all[index]; // save element
        all[index] = all[k]; // overwrite chosen with last element
    }
    return result;
}

它的工作和性能似乎很好,但我不禁想到仍然必须有一些更高性能的方式这样做,我正在重新发明轮子.我考虑过做不同的事情nb > (max / 2)(删除元素而不是选择元素)但是因为你不能在java中截断数组,你仍然最终会复制你需要的所有元素.如果这种方法花费很多nb = max-1

有没有内置的方法可以在java中有效地随机选择不同的int？

编辑1:

高性能的意思是节省时间.我希望它快.我将主要使用小套的randoms.

编辑2:

我尝试过像这样使用shuffle但是由于所有额外的对象创建,它在时间上要贵得多.

public static Integer[] distinctRandoms2(int nb, int max) {
    ArrayList<Integer> all = new ArrayList<Integer>(max);
    for (int i = 0; i < max; i++) {
        all.add(i);
    }
    if (max <= nb) {
        return all.toArray(new Integer[max]);
    }
    Collections.shuffle(all);
    return all.subList(0, nb).toArray(new Integer[nb]);
}

Answer 1

这取决于您所说的Performant和 的含义Random。

如果您确实需要成本O(1)或类似的东西，那么您可以使用线性反馈移位寄存器或LFSR。它使用对前一个数字的简单操作来生成类似随机的数字序列（即统计上随机但理论上可预测）XOR，因此可能是最快的机制。

如果您想要任何 n 位数字，则此方法最合适。通过丢弃超出所需范围的数字来限制数字范围可能会降低性能。