Manera eficiente de reordenar una colección basada en mapas C++

Question

Tengo una colección grande (ish -> 100K) mapeo un identificador de usuario (un int) para el recuento de diferentes productos que han comprado (también un int.) Necesito reorganizar los datos de la manera más eficiente posible para encontrar cuántos usuarios tienen diferentes números de productos. Por ejemplo, cuántos usuarios tienen 1 producto, cuántos usuarios tienen dos productos, etc.

He logrado esto invirtiendo los datos originales de std::map en un std::multimap (donde la clave y el valor simplemente se invierten). a continuación, puede elegir el número de usuarios que tienen N productos utilizando count(N) (aunque también almacenan únicamente los valores en un conjunto para poder estar seguro del número exacto de los valores que estaba interactuando sobre y su orden)

Código se ve así:

// uc is a std::map<int, int> containing the original 
// mapping of user identifier to the count of different 
// products that they've bought. 
std::set<int> uniqueCounts; 
std::multimap<int, int> cu; // This maps count to user. 

for (map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    cu.insert(std::pair<int, int>(it->second, it->first)); 
    uniqueCounts.insert(it->second); 
} 

// Now write this out 
for (std::set<int>::const_iterator it = uniqueCounts.begin(); 
     it != uniqueCounts.end(); ++it) 
{ 
    std::cout << "==> There are " 
      << cu.count(*it) << " users that have bought " 
      << *it << " products(s)" << std::endl; 
} 

No puedo evitar sentir que esta no es la forma más eficiente de hacerlo. Alguien sabe de un método inteligente de hacer esto?

Estoy limitado en que No puedo usar Boost o C++ 11 para hacer esto.

Ah, también, en caso de que alguien se pregunte, esto no es tarea, ni una pregunta de la entrevista.

Answer 1

Suponiendo que conozca la cantidad máxima de productos que un solo usuario podría haber comprado, es posible que observe un mejor rendimiento al usar un vector para almacenar los resultados de la operación. En este caso, necesitará una asignación para casi todas las entradas en el mapa original, que probablemente no sea la opción más rápida.

También reduciría la búsqueda en un mapa, obtendría los beneficios de la localidad de memoria y reemplazaría la llamada para contar con el multimapa (que no es una operación de tiempo constante) con una búsqueda de tiempo constante del vector .

Por lo que podría hacer algo como esto:

std::vector<int> uniqueCounts(MAX_PRODUCTS_PER_USER); 

for (map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    uniqueCounts[ uc.second ]++; 
} 

// Now write this out 
for (int i = 0, std::vector<int>::const_iterator it = uniqueCounts.begin(); 
     it != uniqueCounts.end(); ++it, ++i) 
{ 
    std::cout << "==> There are " 
      << *it << " users that have bought " 
      << i << " products(s)" << std::endl; 
} 

Incluso si usted no sabe el número máximo de productos, parece que sólo podía adivinar un máximo y adaptar este código para aumentar el tamaño de el vector si es necesario. Seguramente resultará en menos asignaciones que su ejemplo original de todos modos.

Todo esto supone que en realidad no necesita los ID de usuario después de haber procesado estos datos (por supuesto, y como se señala en los comentarios a continuación, que el número de productos comprados para cada usuario es relativamente pequeño & conjunto contiguo. De lo contrario, será mejor que use un mapa en lugar de un vector; todavía evitará llamar a la función multimap :: count, pero posiblemente perderá algunos de los otros beneficios)

Answer 2

Si puede, le recomendaría mantener ambos datos actualizados todo el tiempo. En otras palabras, mantendría un segundo mapa que mapea el número de productos comprados a la cantidad de clientes que compraron tantos productos. Este mapa contiene la respuesta exacta a tu pregunta si la mantienes. Cada vez que un cliente compra un producto, sea n la cantidad de productos que este cliente ha comprado. Reste uno del valor en la tecla n-1. Agregue uno al valor en la tecla n. Si el rango de teclas es lo suficientemente pequeño, esto podría ser una matriz en lugar de un mapa. ¿Alguna vez espera que un solo cliente compre cientos de productos?

Answer 3

Depende de lo que significa por "más eficiente". En primer lugar, ¿es esto realmente un cuello de botella?Claro, 100k entradas es mucho, pero si solo tienes esto cada pocos minutos, está bien si el algoritmo toma un par de segundos.

La única área de mejora que veo es el uso de la memoria. Si esto es una preocupación, puede omitir la generación de la multimap y sólo seguir un mapa contador alrededor, algo como esto (cuidado, mi C++ es un poco oxidado):

std::map<int, int> countFrequency; // count => how many customers with that count 

for (std::map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    // If it->second is not yet in countFrequency, 
    // the default constructor initializes it to 0. 
    countFrequency[it->second] += 1; 
} 

// Now write this out 
for (std::map<int, int>::const_iterator it = countFrequency.begin(); 
     it != countFrequency.end(); ++it) 
{ 
    std::cout << "==> There are " 
      << it->second << " users that have bought " 
      << it->first << " products(s)" << std::endl; 
} 

Si se añade y compra un usuario count elementos, puede actualizar countFrequency con

countFrequency[count] += 1; 

Si un usuario existente va desde oldCount a newCount elementos, puede actualizar countFrequency con

countFrequency[oldCount] -= 1; 
countFrequency[newCount] += 1; 

Ahora, solo como un lado, recomiendo usar un unsigned int para el recuento (a menos que haya una razón legítima para recuentos negativos) y typedef'ing un tipo userID, para mayor legibilidad.

Answer 4

Solo para alondras, este es un enfoque mixto que usa un vector si los datos son pequeños, y un map para cubrir el caso donde un usuario ha comprado una cantidad realmente absurda de productos. Dudo que realmente necesite este último en una aplicación de la tienda, pero una versión más general del problema podría beneficiarse de ello.

typedef std::map<int, int> Map; 
typedef Map::const_iterator It; 

template <typename Container> 
void get_counts(const Map &source, Container &dest) { 
    for (It it = source.begin(); it != source.end(); ++it) { 
     ++dest[it->second]; 
    } 
} 

template <typename Container> 
void print_counts(Container &people, int max_count) { 
    for (int i = 0; i <= max_count; ++i) { 
     if contains(people, i) { 
      std::cout << "==> There are " 
       << people[i] << " users that have bought " 
       << i << " products(s)" << std::endl; 
     } 
    } 
} 


// As an alternative to this overloaded contains(), you could write 
// an overloaded print_counts -- after all the one above is not an 
// efficient way to iterate a sparsely-populated map. 
// Or you might prefer a template function that visits 
// each entry in the container, calling a specified functor to 
// will print the output, and passing it the key and value. 
// This is just the smallest point of customization I thought of. 
bool contains(const Map &c, int key) { 
    return c.count(key); 
} 
bool contains(const std::vector<int, int> &c, int key) { 
    // also check 0 < key < c.size() for a more general-purpose function 
    return c[key]; 
} 

void do_everything(const Map &uc) { 
    // first get the max product count 
    int max_count = 0; 
    for (It it = uc.begin(); it != uc.end(); ++it) { 
     max_count = max(max_count, it->second); 
    } 

    if (max_count > uc.size()) { // or some other threshold 
     Map counts; 
     get_counts(uc, counts); 
     print_counts(counts, max_count); 
    } else { 
     std::vector<int> counts(max_count+1); 
     get_counts(uc, counts); 
     print_counts(counts, max_count); 
    } 
} 

Desde aquí se podría refactorizar, para crear una plantilla de clase CountReOrderer, que toma un parámetro de plantilla diciéndole que si desea utilizar un vector o una map de los conteos.