c++ - 确定二维数组的唯一行 (vector>)

Question

我正在使用 std::vector<std::vector<T> > 数据类型来存储二维矩阵/数组。我想确定这个矩阵的唯一行。我正在寻找有关如何进行此操作的任何建议或指示。

我试过两种方法。

方法一:略显复杂。我用 0/1 为每一行保留一个索引，指示该行是否为重复值，然后遍历矩阵，将每个唯一行的索引存储在 deque 中。我想将结果存储在 <vector<vector<T> > 中，因此从这个索引双端队列中，我预先分配并将矩阵中的行分配给返回值。

方法 2:更容易阅读，并且在许多情况下比方法 1 更快。我保留了一个已找到的唯一行的双端队列，然后循环遍历这些行并将每一行与 deque 中的所有条目进行比较.

我正在将这两种方法与 matlab 进行比较，这些 C++ 例程要慢几个数量级。有没有人对我如何加快此操作有任何聪明的想法？我希望对可能有数百万行的矩阵执行此操作。

我在循环期间将唯一行存储在双端队列中以避免调整 vector 大小的成本，然后将 deque 复制到 vector<vector<T> > 以获得结果。我已经仔细地对这个操作进行了基准测试，它几乎不会减慢操作速度，例如，在一个有 100,000 行的矩阵上，它只占不到 0.5% 的运行时间。

谢谢，

鲍勃

这是代码。如果有人对显示用法的更完整示例感兴趣，请给我留言，我可以将它们放在一起。

方法一:

  template <typename T>
      void uniqueRows( const std::vector<std::vector<T> > &A,
                       std::vector<std::vector<T> > &ret) {
    // Go through a vector<vector<T> > and find the unique rows
    // have a value ind for each row that is 1/0 indicating if a value
    // has been previously searched.

    // cur : current item being compared to every item
    // num : number of values searched for.  Once all the values in the
    //  matrix have been searched, terminate.

    size_t N = A.size();
    size_t num=1,cur=0,it=1;
    std::vector<unsigned char> ind(N,0);
    std::deque<size_t> ulist;  // create a deque to store the unique inds

    ind[cur] = 1;
    ulist.push_back(0); // ret.push_back(A[0]);

    while(num < N ) {

      if(it >= N ) {
        ++cur;   // find next non-duplicate value, push back
        while(ind[cur])
          ++cur;

        ulist.push_back(cur); //ret.push_back(A[cur]);
        ++num;
        it = cur+1; // start search for duplicates at the next row

        if(it >= N && num == N)
          break;
      }

      if(!ind[it] && A[cur]==A[it]) {        
        ind[it] = 1; // mark as duplicate
        ++num;
      }
      ++it;
    } // ~while num

    // loop over the deque and .push_back the unique vectors    
    std::deque<size_t>::iterator iter;
    const std::deque<size_t>::iterator end = ulist.end();
    ret.reserve(ulist.size());

    for(iter= ulist.begin(); iter != end; ++iter) {
      ret.push_back(A[*iter]);
    }
  }

方法2的代码如下:

  template <typename T>
      inline bool isInList(const std::deque< std::vector<T> > &A,
                    const std::vector<T> &b) {
    typename std::deque<std::vector<T> >::const_iterator it;
    const typename std::deque<std::vector<T> >::const_iterator end = A.end();

    for(it = A.begin(); it != end; ++it) {
      if(*it == b)
        return true;
    }
    return false;
  }

  template <typename T>
  void uniqueRows1(const::std::vector<std::vector<T> > &A,
                   std::vector<std::vector<T> > &ret) {    
    typename std::deque<std::vector<T> > ulist;
    typename std::vector<std::vector<T> >::const_iterator it = A.begin();
    const typename std::vector<std::vector<T> >::const_iterator end = A.end();

    ulist.push_back(*it);

    for(++it; it != end; ++it) {
      if(!isInList(ulist,*it)) {
        ulist.push_back(*it);
      }
    }
    ret.reserve(ulist.size());

    for(size_t i = 0; i != ulist.size(); ++i) {
      ret.push_back(ulist[i]);
    }
  }

Answer 1

您还应该考虑使用哈希，它保留行顺序 并且可以更快(摊销O(m *n) 如果允许更改原件，O(2*m*n) 如果需要拷贝)比 排序/unique——对于大矩阵尤其明显(在小矩阵上，你可能最好使用 Billy 的解决方案，因为他不需要额外的内存分配来跟踪哈希值。)

反正趁着Boost.Unordered ，这是您可以执行的操作:

#include <vector>
#include <boost/foreach.hpp>
#include <boost/ref.hpp>
#include <boost/typeof/typeof.hpp>
#include <boost/unordered_set.hpp>

namespace boost {
  template< typename T >
  size_t hash_value(const boost::reference_wrapper< T >& v) {
    return boost::hash_value(v.get());
  }
  template< typename T >
  bool operator==(const boost::reference_wrapper< T >& lhs, const boost::reference_wrapper< T >& rhs) {
    return lhs.get() == rhs.get();
  }
}

// destructive, but fast if the original copy is no longer required
template <typename T>
void uniqueRows_inplace(std::vector<std::vector<T> >& A)
{
  boost::unordered_set< boost::reference_wrapper< std::vector< T > const > > unique(A.size());
  for (BOOST_AUTO(it, A.begin()); it != A.end(); ) {
    if (unique.insert(boost::cref(*it)).second) {
      ++it;
    } else {
      A.erase(it);
    }
  }
}

// returning a copy (extra copying cost)
template <typename T>
void uniqueRows_copy(const std::vector<std::vector<T> > &A,
                 std::vector< std::vector< T > > &ret)
{
  ret.reserve(A.size());
  boost::unordered_set< boost::reference_wrapper< std::vector< T > const > > unique;
  BOOST_FOREACH(const std::vector< T >& row, A) {
    if (unique.insert(boost::cref(row)).second) {
      ret.push_back(row);
    }
  }
}