※ 引述《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% (和记忆体大小呈正比). 所以在需要降 低复制成本的情况下, 可以考虑这样跳着取值的方式. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.193.76.216 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1587169372.A.8A6.html ※ 编辑: loveme00835 (123.193.76.216 台湾), 04/18/2020 14:17:41