IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Trouver les uniques de tuples de dimensions arbitraires


Sujet :

C++

  1. #1
    Membre du Club
    Inscrit en
    Février 2013
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : Février 2013
    Messages : 92
    Points : 49
    Points
    49
    Par défaut Trouver les uniques de tuples de dimensions arbitraires
    Bonjour à toutes et à tous,

    J'ai une grande (10^10 voire 10^15) collection de points dans un espace en d-dimensions (d pouvant prendre pour valeur d={1,2,3,4,...}). Ces points sont des entiers positifs ou négatifs (Z).
    Je cherche simplement à connaitre, dans cette collection et le plus rapidement possible, le nombre de points uniques car de nombreux points sont répétés (valeurs identiques) à des emplacements aléatoires de ma collection.
    Par exemple en dimension d=3 ça donnerait quelque chose comme ça:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    1, -1, 10;
    -1, 50, -224;
    0, 0, 0; 
    -2, -1, 3;
    -1, 1, 10;
    1, -1, 10;
    -1, 50, -224;
    etc.
    Dans cet exemple il y a 5 points uniques (les 1ers et 2emes tuples sont répétés).
    Dans mon soucis de performance, je cherche quelle structure (tuples? list? autre?) serait la plus efficace pour traiter cette question.

    Mon idée première était d'utiliser Amardillo et de stocker simplement les points dans un tableau en d-dimensions (comme dans l'exemple) et de compter les lignes uniques (1 ligne correspond à un tuple), grâce à la commande size(unique(Collection)). Malheureusement, à contrario de Matlab (Armadillo est inspiré de Matlab), unique() est uniquement implémentée pour les éléments d'un vecteur (il ne trouve pas les tuples). J'imagine cependant qu'il doit exister plusieurs solutions efficaces à ce problème (dans la STL ou ailleurs). Mais je ne connais pas suffisamment bien le langage pour m'en sortir de manière performante.

    Merci pour vos éclairages!

  2. #2
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    Juin 2010
    Messages
    7 113
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : Juin 2010
    Messages : 7 113
    Points : 32 958
    Points
    32 958
    Billets dans le blog
    4
    Par défaut
    set ou mieux : unordered_set ?
    Quant à l'efficacité, ça dépendra de ta fonction de hash, et de la quantité de données. Y'a pas de miracles : pour vérifier si la valeur est déjà présente, il faut vérifier si elle l'est ou non dans l'ensemble des données.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  3. #3
    Membre expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    739
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2011
    Messages : 739
    Points : 3 627
    Points
    3 627
    Par défaut
    Il faudrait indiquer comme tu as procédé, parce que std::unique fonctionne très bien avec des collections qui contiennent des tuples. Et pour des comparaisons spécifiques, on peut toujours passer un comparateur comme 3ème paramètre. D'ailleurs, std::unique, comme tous les algorithmes de la STL, se fiche du type de container, ce qui l'intéresse est la catégorie de l'itérateur qu'on lui passe (ForwardIterator ici).

    Mais un des prérequis de std::unique est d'avoir une collection triée. Il faudra probablement utiliser std::sort avant.

    Une autre approche est d'utiliser std::unordered_set (constructeur (2) avec potentiellement une valeur de bucket_count élevée (il faudrait faire des mesures)).

  4. #4
    Membre du Club
    Inscrit en
    Février 2013
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : Février 2013
    Messages : 92
    Points : 49
    Points
    49
    Par défaut
    Merci pour ces retours!
    Et bien j'ai pour l'instant la solution codée en Matlab et une partie en C++ mais je souhaitais savoir vers quelle structure m'orienter avant de commencer à implémenter des tuples ou autres listes.
    Du coup je pars sur des tuples avec un combo std::sort() puit std::unique()
    Edit: je vois que unordered_set est bien efficace aussi, du coup j'ai envie de tester les deux!

  5. #5
    Membre éprouvé
    Femme Profil pro
    ..
    Inscrit en
    Décembre 2019
    Messages
    562
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 94
    Localisation : Autre

    Informations professionnelles :
    Activité : ..

    Informations forums :
    Inscription : Décembre 2019
    Messages : 562
    Points : 1 253
    Points
    1 253
    Par défaut
    Bonjour,

    Actuellement, comment sont stockées toutes ces données ?

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Trouver les éléments unique d'une liste
    Par Loki83 dans le forum Excel
    Réponses: 4
    Dernier message: 27/11/2008, 16h28
  2. Trouver les valeurs uniques d'un vecteur
    Par Ptinéwik dans le forum MATLAB
    Réponses: 3
    Dernier message: 21/01/2008, 17h14
  3. Trouver les redirections dans des traces
    Par severine dans le forum Développement
    Réponses: 3
    Dernier message: 21/04/2004, 19h51
  4. [GUI] Ou trouver les standard ?
    Par Braim dans le forum Windows
    Réponses: 5
    Dernier message: 01/10/2003, 09h13

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo