Cita:
Iniciado por lareto 
Esta nueva versión es más rápida porque no hace nada. Pero de todos modos, si al corregirla conservas la idea, no será más rápida; las dos son de una complejidad O(log N) pero la "optimizada" tendría el doble de pendiente, demoraría el doble que mi versión.
Si y no... Es cierto que la versión que he puesto al final no funciona... cosas de montar el código directamente en el foro... pero no pasa nada, pongo un ejemplo completo, compilado y probado... ahora si puedo compilar :)
Código C++:
Ver originalstd::unordered_map<int, int> estilo_cpp1(std::vector< int > v)
{
std::unordered_map<int, int> m; // las funciones devuelven un map para
// no tener que mostrar con cout
// los miles de valores
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_cpp2(std::vector< int > v)
{
std::unordered_map<int, int> m; // las funciones devuelven un map para
// no tener que mostrar con cout
// los miles de valores
std::sort(std::begin(v), std::end(v)); // comienza el procese real
for( auto it = v.begin( ); it != v.end( ); ++it )
m[ *it ]++;
return m;
}
int main()
{
using namespace std::chrono;
steady_clock::time_point t1;
duration<double> demora1, demora2;
std::unordered_map<int, int> m1, m2;
std::minstd_rand0 generator; // llena un vector con elementos al azar
for(int n=1; n<30000000; n*=2)
{
std::cout << "n = " << n << '\n';
std::vector<int> v;
v.reserve( n );
for ( int i = 0; i < n; ++i )
v.push_back ( generator() % n );
t1 = steady_clock::now();
m1 = estilo_cpp1(v);
demora1 = duration_cast<duration<double>>(steady_clock::now() - t1);
t1 = steady_clock::now();
m2 = estilo_cpp2(v);
demora2 = duration_cast<duration<double>>(steady_clock::now()- t1);
std::cout << std::setprecision(6) << std::fixed;
std::cout << "estilo_cpp1(): " << demora1.count() << " segundos\n";
std::cout << "estilo_cpp2(): " << demora2.count() << " segundos\n";
std::cout << "diferencia relativa = " << (demora1.count()-demora2.count())/demora2.count() * 100 << " %\n" << std::endl;
}
}
...conseguimos exactamente la misma salida y con una mejora del rendimiento que varía... con pocos elementos he llegado a una mejora cercana al 2000% (poco fiable son procesos muy rápidos y cualquier interrupción dispara los tiempos) pero con cifras más altas la mejora se situa en torno al 12% - 15%.
Por cierto, he sacado la generación del vector fuera de las funciones por dos motivos:
1. Su generación no afecta a la medida de tiempos (medidas más precisas)
2. Ambas funciones van a trabajar con la misma colección de datos.
Sobre el motivo de usar el mapa... pues no se, como no podía probarlo tampoco tenía muy claro el impacto que podía tener con respecto a tu versión... esta mañana lo he probado y efectivamente rueda un 20% más lento (aprox.), cosas del directo.
Un saludo