Je suis en train de mettre en œuvre un algorithme qui implique beaucoup de vérifier si des éléments sont dans un ensemble / liste. J'utilisais J'ai décidé que j'essaierais d'utiliser Toutefois, cette fonction prend environ 2S pour de très petits ensembles (1-3 éléments) Ce qui rend tout mon algorithme inutilisable. La classe personnalisée que j'utilise ressemble à ceci: L'opérateur de comparaison que j'ai mis en œuvre ressemble à ceci: éditer: la fonction de concaténate ne semble pas prendre beaucoup de temps lors de l'exécution, elle ressemble à ceci: std :: vecteur , mais le temps augmentait de manière exponentielle, car le vecteur grandirait. std :: Set Conteneurs Commandez de ne pas avoir à explorer l'ensemble du conteneur pour savoir s'il contient un certain élément.
J'ai mis en place la fonction suivante qui vérifie si un élément fait partie d'un ensemble donné:
3 Réponses :
Votre opérateur Du: P> prend une copie tuple code> peut faire cela: bool operator<(const Node& other) const {
return std::make_tuple(coordinates[0], coordinates[1], coordinates[2]) <
std::make_tuple(other.coordinates[0], other.coordinates[1], other.coordinates[2]);
}
Il y a exactement le problème pour in_set
Tout d'abord, vous pouvez essayer de passer défini comme const & et non dans l'opérateur et P> bool operator<(const Node& other) const
Le vrai problème n'est pas la copie, mais la façon dont l'opérateur
Savez-vous pourquoi il prend tellement de temps p>
concaténate (1, 100000000) code> prend 1,3 seconde sur mon PI de framboise, cette façon de faire est trop lente, et en fait inutile p>Notez aussi que pour le possible. Overflows concaténate em> peut donner le même résultat pour différents nœuds, il est non compatible pour un opérateur p>
Comment le rendre plus rapide? P> BlockQuote>
Vous devez trouver autre chose que ces appels de concaténates pour mettre en œuvre votre Opérateur P>
Quel est votre besoin? est l'ordre dans l'ensemble est important ou peut être remplacé par n'importe quel autre? p>
Il n'est pas obligatoire de créer un identifiant unique pour comparer deux nœuds, comparez-les directement, par exemple: P>
bool operator<(const Node & other) const{ if (coordinates[0] < other.coordinates[0]) return true; if (coordinates[0] >= other.coordinates[0]) return false; if (coordinates[1] < other.coordinates[1]) return true; if (coordinates[1] >= other.coordinates[1]) return false; return (coordinates[2] < other.coordinates[2]); }
Il suffit d'utiliser std :: cravate ou std :: make_tuple ici.
Passez-vous vraiment l'ensemble comme ça? Par valeur? Vous êtes également manquants de demi-colons sur les déclarations de classe, veuillez publier un vrai code compilable réel. Lisez sur la façon dont on crée un exemple de reproductible minimal .
S / exponentiellement / linéairement / peut-être?
En outre, postez définitivement la source de
concaténate .Si vous avez un problème de performance, il est dans votre opérateur
@Storyteller Oui, je suis nouveau à c, devrais-je passer un pointeur à la place?
dans
in_set et votre opérateur
Quelles sont vos données réelles? Il ne faut pas prendre quelques secondes pour passer un petit ensemble
par valeur. Votreconcaténate prendra longtemps sii est petit etj est grand et peut également déborder et causer un comportement non défini. Cela nécessite un exemple de reproductible minimal .Qu'est-ce que
concaténate est censé faire?2 secondes pour exécuter
in_set sur un ensemble d'éléments 1-3 est extrême même avec toutes les inefficacances de votre code. Je soupçonne quelque chose d'autre se passe.Concaténate crée un identifiant INT unique pour chaque nœud pour les rendre facilement comparables
@Codophage Vous n'avez pas besoin de créer un identifiant unique pour comparer deux nœuds, les comparer directement comme ma réponse
C'est XY Problème .
Y Voici comment corriger votre «code> définir WHERE BEST-UTILISERX est un problème de performance de certaines structures de données. Je ne suis pas convaincu queSet est une solution appropriée pourx , je soupçonne qu'une sorte de b-arbre serait un meilleur choix.@Marekr l'ensemble semble la bonne solution parce qu'il dit qu'il recherche beaucoup si un nœud est dans sa séquence
@Codophage j'ai édité ma proposition d'opérateur <, mon précédent était faux
@bruno Comment savez-vous? Connaissez-vous le problème
x ? Je soupçonne un problème de détection de collision en 3 dimensions depuis sonnoeud (code> int Coordinates [3] , donc simpledéfinir est toujours un mauvais choix .@Marekr j'ai édité ma réponse pour expliquer pourquoi ça marche
@bruno à nouveau: Comment savez-vous cela? Vous n'êtes pas
op . Peut-être que vous le connaissez en personne ou à un problème, il est en réalité magnifique avec.@Marekr je ne le connais pas mais il dit Je suis en train de mettre en œuvre un algorithme qui implique beaucoup de vérifier si des éléments sont dans un ensemble / liste alors Savez-vous pourquoi il prend la sorte Beaucoup de temps, et plus important encore, comment le rendre plus rapide? Je lui réponds, non?
Je suis en train de mettre en œuvre l'algorithme d'une étoile pour la recherche de chemin 3D
@Codophage est ma proposition ok pour vous?
La copie faisait causer le problème de la vitesse principale, je vais m'assurer que je vais tester votre correctif pour la concaténation ainsi que Botje pour voir si peut me faire gagner des millisecondes