Элегантный способ нарисовать n случайных значений в C 11?

ProgramBox

Элегантный способ нарисовать n случайных значений в C 11?

Post author:admin
Запись опубликована:2 апреля, 2023
Post category:Вопросы по программированию

#c #c 11 #random

#c #c 11 #Случайный

Вопрос:

Для моей программы до сих пор мне нужно было время от времени рисовать одно случайное значение в [0 .. k[, и использование функций C 11 <random> работает очень хорошо. Мой текущий код выглядит примерно так

 class Random
{
public:
  Random() : rng( rd() ) { }

  inline int getRandNum( int limit ) { return ( numbers(rng) % limit ); } 

private:
  std::random_device rd;
  std::mt19937 rng;
  std::uniform_int_distribution<int> numbers;
};

Теперь мне нужно нарисовать подряд n разных значений в [0 ..k[. Я искал что-то в <random> разрешении этого, но либо я не могу это найти, либо такой вещи еще не существует. Есть ли умный, более элегантный способ продолжить, чем вызвать мою функцию getRandNum и повторять, пока я не получу n разных значений?

РЕДАКТИРОВАТЬ: чтобы дать представление, в моей программе k — это несколько тысяч, а n — несколько десятков.

1. Насколько велик диапазон 0 .. k и насколько велик ‘n’? Ответы на эти вопросы определят наилучшее решение.

2. С массивом [0..k[ вы можете использовать std::shuffle

3. Если ‘n’ мало по сравнению с размером диапазона 0.. k, то функция draw-and-discard использует меньший объем памяти для решения проблемы за счет вычислительных затрат на удаление и повторное рисование из-за нескольких коллизий. Если n приблизится к размеру диапазона, коллизии станут чрезмерно распространенными, но экономия памяти при извлечении и отбрасывании будет несущественной, поскольку отслеживание розыгрышей будет потреблять почти тот же объем памяти, что и метод генерации и перемешивания. В таком случае оптимальным является генерация и перетасовка.

4. Обратите внимание, что ваш текущий код ошибочен: у вас, вероятно, есть шаг где-то в дистрибутиве. Вы должны создать распределение в getRandNum функции, передаваемой (0, k-1) конструктору, и избегать изменения размера пользовательского диапазона.

5. @FlorianRichoux: в этом случае нет смысла иметь экземпляр std::uniform_int_distribution ; единственный интерес экземпляра (в целом) заключается в обеспечении правильного распределения, если вы делаете это вручную на стороне, вы можете так же легко создавать новый экземпляр каждый раз. И если вы хотите правильно использовать дистрибутив, то вам нужно уточнить его диапазон при создании (вы могли бы уточнить диапазон, 0, k*l*m где k , l и m — это ограничения, которые вы собираетесь использовать позже). Кстати, я хотел бы отметить, что % для интегралов, пожалуй, одна из самых медленных операций процессора.

Ответ №1:

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

По сути, вы хотите перетасовать числа от 0 до k и выбрать первые n чисел, где n <= k. Это можно сделать с помощью алгоритма выборки из резервуара. Смотрите эту ссылку на Википедию для псевдокода.

Обратите внимание, что можно получить n чисел, не сохраняя все k чисел и не перетасовывая их. То есть можно просто использовать O (n) пробел, где n — количество случайных чисел, которые вы хотите получить, вместо O (k). Временная сложность для этого алгоритма равна O (k), если предположить, что генерация случайного числа занимает O (1) времени.

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

2. @FreeNickname. Вы правы, но я считаю, что это то, чего хочет op. Он заявил, что хочет «нарисовать n разных значений в [0, k]», если я не неправильно понял, что вы имели в виду.

3.да, вы правы. Я был смущен <random> . И на самом деле, если это так, то вызов <random> n раз на самом деле не является правильным решением, поскольку он может выдавать одно и то же число более одного раза.

4. Да, я хочу n разных значений, поэтому случайная перестановка [0 .. k[ и затем взятие n первого числа — это решение моей проблемы. Меня беспокоит то, что это действительно время O (k), и мне скорее нравится что-то в O (n). Меня не волнует сложность пространства.

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

Ответ №2:

Если k равно нескольким тысячам, а n — десяткам, то генерация перестановок действительно не лучший выбор. Но вызов getRandNum — это тоже не то, что вы хотите, потому что он может возвращать одно и то же значение несколько раз. Один из вариантов — сгенерировать случайную последовательность сразу, проверяя, чтобы числа не повторялись. Самый простой (и, возможно, даже самый эффективный) способ добиться этого — использовать set .

Вот так:

 #include <vector>
#include <set>
#include <iostream>
#include <random>

class Random
{
public:
  Random() : rng( rd() ) { }

  inline int getRandNum( int limit ) { return ( numbers(rng) % limit ); }
  std::set<int> getRandSequence(int limit, int n);

private:
  std::random_device rd;
  std::mt19937 rng;
  std::uniform_int_distribution<int> numbers;
};

std::set<int> Random::getRandSequence(int limit, int n)
{
    std::set<int> generatedSequence;
    while (generatedSequence.size() < n) //size() for set is O(1) if I'm not mistaken
        generatedSequence.insert(getRandNum(limit));
    return generatedSequence;
}

int main()
{
    Random r;
    auto sequence = r.getRandSequence(1000, 10);
    std::cout << "Seq;uence: "  << std::endl;
    for (int number : sequence)
        std::cout << number << std::endl;
    std::cout << "End" << std::endl;

    return 0;
}

Демонстрация Ideone.

Кстати, random_device создание обходится дорого, а uniform_int_distribution создание, насколько я помню, нет. Так что это может быть еще более эффективным:

 std::set<int> Random::getRandSequence(int limit, int n)
{
    std::uniform_int_distribution<int> uiniformDistribution(0, limit);
    std::set<int> generatedSequence;
    while (generatedSequence.size() < n)
        generatedSequence.insert(uiniformDistribution(rng));
    return generatedSequence;
}

Кроме того, когда вы получаете равномерное распределение, а затем применяете % limit к нему, вы больше не получаете равномерное распределение.

Ответ №3:

 std::random_device rd; // obtain a random number from hardware
std::mt19937 eng(rd()); // seed the generator
std::uniform_int_distribution<> distr(0, 1500); // define the range

for(int a=0; a<limit; a  ){
    cout << distr(eng);  //draw random nubmer