如何有效地比较矢量与C++？

Question

我需要C++中的微优化建议用于矢量比较函数,它比较两个向量的相等性和元素的顺序无关紧要.

template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
  int n = a.size();
  std::vector<bool> free(n, true);
  for (int i = 0; i < n; i++) {
    bool matchFound = false;
    for (int j = 0; j < n; j++) {
      if (free[j] && a[i] == b[j]) {
        matchFound = true;
        free[j] = false;
        break;
      }
    }
    if (!matchFound) return false;
  }
  return true;
}

这个功能被大量使用,我正在考虑优化它的可能方法.你能给我一些建议吗？顺便说一句,我使用的是C++ 11.

谢谢

Answer 1

它只是意识到这个代码只做了一种"设置等效"检查(现在我看到你确实这么说,我是一个糟糕的读者!).这可以更简单地实现

template <class T>
static bool compareVectors(vector<T> a, vector<T> b)
{
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    return (a == b);
}

您需要包含标题algorithm.

如果向量总是大小相同,则可能需要在方法的开头添加断言:

assert(a.size() == b.size());

如果您错误地执行了不等长度的此操作,这对于调试程序非常方便.

否则,如果矢量长度不等,则矢量不能相同,所以只需添加即可

if ( a.size() != b.size() )
{
   return false;
}

在排序说明之前.这将为您节省大量时间.

这在技术上的复杂性是O(n*log(n))因为它主要依赖于(通常)复杂性的排序.这比你的O(n^2)方法更好,但由于需要的副本可能会更糟.如果您的原始矢量可能被排序,这是无关紧要的.

如果你想坚持你的方法,但调整它,这里是我的想法:

你可以使用std::find这个:

template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
  const size_t n = a.size(); // make it const and unsigned!
  std::vector<bool> free(n, true);
  for ( size_t i = 0; i < n; ++i )
  {
      bool matchFound = false;
      auto start = b.cbegin();
      while ( true )
      {
          const auto position = std::find(start, b.cend(), a[i]);
          if ( position == b.cend() )
          {
              break; // nothing found
          }
          const auto index = position - b.cbegin();
          if ( free[index] )
          {
             // free pair found
             free[index] = false;
             matchFound = true;
             break;
          }
          else
          {
             start = position + 1; // search in the rest
          }
      }
      if ( !matchFound )
      {
         return false;
      }
   }
   return true;
}

另一种可能性是更换结构以存储自由位置.您可以尝试std::bitset或仅将已使用的索引存储在向量中,并检查该索引向量中是否存在匹配.如果此函数的结果通常是相同的(因此大部分都是真的或大多数是假的),您可以优化数据结构以反映这一点.例如,如果结果通常是假的,我会使用已使用索引的列表,因为可能只需要存储少量索引.

此方法与您的方法具有相同的复杂性.使用std :: find搜索事物有时比手动搜索更好.(例如,如果数据已排序且编译器知道它,则可以是二进制搜索).

Answer 2

您可以概率地比较O(n)中的两个未排序向量(u,v):

计算:

U= xor(h(u[0]), h(u[1]), ..., h(u[n-1]))
V= xor(h(v[0]), h(v[1]), ..., h(v[n-1]))

如果U == V则矢量可能相等.

h(x)是任何非加密哈希函数 - 例如MurmurHash.(加密功能也可以,但通常会更慢).

(即使没有散列,这也可以工作,但是当值具有相对较小的范围时,它将不那么稳健).

对于许多实际应用来说,128位散列函数就足够了.

Answer 3

我注意到大多数提出的解决方案涉及输入向量的排序.我认为排序数组计算更多的是评估两个向量相等的严格必要条件(如果输入向量是常数,则需要复制制作).另一种方法是构建一个关联容器来计算每个向量中的元素...也可以在parrallel中减少两个向量.在非常大的向量的情况下,可以提供一个很好的加速.

template <typename T>  bool compareVector(const std::vector<T> &  vec1, const std::vector<T> & vec2) {
    if (vec1.size() != vec2.size())
        return false ;

    //Here we assuame that T is hashable ...
    auto count_set =  std::unordered_map<T,int>();

    //We count the element in each vector...
    for (unsigned int count = 0 ; count <  vec1.size();++count)
    {
        count_set[vec1[count]]++;
        count_set[vec2[count]]--;
    } ;

    // If everything balance out we should have zero everywhere
    return std::all_of(count_set.begin(),count_set.end(),[](const std::pair<T,int> p) { return p.second == 0 ;});

}

这种方式取决于您的hashsing函数的性能,我们可能会得到booth矢量长度的线性复杂度(vs n*logn与排序).NB代码可能有一些bug,确实有时间检查它...

基于这种比较两种向量与基于排序的比较的方法我得到ubuntu 13.10,vmware core i7 gen 3:

通过计数比较500个元素的200个向量需要0.184113秒

通过排序比较500个元素的200个向量需要0.276409秒

通过计数比较1000个元素的200个向量需要0.359848秒

通过排序比较1000个元素的200个向量需要0.559436秒

通过计数比较5000个元素的200个向量需要1.78584秒

通过排序比较200个5000个元素的矢量需要2.97983秒