Подтвердить что ты не робот

Создание m различных случайных чисел в диапазоне [0..n-1]

У меня есть два метода генерации т различных случайных чисел в диапазоне [0..n-1]

Метод 1:

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

Метод 2:

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

Первый метод более эффективен, когда n много больше m, тогда как второй более эффективен в противном случае. Но "намного больше" не является строгим понятием, не так ли?:)

Вопрос: Какую формулу n и m следует использовать, чтобы определить, будет ли метод method1 или method2 более эффективным? (в терминах математического ожидания времени выполнения)

4b9b3361

ОТВЕТЫ

Ответ 1

Чистая математика:
Позвольте рассчитать количество вызовов функций rand() в обоих случаях и сравнить результаты:

Случай 1: см. математическое ожидание вызовов на шаге i = k, когда у вас уже выбрано k чисел. Вероятность получить число с одним вызовом rand() равна p = (n-k)/n. Нам нужно знать математическое ожидание количества таких вызовов, которое приводит к получению числа, которого у нас пока нет.

Вероятность получить его с помощью вызова 1 p. Использование 2 вызовов - q * p, где q = 1 - p. В общем случае вероятность получить его точно после вызовов n составляет (q^(n-1))*p. Таким образом, математическое ожидание - это
Sum[ n * q^(n-1) * p ], n = 1 --> INF. Эта сумма равна 1/p (доказана волфрами альфа).

Итак, на шаге i = k вы выполните вызовы 1/p = n/(n-k) функции rand().

Теперь давайте суммируем в целом:

Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T - количество вызовов rand в методе 1.
Здесь T = Sum[ 1/(n - k) ], k = 0 --> m - 1

Случай 2:

Здесь rand() вызывается внутри random_shuffle n - 1 раз (в большинстве реализаций).

Теперь, чтобы выбрать метод, мы должны сравнить эти два значения: n * T ? n - 1.
Итак, чтобы выбрать подходящий метод, вычислите T, как описано выше. Если T < (n - 1)/n лучше использовать первый метод. В противном случае используйте второй метод.

Ответ 3

Лично я бы использовал метод 1, а затем, если M > N/2, выберите значения N-M, а затем инвертируйте массив (верните числа, которые не были выбраны). Например, если N равно 1000, и вы хотите из них 950, выбрали 50 значений, используя метод 1, а затем верните остальные 950.

Изменить: хотя, если для вашей цели будет постоянная производительность, я бы использовал модифицированный метод 2, который не выполняет полный перетасовки, но только перетасовывает первые M элементов вашего массива длины N.

int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;

for (int i =0; i < m; ++i) {
   int j = rand(n-i); // Pick random number from 0 <= r < n-i.  Pick favorite method
   // j == 0 means don't swap, otherwise swap with the element j away
   if (j != 0) { 
      std::swap(arr[i], arr[i+j]);
   }
}
result = first m elements in arr;

Ответ 4

Вот алгоритм, который будет работать в O (n) памяти и O (n) времени (где n - количество возвращенных результатов, а не размер набора, который вы выбираете) для любого набора результатов. Это в Python для удобства, потому что он использует хэш-таблицу:

def random_elements(num_elements, set_size):
    state = {}
    for i in range(num_elements):
        # Swap state[i] with a random element
        swap_with = random.randint(i, set_size - 1)
        state[i], state[swap_with] = state.get(swap_with, swap_with), state.get(i, i)
    return [state[i] for i in range(num_elements) # effectively state[:num_elements] if it were a list/array.

Это всего лишь частичная перетасовка "рыбалка-ят", причем массив перемещается в виде разреженной хэш-таблицы - любой элемент, который не присутствует, равен его индексу. Мы перетасовываем первые индексы num_elements и возвращаем эти значения. В случае, когда set_size = 1, это эквивалентно выбору случайного числа в диапазоне, а в случае num_elements = set_size это эквивалентно стандартным перетасовкам рыба-яса.

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

Ответ 5

Как насчет третьего метода?

int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   r = rand()%(n-i);
   r += (number of items in result <= r)
   result[i] = r;   
}

Изменить он должен быть < =. и на самом деле это была бы дополнительная логика, чтобы избежать столкновений.

Это лучше, например, используя Современный метод от Fisher-Yates

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;

for(i = 0; i < m; ++i)
    swap(arr, n-i, rand()%(n-i) );

result = last m elements in arr;

Ответ 6

Говоря о математическом ожидании, он довольно бесполезен, но я все равно отправлю его: D

Перемешивание простое O (m).

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

p=1          E[X1]=1            = 1           = 1
p=1-1/n      E[x2]=1/(1-1/n)    = 1 + 1/(n-1) = 1 + 1/(n-1) 
p=1-2/n      E[x3]=1/(1-1/n)    = 1 + 2/(n-2) = 1 + 1/(n-2) + 1/(n-2)
p=1-3/n      E[X4]=1/(1-2/n)    = 1 + 3/(n-3) = 1 + 1/(n-3) + 1/(n-3) + 1(n-3)
....
p=1-(m-1)/n) E[Xm]=1/(1-(m-1)/n))

Обратите внимание, что сумму можно разбить на треугольник, см. правую часть.

Воспользуемся формулой для гармонического ряда: H_n = Sum k = 0- > n (1/k) = approx ln (k)

Sum(E[Xk]) = m + ln(n-1)-ln(n-m-1) + ln(n-2)-ln(n-m-1) + ... = m + ln(n-1) + ln(n-2) + ... - (m-1)*ln(n-m-1) ..

И есть какая-то forumla для суммы гармонических рядов, если вы все еще заинтересованы, я буду искать ее...

Обновление: на самом деле это довольно красивая формула (благодаря блестящей книге Бетонной математики)

Sum(H_k) k=0->n = n*H_n - n

Итак, ожидаемое количество шагов:

Sum(E[Xk]) = m + (n-1)*ln(n-1) - (n-1) - (n-m-1)*ln(n-m-1) - (n-m-1)) - (m-1)*ln(n-m-1).

Примечание. Я не проверил его.

Ответ 7

Это немного длинный снимок, но он может работать, в зависимости от вашей системы.

  • Начните с разумного соотношения, например 0.5.
  • Когда приходит запрос, обработайте его любым способом, который вы получаете от текущего значения порогового коэффициента.
  • Запишите время, которое требуется, и когда у вас есть "пустое" время, выполните ту же задачу другим методом.
  • Если альтернативное решение намного быстрее оригинального, настройте порог вверх или вниз.

Очевидным недостатком этого метода является то, что в сильно изменяющихся системах загрузки ваш "автономный" тест не будет слишком надежным.

Ответ 8

Был предложен Фишер-Йейтс шаффл. Не знаю, генерирует ли следующий код одинаково распределенные целые числа, но он хотя бы компактен и однопроходен:

std::random_device rd;
std::mt19937 g(rd());
for (size_type i = 1; i < std::size(v); ++i) {
    v[i] = std::exchange(v[g() % i], i);
}

Ответ 9

Как насчет использования набора вместо массива, я думаю, что это гораздо проще, чем массив

set<int> Numbers;
while (Numbers.size() < m) {
   Numbers.insert(rand() % n);
}

Ответ 10

Возможно, было бы проще запустить его в режиме отладки (и сохранить один метод в качестве примечания) пару раз, чтобы получить среднее значение, а затем использовать другой метод, чтобы получить среднее значение от этого

Ответ 11

Я не советую этот метод, но он работает

#include <iostream>
#include <random>
#include <ctime>

using namespace std;

int randArray[26];
int index = 0;

bool unique(int rand) {

    for (int i = 0; i < index; i++)
        if (rand == randArray[i])
            return false;
    index++;
    return true;
}


int main()
{
    srand(time(NULL));

    for (int i = 1; i < 26; i++)
        randArray[i] = -1;

    for (int i = 0; i < 26; i++) {

        randArray[i] = rand() % 26;

        while (!unique(randArray[i])) {
            randArray[i] = rand() % 26;
        }
    }

    for (int i = 0; i < 26; i++) {
        cout << randArray[i] << " ";
    }

    cout << "\n" << index << endl;


    return 0;
}