從C++中的兩個相關向量進行隨機選擇的最快方法是什麼？

Question

我想要做的是洗牌現有的數組（矢量）。這裏有一個問題，實際上有兩個相互依賴的數組（向量）。更準確地說，我有一個包含模式的2d向量，所以每一行代表一個模式，然後是另一個包含每個模式所需輸出的2d向量。

所以它看起來像這樣的事情：

vector<vector<float>> P{ vector <float> {0, 0}, 
         vector <float> {1, 0}, 
         vector <float> {0, 1}, 
         vector <float> {1, 1} }; 

vector<vector<float>> T{ vector <float> {0}, 
         vector <float> {1}, 
         vector <float> {1}, 
         vector <float> {0} }; 

現在我需要重新洗牌的格局集合，因此他們的個人行的次序每次都不同，我們遍歷P.我再次說，既然普的大小（）這裏是4，因此我們有4個模式，我們希望一次選擇一個模式，直到我們訪問所有模式。

當所有的模式一個接一個被選中時，一個時期就完成了，我們需要改變下一個時期的模式順序。我們將這樣做任意次數，每次這些模式順序需要改變，（例如第一次（0,0）是第一次，然後是（0,1）和（1,0） ）和最後（1,1），在第二個時期，我們可能有（1,1）（1,0）（0,0）（0,1）作爲模式）。

所以當我們洗牌的模式集合，我們需要有目標集合洗牌完全一樣。什麼是最快的方式？有不同的方式，通過我的頭跑，如：

• 創建映射出這兩個數組中，並映射與相應的目標每個圖案，然後洗牌模式集合。無論何時需要目標，都可以通過地圖輕鬆訪問。

• 使用元組創建一個新列表並隨機播放新創建的元組並開始工作。

• 只是使用0到3之間的一個隨機數並選擇一個數字（模式索引）並使用它，將索引存儲在一個數組中，該數組用於防止在一個時期中選擇相同的索引兩次。

在這種情況下你會有什麼建議？

Answer 1

似乎要洗牌指標：

std::vector<std::size_t> indexes{0, 1, 2, 3}; // or initialize with std::iota 

std::shuffle(indexes.begin(), indexes.end(), my_random_generator); 

Answer 2

你提的問題是非常難，因爲它缺乏很多的信息確切回答。即使有了所有需要的信息，如果沒有測量不同的選擇，一個確定的答案仍然是非常難以給出。

第一個也是最重要的問題是：你試圖快速創建什麼 - 生成一個新的時代或訪問你的數據？回答這個問題需要知道您擁有的實際數據的大小，您在其他代碼中訪問數據的方式和次數，在運行時如何修改/生成數據等。

以下是一些常規建議雖然。如果您知道您的T和P的內部向量的大小 - 請使用std::array而不是std::vector。這樣你的內部數組將被放置在一塊改善緩存行爲的內存中。出於同樣的原因，如果可以的話，將模式和輸出組合成std::tuple或std::pair或struct，並將它們全部放在一個數組中。

讓我們假設你可以把它們放到一個單獨的向量中。然後，關於洗牌本身，您可以將洗牌索引轉換爲靜態向量或洗牌向量本身。對指標向量進行排序可能會更快，但是每次訪問模式結果對時都會付出額外的間接費用，這可能會讓您的整體表現方式比對整個向量本身進行糟糕。在作出決定時，您的訪問模式至關重要 - 衡量您的選擇！

如果由於某種原因，你絕對不能把所有東西放在一個向量中，並且額外的索引數組太昂貴了，可以考慮使用這段代碼（注意，你需要boost和C++ 14編譯器才能工作，現場演示here） ：

#include <iostream> 
#include <string> 
#include <random> 
#include <vector> 
#include <tuple> 
#include <utility> 
#include <algorithm> 

#include <boost/iterator/iterator_facade.hpp> 

template <typename... IteratorTypes> 
using value_tuple = std::tuple<typename IteratorTypes::value_type...>; 

template <typename... IteratorTypes> 
class reference_tuple : public std::tuple<typename IteratorTypes::value_type&...> { 
    using std::tuple<typename IteratorTypes::value_type&...>::tuple; 
}; 

template<typename... IteratorTypes, size_t... Index> 
void swap_impl(reference_tuple<IteratorTypes...> left, reference_tuple<IteratorTypes...> right, std::index_sequence<Index...>) 
{ 
    using std::swap; 
    int dummy[] = {(swap(std::get<Index>(left), std::get<Index>(right)), 0)...}; 
    (void)dummy; 
} 

template <typename... IteratorTypes> 
void swap(reference_tuple<IteratorTypes...> left, reference_tuple<IteratorTypes...> right) 
{ 
    swap_impl(left, right, std::index_sequence_for<IteratorTypes...>{}); 
} 


template <typename... IteratorTypes> 
class zip_iter 
    : public boost::iterator_facade< 
    zip_iter<IteratorTypes...>   // Derived 
    , value_tuple<IteratorTypes...>  // Value 
    , boost::random_access_traversal_tag 
    , reference_tuple<IteratorTypes...> // Reference 
    > 
{ 
public: 
    zip_iter() = default; 

    explicit zip_iter(IteratorTypes... iters) 
     : iterators(iters...) 
    { 
    } 


private: 
    friend class boost::iterator_core_access; 

    void increment() { increment_impl(std::index_sequence_for<IteratorTypes...>()); } 

    template<size_t... Index> 
    void increment_impl(std::index_sequence<Index...>) 
    { 
     int dummy[] = {(++std::get<Index>(iterators), 0)...}; 
     (void)dummy; 
    } 

    void decrement() { decrement_impl(std::index_sequence_for<IteratorTypes...>()); } 

    template<size_t... Index> 
    void decrement_impl(std::index_sequence<Index...>) 
    { 
     int dummy[] = {(--std::get<Index>(iterators), 0)...}; 
     (void)dummy; 
    } 

    template<typename diff_t> 
    void advance(diff_t n) { advance_impl(n, std::index_sequence_for<IteratorTypes...>()); } 

    template<typename diff_t, size_t... Index> 
    void advance_impl(diff_t n, std::index_sequence<Index...>) 
    { 
     int dummy[] = {(std::advance(std::get<Index>(iterators), n), 0)...}; 
     (void)dummy; 
    } 

    bool equal(zip_iter const& other) const 
    { 
     return std::get<0>(iterators) == std::get<0>(other.iterators); 
    } 

    auto dereference() const { 
     return dereferenceImpl(std::index_sequence_for<IteratorTypes...>{}); 
    } 

    template<std::size_t... Index> 
    auto dereferenceImpl(std::index_sequence<Index...>) const 
    { 
     return reference_tuple<IteratorTypes...>(*std::get<Index>(iterators)...); 
    } 

    auto distance_to(zip_iter const& r) const 
    { 
     return std::distance(std::get<0>(iterators), std::get<0>(r.iterators)); 
    } 

    std::tuple<IteratorTypes...> iterators; 
}; 

template<typename... Iterators> 
auto make_zip_iter(Iterators... iters) 
{ 
    return zip_iter<Iterators...>(iters...); 
} 

int main() 
{ 
    std::mt19937 rng(std::random_device{}()); 

    std::vector<int> ints(10); 
    std::iota(ints.begin(), ints.end(), 0); 

    std::cout << "Before: "; 
    for (auto i : ints) { 
     std::cout << i << " "; 
    } 
    std::cout << "\n"; 

    std::vector<int> ints2{ints}; 

    std::shuffle(make_zip_iter(ints.begin(), ints2.begin()), make_zip_iter(ints.end(), ints2.end()), rng); 

    std::cout << "Are equal: " << (ints == ints2) << "\n"; 

    std::cout << "After: "; 
    for (auto i : ints) { 
     std::cout << i << " "; 
    } 
}