elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Problema k-paired (k-emparejados) en O(N)
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Problema k-paired (k-emparejados) en O(N)  (Leído 3,068 veces)
RayR

Desconectado Desconectado

Mensajes: 140


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #10 en: 20 Septiembre 2019, 03:07 am »

Qué gusto ver que cada vez sea más común ver presentaciones como la de Andrei Alexandrescu en las conferencias "grandes". Parece que siguen rindiendo frutos los esfuerzos de varias personalidades del software por concientizar sobre la necesidad de escribir software eficiente.

Creo que dice mucho el hecho de que algunos pesos pesados de C++ presenten como novedades y descubrimientos cosas que ya eran bien sabidas hace un par de décadas por cualquiera interesado en la optimización. Y esto en una charla dirigida a profesionales. De hecho, yo vi la conferencia sobre la caché de Scott Meyers por unos amigos que me enviaron el link, donde ponían que iba a ver a Scott Meyers descubriendo el agua tibia. Pero hablando en serio, sí tiene mérito que difundan ese tipo de información. Durante mucho tiempo, mucha gente en la industria le ha restado importancia a la optimización de bajo nivel debido a la falacia de que “las computadoras ya son lo suficientemente rápidas”, o con el argumento de que ese tipo de optimización es dependiente de la arquitectura. Como si los programadores y nuestros clientes usáramos máquinas abstractas para hacer nuestro trabajo...

Aunque tiene su parte de verdad lo que dice Alexandrescu, en cuanto a que los libros que típicamente se usan en las universidades casi no mencionan nada de eso, sí que ha habido varias publicaciones, algo más especializadas, que tocaban esos temas. Y si de literatura “clásica” hablamos, ahí están, y estaban, los manuales oficiales de los procesadores, que siempre fueron la referencia #1 a consultar si se quería optimizar, así que no había excusa. Otra cosa es que muchos hayan vivido en una burbuja teórica/académica. Incluso antes uno podía solicitar a Intel el paquete de versiones impresas de sus manuales oficiales y los enviaban gratuitamente. No siempre, pero a veces sí. Yo aún tengo mi colección de 2004 y ahí se explican prácticamente todas esas "revelaciones" de las que hablan Alexandrescu y Scott Meyers. Igualmente tengo algunas revistas de los 90 y principios de 2000 donde también se exponía esa información. De hecho, llevo unas semanas hurgando en mis códigos viejos, pues estoy pensando liberarlos como open source, y tengo archivos desde 1998 con funciones en las que comenté que eran más eficientes que otras versiones aparentemente más optimizadas, debido a las cachés del procesador y la predicción de saltos (branch prediction). Es decir, muchos, incluyéndome a mí, que era un novato, ya conocíamos y aplicábamos todo eso en los años noventa. Como digo, la información estaba, para quien se interesara en buscarla. Y la realidad es que casi ninguno de los ejemplos que se muestran en esas conferencias tiene nada de sorprendente. Que se presenten de esa forma, cuando la mayoría son más bien obviedades, dice mucho sobre el triste estado actual de buena parte de la industria. Por eso me parece tan relevante que estos asuntos dejen de ser temas de nicho y cada aparezcan más en los grandes eventos. Ojalá empiecen a permear en la academia y podamos tener mejor software en el futuro.


En línea

dijsktra

Desconectado Desconectado

Mensajes: 103


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #11 en: 20 Septiembre 2019, 10:14 am »

Tu mensaje esta lleno de cosas interesantes....
...
 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.

La clave está en que estamos juzgando el caso peor, y tu distribución std::iota (junto con el valor k) puede entrar en ese caso.

 Como tu dices, binSearch es logaritmico, pero fijate, debido a la distrbución std::iota (junto con el valor k) trabajas mucho  para avanzar solamente 1 posición, cosa que se consigue en el mío en O(1) m=m+1.
Imaginate k=2
Código:
1  5  6........................................................... 1000000000 (Arbitrariamente grande,N)
trabajas mucho (del orden de O(log(N)) para pasar del 1 al 5, del 5 al 6


Citar
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
  1. size_t n_pares(const std::vector<int>& v, int k)
  2. {
  3.    assert(std::is_sorted(v.begin(), v.end()) && "v debe estar ordenado.");
  4.    assert(v.size() && "v no puede venir vacio.");
  5.  
  6.    auto n{ 0u };
  7.    auto it = v.begin();
  8.  
  9.    for (auto i = v.begin(), j = v.end(); i != j; ++i)
  10.    {
  11.        it = std::find(it, j, *i + k);
  12.  
  13.        if (it != j) {
  14.            ++n;
  15.            ++it;
  16.        }
  17.        else {
  18.            it = i + 1;
  19.        }
  20.    }
  21.  
  22.    return n;
  23. }

Ahora los resultados son hasta ligeramente mejores que los de los de k_paired. Joder.


UN mundo muy ingrato.


Je,je,je... Tiene toda la explicacion... En este caso, la naturaleza de iota, k, y el problema, constituyen el caso mejor para find... No tienen que moverse casi nada, estan preguntando por el elmeento siguiente y los datos de entrada están al principio, no da "saltos" como el binsearch. con k=4

Código:
1  5  6........................................................... 1000000000 (Arbitrariamente grande,N)

Del 1 al 5, la busqueda se detiene en el primero. Idem para 5  a 6...

A nadie engañamos diciendo que es en O(N^2) en el caso peor... Pero este, era el mejor caso posible...


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)
Loretz

Desconectado Desconectado

Mensajes: 112


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #12 en: 22 Septiembre 2019, 23:47 pm »

Por si hubiera alguien más interesado:

Tengo una variante prácticamente un 20% más rápida; ¿alguien más quiere probar suertes y poner aquí sus resultados?

[Visual Studio 2019 v.16.2.5] (((NOTA de Interés... al menos para mí... Con Mingw g++ 8.2.0 no encuentro ninguna diferencia)))

Citar
Elementos al azar (uniform distribution) desde 1 hasta 2147483647
k == 25


Vector size == 99999

k_paired():
hallados == 6
demora: 0.0002796 seg

n_pares():
hallados == 6
demora: 0.0002281 seg (-18.4192 %)


Vector size == 999748

k_paired():
hallados == 484
demora: 0.0031284 seg

n_pares():
hallados == 484
demora: 0.0024078 seg (-23.0341 %)


Vector size == 9974323

k_paired():
hallados == 46206
demora: 0.0451042 seg

n_pares():
hallados == 46206
demora: 0.0338307 seg (-24.9943 %)


Vector size == 97464323

k_paired():
hallados == 4423642
demora: 0.889701 seg

n_pares():
hallados == 4423642
demora: 0.778881 seg (-12.4559 %)


Vector size == 783444620

k_paired():
hallados == 285821970
demora: 8.40441 seg

n_pares():
hallados == 285821970
demora: 6.8764 seg (-18.181 %)


« Última modificación: 23 Septiembre 2019, 00:13 am por Loretz » En línea

AzøZ

Desconectado Desconectado

Mensajes: 1


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #13 en: 23 Septiembre 2019, 03:43 am »

Código
  1. int k_paired(const std::vector<int>& arr, const int k)
  2. {
  3.  size_t i = 0,j = 1,res = 0;
  4.  while(i<arr.size() && j<arr.size())
  5.  {
  6.     if (i != j && arr[j]-arr[i] == k)
  7.     {
  8.        res++;
  9.        i++;
  10.        j++;
  11.     }
  12.     else if(arr[j]-arr[i]<k)
  13.        j++;
  14.     else
  15.        i++;
  16.  }
  17.   return res;
  18. }

Creo es una variante ligeramente mas rapida que las anteriores segun las mediciones que realize @loretz estaria interesante ver tu solucion.
En línea

Loretz

Desconectado Desconectado

Mensajes: 112


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #14 en: 23 Septiembre 2019, 07:01 am »

Sí sí, es que quería mantener una atmósfera de misterio...

Las pruebas las hice con:

Código
  1. size_t n_pares(const std::vector<int>& v, int k)
  2. {
  3.    auto n{ 0 };
  4.    auto it{ v.begin() };
  5.  
  6.    for (auto i = v.begin(), j = v.end();
  7.        i < j;
  8.        ++i)  // avanza la cola
  9.    {
  10.        while (it != j && *it < *i + k) {  // avanza la cabeza
  11.            ++it;
  12.        };
  13.  
  14.        if (it == j) { // no tanto que se caiga
  15.            break;
  16.        }
  17.  
  18.        else if (*it == *i + k) {  // se ha formado una pareja
  19.            ++n;
  20.        }
  21.    }
  22.  
  23.    return n;
  24. }

Y ejecutando la misma prueba para cada una de las tres funciones, en Visual Studio, ha resultado:

Citar
Visual Studio:
-------------

Elementos al azar (uniform distribution) desde 1 hasta 2147483647
k == 25


Vector size == 99998

n_pares():
hallados == 7
demora: 0.0002385 seg

k_paired():
hallados == 7
demora: 0.0003567 seg (49.5597 %)

k_zoz():
hallados == 7
demora: 0.0005064 seg (112.327 %)


Vector size == 999767

n_pares():
hallados == 462
demora: 0.002672 seg

k_paired():
hallados == 462
demora: 0.0038684 seg (44.7754 %)

k_zoz():
hallados == 462
demora: 0.005371 seg (101.01 %)


Vector size == 9974491

n_pares():
hallados == 46567
demora: 0.0346364 seg

k_paired():
hallados == 46567
demora: 0.0532758 seg (53.8145 %)

k_zoz():
hallados == 46567
demora: 0.0667464 seg (92.7059 %)


Vector size == 97464998

n_pares():
hallados == 4419710
demora: 0.796983 seg

k_paired():
hallados == 4419710
demora: 0.922205 seg (15.712 %)

k_zoz():
hallados == 4419710
demora: 1.12035 seg (40.5734 %)


Vector size == 783463366

n_pares():
hallados == 285828837
demora: 6.97443 seg

k_paired():
hallados == 285828837
demora: 8.55857 seg (22.7136 %)

k_zoz():
hallados == 285828837
demora: 9.50019 seg (36.2146 %)

Curioso, al menos a mí me lo parece.

Pero lo mismo con Mingw (g++ -O3 -Wall -pedantic)
resulta:

Citar
Elementos al azar (uniform distribution) desde 1 hasta 2147483647
k == 25


Vector size == 99997

n_pares():
hallados == 5
demora: 0.000945 seg

k_paired():
hallados == 5
demora: 0 seg (-100 %)

k_zoz():
hallados == 5
demora: 0 seg (-100 %)


Vector size == 999744

n_pares():
hallados == 456
demora: 0.002965 seg

k_paired():
hallados == 456
demora: 0.003038 seg (2.46206 %)

k_zoz():
hallados == 456
demora: 0.003999 seg (34.8735 %)


Vector size == 9974357

n_pares():
hallados == 46171
demora: 0.046053 seg

k_paired():
hallados == 46171
demora: 0.033003 seg (-28.3369 %)

k_zoz():
hallados == 46171
demora: 0.048001 seg (4.22991 %)


Vector size == 97462426

n_pares():
hallados == 4422382
demora: 0.875945 seg

k_paired():
hallados == 4422382
demora: 0.785002 seg (-10.3823 %)

k_zoz():
hallados == 4422382
demora: 0.966 seg (10.2809 %)


Vector size == 783434184

n_pares():
hallados == 285793753
demora: 7.66395 seg

k_paired():
hallados == 285793753
demora: 7.158 seg (-6.60165 %)

k_zoz():
hallados == 285793753
demora: 8.702 seg (13.5446 %)

Jé, nuevo desafío... ¿quién me lo explica?


En línea

dijsktra

Desconectado Desconectado

Mensajes: 103


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #15 en: 24 Septiembre 2019, 10:45 am »

Sí sí, es que quería mantener una atmósfera de misterio...
Y ejecutando la misma prueba para cada una de las tres funciones, en Visual Studio, ha resultado:

Curioso, al menos a mí me lo parece.
Jé, nuevo desafío... ¿quién me lo explica?
Un momento, amigo...

Código:
Elementos al azar (uniform distribution) desde 1 hasta 2147483647

Las pruebas quedan invalidadas... Si pones elementos al azar, entonces ya no estarán ordenados estrictamente creciente, y los algoritmos no funcionarán en absoluto... Es conforme a esa precondición que programamamos el algoritmo... De nada sirve ir muy rápido si no computa las cosas que se espera.

Si los elementos están al azar, no ordenados, entonces, el algoritmo solo puede ser O(N^2). Por supuesto, este no vale, hay que cambiarlo.
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)
Loretz

Desconectado Desconectado

Mensajes: 112


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #16 en: 24 Septiembre 2019, 19:15 pm »

Los elementos del vector sí están ordenados (y no se repiten), sólo que son generados al azar. Pongo el algoritmo acá abajo:

Se invoca con el vector ya del tamaño apropiado; se carga con valores al azar, se ordena y se eliminan los duplicados:

Código
  1. void llenar(std::vector<int>& v, int min, int max)
  2. {
  3.    static std::random_device rd;
  4.    static std::mt19937 mte(rd());
  5.    std::uniform_int_distribution<int> dist(min, max);
  6.  
  7.    std::generate(v.begin(), v.end(), [&]() { return dist(mte); });
  8.  
  9.    std::sort(v.begin(), v.end());
  10.    v.erase(unique(v.begin(), v.end()), v.end());
  11. }
.

En línea

dijsktra

Desconectado Desconectado

Mensajes: 103


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #17 en: 25 Septiembre 2019, 17:13 pm »

Asi sólo con datos de tiempos, y no en una gráfica es dificil de ver....

Haz una ultima prueba, con distros aleatorias y k = 1.

Si interpolaramos en una gráfica  las mediciones, deberíamos ver que las medidas de cada una se acercan a 3 rectas... (por eso es linear. Desde la teoría de la complejidad, da igual que una vaya el doble, el triple, o k-veces más rápido, los factores constantes dan igual...)

Pero si se interpolan las curvas y vemos que alguna da una parabola, algo no va bien, pues en los tres casos, n_paired, k_paired, y zoz?paired son lineales...  Si, en el doble bucle interior tambien se comporta lineal, ya que al ser la instrucción critica se ejecuta un máximo de N veces...

La que no debería ser una recta es la del  lower_bound...

Un buen trabajo ! Enhorabuena


Los elementos del vector sí están ordenados (y no se repiten), sólo que son generados al azar. Pongo el algoritmo acá abajo:

Se invoca con el vector ya del tamaño apropiado; se carga con valores al azar, se ordena y se eliminan los duplicados:


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)
RayR

Desconectado Desconectado

Mensajes: 140


Ver Perfil
Re: Problema k-paired (k-emparejados) en O(N)
« Respuesta #18 en: 27 Septiembre 2019, 01:06 am »

Lo ideal sería hacer un número muy grande de pruebas, incluso usando semillas iguales en ambos compiladores, para tratar de eliminar algunas variables y evitar resultados atípicos y así hacernos una mejor idea de lo que sucede. De cualquier forma, como bien dice dijsktra, es de esperar que haya ciertas variaciones, siempre y cuando al final las funciones tengan un comportamiento lineal. Luego, por supuesto, ya entran en juego los compiladores; algunos sabrán optimizar mejor algunas funciones u otras; o incluso partes de una función, lo que podría explicar resultados aparentemente inconsistentes: quizás con ciertas distribuciones o tamaños, algunos "branches" tienden a ejecutarse más frecuentemente,y si resulta que un compilador no hizo un buen trabajo optimizando esa parte específica del código, puede dar resultados muy pobres cuando con otros tamaños brillaba.

Aún así, a veces distintos procesadores, incluso del mismo fabricante, pueden comportarse de forma distinta, lo cual es frustrante, pero, en fin...  Yo lo probé con lo que tengo ahora que es MinGW-w64 en su versión de 64 bits, por lo que también compilé para esa arquitectura en Visual Studio 2019. Eso hace que mis resultados sean distintos. Por eso, y porque tampoco hice muchas pruebas, no pongo los números, pero sí algunas cosas que encontré por si acaso son de interés. En mi caso, casi siempre k_paired() se comporta un poco mejor (más o menos un 8%) que n_pares(), para todos los tamaños y en ambos compiladores, pero especialmente en MinGW-w6. Además, con todas las funciones, y sobre todo con k_paired(), MinGW-w64 generó mejores resultados (cerca del 10%). Tomaría mucho tiempo hacer un buen análisis, pero de forma breve, en una revisión rápida al código generado, veo que Visual C++ hizo inline todas las funciones, mientras que MinGW-w64 no lo hizo con ninguna. En este caso, eso por sí sólo no debería influir mucho, pero pudiera ser útil hacer experimentos cambiando eso. Centrándome en k_paired() y la diferencia de su ejecución entre compiladores (que me pareció lo más interesante), MinGW-w64 generó código con más instrucciones y que a simple vista pudiera parecer menos eficiente, pero en realidad lo que hizo es un loop unrolling parcial. Pongo aquí un pseudocódigo resumido de lo que hace el ensamblador que genera este compilador:

Código:
bucle:
resta = v4[n] - v4[m]
if (resta > k) goto block3
block2:
tmp++
sumando = (resta == k)
r += sumando
if (tmp >= N) goto fin
n = tmp
resta = v4[n] - v4[m]
if (resta <= k) goto block2
block3:
m++
if (tmp > N) goto fin
goto bucle
fin:
return r

Lo interesante es ver que hace la comparación de la resta con k en dos partes diferentes. El código generado por Visual C++ es muy similar, aunque no hace esa segunda resta y comparación, sino que directamente salta de vuelta al inicio del bucle, que sería lo más normal, dado el código fuente original. Los saltos no son operaciones muy costosas, pero a los procesadores les gusta el código secuencial; no por nada el compilador decidió hacer esa optimización, así que esto podría explicar el peor rendimiento de VC++. Y es que realmente no hay ninguna otra diferencia importante entre el código generado por los compiladores para esa función. Es probable que con las otras funciones y con el MinGW original y VC++ compilando a 32 bits pase algo similar (o no) pero eso ya requeriría dedicarle algo más de tiempo.

Edito:

Como me quedó la curiosidad, quise corroborar mi conjetura y modifiqué el ensamblador generado por VC++ para incluir la optimización de MinGW-w64 (con lo que además  se elimina un salto adicional que hacía VC++, y que se me pasó mencionar en el párrafo anterior),  y efectivamente, eso cambia todo. La nueva función modificada es alrededor de un 20% más rápida que la que genera VC++, aunque la ganancia tiende a disminuir con vectores muy grandes. Aún así, incluso en el peor de los casos, obtuve una mejora del 10%. Y de hecho, con esta función, VC++ ahora supera ligera, pero consistentemente, a MinGW-w64 (en el caso de k_paired, las otras funciones no las toqué). Esto también tiene su explicación: en el código que genera MinGW-w64, en cada iteración del bucle se calcula la dirección de v4[n] mediante (v4+n*4), y lo mismo para v4[m], mientras que VC++ usa directamente punteros que simplemente incrementa ptrN+=4, ptrM+=4, ahorrándose las multiplicaciones. Aquí tenemos un caso en el que cada compilador optimizó mejor una parte de la función, y lo hizo peor en otra, aunque, por supuesto, la disminución de saltos de MinGW-w64 tuvo más peso. Si a alguien le interesa, le puedo pasar el código ensamblador de la función, que es una copia de lo generado por el compilador, y sólo le hice la modificación mencionada. Lamentablemente, como Visual C++ no admite inline asm en 64 bits, se tendría que hacer un archivo .asm externo con la función y enlazarlo a su proyecto.

Hagamos caso a lo que dicen Scott Meyers y Andrei Alexandrescu en las conferencias mencionadas atrás. Para escribir programas eficientes en el mundo real, es crucial recurrir al bajo nivel. Aquí se cambiaron sólo 4 líneas de código y se obtuvo una función más rápida que las generadas por cualquiera de estos dos compiladores, con todo y -O3 u /O2. Y fue algo hecho muy a lo rápido.

Me quedo con esto de Alexandrescu (énfasis mío):

Citar
Throw the structures & algos book away
Research papers & industry is where it's at
« Última modificación: 1 Octubre 2019, 07:52 am por RayR » En línea

Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines