C++: La forma más rápida de ordenar una lista de números y su índice

Question

Tengo una pregunta que podría parecer muy básica, pero es en un contexto donde "cada cuenta de CPU cuenta" (esto es parte de un algoritmo más grande que ser utilizado en supercomputadoras).

El problema es bastante simple: ¿cuál es la forma más rápida de ordenar una lista de números largos largos sin signo y sus índices originales? (. Al principio, los números largos entero largo sin signo están en un orden completamente al azar)

Example : 
Before 
Numbers: 32 91 11 72 
Indexes: 0 1 2 3 
After 
Numbers: 11 32 72 91 
Indexes: 2 0 3 1 

Por "forma más rápida", quiero decir: ¿qué algoritmo de usar: std :: sort, C qsort, u otra algoritmo de clasificación disponible en la web? ¿Qué contenedor usar (C array, std :: vector, std :: map ...)? Cómo ordenar los índices al mismo tiempo (use structures, std :: pair, std :: map ...)?

¡Muchas gracias!

EDITAR: ¿cuántos elemento ordenar? -> típicamente 4Go de los números

Answer 1

El punto de partida obvio sería una estructura con operator< definido para ello:

struct data { 
    unsigned long long int number; 
    size_t index; 
}; 

struct by_number { 
    bool operator()(data const &left, data const &right) { 
     return left.number < right.number; 
    } 
}; 

... y un std :: vector para contener los datos:

std::vector<data> items; 

y std::sort que hacer la clasificación:

std::sort(items.begin(), items.end(), by_number()); 

El simple hecho es, que los contenedores normales (y tal) son suficientemente eficiente que el uso de ellos no hace que su código sustancialmente menos eficiente. Usted podría ser capaz de hacerlo mejor al escribir una parte de una manera diferente, pero es casi imposible que lo haga peor. Comience desde sólido y legible, y pruebe: no intente (intente) optimizar prematuramente.

Editar: por supuesto en C++ 11, se puede utilizar una expresión lambda en su lugar:

std::sort(items.begin(), items.end(), 
      [](data const &a, data const &b) { return a.number < b.number; }); 

Esto es generalmente un poco más cómodo para escribir. La legibilidad depende - para algo simple como esto, diría que sort ... by_number es bastante legible, pero eso depende (en gran medida) del nombre que le das al operador de comparación. La lambda hace que los criterios de clasificación reales sean más fáciles de encontrar, por lo que no es necesario elegir un nombre con cuidado para que el código sea legible.

Answer 2

Utilice std::vector y std::sort. Eso debería proporcionar el método de clasificación más rápido. Para encontrar el índice original crea una estructura.

struct A { 
    int num; 
    int index; 
} 

luego hacer su propia predicados para comparar tipo que compara el num de la estructura.

struct Predicate { 
    bool operator()(const A first, const A second) { 
     return first.num < second.num; 
    } 
} 

std::sort(vec.begin(), vec.end(), Predicate())

Answer 3

struct SomeValue 
{ 
    unsigned long long val; 
    size_t index; 
    bool operator<(const SomeValue& rhs)const 
    { 
     return val < rhs.val; 
    } 
} 

#include <algorithm> 
std::vector<SomeValue> somevec; 
//fill it... 
std::sort(somevec.begin(),somevec.end()); 

Answer 4

std::pair y std::sort se ajuste a sus necesidades idealmente: si se pone el valor en el pair.first y el índice de pair.second, sólo tiene que llamar a un sort en un vector de pair s, así:

// This is your original data. It does not need to be in a vector 
vector<long> orig; 
orig.push_back(10); 
orig.push_back(3); 
orig.push_back(6); 
orig.push_back(11); 
orig.push_back(2); 
orig.push_back(19); 
orig.push_back(7); 
// This is a vector of {value,index} pairs 
vector<pair<long,size_t> > vp; 
vp.reserve(orig.size()); 
for (size_t i = 0 ; i != orig.size() ; i++) { 
    vp.push_back(make_pair(orig[i], i)); 
} 
// Sorting will put lower values ahead of larger ones, 
// resolving ties using the original index 
sort(vp.begin(), vp.end()); 
for (size_t i = 0 ; i != vp.size() ; i++) { 
    cout << vp[i].first << " " << vp[i].second << endl; 
} 

Answer 5

std::sort ha demostrado ser más rápido que el antiguo qsort debido a la falta de direccionamiento indirecto y la posibilidad de incluir operaciones críticas.

Es probable que las implementaciones de std::sort sean altamente optimizadas y difíciles de superar, pero no imposibles. Si sus datos son de longitud y corto fijos, puede encontrar que Radix sort es más rápido. Timsort es relativamente nuevo y ha dado buenos resultados para Python.

Puede mantener la matriz de índice separada de la matriz de valores, pero creo que el nivel adicional de indirección resultará ser un asesino de velocidad. Mejor mantenerlos juntos en una estructura o std::pair.

Como siempre con cualquier aplicación de velocidad crítica, debe probar algunas implementaciones reales y compararlas para saber con certeza cuál es la más rápida.

Answer 6

¿Esto se usará en superordenadores?

En ese caso es posible que desee buscar algoritmos de clasificación paralelos. Eso solo tendrá sentido para clasificar grandes conjuntos de datos, pero la ganancia si la necesita es sustancial.

Answer 7

Puede ser que this sea una lectura interesante. Empezaría con el tipo de STL y solo luego trataría de mejorarlo si pudiera. No estoy seguro de si tiene acceso a un compilador de C++ 11 (como gcc4.7) en esta supercomputadora, pero sugeriría que std :: sort con std :: futures y std :: threads lo lleven del todo un poco del camino con respecto a la paralelización del problema de una manera sostenible.

Aquí está another question que compara std :: sort con qsort.

Finalmente, hay this article en Dr. Dobb's que compara el rendimiento de los algoritmos paralelos.

Answer 8

Se podría un valor de números y los índices y luego índices acaba de clasificación separando, de esta manera:

#include <vector> 
#include <algorithm> 
#include <iostream> 

void PrintElements(const std::vector<unsigned long long>& numbers, const std::vector<size_t>& indexes) { 

    std::cout << "\tNumbers:"; 
    for (auto i = indexes.begin(); i != indexes.end(); ++i) 
     std::cout << '\t' << numbers[*i]; 
    std::cout << std::endl; 

    std::cout << "\tIndexes:"; 
    for (auto i = indexes.begin(); i != indexes.end(); ++i) 
     std::cout << '\t' << *i; 
    std::cout << std::endl; 

} 

int main() { 

    std::vector<unsigned long long> numbers; 
    std::vector<size_t> indexes; 

    numbers.reserve(4); // An overkill for this few elements, but important for billions. 
    numbers.push_back(32); 
    numbers.push_back(91); 
    numbers.push_back(11); 
    numbers.push_back(72); 

    indexes.reserve(numbers.capacity()); 
    indexes.push_back(0); 
    indexes.push_back(1); 
    indexes.push_back(2); 
    indexes.push_back(3); 

    std::cout << "BEFORE:" << std::endl; 
    PrintElements(numbers, indexes); 

    std::sort(
     indexes.begin(), 
     indexes.end(), 
     [&numbers](size_t i1, size_t i2) { 
      return numbers[i1] < numbers[i2]; 
     } 
    ); 

    std::cout << "AFTER:" << std::endl; 
    PrintElements(numbers, indexes); 

    return EXIT_SUCCESS; 

} 

Esta impresora:

BEFORE: 
     Numbers:  32  91  11  72 
     Indexes:  0  1  2  3 
AFTER: 
     Numbers:  11  32  72  91 
     Indexes:  2  0  3  1 

La idea es que los elementos ordenados son pequeños y rápidos para moverse durante el género. Sin embargo, en las CPUs modernas, los efectos del acceso indirecto a numbers en el almacenamiento en caché podrían arruinar estas ganancias, por lo que recomiendo la evaluación comparativa de cantidades de datos realistas antes de tomar una decisión final para usarlas.