comment pourrais-je trier une liste et obtenir les meilleurs éléments K? (STL)

Question

J'ai un vecteur de doubles. Je veux trier du plus haut au plus bas, et obtenir les indices des éléments K supérieurs. std :: tri ne fait que trier et ne retourne pas les index je crois. Quel serait un moyen rapide d'obtenir les meilleurs indices K des éléments les plus importants?

Answer 1

La première chose qui vient à l'esprit est un peu hackish, mais vous pouvez définir une struct qui a stocké à la fois le double et son index d'origine, puis surcharger l'opérateur < pour trier en fonction du double:

struct s { 
    double d; 
    int index; 
    bool operator < (const struct &s) const { 
     return d < s.d; 
    } 
}; 

Ensuite, vous pouvez récupérer les index d'origine de la structure.

exemple Fuller:

vector<double> orig; 
vector<s> v; 
... 
for (int i=0; i < orig.size(); ++i) { 
    s s_temp; 
    s_temp.d = orig[i]; 
    s_temp.index = i; 
    v.push_back(s); 
} 
sort(v.begin(), v.end()); 
//now just retrieve v[i].index 

Cela les laisser triées de la plus petite à la plus grande, mais vous pouvez surcharger la place l'opérateur> puis passer plus à la fonction de tri si on le souhaite.

Answer 2

Vous n'êtes pas sûr des algorithmes pré-conservés, mais jetez un oeil à selection algorithms; Si vous avez besoin des K premiers éléments d'un ensemble de N valeurs et N est beaucoup plus grand que K, il existe des méthodes beaucoup plus efficaces.

Si vous pouvez créer une classe d'indexation (comme la réponse de @ user470379 - essentiellement une classe qui encapsule un pointeur/index sur les données "réelles" en lecture seule), utilisez une file d'attente prioritaire de taille maximale K, et ajoutez chaque élément non trié à la file d'attente prioritaire, en supprimant l'élément le plus en bas lorsque la file atteint la taille K + 1. Dans les cas comme N = 10 , K = 100, cela gère les cas beaucoup plus simplement + efficacement qu'un tri complet.

Answer 3

OK, qu'en pensez-vous?

bool isSmaller (std::pair<double, int> x, std::pair<double, int> y) 
{ 
    return x.first< y.first; 
} 

int main() 
{ 
    //... 
    //you have your vector<double> here, say name is d; 
    std::vector<std::pair<double, int> > newVec(d.size()); 
    for(int i = 0; i < newVec.size(); ++i) 
    { 
     newVec[i].first = d[i]; 
     newVec[i].second = i; //store the initial index 
    } 
    std::sort(newVec.begin(), newVec.end(), &isSmaller); 
    //now you can iterate through first k elements and the second components will be the initial indices 
} 

Answer 4

Utilisation multimap pour vector « s (valeur, index) pour gérer dups. Utilisez les itérateurs inversés pour parcourir les résultats dans l'ordre décroissant.

#include <multimap> 
#include <vector> 
using namespace std; 

multimap<double, size_t> indices; 
vector<double> values; 

values.push_back(1.0); 
values.push_back(2.0); 
values.push_back(3.0); 
values.push_back(4.0); 

size_t i = 0; 
for(vector<double>::const_iterator iter = values.begin(); 
     iter != values.end(); ++iter, ++i) 
{ 
    indices.insert(make_pair<double,int>(*iter, i)); 
} 

i = 0; 
size_t limit = 2; 
for (multimap<double, size_t>::const_reverse_iterator iter = indices.rbegin(); 
    iter != indices.rend() && i < limit; ++iter, ++i) 
{ 
    cout << "Value " << iter->first << " index " << iter->second << endl; 
} 

sortie est

Valeur 4 Indice 3

Valeur 3 Indice 2

Si vous voulez juste les vector indices après tri, utilisez ceci:

#include <algorithm> 
#include <vector> 
using namespace std; 

vector<double> values; 

values.push_back(1.0); 
values.push_back(2.0); 
values.push_back(3.0); 
values.push_back(4.0); 

sort(values.rbegin(), values.rend()); 

Les K premières entrées sont indexées de 0 à K-1, et apparaissent dans l'ordre décroissant. Celui-ci utilise itérateurs inverse combinés à la norme sort (en utilisant less<double> pour atteindre l'ordre décroissant lorsque itéré avant Équivalemment.

sort(values.rbegin(), values.rend(), less<double>()); 

Exemple de code pour l'excellente solution nth_element suggérée par @Kiril ici (K = 125000, N = 500000). Je voulais essayer ça, alors voilà.

vector<double> values; 

for (size_t i = 0; i < 500000; ++i) 
{ 
    values.push_back(rand()); 
} 

nth_element(values.begin(), values.begin()+375000, values.end()); 
sort(values.begin()+375000, values.end()); 

vector<double> results(values.rbegin(), values.rbegin() + values.size() - 375000); 

Answer 5

vous pouvez utiliser le nth_element algorithme STL - cela vous renvoyer les N plus grands éléments (ce qui est le plus rapide, en utilisant stl) et ensuite utiliser .Sort sur eux, ou vous pouvez utiliser l'algorithme de partial_sort, si vous voulez que les premiers éléments de K à trier (:

en utilisant simplement .Sort est horrible - il est très lent pour le but que vous voulez .. .Sort est grand algorithme STL, mais pour trier le tout récipient, non seulement les premiers éléments K (ce n'est pas un accident l'existence de nth_element et partial_sort;)

Answer 6

Vous avez donc réellement besoin d'une structure qui mappe les indices en doubles correspondants.

Vous pouvez utiliser la classe std::multimap pour effectuer cette correspondance. Comme Jason l'a noté std::map ne permet pas les clés en double. Après avoir fait cela, vous pouvez itérer sur les dix premiers éléments car la carte préserve le tri des clés des éléments.