查找唯一向量的索引和逆映射

我有一個std::vector<int>重複的值。我可以使用std::unique()和std::vector::erase()找到唯一值，但是如何通過逆映射向量有效地找到索引向量並通過給定唯一值向量構造原始向量。讓我來說明這一點使用的一個示例：查找唯一向量的索引和逆映射

std::vector<int> vec = {3, 2, 3, 3, 6, 5, 5, 6, 2, 6}; 
std::vector<int> uvec = {3, 2, 6, 5}; // vector of unique values 
std::vector<int> idx_vec = {0, 1, 4, 5}; // vector of indices 
std::vector<int> inv_vec = {0, 1, 0, 0, 2, 3, 3, 2, 1, 2}; // inverse mapping

逆映射向量是這樣的，與它的指標可以構建使用唯一向量的原始矢量即

std::vector<int> orig_vec(ivec.size()); // construct the original vector 
std::for_each(ivec.begin(), ivec.end(), 
    [&uvec,&inv_vec,&orig_vec](int idx) {orig_vec[idx] = uvec[inv_vec[idx]];});

以及指數向量是簡單地原始向量中唯一值的首次出現的向量索引。

我的基本解決方案遠沒有效率。它不使用STL算法，最壞的情況是O(n^2)。

template <typename T> 
inline std::tuple<std::vector<T>,std::vector<int>,vector<int>> 
unique_idx_inv(const std::vector<T> &a) { 
    auto size_a = size(a); 
    std::vector<T> uniques; 
    std::vector<int> idx; // vector of indices 
    vector<int> inv(size_a); // vector of inverse mapping 

    for (auto i=0; i<size_a; ++i) { 
     auto counter = 0; 
     for (auto j=0; j<uniques.size(); ++j) { 
      if (uniques[j]==a[i]) { 
       counter +=1; 
       break; 
      } 
     } 
     if (counter==0) { 
      uniques.push_back(a[i]); 
      idx.push_back(i); 
     } 
    } 

    for (auto i=0; i<size_a; ++i) { 
     for (auto j=0; j<uniques.size(); ++j) { 
      if (uniques[j]==a[i]) { 
       inv[i] = j; 
       break; 
      } 
     } 
    } 

    return std::make_tuple(uniques,idx,inv); 
}

這與典型的std::sort+std::erase+std::unique方法（其中的方式只計算唯一值，而不是指標或反向），我得到g++ -O3在我的筆記本下列時間[爲size=10000向量只有一個重複的比較值]

Find uniques+indices+inverse:      145ms 
Find only uniques using STL's sort+erase+unique  0.48ms

當然這兩種方法都是不完全相同，因爲後者一個排序的索引，但仍相信我上面張貼的溶液可以顯着地優化。任何想法我怎麼能做到這一點？

來源

2017-01-22 Tasam Farkie

如果我沒有錯，下面的解決方案應該是O（N日誌（N））

（我已經改變了指標的std::size_t值）

template <typename T> 
inline std::tuple<std::vector<T>, 
        std::vector<std::size_t>, 
        std::vector<std::size_t>> 
unique_idx_inv(const std::vector<T> &a) 
{ 
    std::size_t    ind; 
    std::map<T, std::size_t> m; 
    std::vector<T>   uniques; 
    std::vector<std::size_t> idx; 
    std::vector<std::size_t> inv; 

    inv.reserve(a.size()); 

    ind = 0U; 

    for (std::size_t i = 0U ; i < a.size() ; ++i) 
    { 
     auto e = m.insert(std::make_pair(a[i], ind)); 

     if (e.second) 
     { 
     uniques.push_back(a[i]); 
     idx.push_back(i); 
     ++ind; 
     } 

     inv.push_back(e.first->second); 
    } 

    return std::make_tuple(uniques,idx,inv); 
}

來源

2017-01-23 00:18:00 max66

的O(n^2)源於您的方法可以通過向量中的嵌套循環來識別重複項。然而，要查明一個元素是否已被讀取，排序後的向量或 - imho更好 - 無序映射更合適。因此，如果不在這裏編寫代碼，我會建議使用形式爲

unordered_map<int,int>的無序映射，它可以同時保存唯一值和索引。我不確定你是否仍然需要這些信息的矢量，但是你可以很容易從地圖中獲得這些矢量。

複雜度應降至O(n log(n))。

來源

2017-01-23 00:24:07

查找唯一向量的索引和逆映射

回答

相關問題