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

您似乎想要调整索引:

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

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

你的问题很难明确回答,因为它缺乏很多信息。即使有了所需的所有信息,如果没有明确的答案,仍然很难给出 测量 不同的选项。

第一个也是最重要的问题是:您试图快速生成新纪元或访问您的数据是什么?回答这个问题需要知道实际数据的大小、在其他代码中访问数据的方式和次数、在运行时如何修改/生成数据等。

不过,这里有一些一般性建议。如果你知道你的内部向量的大小 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 << " ";
    }
}