※ 引述《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://www.ptt.cc/bbs/C_and_CPP/M.1587169372.A.8A6.html
※ 編輯: loveme00835 (123.193.76.216 臺灣), 04/18/2020 14:17:41