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

Question

Допустим, у меня есть список данных: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, где n = 10 элементов

Я бы хотел случайным образом выбрать k элементов этого набора для формирования подсписка, скажем, k = 5.

В этом случае я мог бы получить подсписок, который выглядит как {9, 3, 5, 2, 7}

Я мог бы сделать это:

• Случайное определение смещения в списке между 0 и текущим размером списка минус 1
• Добавление этого элемента в мой подсписок
• Стирание этого элемента из исходного списка
• Повторяйте, пока не будет найден нужный размер

Проблема в том, что по мере увеличения исходного списка смещение и время удаления также увеличиваются, и для любого достаточно большого списка (скажем, более 1 000 000 элементов) выполнение этого алгоритма занимает довольно много времени.

Есть ли более быстрый способ генерации случайной последовательности из списка данных? Реализация генератора случайных чисел должна быть обойдена для этой проблемы, вместо этого, сосредоточив внимание на том, как результат RNG используется в предложенном алгоритме.

Есть мысли?

Сейчас я использую список C ++ STL

Answer 1

Я бы использовал random_shuffle.Вы можете изменить генератор, указав третий параметр.

Для этого требуются итераторы с произвольным доступом, поэтому вы можете переключиться на std::vector (который обычно намного лучше и предпочтительнее, чем std::list, возможно, худший контейнер), или просто оперируйте каким-нибудь массивом.Я продемонстрирую оба:

int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::random_shuffle(data, data + 10); 

// or

std::vector data; // populate it
std::random_shuffle(data.begin(), data.end());

Теперь все в случайном порядке, просто обработайте элементы k кулака как ваше подмножество:

// now treat data[0] through data[k] as your random subset, or:
std::vector subset(data, data + k);

// or
data.resize(k); // shrink vector

---

Обратите внимание, что в другомвопрос, Джерри делится отличным способом делать то, что вы хотите.

Answer 2

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

См. Примеры> Современный метод

Вам не нужно перетасовывать свой весь список.O (k) (лучше, чем O (n))

Answer 3

Минимальный пример использования OutputIterators и std::random_shuffle.Обратите внимание, что алгоритм изменит ваш исходный ввод, поэтому было бы разумно сделать копию перед вызовом функции.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

template<class It, class OutIt>
void take_random_n(It begin, It end, OutIt out, size_t n) {
  std::random_shuffle(begin, end);
  It end2 = begin;
  std::advance(end2, n);
  std::copy(begin, end2, out);
}

int main() {
  std::vector<int> a;
  int b[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  take_random_n(b, b + 10, std::back_inserter(a), 4);
  for(std::vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    std::cout << *it << " ";
}

Answer 4

Или вы можете сделать это:

• Случайное определение смещения в пределах список, между 0 и текущим размер списка.
• Добавление этого элемента к вашему Подсписок.
• Повторяйте, пока подсписок не станет , вероятно, достаточно длинным, чтобы содержать правильное количество элементов. Например, если вы выбираете 10 из 1 000 000 элементов, подсписок из 10, вероятно, будет достаточно длинным. Вам не нужно быть сверхточным при расчете количества дополнительных элементов, которые вы должны выбрать
• Теперь убедитесь, что все элементы в подсписке разные. Если нет, удалите дубликаты. Если ваш подсписок слишком короткий, выберите еще один из основного списка. Если нет, то все готово.

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

И я не имею ни малейшего понятия о том, как производительность этого подхода будет сравниваться с производительностью предложенного random_shuffle списка из 10 ^ 6 элементов.

Answer 5

Перемешайте список, затем возьмите первые (или последние) k элементы. Если вы используете алгоритм O (n), такой как Fisher-Yates shuffle, то весь процесс будет O (n).

Answer 6

Мои 2 цента (используя только stl и нуждаются в большинстве прямых итераторов):

//-----------------------------------------------------------------------------
#include <cstdlib>
//-----------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
//-----------------------------------------------------------------------------
// random generator
template< typename DiffType >
struct RandomlyRandom{
  DiffType operator()( DiffType i ){
    return std::rand() % i;
  }
};
//-----------------------------------------------------------------------------
// we'll have two iterators:
//  - the first starts at the begining of the range
// and moves one element at a time for n times
//  - the second starts at random in the middle of the range
// and will move a random number of elements inside the range
//
// then we swap their values
template< typename FwdIter, typename Fn >
void random_shuffle_n( FwdIter begin, FwdIter end, Fn& Func, size_t n ){
typedef typename std::iterator_traits<FwdIter>::difference_type difference_type;

FwdIter first = begin;
FwdIter second = begin;

difference_type dist  = std::distance( begin, end );
difference_type offset = Func( dist ) % dist;
difference_type index = offset;
std::advance( second, offset ); // try to put some distance between first & second

  do{
    offset = Func( dist ) % dist;
    index += offset;
    if( index >= dist ){
      second = begin;
      index = offset = index % dist;
    }
    std::advance( second, offset );

    std::swap( *first++, *second );
  }while( n-- > 0 );
}
//-----------------------------------------------------------------------------
int main( int argc, char* argv[] ){
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::list< int > lst( arr, arr + sizeof( arr ) / sizeof( arr[ 0 ] ) );

  std::copy( lst.begin(), lst.end(), std::ostream_iterator< int >( std::cout, " " ) ); 
  std::cout << std::endl;
  RandomlyRandom< std::list< int >::difference_type > rand;

  for( int i = 0; i < 100;  i++ ){
    random_shuffle_n( lst.begin(), lst.end(), rand, 5 );
    std::copy( lst.begin(), lst.end(), std::ostream_iterator< int >( std::cout, " " ) ); 
    std::cout << std::endl;
  }

  return 0;
}
//-----------------------------------------------------------------------------

Answer 7

В большинстве ответов предлагается перетасовать начальный контейнер.Если вы не хотите, чтобы он был изменен, вы все равно можете использовать этот подход, но сначала вам нужно скопировать контейнер. Решение @ pmr (что приятно, потому что он превращает его в функцию) станет:

template <typename InputIterator, typename Size, typename OutputIterator>
void take_random_n(InputIterator first, InputIterator  last, 
                   Size          n,     OutputIterator result)
{
    typedef typename std::iterator_traits<InputIterator>::value_type value_type;

    std::vector<value_type> shufflingVec(first, last);

    std::random_shuffle(shufflingVec.begin(), shufflingVec.end());

    std::copy(shufflingVec.begin(), shufflingVec.begin() + n, result);
}

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

template <typename InputIterator, typename Size, typename OutputIterator>
void take_random_n(InputIterator first, InputIterator  last, 
                   Size          n,     OutputIterator result)
{
    typedef typename 
        std::iterator_traits<InputIterator>::value_type      value_type;
    typedef typename 
        std::iterator_traits<InputIterator>::difference_type difference_type;

    difference_type size = std::distance(first, last);

    std::vector<value_type> indexesVec(
        boost::counting_iterator<size_t>(0),
        boost::counting_iterator<size_t>(size));

    // counting_iterator generates incrementing numbers. Easy to implement if you
    // can't use Boost

    std::random_shuffle(indexesVec.begin(), indexesVec.end());

    for (Size i = 0 ; i < n ; ++i)
    {
        *result++ = *std::advance(first, indexesVec[i]);
    }
}

// Disclaimer: I have not tested the code above!

Вы заметите, что последнее решение будет работать очень по-разному в зависимости от типа используемых итераторов: с итераторами с произвольным доступом (как указатели или vector<T>::iterator), все будет в порядке, но с другими типами итераторов использование std::distance и многочисленные вызовы std::advance могут вызвать значительные издержки.

Answer 8

Назначьте случайное число каждой записи в вашем списке, затем отсортируйте список по случайному номеру. Выберите первые n записей, которые вы хотите.

Answer 9

Перемешайте ваш массив, используя алгоритм Затем вы можете просмотреть случайные элементы с начала массива.

Answer 10

Вы можете перетасовать его с помощью std :: random_shuffle , а затем просто скопировать первые сколько угодно элементов в новый список.