0votos

Subsecuencias de Wirth en C

por josejuan hace 6 años

A veces ser bruto tiene sus ventajas. La versión de C mejora a Haskell en 125 veces más rápido. Cierto que Haskell está paralelizado (y con suficientes procesadores lo mejoraría), pero un buen ejemplo de que a veces hacer el bruto merece la pena XD XD XD

Encontrar todas las cadenas de N caracteres "A", "B" o "C" tales que no contengan dos subsecuencias consecutivas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/* 
 
En un Atom D510 con 2 cores 4 thread (no reales): 
 
La versión de Haskell 
 
solveet$ time -f "%E, %M" ./wiwi 40 +RTS -N4 
484446 
2:20.15, 527772 
 
 
Ésta versión en C 
 
solveet$ time -f "%E, %M" ./a.out 40 
484446 strings 
0:01.12, 484 
 
 
En ese mismo Atom, la versión en C puede llegar a n=55 en sólo 140 segundos! 
 
 
Aún hay margen para la mejora, por ejemplo, si tenemos 3 símbolos (ABC) y 
tenemos que generar todas las secuencias Wirth, podemos empezar únicamente 
a partir de 
 
"AB..." 
 
NO GENERANDO las versiones "AC", "BC", "BA", "CA" ni "CB". 
 
Es decir, hemos reducido el problema ¡a la sexta parte! (eg. si generar las 
secuencias N=40 nos lleva un minuto ¡ahora lo haremos en sólo 10 segundos!). 
 
¿Y que pasa con las secuencias que faltan? 
 
Bueno, si sólo se trata de contar las secuencias, multiplicamos por 6. 
 
Si se trata de mostrarlas, al mostrar una secuencia generada, haremos los 
reemplazamientos que nos aparecen arriba ("AB" -> "AC", "AB" -> "BC", ...) 
y listo. 
 
En "producción" este tipo de "trucos" (ahora sí es un truco artero) no sólo 
es válido, ¡sino necesarios! para obtener el máximo rendimiento; pero aquí 
en solveet yo no suelo utilizarlos porque no modifican en nada el problema 
inicial. 
 
*/ 
#include <stdio.h> 
#include <stdlib.h> 
 
//#define SHOWWIRTH printf("%s\n", w) 
#define SHOWWIRTH ; 
 
int Wirth(int n) { 
 
  char w[n + 1]      // pila de backtracking y resultado 
     , *iw = w       // índice de pila 
     , *Stop = w - 1 // centinela de fin de proceso 
     , *End = w + n; // centinela de solución en cola 
  int ns = 0;        // contador de soluciones 
 
  w[n] = 0;          // zstring 
  *iw++ = 'A';       // inicializamos 
 
#define BACK {\ 
  while(--iw != Stop) \ 
    if     (*iw == 'A') {*iw++ = 'B'; break;} \ 
    else if(*iw == 'B') {*iw++ = 'C'; break;} \ 
  if(iw == Stop) \ 
    break; \ 
 
  for(;;) { 
    char c = 0; 
    int l = (iw - w) >> 1; 
    while(l) { 
      char *a = iw - 1, *b = a - l, *k = b; 
      while(a > k && *a == *b) {a--; b--;} 
      if(a <= k) {c = 1; break;} // iguales! 
      l--; 
    if(c) BACK // si repite prefijos vamos pa'tras 
    else if(iw == End) {   // si estamos al final... 
                ns++;      // ...contabilizamos... 
                SHOWWIRTH; // ...reportamos... 
                BACK}      // ...y vamos pa'tras. 
    else *iw++ = 'A'; // añadimos char 
  return ns; 
 
int main(int argc, char **argv) { 
  if(argc != 2) { 
    fprintf(stderr, "Usage: %s num\n", argv[0]); 
    return 1; 
  printf("%i strings\n", Wirth(atoi(argv[1]))); 
  return 0; 
4 comentarios
0votos

Escrito por xurxof hace 6 años

Pues no acabo de entender la técnica de generar sólo la rama 'AB..' y luego sustituir por 'AC','BA'... Para n=3, por ejemplo, se generaría 'ABA' y 'ABC', pero al sustituir 'AB' por 'AC' obtendíramos 'ACA' y 'ACC', no siendo este último elemento una secuencia Wirth.
1votos

Escrito por josejuan hace 6 años

"Pues no acabo de entender la técnica de generar sólo la rama 'AB..'"

Eso es porque te has tomado al pie de la letra lo de reemplazar (estilo "replace"). Pero es culpa mía porque quizás doy muchas cosas por sentado.

Si nosotros tenemos n símbolos (sean 3 por simplificar, pero el esquema es general), entonces podemos indicarlos como

   S1 S2 S3 ... Sn

Así, si tenemos una secuencia de Wirth de la forma

   S1 S2 S3 S2 S1 S3

podemos reemplazar S1, S2 y S3 por cualesquiera símbolos (diferentes entre sí, claro) que todas las cadenas serán de Wirth. Por ejemplo, si reemplazamos el conjunto ordenado

  {S1, S2, S3} -> {'A', 'B', 'C'}

obtenemos

   "ABCBAC"

y si lo reemplazamos así

   {S1, S2, S3} -> {'A', 'C', 'B'}

tenemos

   "ACBCAB"

que también será de Wirth.


Por tanto, la estrategia consiste en generar una ÚNICA secuencia de Wirth "no reemplazada", para ello, en el caso de n=3 (3 símbolos), cualquier secuencia de Wirth debe empezar "por un símbolo y luego otro diferente", es decir S1 y luego S2.

Luego, basta obtener con esos S1, S2 y S3 todas las permutaciones de N elementos, en caso de tener 3 símbolos es 3! = 6.

Como ya tenemos el algoritmo que trabaja con los símbolos A, B y C; tanto da llamar S1, S2 y S3 que A, B y C al "conjunto genérico".

Por tanto, cuando yo digo que reemplaces AB por AC estoy indicando (creí que obviamente) que en realidad se reemplaza B por C. Cuando digo AB por BC, entonces es intercambiar las A por B, las B (originales) por C y las C originales por la A. Un ejemplo de éste último "reemplazo" sería que la cadena

  "ACBCAB"

cambiamos (pongo minúsculas para diferenciar las originales de las finales)

Aes por Bes:

  "ACBCAB" -> "bCBCbB"

Y ahora Bes por Ces:

  "bCBCbB" -> "bCcCbc"

Y por último las Ces por Aes:

  "bCcCbc" -> "bacabc"

Que es una secuencia Wirth.



Espero haberlo aclarado ;)
0votos

Escrito por josejuan hace 6 años

Por cierto, en general, el speedup ¡mayor que exponencial!, nada más y nada menos que una mejora factorial (mucho mayor que exponencial).

Sí, si nosotros tenemos que generar todas las secuencias Wirth de N elementos, hemos dicho que obtendremos N! representaciones de golpe con cada secuencia Wirth genérica (las creadas con los símbolos aún no reemplazados S1, S2, ...).

Es decir con N elementos, si M son el número total de secuencias Wirth finales (usando por ejemplo ABCDEF...) y P son el número de secuencias Wirth genéricas (las S1 S2 S3 ...), entonces se cumple la siguiente relación

M = P * N!

más ejemplos, con N=3 símbolos hay M=484446 secuencias Wirth finales, si implementamos el algoritmo propuesto, únicamente tendríamos que generar

P = 484446 / 3! = 484446 / 6 = 80741

si por ejemplo usamos un diccionario con N=20 símbolos, el speedup es de 20! = 2e18.

¿Y cómo generamos sólo las secuencias Wirth genéricas?

Bueno, para el caso de 3 símbolos hemos dicho "primero un símbolo y luego otro sin repetir", en general es un poco más complicado.

Para generar sólo las secuencias genéricas, hay que "expandir los símbolos sin eliminar completamente uno que ya haya aparecido" ¿cómo?.

Sí, nosotros empezamos metiendo el símbolo A (bueno es S1 pero con letras es más fácil de seguir) y tenemos

"A...

cuando terminemos esa recursividad, no podremos quitar la A (porque sino no quedaría ninguna), luego ya habremos terminado.

Bien, seguimos y tenemos que añadir el siguiente símbolo

"AB...

en la recursividad contemplaremos añadir también más Aes por ejemplo

"ABA...

esta segunda A sí la podemos eliminar, ¡pero no la B!, una vez añadida ya no la podemos quitar.

Y así, generaremos sólo las secuencias genéricas (en el ejemplo las 80741 en lugar de las 484446).

En cuanto al speedup, está muy bien, hemos reducido el problema ¡en un factor factorial! wow! si, claro, la pega está en que probablemente (no me he parado a demostrarlo) el nº de combinaciones genéricas seguirá siendo factorial.

Pero bueno, si alguna vez tengo que generar secuencias Wirth en producción, tendré este speedup en cuenta ¡claro!

XD
0votos

Escrito por josejuan hace 6 años

Ya puestos, en éste mismo código, basta con cambiar

     , *Stop = w + 1 // centinela de fin de proceso


y luego en la inicialización añadir B, es decir

  *iw++ = 'A';       // inicializamos
  *iw++ = 'B';       // inicializamos


luego para ajustar el conteo podemos hacer (o no, dejar sólo las finales, pero así podemos comparar con los datos que ya tenemos)

  return ns * 6;


y ya tenemos ajustado el código para que genere sólo secuencias genéricas.

Antes, generar todas las secuencias (finales) para una longitud de 50 le tomaba (AMD Phenom X6 2,7Ghz)

solveet]$ time -f "%E, %M" ./wFinal 50
6778926 strings
0:08.16, 476


ahora, generar sólo las genéricas le lleva

solveet]$ time -f "%E, %M" ./wGenericas 50
6778926 strings
0:01.29, 476


que, como era de esperar es 6,32 veces menos tiempo.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.