从 C++ 中的两个相关向量进行随机选择的最快方法是什么？

Question

我想做的是打乱现有数组（向量）。这里有一个问题，实际上有两个数组（向量）相互依赖。

更确切地说，我有一个包含模式的二维向量，因此每一行表示一个模式，然后还有另一个二维向量，其中包含每个模式的所需输出。

所以它看起来像这样：

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 的 size() 是 4，因此我们有 4 个模式，我们想要select 一次一个，直到我们访问所有这些。

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

因此，当我们打乱模式集合时，我们也需要对目标集合进行完全相同的打乱。这样做最快的方法是什么？运行通过我的头脑有不同的方式，例如：

从这两个数组中创建一个映射，并将每个模式映射到相应的目标，然后打乱模式集合。每当需要目标时，都可以通过地图轻松访问。
使用元组创建一个新列表并打乱新创建的元组并开始。
只需使用 0 到 3 之间的运行dom 数字并选择一个数字（模式索引）并使用它，将索引存储在数组中，用于防止select在一个时期两次使用相同的索引。

在这种情况下，您有什么建议？

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

您的问题缺少很多信息，因此很难给出明确的答案。即使拥有所需的所有信息，如果不衡量不同的选项，仍然很难给出明确的答案。

第一个也是最重要的问题是：您要加快速度的是什么 - 生成一个新纪元或访问您的数据？回答这个问题需要知道你拥有的实际数据的大小、你在其他代码中访问你的数据的方式和次数、你的数据在运行时如何modified/generated，等等。

这里有一些一般性建议。如果您知道 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 << " ";
    }
}

从 C++ 中的两个相关向量进行随机选择的最快方法是什么？

What is the fastest way of making random selection from two dependent vectors in C++?

c++

shuffle

vector

multidimensional-array