Random в Qt

[m_ax]

генератор случайных уникальных чисел (весьма известный пример):

Код

C++ (Qt)
class URandGen
{
public:
    URandGen(int lim) : limit(lim) {}
    int operator()() {
        while (true) {
            int i = rand()%limit;
            if (used.find(i) == used.end()) {
                used.insert(i);
                return i;
            }
        }
    }
private:
    std::set<int> used;
    int limit;
};
 
...
 
URandGen uRand(100);
std::cout << uRand() << std::endl;
 

[Igors]

Это получается не очень и случайные числа. При 3 из 4 первым числом будет либо 1(1 вариант из RAND_MAX) либо 0. Ну явно не годится. Работать должно на любых числах. Я думаю ему в идеале нужны все числа из диапазона но в случайном порядке.

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

Код

C++ (Qt)
int i. limit = data.size();
for (i = 0; i < limit / 2; ++i)
 qSwap(data[qRand() % limit], data[qRand() % limit]);
 

[Igors]

генератор случайных уникальных чисел (весьма известный пример):

Я так вижу что когда человек писал "это" он хотел показать себя грамотным

- operator ()
- владение STL
- private (мол, хороший тон)

Но вот о том как это работает - ни хрена он не думал.

- создание доп контейнера и операции с ним (совсем недешевые)
- сколько же потребуется qrand() чтобы в конце-концов попасть на последний элемент из 1000?

Поэтому сколько "синтаксического сахара" не добавляй - говнокод остается говнокодом 

[V1KT0P]

Как правило порядок следования должен быть сохранен.

Как условие диктует так и надо =). В данном случае нужно случайное значение =). А если как "правило", то вообще можно попробовать взять полином и замутить псевдо-случайную последовательность =).

[m_ax]

генератор случайных уникальных чисел (весьма известный пример):

Я так вижу что когда человек писал "это" он хотел показать себя грамотным

- operator ()
- владение STL
- private (мол, хороший тон)

Но вот о том как это работает - ни хрена он не думал.

- создание доп контейнера и операции с ним (совсем недешевые)
- сколько же потребуется qrand() чтобы в конце-концов попасть на последний элемент из 1000?

Поэтому сколько "синтаксического сахара" не добавляй - говнокод остается говнокодом 

Не буду судить о чём он думал, но во всяком случае он выдаёт 100% уникальные случайные числа из заданного диапазона.
Или вы как то по другому представляете себе генератор уникальных (не повторяющихся) чисел? Квази не повторяющихся?

А rand можно заменить на что-нить более быстрое..

[V1KT0P]

Или вы как то по другому представляете себе генератор уникальных (не повторяющихся) чисел? Квази не повторяющихся?

Я пока что вижу два выхода: либо использовать список, либо полиномы. Правда насколько производительным будет вариант на полиномах...

[m_ax]

Или вы как то по другому представляете себе генератор уникальных (не повторяющихся) чисел? Квази не повторяющихся?

Я пока что вижу два выхода: либо использовать список, либо полиномы. Правда насколько производительным будет вариант на полиномах...

На полиномах это как?
Вариант с URandGen  на самом деле не очень хорош, с точки зрения производительности и т.д, как заметил igors, но это всего лишь пример..

[V1KT0P]

На полиномах это как?
Вариант с URandGen  на самом деле не очень хорош, с точки зрения производительности и т.д, как заметил igors, но это всего лишь пример..

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

[Igors]

Или вы как то по другому представляете себе генератор уникальных (не повторяющихся) чисел? Квази не повторяющихся?

Ну а почему бы просто не создать массив последовательных чисел, перемешать его и брать подряд из перемешанного? Минус - хранение доп массива, пусть на порядок дешевле std::set. Если это не устраивает по памяти - придется читать теорию.

Как условие диктует так и надо =). В данном случае нужно случайное значение =).

Если порядок не важен, то, как уже говорилось, мешаем массив - и все дела

А если как "правило", то вообще можно попробовать взять полином и замутить псевдо-случайную последовательность =).

"Случайные числа" и "случайная последовательность" - это 2 большие разницы Как раз последовательность гарантирует что не будет чисел слишком близких друг к другу. Статейку про "полиномы" лучше спрячьте - ее писал лох который не удосужился открыть книжки.

[splpwn]

Код

C++ (Qt)
qsrand (QDateTime::currentMSecsSinceEpoch());
QList<int> src; // исходный массив
QSet<int> dst; // наша выборка
int n; // количество элементов выборки
while (dst.size() < n)
    dst.insert(src.at(qrand() % src.size()));

Почему то всегда одинаковую последовательность выдаёт.

[m_ax]

Ну а почему бы просто не создать массив последовательных чисел, перемешать его и брать подряд из перемешанного?

Да. пожалуй, так..

Вот пример:

Код

C++ (Qt)
template <unsigned long N>
class URandGen
{
public:
    typedef unsigned long size_type;
    URandGen() {
        m_arr = new int[N];
        for (size_type i = 0; i < N; ++i)
            m_arr[i] = i;
        reset();
    }
    ~URandGen() {
        delete []m_arr;
    }
 
    void reset() {
        for (size_type i = 0; i < N; ++i) {
            std::swap(m_arr[i], m_arr[rand()%N]);
        }
    }
    int operator()() {
        static size_type i = 0;
        if (i == N) {
            reset();
            i = 0;
        }
        return m_arr[i++];
    }
private:
    int *m_arr;
};
 

Код

C++ (Qt)
int main()
{
    const int N = 10;
    int arr[N];
    URandGen<N> r;
    std::copy(arr, arr+N, std::ostream_iterator<int>(std::cout, " "));
 
    return 0;
}
 

[Igors]

Ну static счетчик не годится - тогда 2 экземпляра заклинят. А вот массив объявить static - есть смысл.
Также цыганщина с оператором () здесь ни к чему, гибче так

Код

C++ (Qt)
int URandGen::Rand( int index = -1 )
{
 if (index >= 0) m_count = index;
 m_count %= N;
 return m_arr[m_count++];
}
 

[V1KT0P]

"Случайные числа" и "случайная последовательность" - это 2 большие разницы Как раз последовательность гарантирует что не будет чисел слишком близких друг к другу. Статейку про "полиномы" лучше спрячьте - ее писал лох который не удосужился открыть книжки.

Да ничего не гарантирует, что в случайных чисел что в случайной последовательности могут попадаться моменты когда несколько чисел будут идти подряд, ибо случайность =). Даже если взять какой-нибудь идеальный генератор случайных чисел, есть вероятность что он выдаст несколько раз одно и то-же значение. Вероятность конечно будет нереально мала, но все-таки она есть =).
Вот твой алгоритм делит на части и из частей вытягивает числа. Тогда проверим насколько он хорош. Возьмем 16 значений из которых нужно взять 4-ре. Получается что твой алгоритм будет выдавать 1 из 256 вариантов. Тогда как тот-же тупой алгоритм со списком будет выдавать 1 из 43680 вариантов. Согласись разница слишком большая.
Представим что автор темы хочет применить алгоритм в игре, тогда получится что с твоим алгоритмом будет много повторов, а некоторые комбинации(которых много) вообще небудет.
А если автор попробует использовать в шифровании, то на твоем алгоритме он станет очень уязвимым =).

[m_ax]

Также цыганщина с оператором () здесь ни к чему, гибче так

Это не цыганщина, скорее дело вкуса. Плюс ко всему, с оператором() объект этого класса можно будет использовать в stl алгоритмах, например std::generate и т.д.  

[Igors]

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

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

Вот твой алгоритм делит на части и из частей вытягивает числа. Тогда проверим насколько он хорош. Возьмем 16 значений из которых нужно взять 4-ре. Получается что твой алгоритм будет выдавать 1 из 256 вариантов. Тогда как тот-же тупой алгоритм со списком будет выдавать 1 из 43680 вариантов. Согласись разница слишком большая.

А кто сказал что требования именно такие? Они могут быть (и часто бывают) совсем другими. Напр ф-ция описана 16 значениями, но можем хранить только 4. Как ни странно, взять просто "каждое 4-е значение" оказывается плохо

По поводу "тупо - это хорошо". Прикинем во что обойдется резвое removeAt всего на 10k элементов

10.000 / 2 = 5.000

Т.е. чтобы получить 1 случайное число смувили в среднем 5 тысяч int, перекачали 20k байт. Что Вы можете сказать о технике и классе программиста предложившего такое решение?