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

Question

У меня есть два метода генерации m различных случайных чисел в диапазоне [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 следует использовать, чтобы определить, будет ли метод1 или метод2 более эффективным? (с точки зрения математического ожидания времени работы)

Answer 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, то лучше использовать первый метод.В противном случае используйте второй метод.

Answer 2

Проверьте описание в Википедии оригинального алгоритма Фишера-Йейтса .Он рекомендует использовать по существу ваш метод 1 до n / 2, а ваш метод 2 - до остатка.

Answer 3

Вот алгоритм, который будет работать в 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.

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

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

Answer 4

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

Редактировать: Хотя, если ваша цель - стабильная производительность, я бы использовал модифицированный метод 2, который не выполняет полное перемешивание, а только перетасовывает первые М элементов вашего массива длины 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;

Answer 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;   
}

---

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

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

//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;

Answer 6

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

Перемешать просто O (м).

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

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) = приблизительно 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) ..

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

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

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).

Примечание: я не проверял это.

Answer 7

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

1. Начните с некоторого разумного соотношения, например 0,5.
2. Когда приходит запросв, обработайте его любым методом, который вы получите из текущего значения порогового отношения.
3. Запишите время, которое требуется, и когда у вас есть «пустое» время, выполните ту же задачу с другим методом.
4. Если альтернативное решение намного быстрее исходного, отрегулируйте порог вверх или вниз.

Очевидным недостатком этого метода является то, что в системах с высокой переменной нагрузкой ваш «автономный» тест выигралне слишком надежен.

Answer 8

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

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

Answer 9

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

#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;
}

Answer 10

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

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);
}