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时，它们各自的行顺序不同我的意思是，因为p的大小()在这里是4，因此我们有4个模式，我们想一次选择一个，直到我们访问所有的模式。

当所有的图案一个接一个地被选中时，一个epoch就完成了，我们需要为下一个epoch改变图案顺序。我们将这样做任意次数，每次，这些模式的顺序需要改变，(例如，第一次(0,0)是第一次，其次是(0,1)和(1,0)，最后是(1,1)，在第二个纪元，我们可能有(1,1)(1,0)(0,0)(0,1)作为模式)。

因此，当我们洗牌模式集合时，我们也需要对目标集合进行完全相同的洗牌。最快的方法是什么?我脑子里闪过几种不同的方法，比如:

• 从这两个数组中创建一个映射，并将每个模式映射到相应的目标，然后对模式集合进行洗牌。当需要一个目标时，它可以很容易地通过地图访问。

• 使用元组创建一个新的列表，并对新创建的元组进行洗牌，然后继续。

• 只是使用0到3之间的随机数并选择一个数字，(模式索引)并使用它，将索引存储在数组中，这是为了防止在一个epoch中两次选择相同的索引。

在这种情况下你有什么建议?

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编译器才能工作，现场演示在这里):

#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 << " ";
    }
}