Déterminer si un non-ordonnée vector<T> a tous les éléments uniques

Profilage mon cpu code a suggéré que je que de passer un long moment de la vérification pour voir si un conteneur contient complètement des éléments uniques. En supposant que j'ai des gros contenant des éléments non triés (avec < et = défini), j'ai deux idées sur la façon dont cela pourrait être fait:

La première à l'aide d'un ensemble:

template <class T>
bool is_unique(vector<T> X) {
  set<T> Y(X.begin(), X.end());
  return X.size() == Y.size();
}

La deuxième boucle sur les éléments:

template <class T>
bool is_unique2(vector<T> X) {
  typename vector<T>::iterator i,j;
  for(i=X.begin();i!=X.end();++i) {
    for(j=i+1;j!=X.end();++j) {
      if(*i == *j) return 0;
    }
  }
  return 1;
}

J'ai testé du mieux que je peux, et de ce que je peux recueillir à partir de la lecture de la documentation sur la STL, la réponse est (comme d'habitude), ça dépend. Je pense que dans le premier cas, si tous les éléments sont uniques, il est très rapide, mais si il y a une grande dégénérescence de l'opération semble prendre en O(N^2). Pour le imbriquée itérateur approche au contraire, cela semble être vrai, il est rapide comme l'éclair si X[0]==X[1] mais prend (à juste titre) O(N^2) si tous les éléments sont uniques.

Est-il une meilleure façon de le faire, peut-être un STL algorithme construit à cet effet? Si non, avez-vous des suggestions à la semaine précédente un peu plus d'efficacité?

  • Si le conteneur ne peut contenir des doublons à tous? Peut-être vous avez besoin d'un jeu, pas un vecteur?
  • Votre mise si is_unique serait plus rapide si elle a pris comme const vector<T>& comme argument, au lieu d'accepter son argument par valeur. De cette façon, vous éviter de faire une copie du vecteur et puis aussi la copie de cette copie dans un ensemble.
  • Neil, le récipient doit d'accès aléatoire (d'où le vecteur) pour d'autres parties du code.
  • Si possible, vous souhaitez peut-être envisager de garder le vecteur trié tout le temps que vous le construire. Que ferait is_unique (si mis en œuvre par std::set ou std::unique) exécuter en temps linéaire. En gardant le vecteur trié, vous répartissez le travail au fil du temps, et d'avoir à "payer" pour une partie du travail qu'une seule fois par élément, plutôt que de prendre un grand succès par devoir tout calculer à chaque fois que vous appelez is_unique.
  • Quel est exactement le type de T?
  • Pouvez-vous définir une fonction de hachage sur votre type d'élément? Si donc, à l'aide d'une table de hachage au lieu de binaire basée sur l'arbre set devrait fonctionner très bien, en particulier si vous effectuez un test d'adhésion sur tous les insérer au lieu d'ajouter tout d'abord et puis de vérifier. Noter que la standard STL n'ont pas de base de hachage récipients, bien hash_set se présente comme une extension, ou de l'utilisation de Boost.
  • En plus de tzaman commentaire, je pense que vous devriez également considérer la taille moyenne de votre jeu de données. Passez-vous le temps de vérifier les collisions en milliers de vecteurs de plusieurs dizaines d'entrées chacun, ou des dizaines de vecteurs de milliers d'entrées de chaque? Lire le papier sur la recherche ou de l'algorithmes de tri écrit dans les 15 dernières années, et il est difficile de ne pas en trouver un qui parle de la façon dont ceci ou cela algorithme dépasse l'actuel champion par tels et tels pour cent dans une liste en particulier de la taille de portée (par exemple, 10k à 50k entrées).

InformationsquelleAutor Hooked | 2010-05-04
  1. 27

    Votre premier exemple devrait être O(N log N) set prend log N fois pour chaque insertion. Je ne pense pas qu'un O plus vite possible.

    Le deuxième exemple est évidemment O(N^2). Le coefficient et l'utilisation de la mémoire est faible, de sorte qu'il pourrait être plus rapide (ou même de la manière la plus rapide) dans certains cas.

    Cela dépend de ce que T est, mais pour le générique de la performance, je vous recommande de trier un vecteur de pointeurs vers les objets.

    template< class T >
bool dereference_less( T const *l, T const *r )
 { return *l < *r; } 

template <class T>
bool is_unique(vector<T> const &x) {
    vector< T const * > vp;
    vp.reserve( x.size() );
    for ( size_t i = 0; i < x.size(); ++ i ) vp.push_back( &x[i] );
    sort( vp.begin(), vp.end(), ptr_fun( &dereference_less<T> ) ); //O(N log N)
    return adjacent_find( vp.begin(), vp.end(),
           not2( ptr_fun( &dereference_less<T> ) ) ) //"opposite functor"
        == vp.end(); //if no adjacent pair (vp_n,vp_n+1) has *vp_n < *vp_n+1
}

    ou dans la STL style,

    template <class I>
bool is_unique(I first, I last) {
    typedef typename iterator_traits<I>::value_type T;
    …

    Et si vous pouvez réorganiser le vecteur d'origine, bien sûr,

    template <class T>
bool is_unique(vector<T> &x) {
    sort( x.begin(), x.end() ); //O(N log N)
    return adjacent_find( x.begin(), x.end() ) == x.end();
}
    • Mettre les choses en tant que pointeurs n'est pas une mauvaise idée. Ce pourrait être appliquée à l'ensemble de base des algorithmes.
    • std::ajacent_find est une bien meilleure idée que std::unique.
    • C'est, de loin, le plus rapide (ou presque) exemple affiché. Serait-il trop vous demander de donner des précisions sur le "STL-style" de sorte que je (et d'autres) pourrait voir comment vous feriez? Aussi l'exécution de votre premier exemple donne le message "error: invalid conversion from ‘const int*’ int*’" sur le &x, retrait de la const semblait faire l'affaire.
    • Ai-je raté quelque chose? Cette édition donne l'erreur: "erreur: pas de match pour les appels d' (std::binary_negate<dereference_less>) (int*&, int*&)’ et ne compile pas.
    • désolé, faut vraiment que j'ai testé. Il y avait un const erreur de justesse (manque un peu de consts plutôt que d'avoir un supplément) et un problème avec le foncteur d'être incompatible avec not2... ici, je suis passé à la ptr_fun foncteur générateur.
    • Le "STL-style" prototype est plus comme la façon dont les fonctions dans <algorithm> sont écrits. Il prend une paire d'itérateurs plutôt que d'un conteneur. Juste remplacer dans ces trois lignes, et vous devriez être bon d'aller. (Mais je n'ai pas le tester ;v) .)
    • Plus rapide Big-O peut être obtenue en utilisant une table de hachage basée set mise en œuvre, au prix d'un certain espace supplémentaire. O(1) insère pour les éléments n == O(n)
    • Merci pour la correction, j'ai beaucoup appris de ce post!
    • correct, j'ai encore oublier les tables de hashage! Cependant la question précise operator< plutôt que d'une fonction de hachage.

    InformationsquelleAutor Potatoswatter
  2. 9

    Vous devez trier le vecteur si vous souhaitez déterminer rapidement si il ne dispose que d'éléments uniques. Sinon le meilleur que vous pouvez faire est de O(n^2) l'exécution, ou O(n log n) exécution avec O(n) l'espace. Je pense que c'est mieux d'écrire une fonction qui suppose l'entrée est trié.

    template<class Fwd>
bool is_unique(In first, In last)
{
    return adjacent_find(first, last) == last;
}

    alors le client trier le vecteur, ou de faire une triés copie du vecteur. Cela va ouvrir une porte pour la programmation dynamique. C'est, si le client a trié les vecteurs dans le passé, alors qu'ils ont la possibilité de maintenir et de se référer à cette triés vecteur afin qu'ils puissent répéter cette opération pour O(n) le temps d'exécution.

    • +1: mieux que std::unique. Aussi la mise en œuvre dans l'esprit de la STL.
    • Sans doute Fwd était censé être In, ou vice-versa?
    InformationsquelleAutor wilhelmtell
  3. 6

    De la bibliothèque standard a std::unique, mais qui serait vous obliger à faire une copie de l'ensemble du conteneur (à noter que dans les deux exemples pour vous faire une copie de l'ensemble du vecteur ainsi, depuis que vous avez inutilement passer le vecteur de la valeur). 

    template <typename T>
bool is_unique(std::vector<T> vec)
{
    std::sort(vec.begin(), vec.end());
    return std::unique(vec.begin(), vec.end()) == vec.end();
}

    Savoir si cela pourrait être plus rapide que l'utilisation d'un std::set serait, comme vous le savez, dépend :-).

    • unique supprime seulement les doublons consécutifs, de sorte que cela ne fonctionne que si le vecteur ont été triés.
    • C'est pourquoi j'ai la copie du vecteur.
    • Asymptotiquement parlant, c'est le même espace et dans le temps les exigences de la is_unique dans la question. Ils sont tous les deux O(n) dans l'espace et le temps O(n log n) dans le temps. C'est-à-dire, leur temps d'exécution sont dominés par le tri (tri explicite dans votre exemple, et le tri interne à std::set dans le cas des OP). Ma suggestion serait d'essayer les deux et de choisir selon ce qui se produit à être plus rapide dans la pratique.
    • Je dois être vieux. Pourquoi ne pouvais-je voir qui? Vous n'avez pas de glisser un edit, juste sous les 5 min. marque, avez-vous?
    • en fait, non, le pire, c'est O(n2), d'exécution et de O(n) l'espace. Le pire des cas de std::sort() est O(n2).
    • n'a pas de pire-cas exigence à tous, il ne avoir la moyenne-cas n log n exigence, et si vous avez vraiment pensé que vous feriez courir dans pervers des cas où vous n'allez pas à obtenir dans le monde réel n log n, vous pouvez utiliser stable_sort(), qui n'ont qu'un n log n la limite supérieure de l'exigence.
    • correct: 25.3.1.1 paragraphe 3. La seule garantie est que la moyenne est de N*log N. Le cplusplus.com site me tromper! cplusplus.com/reference/algorithm/sort dit pire des cas de tri en O(n^2)
    • de Violet-Magenta: c'est parce Que std::sort pouvez utiliser quelque chose comme introsort qui a O(n^2) complexité, tout en std::stable_sort est généralement mis en œuvre à l'aide d'un formulaire de fusion de tri.
    • Je suis venu à la conclusion que cplusplus.com est d'assez mauvaise qualité. J'ai signalé une demi-douzaine des erreurs ou si au cours de la dernière quelques mois et aucun d'entre eux ont été corrigés.
    • C'est stupide rapide pour un type simple <T>==<int>, bien plus rapide que n'importe quel autre exemple (la copie est tellement bas). En général, cela peut ne pas être le cas pour moi, mais je vais devoir garder cet état d'esprit pour une utilisation future!
    • Sérieusement? Faire une erreur n'est pas aussi mauvais que ne pas corriger l'erreur! Ne répondent-ils au moins?
    • Je n'ai pas de réponse à tout, qu'est-ce qui m'énervait. Je n'ai pas l'esprit de rapports de bugs et d'expliquer pourquoi ils ont besoin d'être corrigé, mais si ils ne vont pas à corriger... hein. Cela dit, je l'utilise encore cplusplus.com quand j'ai besoin d'une recherche rapide sur quelque chose 😛
    • la vérité, même ici. Même si Google travaille en votant avec la souris ou le HTML. :s

    InformationsquelleAutor James McNellis
  4. 6

    Est impossible de simplement utiliser un conteneur qui offre cette "garantie" à partir de l'obtenir-aller? Serait-il utile de marquer un double au moment de l'insertion plutôt que à un certain moment dans l'avenir? Quand j'ai voulu faire quelque chose comme cela, c'est la direction que j'ai fait; juste en utilisant le jeu comme le "premier" conteneur, et peut-être la construction d'un vecteur parallèle si j'avais besoin de maintenir l'ordre original, mais bien sûr cela fait quelques hypothèses à propos de la mémoire et du PROCESSEUR de la disponibilité...

    InformationsquelleAutor dash-tom-bang
  5. 6

    Pour une chose que vous pouvez combiner les avantages des deux: arrêter de construire le jeu, si vous l'avez déjà découvert un doublon:

    template <class T>
bool is_unique(const std::vector<T>& vec)
{
    std::set<T> test;
    for (typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
        if (!test.insert(*it).second) {
            return false;
        }
    }
    return true;
}

    BTW, Potatoswatter fait un bon point que, dans le cas générique, vous voudrez peut-être éviter la copie de T, dans ce cas, vous pouvez utiliser un std::set<const T*, dereference_less> à la place.

    Vous pouvez bien sûr potentiellement faire beaucoup mieux si elle n'était pas générique. E. g si vous aviez un vecteur d'entiers de l'aire de répartition connue, vous pouvez simplement marquer dans un tableau (ou même bitset) si un élément existe.

    • Mais c'est encore très cher, car set utilise des allocations dynamiques. Vous êtes essentiellement de la construction d'un set lorsque vous n'en avez pas besoin. Donc la solution est correct mathématiquement, mais cher dans la pratique.
    • Oui, mais quand vous commencez par trier le vecteur, tu vas avoir de faire le tri, qui tombe sous le même scénario des cas les pires que l'OP s #1. Aussi, le tri d'un vecteur peut être coûteux, si T est cher à l'échange. - C'est au sujet de trouver une voie moyenne entre le pire des cas, de l'une ou l'autre approche. Dans l'ensemble, ça dépendra fortement sur les types et la nature des données - comment souvent il sont ou ne sont pas des doublons.
    • L'ajout de tous les éléments d'un vecteur et de tri, il est généralement plus rapide que l'insertion d'éléments et de maintien de l'ordre...
    • J'aimerais être d'accord avec WilhelmTell basé sur le test d'un des cas les pires environnement où tous les éléments sont déjà triés. Dans ce cas, il semble fonctionner beaucoup plus lent puis le premier exemple, lorsque, en théorie, il devrait être d'environ la même vitesse.
    • Ou tout simplement créer un autre vecteur de même longueur que le vecteur d'origine, mais elle est composée de T* éléments. Ensuite trier les via un déréférencement.
    • Ou faire un std::sort sur le contenant d'origine avec un prédicat qui agit normal, mais déclenche une exception dès qu'il compare deux égaux (et pas seulement l'équivalent, bien que vous pouvez le faire aussi) des valeurs. Si vous attrapez l'exception alors vous savez qu'il n'est pas unique déjà, sinon il est unique.

    InformationsquelleAutor UncleBens
  6. 2

    Vous pouvez utiliser std::unique, mais il exige de la gamme à être triés d'abord:

    template <class T>
bool is_unique(vector<T> X) {
  std::sort(X.begin(), X.end());
  return std::unique(X.begin(), X.end()) == X.end();
}

    std::unique modifie la séquence et retourne un itérateur à la fin de la série unique, donc si c'est encore la fin du vecteur, alors il doit être unique.

    Cela fonctionne en nlog(n); le même que votre exemple de l'ensemble. Je ne pense pas que vous pouvez théoriquement garantie à le faire plus vite, bien que l'utilisation de C++0x std::unordered_set au lieu de std::set serait-il le faire, prévue dans le temps linéaire - mais qui nécessite que vos éléments hashable ainsi que d'avoir operator == définies, ce qui pourrait ne pas être si facile.

    Aussi, si vous n'êtes pas modifier le vecteur dans votre exemple, vous souhaitez améliorer les performances en passant par la const de référence, afin de ne pas faire inutilement copie de celui-ci.

    InformationsquelleAutor Peter
  7. 2

    Si je peux ajouter mon propre 2 cents.

    Tout d'abord, comme @Potatoswatter a fait remarquer, à moins que vos éléments sont à bas prix pour copier (intégré/petites Gousses), vous aurez envie d'utiliser des pointeurs sur les éléments d'origine, plutôt que de les copier.

    Deuxième, il y a 2 stratégies disponibles.

    1. Assurez-vous simplement qu'il n'y a pas de double inséré dans la première place. Cela signifie, bien sûr, le contrôle de l'insertion, qui est généralement assuré par la création d'une classe dédiée (avec le vecteur d'attributs).
    2. Chaque fois que la propriété est nécessaire, vérifier les doublons

    Je dois l'avouer, je pencherais vers le premier. L'Encapsulation, la séparation claire des responsabilités et tout ça.

    De toute façon, il y a un certain nombre de façons, selon les besoins. La première question est:

    • devons-nous laisser les éléments de la vector dans un ordre particulier ou peut-on les "gâcher" avec eux ?

    Si l'on peut mess avec eux, je voudrais vous suggérons de garder la vector triés: Loki::AssocVector devrait vous obtenir a commencé.
    Si non, alors nous avons besoin de garder un index sur la structure afin d'assurer cette propriété... attendez une minute: Boost.MultiIndex à la rescousse ?

    Troisièmement: comme vous l'avez remarqué vous-même, une simple recherche linéaire doublé le rendement d'un O(N2) la complexité en moyenne, ce qui n'est pas bon.

    Si < est déjà défini, alors que le tri est évidente, avec son O(N log N) la complexité.
    Il pourrait également être la peine de faire T Hashable, car un std::tr1::hash_set pourrait donner un meilleur temps (je sais, vous avez besoin d'un RandomAccessIterator, mais si T est Hashable, alors il est facile d'avoir T* Hashable d' 😉 )

    Mais en fin de compte, le vrai problème ici, c'est que nos conseils sont nécessaires générique parce que nous manquons de données.

    • Qu'est-ce que T, avez-vous l'intention de l'algorithme générique ?
    • Quel est le nombre d'éléments ? 10, 100, 10.000, 1.000.000 ? Parce que la complexité asymptotique est une sorte de discutable lorsque l'on traite avec quelques centaines....
    • Et bien sûr: pouvez-vous vous assurer de l'unicité au moment de l'insertion ? Pouvez-vous modifier le vecteur lui-même ?
    InformationsquelleAutor Matthieu M.
  8. 1

    Bien, votre premier ne devrait prendre N log(N), donc c'est clairement le meilleur scénario de la pire éventualité pour cette application.

    Toutefois, vous devriez être en mesure de mieux dans le meilleur des cas, si vous vérifiez que vous ajoutez quelque chose à l'ensemble:

    template <class T>
bool is_unique3(vector<T> X) {
  set<T> Y;
  typename vector<T>::const_iterator i;
  for(i=X.begin(); i!=X.end(); ++i) {
    if (Y.find(*i) != Y.end()) {
      return false;
    }
    Y.insert(*i);
  }
  return true;
}

    Ce qui devrait avoir O(1) meilleur des cas, O(N log(N)) pire des cas, et la moyenne des cas, dépend de la distribution des intrants.

    InformationsquelleAutor clahey
  9. 1

    Si le type T que Vous stockez dans Votre vecteur est grande et la copie c'est cher, envisager la création d'un vecteur de pointeurs ou des itérateurs pour Votre les éléments du vecteur. Tri sur la base de l'élément pointé, puis vérifier l'unicité.

    Vous pouvez également utiliser les std::set pour que. Le modèle ressemble à ceci

    template <class Key,class Traits=less<Key>,class Allocator=allocator<Key> > class set

    Je pense que Vous pouvez fournir des Traits de paramètre et d'insérer des premières indications pour la vitesse ou de mettre en œuvre une simple classe wrapper pour les pointeurs avec < opérateur de.

    Ne pas utiliser le constructeur pour l'insertion dans le jeu. Utiliser la méthode d'insertion. La méthode (l'un des surcharges) a une signature

    pair <iterator, bool> insert(const value_type& _Val);

    En vérifiant le résultat (second membre), Vous pouvez souvent de détecter les doublons d'autant plus vite que si Vous avez inséré tous les éléments.

    InformationsquelleAutor Maciej Hehl
  10. 1

    Dans la (très) cas particulier de tri des valeurs discrètes avec un, pas trop grand, valeur maximale N.

    Vous devriez être en mesure de commencer un seau de tri et de simplement de vérifier que le nombre de valeurs dans chaque seau est inférieur à 2. 

    bool is_unique(const vector<int>& X, int N)
{
  vector<int> buckets(N,0);
  typename vector<int>::const_iterator i;
  for(i = X.begin(); i != X.end(); ++i)
    if(++buckets[*i] > 1)
      return false;
  return true;
}

    La complexité de ce serait O(n).

    InformationsquelleAutor log0
  11. 0

    À l'aide de l'actuel C++ conteneurs standard, vous avez une bonne solution dans votre premier exemple. Mais si vous pouvez utiliser une table de hachage contenant, vous pourriez être en mesure de faire mieux, comme le hachage ensemble des nO(1) au lieu de nO(log n) pour un ensemble standard. Bien sûr, tout dépendra de la taille de n et de votre bibliothèque particulière de mise en œuvre.

    • Une table de hachage va vous donner grand-thêta de 1 et O(n^2).
    • Que... n'est-ce pas son droit. Soins à partager vos calculs? L'insertion dans une table de hachage est censé être en O(n) amorti. En supposant que votre table de hachage est un moyen de détecter les collisions, vous devriez le savoir le temps que vous avez inséré le dernier élément s'il y a une collision. La seule façon que je peux penser à faire en O (N^2) si vous suppose que le vecteur vérifié pour les collisions, sur chaque insert (dont je ne pense pas que a fait partie de la question), et uniquement si il a jeté la carte après chaque mise à jour du vecteur.
    • Je n'ai aucune idée de ce que cela signifie dans mon commentaire. C'est O(n), et je blâme le chat pour cette faute de frappe.
    InformationsquelleAutor Mark Ransom