1

我正在寻找一种在 C++ 中构建多个向量联合的快速方法。

更具体地说：我有一组向量（通常是 15-20 vectors，有几千个无符号整数；总是排序且唯一的，因此它们也可以是std::set）。对于每个阶段，我选择其中的一些（通常是 5-10 个）并构建一个联合向量。比我保存联合向量的长度并选择其他一些向量。这将进行数千次。最后我只对最短联合向量的长度感兴趣。

Small example: 

V1: {0, 4, 19, 40}
V2: {2, 4, 8, 9, 19}
V3: {0, 1, 2, 4, 40}
V4: {9, 10} 

// The Input Vectors V1, V2 … are always sorted and unique (could also be an std::set) 

Choose V1 , V3; 
Union Vector = {0, 1, 2, 4, 19, 40} -> Size = 6; 

Choose V1, V4; 
Union Vector = {0,4, 9, 10, 19 ,40} -> Size = 6; 

… and so on …

目前我正在使用std::set_union，但我确信一定有更快的方法。

vector< vector<uint64_t>> collection; 
vector<uint64_t> chosen; 

for(unsigned int i = 0; i<chosen->size(); i++) {
    set_union(collection.at(choosen.at(i)).begin(),
              collection.at(choosen.at(i)).end(),
              unionVector.begin(),
              unionVector.end(),
              back_inserter(unionVectorTmp));
    unionVector.swap(unionVectorTmp);
    unionVectorTmp.clear();
}

我很感激每一个参考。

编辑 27.04.2017 一个新想法：

     unordered_set<unsigned int> unionSet;
     unsigned int counter = 0;

     for(const auto &sel : selection){
        for(const auto &val : sel){
            auto r = unionSet.insert(val);
            if(r.second){
                counter++;
            }
        }
    }
4

3 回答 3

2

如果它们已排序，您可以在运行时滚动您自己的 O(N+M)。否则，您可以使用具有类似运行时的哈希表

于 2017-04-26T15:07:31.993 回答
0

无需创建整个联合向量。您可以通过保留迭代器列表并适当地比较/递增它们来计算所选向量中唯一元素的数量。

这是伪代码：

int countUnique(const std::vector<std::vector<unsigned int>>& selection)
{
  std::vector<std::vector<unsigned int>::const_iterator> iters;
  for (const auto& sel : selection) {
    iters.push_back(sel.begin());
  }
  auto atEnd = [&]() -> bool {
    // check if all iterators equal end
  };
  int count = 0;
  while (!atEnd()) {
    const int min = 0; // find minimum value among iterators

    for (size_t i = 0; i < iters.size(); ++i) {
      if (iters[i] != selection[i].end() && *iters[i] == min) {
        ++iters[i];
      }
    }

    ++count;
  }
  return count;
}

这使用了您的输入向量已排序并且仅包含唯一元素的事实。

这个想法是在每个选定的向量中保留一个迭代器。这些迭代器中的最小值是联合向量中的下一个唯一值。然后我们递增所有值等于该最小值的迭代器。我们重复此操作，直到所有迭代器都位于所选向量的末尾。

于 2017-04-26T16:12:25.530 回答
0

C++98 中事实上的方法是set_intersection，但是使用 c++11（或 TR1）你可以去unordered_set，只要对初始向量进行排序，你就会有一个很好的 O(N) 算法。

  1. 用你的第一个向量构造一个 unordered_set
  2. 检查第二个向量的元素是否在集合中

这样的事情会做：

std::unordered_set<int> us(std::begin(v1), std::end(v1));
auto res = std::count_if(std::begin(v2), std::end(v2), [&](int n) {return us.find(n) != std::end(us);}
于 2017-04-26T15:49:41.717 回答