Geek asks and answers

Java - shuffling a certain number of elements in an array

My problem is this: I need to shuffle the array and then only get the first N elements.

I am currently shuffling the entire array, which has 50+ elements, but this gives me performance problems, as the shuffling procedure is called 1e + 9 times.

I am currently implementing a Fisher-Yates shuffle algorithm:

public static void shuffle(int[] array) {
    Random gen = new Random();
    for (int i = array.length - 1; i > 0; i--) {
        int index = gen.nextInt(i + 1);
        int a = array[index];
        array[index] = array[i];
        array[i] = a;
    }
}

Then I select only the first N elements.

I also tried using reservoir samples , but that only saved me for 1 second. This is not enough, since my program runs for 30 seconds. Also, I could have implemented it incorrectly because I am not getting the same results compared to the Fisher-Yates algorithm. This is my implementation:

public static int[] shuffle(int[] array, int N) {
    int[] ret = new int[N];
    for (int i = 0; i < N; i++) {
        ret[i] = array[i];
    }
    Random gen = new Random();
    int j;
    for (int i = N; i < array.length; i++) {
        j = gen.nextInt(i+1);
        if (j <= N - 1)
            ret[j] = array[i];
    }
    return ret;
}

, , N , N, 50+. , - , - .

-1: "int []" .

-2: N 10.

+3
3

N :

  • r.
  • r .
  • r 1.
  • N .

:

public static int[] shuffle(int[] array, int N) {
    int[] result = new int[N];
    int length = array.length;

    Random gen = new Random();

    for (int i = 0; i < N; i++) {
        int r = gen.nextInt(length);

        result[i] = array[r];

        array[r] = array[length-1];
        length--;
    }

    return result;
}

FY, N , .

:

  • N . , 0 1 .
  • - . N=10 1000000, 1000000, 10.
+3

FY, N , N . , , , N . , N/50. .

, . , 19 . .

+1

, Collection.shuffle :

public static int[] shuffle(int[] array, int N) { 
    List<Integer> list = new ArrayList<Integer>();
    for (int r : array) {
       list.add(r);
    }
    Collections.shuffle(list);
    Integer[] ret = list.toArray(); // Integer is int, except autoboxed 
    return ret;
}
0

More articles:


All Articles