Выбор случайных чисел эффективно

Question

Выбор случайных чисел эффективно

У меня есть метод, который использует случайные выборки для приближения вычисления. Этот метод называют миллионами времен, таким образом, его очень важное, что процесс выбора случайных чисел эффективен.

Я не уверен как быстро javas Random().nextInt действительно, но моя программа, кажется, не извлекает выгоду так же, как я хотел бы ее также.

При выборе случайных чисел я делаю следующее (в полу псевдокоде):

// Repeat this 300000 times
Set set = new Set();
while(set.length != 5)
    set.add(randomNumber(MIN,MAX));

Теперь, это, очевидно, имеет плохое время выполнения худшего случая, поскольку случайная функция в теории может добавить дублированные числа для вечности, таким образом остающейся в цикле с условием продолжения навсегда. Однако числа выбраны из {0.. 45}, таким образом, дублированное значение по большей части маловероятно.

Когда я использую вышеупомянутый метод, только на 40% быстрее, чем мой другой метод, который не приближается, но приводит к корректному результату. Это, выполнил ~ 1 миллион раз, таким образом, я ожидал, что этот новый метод будет по крайней мере на 50% быстрее.

У Вас есть какие-либо предложения для более быстрого метода? Или возможно Вы знаете более эффективного способа поколения ряд случайных чисел.

Для разъяснения вот, эти два метода:

// Run through all combinations (1 million). This takes 5 seconds
 for(int c1 = 0; c1 < deck.length; c1++){
    for(int c2 = c1+1; c2 < deck.length; c2++){
     for(int c3 = c2+1; c3 < deck.length; c3++){
        for(int c4 = c3+1; c4 < deck.length; c4++){
         for(int c5 = c4+1; c5 < deck.length; c5++){
             enumeration(hands, cards, deck, c1, c2, c3, c4, c5);
         }
            } 
      }     
   }
   }

// Approximate (300000 combinations). This takes 3 seconds
Random rand = new Random();
HashSet<Integer> set = new HashSet<Integer>();
int[] numbers = new int[5];
while(enumerations < 300000){
set.clear();
while(set.size() != 5){
    set.add(rand.nextInt(deck.length));
}
Iterator<Integer> i = set.iterator();
int n = 0;
while(i.hasNext()){
    numbers[n] = i.next();
    n++;
}

После некоторого тестирования и профилирования, я нашел, что этот метод был самым эффективным:

Random rand = new Random();
int[] numbers = new int[5];
ArrayList<Integer> list = new ArrayList<Integer>();
while(enumerations < 300000){
 while(list.size() != 5) {
     int i = rand.nextInt(deck.length);
        if(!list.contains(i)) list.add(i);
 }
 int index = 0;
 for(int i : list){ numbers[index] = i; index++; }
 enumeration(hands, cards, deck,numbers);
}

12

java random montecarlo approximation

задан 5 revs, 2 users 100% 26 March 2010 в 21:45

8 ответов

Обычный метод - начать со списка всех возможных входов и произвольно выбирать из него, удаляя все по ходу. Таким образом, нет риска выбрать дубликат и выполнить цикл в течение неизвестного времени. Конечно, этот метод работает только с дискретными данными, но, к счастью, с целыми числами. Также помните, что выбор и удаление вашего списка (или другой структуры данных) должны быть O (1), если это возможно, поскольку вы фокусируетесь на скорости.

2