Dado un vector de enteros V[0..N) , con todos sus componentes siguiendo un orden stricto creciente, (1,5,17,20) y un numero k >=0 , diseñar un algoritmo de complejidad lineal que resuelva el número de pares de componentes <i,j> , con 0<=i,j<N, tales que Vi-Vj=k.
En la siguientee lineas se da unos ejemplos como ilustracion
Código:
5 3 (Numero de componentes del vector y k) 1 4 5 6 8 (Componentes del vector) 2 (Resultado)
4 2 (Numero de componentes del vector y k) 1 4 5 6 (Componentes del vector) 1 (Resultado)
3 0 (Numero de componentes del vector y k) 1 2 3 (Componentes del vector) 3 Resultado)
Yo dispongo de la solución. La pongo en dos días. Pero ahí esta el reto. Cuanto más simple mejor!
En línea
Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
El enunciado dice que i-j=0, sin embargo no hay pares en {1, 2, 3} ,dónde la resta de dos elementos del conjunto de 0.
Citar
Dado un vector de enteros V[0..N) , con todos sus componentes siguiendo un orden stricto creciente, (1,5,17,20) y un numero k >=0 , diseñar un algoritmo de complejidad lineal que resuelva el número de pares de componentes <i,j> , con 0 <= i, j < N, tales que Vi-Vj = k.
En ese supuesto, las soluciones serían:
(0,0) ya que V[0] - V[0] = k
(1,1) ya que V[1] - V[1] = k
(2,2) ya que V[2] - V[2] = k
Donde para todas las soluciones se cumplen todas las condiciones del enunciado. Es más se puede dar por supuesto que como el orden debe ser estrictamente creciente (no hay repetidos), siempre que k = 0, el número de pares que satisfacen las condiciones es N y por tanto la solución también.
En línea
Código
cout<<"Todos tenemos un defecto, un error en nuestro código"<< endl;
Estupendo intento, Loretz, buena exhibición de recursos... No obstante creo que el punto flaco reside en la llamada que haces a lower_bound, lo que eleva la complejidad de tu algoritmo a O(Nlog(N)). Mejor que cuadrático O(N^2), al menos...
... for (auto i = v.begin(), j = v.end(); i != j && it != j; ++i) { auto s = *i + k; it = std::lower_bound(it, j, s);
if (it != j && *it == s) { ++n; ++it; } } ...
A ver que te parece ésta, en O(N): Brevemente, para evitar llamadas a lower_bound, controlas con una variable extra m, que parte del vector recorrido YA sabes que no va a emparejar con el actual en curso V[n], por lo que no hace falta volver a recorrer... Ah!, y lo mismo vale para vectores vacíos
v4.size() == 100000000 99999975 demora: 0.32598 seg
Se lo ve muy lineal, ciertamente; y sobre todo, 10 veces más rápido que usando lower_bound; nada mal.
Pero la versión con lower_bound (que llamé "n_pares") no es O(Nlog(N)), es en realidad prácticamente equivalente a k_paired, también avanza como un gusano, y creía que debía comportarse de la misma manera, con un desenvolvimiento lineal, aunque resultó 10 veces más lento. Un oprobio. Si te fijas en esta línea:
Código:
it = std::lower_bound(it, j, s);
it queda posicionado en la posición buscada o en una más allá del límite s, esperando en el mejor lugar para la próxima iteración. Y lower_bound es un binary search, logarítmico, que es mejor que avanzar secuencialmente, o mejor dicho, creí que debería serlo.
Casualmente justo ayer Andrei Alexandrescu dio una charla sobre estas cuestiones en la CppCon, y comentaba que después de fracasar con todas las soluciones inteligentes comenzó a probas las estúpidas; y, sorpresa...
Si esto no se pone demasiado pesado, comento que:
Yo también probé con una solución (aparentemente) muy inferior a la versión con lower_bound, donde lo reemplazo por un estúpido find, haciendo ahora sí una solución (prácticamente) O(N2), pero no, curiosamente:
Código
size_t n_pares(const std::vector<int>& v, int k)
{
assert(std::is_sorted(v.begin(), v.end())&&"v debe estar ordenado.");
assert(v.size()&&"v no puede venir vacio.");
auto n{ 0u };
auto it = v.begin();
for(auto i = v.begin(), j = v.end(); i != j;++i)
{
it = std::find(it, j, *i + k);
if(it != j){
++n;
++it;
}
else{
it = i +1;
}
}
return n;
}
Ahora los resultados son hasta ligeramente mejores que los de los de k_paired. Joder.
Código:
k_paired n_pares ------------ ------------
v4.size() == 10000 v4.size() == 10000 9975 9975 demora: 0.0001789 seg demora: 0.0001686 seg
v4.size() == 100000 v4.size() == 100000 99975 99975 demora: 0.0004935 seg demora: 0.0004539 seg
v4.size() == 1000000 v4.size() == 1000000 999975 999975 demora: 0.0037331 seg demora: 0.0026152 seg
v4.size() == 10000000 v4.size() == 10000000 9999975 9999975 demora: 0.03295 seg demora: 0.0266995 seg
v4.size() == 100000000 v4.size() == 100000000 99999975 99999975 demora: 0.32598 seg demora: 0.26099 seg
UN mundo muy ingrato.
Para los que se las arreglan con el inglés vale la pena también el histórico: "CPU cache and why you care" de Scott Meyers: https://youtu.be/3G-LO9T3D1M
Autor
En línea
