Russian Qt Forum

Добрый вечер, друзья.
Подскажите. Как реализовать случайную выборку из фиксированного набора чисел без повторений?

qrand(), QSet или QHash. хотя не совсем понятно зачем тут использовать Qt - STL будет вполне достаточно.

Непонятно, приведите пример с тремя числами без повторений пожалуйста.

Вот например банальный пример:

C++ (Qt)
qsrand (QDateTime::currentMSecsSinceEpoch());
QList<int> numbers;
for (int i=0; i<4; ++i)
    numbers.append(i);
for (int i=0; i<3; ++i) {
    int num = qrand() % numbers.count();
    qDebug() << numbers.at(num);
    numbers.removeAt(num);
}

C++ (Qt)
int RandIndex( int limit,  // число элементов в исходном массиве
               int numSel,  // число выбираемых
               int n )      // выбираемое
{
 int beg = n * limit / numSel;
 int end = (n + 1) * limit / numSel;
 return beg + (qrand() % (end - beg)); 
}
 

Не много ли он жрет ресурсов?

Так написал-же банальный пример, а не высокопроизводительный идеальный =). Я даже мозг не включал, его жара плавит =(, хочу кондиционер...

Только я что-то не понял в твоем алгоритме:
Первым я выбрал количество чисел: 4, дальше указал число выбираемых чисел: 3, дальше указывал номер выбираемого числа, но что то в результате получил 0, 0, 1. С какого оно повторило 0, да в алгоритм не вникал, лениво =).

C++ (Qt)
    qDebug() << RandIndex(4, 3, 0);
    qDebug() << RandIndex(4, 3, 1);
    qDebug() << RandIndex(4, 3, 2);

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

пользуемся тем, что все элементы QSet уникальны. считаем, что src.size() > n, иначе в коде нет особого смысла. если использовать QHash вместо QSet, то можно ещё индекс сохранять.
ну так попросили же пример на Qt :D

Ахаха, только что замерил производительность на 100000 значений при 99990. Мой банальный тупой алгоритм отработал за 1-2 секунды. А твой пришлось прибить после 15 секунд, лень дальше ждать =).

Там я сначала перепутал деление, должно быть * limit / numSel; (как сейчас)

И что будет для выборки 3 элементов из исходных (7,  7, 7, 1) ? Также никто не говорил что можно менять порядок следования

Стремление задействовать как можно больше "мощных тулзлов" и написать "как можно короче" выдает начинающего с головой  :)

Ладно, вот более интересная задачка на ту же тему. Все то же самое + доп условия

- исходный массив отсортирован (выборка тоже должна быть сортирована)
- разница между любыми 2 соседними значениями выборки не должна быть меньше заданного N

Вспомнился старый мультфильм в котором (кажется) мышонок на пне под гитару пел что-то типа
:)

Да ладно, что лулзы нельзя уже половить =). Я как увидел цикл с неопределенным количеством итераций, так не удержался.
Ты свой алгоритм тестировал? У меня тоже самое 0 0 1.

То у Вас с copy/paste проблемы, у меня все норм (0, 1, 3) или (0, 1, 2)

Да действительно. Теперь другая проблема, нам нужны случайные числа, а в твоем алгоритме у меня постоянно первым 0 идет. Я что-то не догоняю смысла алгоритма.

Елы-палы, что ж тут "не догнать"? Делим на примерно равные интервалы, из каждого выбираем случайное число.

По поводу первого нуля. Во-первых взять число элементов побольше напр не 4 а 24. А во-вторых да, что-то у них с qrand - первое возвращаемое всегда маленькое если привести к [0..1]. Поэтому лучше использовать остаток от деления (исправил)

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

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

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;
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот пример:

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

Ну 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++];
}
 

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

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

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

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

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

10.000 / 2 = 5.000

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

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

"Свой" здесь неуместно, все это вещи известные. Как достичь "той же тупизны" уже дважды приводилось (в постах #16 и #25). Ладно, еще раз

C++ (Qt)
for (int i = 0; i < numSel; ++i)
 qSwap(data[i], data[qrand() % data.size()]);
 
// первые numSel элементов - подвыборка
 

Вы уж сравните с Вашим по скорости  :)

Так вроде свояли же уже достаточно быстрый генератор)

Осталось сравнить с какой-нить другой реализацией: Пример теста:

C++ (Qt)
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
 
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();
        m_index = 0;
    }
    ~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()() {
        if (m_index == N) {
            reset();
            m_index = 0;
        }
        return m_arr[m_index++];
    }
private:
    int *m_arr;
    size_type m_index;
};
 
int main()
{
    srand(time(0));
    const int N = 1000000;
    int *arr = new int[N];
    URandGen<N> randGen;
    clock_t start = clock();
    std::generate(arr, arr+N, randGen);
    std::cout << "time = " << float(clock()-start)/CLOCKS_PER_SEC << " sec" << std::endl;
 
    //std::copy(arr, arr+N, std::ostream_iterator<int>(std::cout, " "));
 
    std::cin.get();
    return 0;
}
 

Осталось подставить вместо URandGen другую реализацию и всё станет ясно)
Хотя сделать что-то быстрее будет ооочень не просто)  

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