¿cómo puedo ordenar una lista y obtener los mejores elementos K? (STL)

Question

Tengo un vector de dobles. Quiero ordenarlo de mayor a menor, y obtener los índices de los elementos K superiores. std :: sort simplemente se ordena y no devuelve los índices que creo. ¿Cuál sería una forma rápida de obtener los mejores índices K de los elementos más grandes?

Answer 1

La primera cosa que viene a la mente es un poco hacker, pero se podría definir una estructura que almacena tanto el doble y su índice original, entonces sobrecargar el operador < para ordenar en base al doble:

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

Entonces podrías recuperar los índices originales de la estructura.

ejemplo 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 

Esto dejarlos ordenados de menor a mayor, pero que podría sobrecargar el operador> lugar y luego pasar en mayor a la función de clasificación si se desea.

Answer 2

No estoy seguro acerca de los algoritmos pre-enlatados, pero eche un vistazo a selection algorithms; si necesita los elementos K superiores de un conjunto de valores N y N es mucho mayor que K, existen métodos mucho más eficientes.

Si se puede crear una clase de indexación (como respuesta de @ user470379 - básicamente una clase que encapsula un puntero/índice para los datos "reales", que es de sólo lectura), a continuación, utilizar una cola de prioridad de tamaño máximo de K, y agregue cada elemento sin clasificar a la cola de prioridad, saltando del elemento inferior cuando la cola alcance el tamaño K + 1. En casos como N = 10 , K = 100, esto maneja casos de manera mucho más simple y eficiente que una clasificación completa.

Answer 3

OK, ¿qué tal esto?

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

Uso multimap para vector 's (valor de índice) para manejar los DUP. Use iteradores inversos para recorrer los resultados en orden descendente.

#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; 
} 

salida es

calidad-precio 4 Índice 3

Valor 3 Índice 2

Si sólo desea los vector índices después de clase, utilice esto:

#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()); 

Las principales entradas K están indexadas por 0 a K-1, y aparecen en orden descendente. Esto utiliza iteradores inversa combinados con el estándar sort (usando less<double> para lograr orden descendente cuando iterado adelante Equivalentemente:.

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

Código de ejemplo para la solución excelente nth_element sugerido por @Kiril aquí (K = 125 000, N = 500.000). Quería probar esto, así que aquí está.

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

se puede utilizar el algoritmo de nth_element STL - esto le devolverá los mayores N elementos (esta es la manera más rápida, utilizando STL) y luego usar .Sort en ellos, o puede utilizar el algoritmo partial_sort, si desea que los primeros elementos de K a ser clasificadas (:

Utilizando sólo .Sort es horrible - es muy lenta con el fin de que deseas .. .Sort es grande algoritmo de STL, pero para la clasificación de todo el contenedor, no sólo los primeros elementos (K, no es un accidente, el existung de nth_element y partial_sort;)

Answer 6

Entonces realmente necesitas una estructura que asigne índices a los dobles correspondientes.

Puede usar la clase std::multimap para realizar esta asignación. Como Jason ha notado std::map no permite llaves duplicadas.

std::vector<double> v; // assume it is populated already 
std::multimap<double, int> m; 
for (int i = 0; i < v.size(); ++i) 
    m.insert(std::make_pair(v[i], i)); 
... 

Después de haber hecho esto usted podría iterar sobre primeros diez elementos como mapa conserva clasificación de llaves de los elementos.