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