交换向量的值和索引

问题描述

我有一个 std::vector，其中包含从 0 到 N 的连续混洗值，并且希望尽可能高效地交换每个值及其在向量中的位置.

I have a std::vector<int> with contiguous shuffled values from 0 to N and want to swap, as efficiently as possible, each value with its position in the vector.

示例:

v[6] = 3;

变成

v[3] = 6;

这是一个简单的问题，但我不知道如何处理它以使其变得微不足道，而且最重要的是非常快.非常感谢您的建议.

This is a simple problem, but I do not know how to handle it in order to make it trivial and, above all, very fast. Thank you very much for your suggestions.

推荐答案

Given N 在编译时并给定数组包含 [0,N) 中的每个索引一次，它相对简单(只要它不必就位，如上面的评论中所述):

Given N at compile time and given the array contains each index in [0,N) exactly once,it's relatively straight forward (as long as it doesn't have to be in-place, as mentioned in the comments above) :

构造一个新数组，使得 v'[n] = find_index(v, n) 并将其分配给旧数组.

Construct a new array so that v'[n] = find_index(v, n) and assign it to the old one.

在这里，我使用带有 std::index_sequence 的可变参数模板将其合并为单个赋值:

Here I used variadic templates with std::index_sequence to roll it into a single assignment:

template<typename T, std::size_t N>
std::size_t find_index(const std::array<T,N>& arr, std::size_t index) {
    return static_cast<std::size_t>(std::distance(arr.begin(), std::find(arr.begin(), arr.end(), index)));
}

template<typename T, std::size_t N, std::size_t... Index>
void swap_index_value(std::array<T,N>& arr, std::index_sequence<Index...> seq){
    arr = { find_index(arr, Index)... };
}

template<typename Integer, std::size_t N>
void swap_index_value(std::array<Integer,N>& arr) {
    swap_index_value(arr, std::make_index_sequence<N>{});
}

这看起来并不复杂.为 [0,N) 中的每个 n 调用 find_index(arr, n)将总共​​进行 N * (N+1)/2 次比较(std::sort 将只需要 N * log(N)).

The complexity of this is does not look great though. Calling find_index(arr, n) for each n in [0,N)will take N * (N+1) / 2 comparisons total (std::sort would only take N * log(N)).

然而，因为我们知道每个索引都存在于数组中，所以我们可以只填写一个索引数组当我们遍历原始数组时，假设 T 是整数类型，我们也可以跳过一些 std::size_t <-> T 转换:

However, since we know each index is present in the array, we could just fill out an array of indicesas we walk over the original array, and assuming T is an integral type we can skip some std::size_t <-> T conversions, too:

template<typename T, std::size_t N>
void swap_index_value(std::array<T,N>& arr){
    std::array<T, N> indices;
    for (T i = 0; i < N; ++i)
        indices[arr[i]] = i;

    arr = indices;
}

我们仍然使用两倍的空间并对我们的数组进行一些随机排序的写入，但本质上我们只有 2*N 个赋值，而且代码比以前更简单.

We're still using twice the space and doing some randomly ordered writes to our array,but essentially we're down to 2*N assignments, and the code is simpler than before.

或者，我们也可以std::sort，如果我们保留一个副本来进行查找:

Alternatively, we could also std::sort if we keep a copy to do lookups in:

template<typename T, std::size_t N>
void swap_index_value(std::array<T,N>& arr){
    std::sort(arr.begin(), arr.end(), [copy = arr](const T& lhs, const T& rhs) {
        return copy[lhs] < copy[rhs];
    });
}

第一个版本这里，第二个版本这里，std::sort 版本这里

First version here,second version here,std::sort version here

基准测试哪个更快留给读者作为练习;)

Benchmarking which one is faster is left as an exercise to the reader ;)

这篇关于交换向量的值和索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！