0votos

A surpassing problem en JavaScript

por josejuan hace 6 años

El coste en el peor caso es O(n + min(S, n)^2); si se asume S < n entonces el coste es O(n + S^2), la mejora consiste en que los datos de entrada sólo se recorren una única vez. La contrapartida es que para valores grandes de S tendríamos coste cuadrático (aunque puede mejorarse). Por ejemplo, para tamaños de S=1024 usaríamos y moveríamos 1M de datos, lo que es un coste muy pequeño si n es grande.

JAlonso tuiteó un libro que contiene una serie de problemas. En él se presenta un problema que se resuelve con coste O(n log n). El desafío consiste en encontrar una solución con coste O(n) y ver porqué en la práctica NO ES más eficiente.

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
// Se considera el alfabeto {'A', 'B', ..., 'Z'} 
function MaxSurpasserCount(s) { 
 
    // desde 'A' hasta 'Z', S elementos 
    var i = 64, F = 90, S = F - i + 1; 
 
    // acumulador, puede hacerse sparse 
    var A = NewArray(S); 
 
    // para cada elemento, el conteo de suBpasser count 
    var C = []; 
 
    // para cada elemento miramos si es su primera aparición 
    // en cualquier caso incrementamos conteo 
    for(var j in s) { 
        var c = s.charCodeAt(j) - i; 
        if(A[c] == 0) 
                C.push({c: c, v: CloneArray(A)}); // puede hacerse incremental 
        A[c]++; 
 
    // máx surpassing count 
    var m = 0; 
 
    // para cada elemento encontrado, calculamos surpasser count 
    // y agregamos al MAX 
    for(var q in C) { 
        var s = 0, h = C[q].c; 
        while(++h < S) s += A[h] - C[q].v[h]; 
        if(m < s) m = s; 
 
    // máx surpassing 
    return m; 
 
function NewArray(n) {var a = []; while(n-- > 0) a.push(0); return a} 
function CloneArray(v) {var a = []; for(var z in v) a[z] = v[z]; return a} 
 
MaxSurpasserCount("GENERATING"); 
 
/* 
    Siguiendo con el análisis de la otra solución, tenemos: 
 
        n log n = n + S^2 
     
    que no tiene solución analítica (no se puede despejar n), en el algoritmo 
    anterior, era mejor n log n para n = 67.108.864, en ese caso, con un diccionario 
    de tamaño 26, a partir de n=165 ya es mejor este algoritmo. 
 
    Para un diccionario de 1024 elementos será mejor si n > 99764. 
 
    Aunque en la práctica me da que tendrá una constante muy pequeña y S^2 afectará menos de lo que parece. 
*/ 
12 comentarios
0votos

Escrito por jneira hace 6 años

Me recuerda bastante a mi solucion en haskell y en ella calcule que las operaciones dentro del loop sobre s dependian de la longitud de C, siendo C en mi solucion no el alfabeto entero sino los elementos unicos de s. ¿Suponiendo aqui tambien que C son los elementos unicos de s, no es su coste igual? ¿Que diferencias habria entre esta version y la de haskell para que su coste sea diferente (en funcion de n y sin entrar en g(m) y h(m)) ?
0votos

Escrito por jneira hace 6 años

Vale ya he visto una diferencia, en mi caso el calculo lo iba haciendo dentro del loop principal sobre n en lugar de crear primero el acumulador con las apariciones de cada una y luego iterar de forma separada sobre ese acumulador para calcular el maximo surpassing.
Aun asi me parece que el hecho de contar las apariciones depende de la longitud final del acumulador (que es la longitud de los elementos unicos de s) ya que hay que hacer un lookup (A[c]) y un update(A[c]++) sobre el en cada paso (aunque sea de grado logm)
0votos

Escrito por josejuan hace 6 años

"ya que hay que hacer un lookup ... en cada paso (aunque sea de grado logm)"

No, no, tiene coste O(1) incluso aunque S fuera muy grande (eg. no cupiese en memoria) hace ya mucho tiempo que se inventó la RAM (Random Access Memory) y los discos de acceso directo XD XD XD

A[c] sobre una estructura de tamaño fija tiene coste O(1) de toda la vida. ;)
0votos

Escrito por jneira hace 6 años

Mmm, cierto acababa de darme cuenta que A es un array fijo y no un mapa. Aun asi tengo otra duda: en este caso la solucion esta fijada a ser cadenas de caracteres con el vocabulario ['a'..'z'] y s.charCodeAt(j) es fijo por representacion interna pero el codigo equivalente generico para buscar el indice de un elemento dentro de un array de elementos cualesquiera ¿no depende de la longitud de ese vocabulario? No se tardara lo mismo en buscar el indice de 4 en [4,5] que en [1..10] o de 'x' en ['a'..'z'] o en ['x','y','z']
0votos

Escrito por josejuan hace 6 años

Recordemos que C es el conjunto del diccionario y S es la cadena de entrada.

En el problema, especifico que el conjunto C es finito (esa es la sutil diferencia con el problema original), por tanto únicamente tienes que poner en correspondencia cada elemento del conjunto con los ordinales.

Esa correspondencia no es obvia para el caso general, pero tanto me da el tipo de representación que uses, que yo (dentro de la máquina) siempre podré conseguir esa representación (a ordinales).

El peor caso de todos es aquel en el que tenga que usar una tabla hash, por ejemplo, si los elementos de C son números de 64 bits arbitrarios (eg. GUID) tendré que usar una tabla hash, pero ésta tiene coste O(1) (salvo casos [que no peor caso] especiales).

Si queremos ser MUY puristas, incluso en haskell cada elemento de C podrá ser serializado a binario y de ahí obtendríamos su clave hash, etc...

Así, queda mostrado que A[c] tiene coste O(1).

Por otro lado, "matemáticamente hablando" (que sería [creo] a lo que te refieres con "el codigo equivalente generico") no tiene sentido hablar de coste, porque éste siempre está sujeto a la máquina en la que se define (eg. una máquina sin acceso aleatorio obviamente ya no se podría). Así, dado un conjunto y una función de orden, puedes definir la función índice, pero no hablar de su coste ¡hasta que no fijes una máquina!.

De todos modos, será frecuente que los elementos (que además ¡están ordenados!) posean una estructura interna que permita indizarlos directamente (eg. las letras mayúsculas).
0votos

Escrito por jneira hace 6 años

Mmm vale, estableciendo un "hash" numerico directo puedes hacer constante el indice de un elemento cualquiera fijada una representacion en una maquina concreta.

Completemos el analisis, si te parece, con la unica operacion que nos queda dentro del loop (ya que push es fijo): CloneArray. En el codigo parece que el coste de la copia depende del tamaño de A (que como deciamos tiene la longitud final de los elementos unicos de s), sin embargo comentas que puede hacerse "incremental".. ¿a que te refieres?¿eso haria que la copia no dependiera de la longitud de a?
0votos

Escrito por josejuan hace 6 años

En el peor caso, esa operación implica |C|^2 (puse S^2 por descuido) porque para cada elemento de C almacenamos un vector de |C| elementos.

Pero como digo, puede mejorarse el caso promedio.

Supuesto que n >> |C| entonces muchos de estos vectores compartirán (en un gran conjunto de datos de entrada) elementos, por ejemplo en el siguiente caso:

"ABCDEFG..."

cada vector comparte con su anterior todos los elementos inferiores al que define (eg. para "E" y "F" el conteo de Aes, Bes, ... es el mismo).

Además, en el último loop (coste |C|) podemos recorrer C como queramos y podemos hacerlo precisamente en el mismo orden en el que han ido apareciendo en S.

Así, podemos poner marcas cada vez que aparece un nuevo elemento (en "A[c] == 0") y formar una estructura acumulativa en lugar de |S|^2.

En el último loop, recorreremos esa estructura en la misma forma en que fue generada (tamaño |S|) una única vez. Tiene pinta entonces de que ese |S|^2 puede reducirse a algo parecido a "|S| log |S|".

Por ejemplo, ¿cuantos elementos suBpassing hay al final? en:

"AABBCCD"

en el caso |S|^2 almacenaríamos

_: {A, B, C, D}
A: {0, 0, 0, 0}
B: {2, 0, 0, 0}
C: {2, 2, 0, 0}
D: {2, 2, 2, 0}

en el caso incremental, almacenaríamos

_: {A, B, C, D}
{0/A;2, 0/B;2, 0/D;2, 0}

donde u/V indica que hasta el elemento V hay esa cantidad.

En el peor caso, tendríamos igualmente |S|^2 elementos, pero en gran cantidad de datos de entrada (como en el ejemplo) se reduce drásticamente.

A partir de esta última estructura, se puede obtener cada "C[q].c" para el último loop, tan sólo hay que ir sumando los valores u1/V1;u2/V2;... según alcancemos V1, V2, ... para cada entrada en la estructura acumulativa.

Como digo, sólo se mejora el caso promedio, no el peor caso que sigue siendo |S|^2. Pero es importante este tipo de análisis, porque la elección del mejor algoritmo (en la práctica) suele estar fuertemente influenciada por la población de las entradas.
0votos

Escrito por josejuan hace 6 años

Y sí, sí se tarda lo mismo, veamos:

Sean:

A = [4, 5]
B = [1..10]
C = ['a'..'z']
D = ['x'..'z']

Tenemos (usa !! si lo prefieres):

A[4 - 4]
B[4 - 1]
C[ord('x') - ord('a')]
D[ord('x') - ord('x')]

en todos los casos el coste es O(1).
0votos

Escrito por jneira hace 6 años

Cierto, la ordenacion sin mas, te da directamente el modo de calcular el indice constante directo para los numeros y las letras.
Sin embargo para otro tipo de datos mas exoticos haria falta algo menos un poco mas engorroso, esto pensando pe en
data ExoticDigits=One | Zero | Five | Four | Nine | Eight | Three | Two | Seven | Six deriving (Eq,Ord,Show)

s=[Zero,One,Two,Zero,Five,Six] 
-- One < Zero == True

que seria utilizable por mi version de haskell
En ese caso habria que hacer un:
toInteger :: ExoticDigits -> Integer
toInteger One=0
toInteger Zero=1
...
0votos

Escrito por josejuan hace 6 años

Bueno, lo único que has hecho es una chapuza de implementación, pero sigue teniendo coste O(1) XD XD XD

Además, no hace falta la función "toInteger" en el loop principal (que recorre 'n') puesto que me sirve directamente la representación interna de Haskell y así, puedes usar la clase de tipos Enum así:

data Exotic = One | Zero | Five | Ten deriving (Eq, Ord, Show, Enum)
fromEnum Zero -- ESTE ES EL QUE USARÍAS COMO ÍNDICE

Ten en cuenta, que el operador de orden no lo uso como índice en ningún momento (que es lo que tú pensabas).

;)
0votos

Escrito por jneira hace 6 años

No, si te estaba dando la razon.. creo :-P
0votos

Escrito por josejuan hace 6 años

¡Oh!, como la implementación era TAN exótica pensé que era un ejemplo de dificultad en obtener el índice abstrayendo el conjunto C (perdón).

Mejor usar "fromEnum"... ;)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.