※ 引述《doasgloria (青柳立夏)》之铭言：
哈囉, 通常发文问效率会提供比较基准, 这样大家才会知道要提供
什么资讯才符合你的需求, 因为没有基准所以我就先以一般常用的
洗牌算法当改进对象. 不管几维的阵列, 假如你是要均匀地打乱
顺序, 利用元素位址相邻的特性, 当作一维阵列来操作就好:
using value_type = int;
using array_type = value_type[3][4];
constexpr std::size_t array_size = 12;
array_type A, B;
value_type * const from = std::addressof(**B);
value_type * const to = std::addressof(**A);
// 1. initialize array 'B'
// 2. copy values from 'B' to 'A'
std::copy_n(from, array_size, to);
// 3. shuffle values in 'A'
std::shuffle(to, std::next(to, array_size),
std::default_random_engine{std::random_device{}()});
类似范例网络上很多就不赘述. 洗牌法的缺点是它需要额外 O(n)
的空间, 加上 swap 操作, 当阵列元素复制成本变高的时候, 往往
得改用间接取值的方式. 所以在这里介绍 O(1) 空间复杂度的方法
, 此种方法可以牺牲部份乱度来换取执行时间.
我们总共需要 2 种 adaptor (配接器):
1. shffule_order_generator (generator adaptor)
2. jump_iterator (iterator adaptor)
shuffle_order_generator 的实作概念和 std::shuffle_order_en-
gine 类似 (但是不会 discard 值), 在内部维护一个表格储存预先
产生好的值, 然后再随机选择表格里的值回传出来, 造成打乱顺序
的效果. 我们可以透过调整表格大小还有巢状包装配接器来得到想
要的乱度.
jump_iterator 封装了 iterator 还有 generator, 每次取值的时
候都是回传 *std::next(i, g()) 的结果: 也就是利用函式的回传
值来决定要存取的物件位置. 实作在下面可以找到:
shuffle_order_generator: https://bit.ly/2wMu907
jump_iterator: https://bit.ly/3etDICd
sequence_generator: https://bit.ly/3ctJHFq
为了说明用法, 我们先来导入一个简单的 generator 型别 sequen-
ce_generator: 给定两个整数 min & max, 它会回传 min, min + 1
, ... , max 的序列. 举个例子, 以下程式码会印出 1 ~ 10:
std::generate_n(
std::ostream_iterator<unsigned>(std::cout, " "), 10,
sequence_generator<unsigned>(1, 10)
);
std::cout << std::endl;
以下程式码也会印出 1 ~ 10, 只是顺序被打乱:
std::generate_n(
std::ostream_iterator<unsigned>(std::cout, " "), 10,
make_shuffle_order_generator<5>(
sequence_generator<unsigned>(1, 10),
std::random_device{}(), 10
)
);
std::cout << std::endl;
然后就是本文的目标: 乱序存取阵列里的元素
std::array<unsigned, 10> values;
std::iota(begin(values), end(values), 1);
auto reader = make_jump_iterator(
begin(values),
make_shuffle_order_generator<5>(
sequence_generator<std::size_t>(0, size(values) - 1),
std::random_device{}(), size(values)
)
);
std::copy_n(reader, size(values),
std::ostream_iterator<unsigned>(std::cout, " "));
std::cout << std::endl;
经过测试, 使用上述方法对原文中提到大小为 3500x3500x3 的阵列
去做复制 (元素型别为 std::int32_t), 和 copy & shuffle 方法
相比, 执行时间减少约 30% (和内存大小呈正比). 所以在需要降
低复制成本的情况下, 可以考虑这样跳着取值的方式.