c++ - 如何有效地从矩阵中生成行的随机子集

Question

我有一个大矩阵 M 实现为 vector<vector<double>有 m 行，即矩阵是 n 列元素的 m 个 vector 的 vector 。

我必须为这个矩阵的行创建两个子集，即 A 包含 k 行，B 包含其他 m-k 行。必须随机选择行。

我不想使用除 STL 之外的任何库，所以也没有提升。

我考虑的两种方法是:

1. 生成行索引的std::random_shuffle，将前k个索引指示的行复制到A，将其他m-k指示的行复制到B
2. 执行 M 的 std::random_shuffle。将 k 行复制到 A，并将 m-k 行复制到 B

是否有其他选项，以及上述两个选项在内存消耗和处理时间方面的比较如何？

谢谢!

Answer 1

如果您不需要 B 以随机顺序排列，那么 random_shuffle 会做比您需要的更多的工作。

如果“STL”是指 SGI 的 STL，则使用 random_sample .

如果“STL”是指 C++ 标准库，那么您就没有 random_sample。您可能想要复制实现，但在第一个 n 步骤后停止。这将减少时间。

请注意，它们都修改了一个序列。根据您实际希望 A 和 B 结束的位置，以及谁拥有原件，这可能意味着您最终每行做 2 个拷贝 - 一次将其放入一个可变容器中进行洗牌，然后再次将其放入它的最终目的地。这比所需的内存和处理时间更多。要解决此问题，您可以交换 临时容器中的行，并放入 A 和 B。或者复制算法，但将其调整为:

• 列出第一个 vector 的索引
• 部分打乱索引列表
• 将前n个索引对应的行复制到A，其余复制到B。

我不确定这会更快还是使用更少的内存，但我怀疑是这样。

random_shuffle 的标准说它执行“交换”。我希望这意味着它对 vector 有效，但您可能想检查它是否实际上使用了优化的 swap，而不是进行任何复制。我认为这应该意味着，特别是因为自然实现是 Fisher-Yates，但我不确定是否应该采用标准中的语言来保证它。如果它正在复制，那么您的第二种方法将非常缓慢。如果它使用 swap 那么它们大致相当。 vector 上的 swap 会比索引上的 swap 稍微慢一些，但速度并不快。与复制一行相比，交换 vector 或索引的速度非常快，而且每个操作都有 M 次，所以我怀疑这会对总运行时间产生巨大影响。

[编辑:Alex Martelli 最近提示滥用术语“STL”来表示 C++ 标准库。在这种情况下，它确实有所作为:-)]