No quiero complicarle la vida a JarolGarcia con una versión más compleja que la que pueda asimilar, pero me parece que puede resultar interesante hacer una comparación entre una solución relativamente simple y artesanal, en estilo C (para lo que tomo como ejemplo y acomodando un poco la respuesta de eferion), y otra en estilo C++.
Yo creo que el estilo C++ tiene una ventaja inmediata: es mucho más fácil pensar en una solución y esa solución es muy fácil de hacer eficiente, mientras que la solución en estilo C puede no ser difícil de pergeniar, pero es más difícil de hacer eficiente o, por lo menos, se necesita bastante más esfuerzo y reinventar varios paraguas para conseguir una solución equivalente. Mi idea es que para obtener una solución eficiente en C++ no hace falta ser demasiado inteligente, sólo estudiar un poco más.
Va el ejemplo de comparación, que espero pueda servirle a alguien.
Para el que quiera compilar y ejecutar el programa, va a necesitar un compilador conforme con el estándar C++11 y un poco de paciencia, porque la prueba así como está en mi máquina se demora casi un minuto entero.
Código C++:
Ver original#include <iostream>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <chrono>
#include <iomanip>
#include <cstdlib>
std::unordered_map<int, int> estilo_cpp(int N)
{
std::unordered_map<int, int> m; // las funciones devuelven un map para
// no tener que mostrar con cout
// los miles de valores
std::minstd_rand0 generator; // llena un vector con elementos al azar
std::vector<int> v;
v.reserve(N);
for(int i=0; i<N; ++i) {
v.push_back(generator()%N);
}
std::sort(std::begin(v), std::end(v)); // comienza el procese real
int cont = 0;
for(auto i=std::begin(v), j=std::end(v); i!=j; i+=cont) {
auto rango = std::equal_range(i, j, *i);
cont = std::distance(rango.first, rango.second);
m[*i] = cont;
}
return m;
}
std::unordered_map<int, int> estilo_c(int N)
{
int cont, pasar;
int i, j;
std::unordered_map<int, int> m; // lo mismo que en la función de arriba
std::minstd_rand0 generator;
int* a = new int[N];
for(int i=0; i<N; ++i) {
a[i] = generator()%N; // llena el array con valores al azar
}
for ( i = 0; i < N; i++ ) { // comienza el proceso real
pasar = 0;
for ( j = i; j-- && !pasar; )
pasar = a[i] == a[j];
if( !pasar ) {
for( j=i, cont=0; j < N; ++j )
cont += a[i] == a[j];
m[i] = cont;
}
}
delete[] a;
return m;
}
int main()
{
using namespace std::chrono;
steady_clock::time_point t1;
duration<double> demora1, demora2;
std::unordered_map<int, int> m1, m2;
for(int n=1; n<300000; n*=2) {
std::cout << "n = " << n << '\n';
t1 = steady_clock::now();
m1 = estilo_c(n);
demora1 = duration_cast<duration<double>>(steady_clock::now() - t1);
t1 = steady_clock::now();
m2 = estilo_cpp(n);
demora2 = duration_cast<duration<double>>(steady_clock::now()- t1);
std::cout << std::setprecision(6) << std::fixed;
std::cout << "estilo_c() : " << demora1.count() << " segundos\n";
std::cout << "estilo_cpp(): " << demora2.count() << " segundos\n";
std::cout << "diferencia relativa = " << (demora1.count()-demora2.count())/demora2.count() * 100 << " %\n" << std::endl;
// a partir de 128 elementos las diferencias relativas aumentan proporcionalmente con n.
// más allá de 32.000 elementos, estilo_c() se hace inviable.
}
}