-1

I have used this code in order to randomise 1000000 numbers without duplication's. Here's what I have so far.

enter code here  protected void randomise() {
    int[] copy = new int[getArray().length];
    // used to indicate if elements have been used
    boolean[] used = new boolean[getArray().length];
    Arrays.fill(used,false);
    for (int index = 0; index < getArray().length; index++) {
        int randomIndex;
        do {
            randomIndex = getRandomIndex();
        } while (used[randomIndex]);
        copy[index] = getArray()[randomIndex];
        used[randomIndex] = true;
    }
    for (int index = 0; index < getArray().length; index++) {
        getArray()[index] = copy[index];
        //Checks if elements in array have already been used
    }
}

public static void main(String[] args) {
    RandomListing count = new SimpleRandomListing(1000000);
    //Will choose 1000000 random numbers
    System.out.println(Arrays.toString(count.getArray()));
}

This method is too slow can you let me know how this can be done more efficiently. I appreciate all replies. Regards,

E-Riz
  • 31,431
  • 9
  • 97
  • 134
James Faulkner
  • 91
  • 9
  • What kind of random numbers do you want? Just the numbers between 0 and 1000000? – Louis Wasserman Oct 04 '16 at 17:30
  • yes without duplication's and more efficient – James Faulkner Oct 04 '16 at 17:33
  • 2
    just create an array of 1M elements, and "shuffle" the elements around a bit as if you were shuffling cards (i.e. pick two random numbers, and shift their values...repeat X number of times) – jamey graham Oct 04 '16 at 17:38
  • in fairness, the linked "already asked" question isn't flagged as answered and doesn't address the "more efficiently" part of this question – jamey graham Oct 04 '16 at 17:44
  • @jameygraham it specifies an O(n) algorithm, which is the most efficient algorithm possible. – Louis Wasserman Oct 04 '16 at 17:50
  • sortof proving my point, the O(n) answer is absolutely not the most efficient way to solve this problem. That said, i did miss that Collections.shuffle() is one of answers in the linked question and is in fact the correct answer (although Collections.shuffle() will "shuffle" n times whereas you can "randomize" 1M elements simply by swapping a single element...it's just not a great distribution of randomness) – jamey graham Oct 04 '16 at 18:07

2 Answers2

0

A more efficient way to do this is by starting with a pool of numbers (e.g. an List of all numbers between 0 and 1000000) and then remove numbers that you've already used. That way, every time you try to get a new number, that number is guaranteed to never having been used before rather than spending time trying to find a "good" unused number.

Mike Laren
  • 8,028
  • 17
  • 51
  • 70
0

It looks like your using a linear search to find matches. Try using a binary search it's more efficient. The array you are searching must be sorted to implement a binary search.

Goot
  • 1