J'ai une opération qui génère en permanence des solutions aléatoires (std::vector<float>). J'évalue les solutions par rapport à une fonction mathématique pour voir leur utilité (float). Je souhaite conserver en permanence les 10 meilleures solutions. Quelle serait la manière la plus efficace de faire cela en C ++?

J'ai besoin de stocker à la fois les solutions (std :: vector) et leur utilité (float). J'effectue plusieurs centaines de milliers d'évaluations et j'ai donc besoin d'une solution efficace.

Edit: Je connais les méthodes de tri. Je recherche des méthodes autres que le tri et le stockage des valeurs. Vous recherchez de meilleures structures de données, le cas échéant.

c++
2
Anthony M Benedict 24 août 2020 à 01:51

2 réponses

Meilleure réponse
  1. Vous évaluez la fonction float score() pour le std::vector<T> solution actuel, vous les stockez dans un std::pair<vector<T>, float>.
  2. Vous utilisez un std::priority_queue< pair<vector<T>, float> > pour stocker les 10 meilleurs solution en fonction de leur score et du score lui-même. std::priority_queue est un tas, il vous permet donc d'extraire sa valeur maximale en fonction d'une fonction compare que vous pouvez configurer pour comparer score_a < score_b.
  3. Stockez les 10 premières paires, puis pour chaque nouvelle, comparez-la avec le haut du tas, si score(new) > score(10th) puis insert(new) dans le priority_queue p, et {{X4} } pour se débarrasser de l'ancien 10e élément.
  4. Vous continuez à faire cela dans une boucle jusqu'à ce que vous soyez à court de vector<T> solution s.
1
Lingo 23 août 2020 à 23:11

Avoir un vecteur de paire, où paire a 1 élément comme solution et un autre élément comme utilité. Ensuite, écrivez un comparateur personnalisé pour comparer les éléments du vecteur.

Ajoutez enfin l'élément, puis triez ce vecteur et supprimez le dernier élément.

Comme @ user4581301 l'a mentionné dans les commentaires, pour 10 éléments, vous n'avez pas besoin de trier. Traversez simplement le vecteur à chaque fois, ou vous pouvez également effectuer une insertion ordonnée dans le vecteur.

Voici quelques liens pour vous aider:

https://www.geeksforgeeks.org/sorting-vector-of-pairs-in-c-set-1-sort-by-first-and-second/

Comparateur pour vecteur >

0
another_CS_guy 23 août 2020 à 23:04