Problema k-paired (k-emparejados) en O(N)

dijsktra · 17 Septiembre 2019, 14:44 PM

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 [Seleccionar]


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!

MAFUS · 17 Septiembre 2019, 22:13 PM

En éste no veo como puede dar 3 de resultado.

Citar3 0 (Numero de componentes del vector y k)
1 2 3 (Componentes del vector)
3 Resultado)

K-YreX · 18 Septiembre 2019, 08:36 AM

Cita de: MAFUS en 17 Septiembre 2019, 22:13 PM
En éste no veo como puede dar 3 de resultado.

Supongo que son todos los pares (i, j) donde i = j. Como son 3 elementos, pues 3 pares.

MAFUS · 18 Septiembre 2019, 12:30 PM

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.

K-YreX · 18 Septiembre 2019, 12:40 PM

Cita de: MAFUS en 18 Septiembre 2019, 12:30 PM
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.

dijsktra · 18 Septiembre 2019, 17:04 PM

YreX-DwX, bravo! Yo mismo no podría haberlo explicado mejor...

Ahora... alguien se anima a hacerlo en O(N)?
En O(N^2) no tiene mucho mérito...

MAFUS · 18 Septiembre 2019, 22:40 PM

Pues sigo sin entenderlo.

Loretz · 18 Septiembre 2019, 23:56 PM

Edito...
Acomodo un poco que puede hacerse un pelín más claro y algo más rápido

Código (cpp) [Seleccionar]

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <numeric>
#include <chrono>

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{ 0 };
    auto it = v.begin();

    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;
        }
    }

    return n;
}

int main()
{
    std::vector v1{ 1, 4, 5, 6, 8 };
    std::vector v2{ 1, 4, 5, 6 };
    std::vector v3{ 1, 2, 3 };

    std::cout << n_pares(v1, 3) << '\n';
    std::cout << n_pares(v2, 2) << '\n';
    std::cout << n_pares(v3, 0) << '\n';

    std::vector<int> v4(1000, 0);

    for (int i = 1; i < 6; ++i) {
        v4.resize(v4.size() * 10);
        std::iota(v4.begin(), v4.end(), 0);

        std::cout << "v4.size() == " << v4.size() << '\n';

        // comienza a contar... desde acá
        auto start = std::chrono::high_resolution_clock::now();
        std::cout << n_pares(v4, 25) << '\n';
        // hasta acá.
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed = finish - start;
        std::cout << "demora: " << elapsed.count() << " seg\n\n";
    }

    std::cout << "No es perfectamente lineal, pero solo se abre un poco a partir de los 100 millones.\n";
}

dijsktra · 19 Septiembre 2019, 09:12 AM

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...

Cita de: Loretz en 18 Septiembre 2019, 23:56 PM
...
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

Código (cpp) [Seleccionar]



/*         
 P : strict(V)
 fun k_paired(V[0..N) of int, int k) dev r
 Q : r =#i,j : 0 <= i , j<N : V[j]-V[i]=k

 I : Q[N/n] and 0 <= m <= n <= N and
     n<N -> \forall i : 0<=i < m : V[n]-V[i] > k   **

     ** m for efficiency reasons, discarding 
        subtrahends V[i] far from V[n].
     

 !B : n==N     B: n<N

  C(N,n,m)= 2N - (m+n) >= 0



Invariant snapshot:
-------------------

k = 20  , r = 0
0                 m                             n           N
+-----+-----+-----+-----+-...-+-----+-----+-----+-----+-...-+
|  1  |  3  |  5  |  40 |     |     | 49  | 50  | 60  |     |
+-----+-----+-----+-----+-...-+-----+-----+-----+-----+-...-+


*/



#include <iostream>

using namespace std;
int k_paired(const int V[], const int N, const int k)
{
  int n,m,r;
  for(n=m=r=0;n<N;)
    if (V[n]-V[m] <= k)
      r+=(V[n++]-V[m] == k);
    else m++;
  return r;

}

#define MAX 100000

int main(int argc, char **args)
{
  int N,k;
  int V[MAX];
  for(cin >> N ; N!=-1 ; cin>>N)
    {
      cin >> k;
      for(int n=0;n<N;n++)
	cin >> V[n];
      cout << k_paired(V,N,k) << endl;
    }
  return 0;
}

A ver si pudieras medir tiempos con tus clases C++...

Loretz · 19 Septiembre 2019, 12:44 PM

Está bien,

pero este algoritmo "k_paired" se comporta realmente en forma lineal. Lo modifiqué mínimamente para hacer una comparación:

Código (cpp) [Seleccionar]

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <numeric>
#include <chrono>

int k_paired(const std::vector<int>& V, const int k)
{
    size_t n, m, r;

    for (n = m = r = 0; n < V.size();)
    {
        if (V[n] - V[m] <= k) {
            r += (V[n++] - V[m] == k);
        }

        else {
            m++;
        }
    }

    return r;
}

int main()
{
    std::vector<int> v4(1000, 0);

    for (int i = 1; i < 6; ++i) {
        v4.resize(v4.size() * 10);
        std::iota(v4.begin(), v4.end(), 0);

        std::cout << "v4.size() == " << v4.size() << '\n';

        // comienza a contar... desde acá
        auto start = std::chrono::high_resolution_clock::now();
        std::cout << k_paired(v4, 37) << '\n';
        // hasta acá.
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed = finish - start;
        std::cout << "demora: " << elapsed.count() << " seg\n\n";
    }
}

Con estos resultados:

Citark_paired
------------

v4.size() == 10000
9975
demora: 0.0001789 seg

v4.size() == 100000
99975
demora: 0.0004935 seg

v4.size() == 1000000
999975
demora: 0.0037331 seg

v4.size() == 10000000
9999975
demora: 0.03295 seg

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 [Seleccionar]

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...

[youtube=640,360]https://www.youtube.com/watch?v=FJJTYQYB1JQ[/youtube]

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 (cpp) [Seleccionar]

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 [Seleccionar]


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