我必須執行以下任務。采取 a std::vector<float>，按降序對元素進行排序，并具有將未排序元素映射到已排序元素的索引。請注意，順序真的很重要：我需要一張地圖，給定未排序向量中的第 i 個元素，告訴我該元素在排序的向量中的位置。反之亦然已經以一種非常聰明的方式（通過 c lambdas）實作，例如，這里：C 排序和跟蹤索引。盡管如此，我還是找不到一種同樣聰明的方法來執行“逆向”任務。我想找到一種快速的方法，因為這種映射必須執行多次，并且向量的大小很大。
請在下面找到一個簡單的示例，說明我需要實作的目標以及我的（可能不是最佳的，因為它依賴于std::find）問題的解決方案。這是執行此任務的最快速/最有效的方式嗎？如果沒有，是否有更好的解決方案？
例子
起始向量：v = {4.5, 1.2, 3.4, 2.3}
排序向量：v_s = {4.5, 3.4, 2.3, 1.2}
我想要什么：map = {0, 3, 1, 2}
我不想要什么：map = {0, 2, 3, 1}
我的解決方案
template <typename A> std::vector<size_t> get_indices(std::vector<A> & v_unsorted, std::vector<A> & v_sorted) {
std::vector<size_t> idx;
for (auto const & element : v_unsorted) {
typename std::vector<A>::iterator itr = std::find(v_sorted.begin(), v_sorted.end(), element);
idx.push_back(std::distance(v_sorted.begin(), itr));
}
return idx;
}
非常感謝您的時間，干杯！
uj5u.com熱心網友回復：
您可以使用下面的代碼。
我的版本get_indices執行以下操作：
使用類似于您在帖子中提到的鏈接中的代碼（C 排序和跟蹤索引）創建索引映射的向量sorted -> unsorted 。
然后通過遍歷這些索引一次，創建排序向量，最終索引映射unsorted -> sorted。
復雜度是O(n * log(n))，因為排序是在 O(n * log(n)) 中完成的，并且最終的遍歷是線性的。
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
template <typename T>
std::vector<size_t> get_indices(std::vector<T> const & v_unsorted, std::vector<T> & v_sorted)
{
std::vector<size_t> idx_sorted2unsorted(v_unsorted.size());
std::iota(idx_sorted2unsorted.begin(), idx_sorted2unsorted.end(), 0);
// Create indices mapping (sorted -> unsorted) sorting in descending order:
std::stable_sort(idx_sorted2unsorted.begin(), idx_sorted2unsorted.end(),
[&v_unsorted](size_t i1, size_t i2)
{ return v_unsorted[i1] > v_unsorted[i2]; }); // You can use '<' for ascending order
// Create final indices (unsorted -> sorted) and sorted array:
std::vector<size_t> idx_unsorted2sorted(v_unsorted.size());
v_sorted.resize(v_unsorted.size());
for (size_t i = 0; i < v_unsorted.size(); i)
{
idx_unsorted2sorted[idx_sorted2unsorted[i]] = i;
v_sorted[i] = v_unsorted[idx_sorted2unsorted[i]];
}
return idx_unsorted2sorted;
}
int main()
{
std::vector<double> v_unsorted{ 4.5, 1.2, 3.4, 2.3 };
std::vector<double> v_sorted;
std::vector<size_t> idx_unsorted2sorted = get_indices(v_unsorted, v_sorted);
for (auto const & i : idx_unsorted2sorted)
{
std::cout << i << ", ";
}
return 0;
}
輸出：
0, 3, 1, 2,
uj5u.com熱心網友回復：
一旦你有了從排序索引到未排序索引的映射，你只需要一個回圈來反轉它。
我正在構建此答案的代碼：https ://stackoverflow.com/a/12399290/4117728 。它提供了一個函式來獲取你不想要的向量：
#include <iostream> #include <vector> #include <numeric> // std::iota #include <algorithm> // std::sort, std::stable_sort using namespace std; template <typename T> vector<size_t> sort_indexes(const vector<T> &v) { // initialize original index locations vector<size_t> idx(v.size()); iota(idx.begin(), idx.end(), 0); // sort indexes based on comparing values in v // using std::stable_sort instead of std::sort // to avoid unnecessary index re-orderings // when v contains elements of equal values stable_sort(idx.begin(), idx.end(), [&v](size_t i1, size_t i2) {return v[i1] < v[i2];}); return idx; }
對向量進行排序是O(N logN)您的代碼呼叫findN 次，結果為O(N*N). 另一方面，添加單個回圈只是線性的，因此排序加上回圈仍然是O(N log N).
int main() {
std::vector<double> unsorted{4.5, 1.2, 3.4, 2.3};
auto idx = sort_indexes(unsorted);
for (auto i : idx) std::cout << unsorted[i] << "\n";
// the vector you do not want
for (auto i : idx) std::cout << i << "\n";
// invert it
std::vector<size_t> idx_inverse(idx.size());
for (size_t i=0;i<idx.size(); i) idx_inverse[ idx[i] ] = i;
// the vector you do want
for (auto i : idx_inverse) std::cout << i << "\n";
}
現場演示
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/489014.html