交换向量的值和索引

交换向量的值和索引

本文介绍了交换向量的值和索引的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个 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 ;)

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

07-23 20:58