tags:

views:

60

answers:

2

Howdy folks,

I am using a datatype of std::vector<std::vector<T> > to store a 2D matrix/array. I would like to determine the unique rows of this matrix. I am looking for any advice or pointers on how to go about doing this operation.

I have tried two methods.

Method 1: slightly convoluted. I keep an index for each row with 0/1 indicating whether the row is a duplicate value, and work through the matrix, storing the index of each unique row in a deque. I want to store the results in a <vector<vector<T> >, and so from this deque of indices, I pre-allocate and then assign the rows from the matrix into the return value.

Method 2: Is easier to read, and in many cases faster than method 1. I keep a deque of the unique rows that have been found, and just loop through the rows and compare each row to all the entries in this deque.

I am comparing both of these methods to matlab, and these C++ routines are orders of magnitude slower. Does anyone have any clever ideas on how I might speed this operation up? I am looking to do this operation on matrices that potentially have millions of rows.

I am storing the unique rows in a deque during the loop to avoid the cost of resizing a vector, and then copying the deque to the vector<vector<T> > for the results. I've benchmarked this operation closely, and it is not anywhere near slowing operation down, it accounts for less than .5% of the runtime on a matrix with 100,000 rows for example.

Thanks,

Bob

Here is the code. If anyone is interested in a more complete example showing the usage, drop me a comment and I can put something together.

Method 1:

  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]);
    }
  }

Here is the code for method 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]);
    }
  }
+4  A: 
Billy ONeal
Hi Billy, thanks for the input, I will give this a try right now
reso
@reso: I have updated my answer.
Billy ONeal
Hi Billy, thanks again, this really improved the speed, great advice. The .first() and .second() calls in your code snippets should potentially be replaced with .begin() and .end() to match the functions supported by std::vector. Thanks again!
reso
I suppose swap in sort doesn't make copies of whole arrays, but isn't input copied unnecessarily? Can the OP count for some return value optimization here? Working with indices (if sufficient) should be much more efficient
Maciej Hehl
@Reso: Lol.. brain fart! @Marciej: I assumed destruction of the original was not an acceptable solution to the problem. If you can live with destruction of the inputs, than of course you can pass a reference. Alternately, replace `unique` with `unique_copy` and pass a back_inserter to `unique_copy`. However, with unique_copy you are still destroying the original input because unique_copy (like unique) requires a sorted range.
Billy ONeal
I was rather thinking about the second copy (if created) when returning the result by value. Maybe the return value optimization makes it cheap, I'm not sure about it. Different interface could guarantee the copy is done once. If a vector of indices was created and sorted it would be much cheaper, and even creating a vector of unique rows (if necessary) based on those indices should be cheaper, especially if there is a significant minority of unique rows
Maciej Hehl
@Maciej: I've never used a compiler which would not NRVO that copy here, and I generally prefer returning a value if that results in the most readable code. If you absolutely must guarantee that no copy is made you can pass in the target vector by reference and copy it explicitly.
Billy ONeal
My benchmarks of this seem to indicate that g++ is performing the NRVO optimization here. I usually pass by reference, but in this instance, passing a copy to be "scarified" to the sort+unique routines seem like a very good idea, same with the NRVO. My only concern with passing a return copy, is that passing by to a constructor, i.e. std::vector<std::vector<T> > = getUniqueRows(); is faster than, std::vector<std::vector<T > > x; x = getUniqueRows(); as the latter seems to make a temporary copy.
reso
+2  A: 

You should also consider using hashing, it preserves row ordering and could be faster (amortized O(m*n) if alteration of the original is permitted, O(2*m*n) if a copy is required) than sort/unique -- especially noticeable for large matrices (on small matrices you are probably better off with Billy's solution since his requires no additional memory allocation to keep track of the hashes.)

Anyway, taking advantage of Boost.Unordered, here's what you can do:

#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);
    }
  }
}
vladr
+1 -- do note that my solution will also be faster when there are few duplicated elements even for large inputs. Hashing requires examination of the entire inner vector while the the comparisons used in `sort` often will compare only the first few elements.
Billy ONeal
very good point. `reso` should profile both implementations to see which best suits his application.
vladr
Thanks for the input Vlad. Unfortunately my application has inputs of either two end members: long vectors with lots of repeated values, or instances where the long vectors have nearly zero duplicate values. My original (and highly naive and un-optimal) approaches, seemed to work well for lots of duplicate values, but really blow up when there are a lot of uniques. I will implement this and have a look just to learn the techniques. Thanks!
reso