如何从数据列表中快速生成随机序列？

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 列表。

- Tim

---

这可能取决于随机选择的元素数量与列表元素数量之比。如果这个比率很低，最好在某种袋子/字典中跟踪生成的数字，以避免重复生成相同的数字。 - pascal

可能是选择单个随机值组合的算法？的重复问题。 - Jerry Coffin

https://dev59.com/OVwY5IYBdhLWcg3w7rr6#32035986 - Nikos M.

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

---

请注意，在另一个问题中，Jerry 分享了一种出色的方法 来实现你想要的。

- GManNickG

---

然后只需从这个洗牌后的列表中读取前n个元素，然后将它们添加到您的新列表中。 - sigint

如果k远小于n，那么这样做比必要的工作更多。 - Mike Seymour

@Mike：好观点。由于似乎这是更优秀的方法，我已经在另一个问题中添加了指向Jerry答案的链接。 - GManNickG

Answer 2

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

请查看示例 > 现代方法

您不需要对整个列表进行洗牌。 O(k)（优于O(n)）

- Tom Sirgedas

Answer 3

使用输出迭代器和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 << " ";
}

- pmr

---

你应该注意到迭代器必须是随机访问迭代器。通常，在模板参数列表中使用类似RandomAccessIterator的名称进行记录。 - Luc Touraille

Answer 4

将列表洗牌，然后取前（或后）k个元素。如果您使用像Fisher-Yates洗牌这样的O(n)算法，则整个过程是O(n)。

- Nick Meyer

Answer 5

或者你可以通过以下方式来完成这个任务：

• 在列表中随机确定一个偏移量，范围在0到当前列表大小之间。
• 将该元素添加到你的子列表中。
• 重复上述步骤，直到子列表可能足够长以包含所需数量的元素。例如，如果你需要从1000000个元素中选择10个，那么子列表长度为10就够了。在计算所需额外元素的数量时，并不需要非常精确。
• 检查子列表中的所有元素是否都不同。如果有重复元素，则删除重复的元素。如果子列表现在太短，从主列表中选择更多元素。否则，任务完成。

我不确定为什么你要从主列表中删除已选择的元素，但如果这是必要的，你可以在构建子列表后再执行此操作。

至于这种方法的性能如何与建议的随机打乱一个包含10^6个元素的列表的性能相比，我一点也不清楚。

- High Performance Mark

---

这是随机抽样的乱序排序。如果 k <<< n，则性能可能还可以，但随着 k 的增加，性能将迅速退化。此外，它要求原始列表由唯一元素组成。 - Dennis Zickefoose

Answer 6

大多数答案都建议对初始容器进行洗牌。如果您不希望修改它，仍然可以使用此方法，但首先需要复制容器。@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 可能会导致相当大的开销。

- Luc Touraille

Answer 7

我的两分意见（仅使用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;
}
//-----------------------------------------------------------------------------

- Eugen Constantin Dinca

Answer 8

你可以使用std::random_shuffle来打乱它，然后将你想要的前几个元素复制到一个新列表中。

- Cogwheel

Answer 9

使用一些算法来打乱你的数组，然后你就可以从数组开头随机查看元素。

- Michael Spector

Answer 10

为列表中的每个条目分配一个随机数，然后按随机数对列表进行排序。选择您想要的前n个条目。

- user351063