Détermination des lignes uniques d'un tableau 2D (vecteur <vector<T>>)

Question

J'utilise un type de données de std::vector<std::vector<T> > pour stocker une matrice/matrice 2D. Je voudrais déterminer les rangées uniques de cette matrice. Je suis à la recherche de conseils ou de conseils sur la façon de faire cette opération.

J'ai essayé deux méthodes.

Méthode 1: légèrement convoluté. Je garde un index pour chaque ligne avec 0/1 indiquant si la ligne est une valeur dupliquée, et travaille à travers la matrice, en stockant l'index de chaque ligne unique dans un deque. Je veux stocker les résultats dans un <vector<vector<T> >, et donc à partir de cette liste d'indices, je pré-allouer, puis affecter les lignes de la matrice dans la valeur de retour. Méthode 2: Est plus facile à lire, et dans de nombreux cas plus rapide que la méthode 1. Je garde une trace des lignes uniques qui ont été trouvées, et je fais juste une boucle dans les lignes et compare chaque ligne à toutes les entrées de cette deque.

Je compare ces deux méthodes à matlab, et ces routines C++ sont plus lentes. Est-ce que quelqu'un a des idées intelligentes sur la façon dont je pourrais accélérer cette opération? Je cherche à faire cette opération sur des matrices qui ont potentiellement des millions de lignes.

Je stocke les lignes uniques dans une deque pendant la boucle pour éviter le coût de redimensionner un vecteur, puis en copiant le deque au vector<vector<T> > pour les résultats. J'ai comparé cette opération de près, et elle ne ralentit pas l'opération, elle représente moins de 0,5% de l'exécution sur une matrice de 100 000 lignes par exemple.

Merci,

Bob

Voici le code. Si quelqu'un est intéressé par un exemple plus complet montrant l'utilisation, laissez-moi un commentaire et je peux mettre quelque chose ensemble.

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

Voici le code pour la méthode 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

Vous devriez également envisager d'utiliser le hachage, il conserve Ordre des ligneset pourrait être plus rapide (amorti O(m*n) si la modification du l'original est permis, O(2*m*n) si une copie est requise) que sort/unique - particulièrement notable pour les grandes matrices (. Sur les petites matrices que vous êtes probablement mieux avec la solution de Billy depuis son nécessite pas d'allocation de mémoire supplémentaire pour garder la trace des hash)

Quoi qu'il en soit, en profitant de Boost.Unordered, voici ce que vous pouvez ne:

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

Answer 2

EDIT: J'ai oublié std :: vector définit déjà operator< et operator== si vous avez besoin même pas utiliser que:

template <typename t> 
std::vector<std::vector<t> > GetUniqueRows(std::vector<std::vector<t> > input) 
{ 
    std::sort(input.begin(), input.end()); 
    input.erase(std::unique(input.begin(), input.end()), input.end()); 
    return input; 
} 

utilisation std::unique en concert avec un foncteur personnalisé qui appelle std::equal sur les deux vecteurs.

std::unique exige que l'entrée soit triée en premier. Utilisez un foncteur personnalisé appelant std::lexicographical_compare sur l'entrée des deux vecteurs. Si vous devez récupérer la sortie non enregistrée, vous devez stocker l'ordre existant d'une manière ou d'une autre. Cela permettra d'atteindre la complexité M * n log pour l'opération de tri (où M est la longueur des vecteurs internes, n est le nombre de vecteurs internes), tandis que l'appel std::unique prendra m*n.

Pour comparaison, vos deux approches existantes sont m * n^2 fois.

EDIT: Exemple:

template <typename t> 
struct VectorEqual : std::binary_function<const std::vector<t>&, const std::vector<t>&, bool> 
{ 
    bool operator()(const std::vector<t>& lhs, const std::vector<t>& rhs) 
    { 
     if (lhs.size() != rhs.size()) return false; 
     return std::equal(lhs.first(), lhs.second(), rhs.first()); 
    } 
}; 

template <typename t> 
struct VectorLess : std::binary_function<const std::vector<t>&, const std::vector<t>&, bool> 
{ 
    bool operator()(const std::vector<t>& lhs, const std::vector<t>& rhs) 
    { 
     return std::lexicographical_compare(lhs.first(), lhs.second(), rhs.first(), rhs.second()); 
    } 
}; 

template <typename t> 
std::vector<std::vector<t> > GetUniqueRows(std::vector<std::vector<t> > input) 
{ 
    std::sort(input.begin(), input.end(), VectorLess<t>()); 
    input.erase(std::unique(input.begin(), input.end(), VectorEqual<t>()), input.end()); 
    return input; 
}