Algoritmos para eliminar columnas por diferencias

Algoritmos, fórmulas, estadísticas...
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Cuando escribí el anterior post no habia leído el del Dr. Pi, seguramente nos hemos cruzado.

Así que queria agradecer al Dr. Pi por la rutina de conversión en C, se parece a la de VB pero seguro que es mas eficiente ya que, para el C, acceder a un caracter de una cadena de caracteres es como acceder a una posición de un array. En VB hay que usar el MID$ y eso penaliza bastante.

Muchas grácias al Dr. Pi.

Un dia de estos me lio la manta a la cabeza y hago una DLL en C++
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

Secretos

Mensaje por Doctorpi »

Hombre, permitidme que me guarde cosillas en la recamara, pero solo deciros que tablas precalculadas, mascaras, OR, AND y SHIFTS de bits es habitual si se pretende ir rapido. Las operaciones anteriormente citadas tienen su equivalente en ensamblador y por lo tanto atacas el problema casi al mas bajo nivel.
En C . OR | , AND & y SHIFT (desplazamientos) >>, << son muy practicos si se sabe su uso y sus aplicaciones.
Ya no digo mas, pero no digo que todo lo que yo hago , tras un estudio y realizar muchas pruebas, no se pueda llegar a conseguir.Es mas seguro que es mejorable.
Hacer un programa Nesquick :lol: es dificil, pero de momento no me quejo de mis resultados en el MQWin. Seguro que os sorprendere, hasta en un P II (porque ya lo he probado :lol: ).
Un saludo y suerte
Dr.Pi
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Gracias Dr.Pi por tu expliacion. He quedado maravillado del calculo que propones para passar el array a byte.

Con eso ya queda todo dicho, sólo falta ponernos a trabajar.

Repito nuevamente, gracias Dr.Pi
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Hoy estoy de un resacon impresionante. Pero prometo que cuando me llegue riego sanguineo al cerebro me pongo a eso.
coarma
10
10
Mensajes: 53
Registrado: Sab 18 Oct, 2003 7:49 pm

Mensaje por coarma »

Uf, se me había olvidado por la maldita falta de tiempo poner una fórmula o método para numerar los 14 triples. Aunque ya lo ha tratado Joan lo pongo aquí como método complementario.

En VB sería:

columna = "1X211X211X1121"
columna = Replace(columna, "X", "3")

For n = 14 To 2 Step -1
parcialnum = (3 ^ (n - 1)) * (Mid(columna, 14 - (n - 1), 1) - 1)
numero = numero + parcialnum
Next n
numero = numero + Right(columna, 1)

así de sencillo, lástima que no pueda ponerlo en notación matemática pero sería algo así como

el sumatorio desde n=14 hasta 2, de 3 elevado a n-1 por el signo cuyo numero de orden es n, menos 1 y a lo anterior se le suma el último signo, (que es el partido 14).
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

Mas cosas

Mensaje por Doctorpi »

Los 14Triples se pueden almacenar en menos de 584Kb, si cada quiniela es un bit. Aqui otra vez os resalto el uso de rutinas de manejo de bits como importantisimas para velocidad y reducir la capacidad de almacenamiento.
Un saludo
Dr.Pi
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Cada quiniela és un bit.. ? o un byte ?
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

cada quiniela un bit.
el primer bit repesenta a "1111111111111"
el bit nº 3^14 representa a "2222222222222"

es decir el numero de orden, o sea la posición, del bit determina si una columna està seleccionada o no.

La idea es muy buena
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Como que cada boleto tiene 8 columnas y un byte tiene 8 bits podemos considerar que un boleto es un byte.

Conociendo la posición del bit dentro de los 3^14 bits hacemos una división entera entre 8:

- el cociente +1 indica el byte donde está el boleto (excepto si el resto es 0)
- el resto indica la columna dentro del boleto
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Ya entiendo lo que dices. pero eso suponiendo que tienes una tabla con todas las columnas cargada en memoria.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Lo que se puede hacer en lugar de cargar las columnas es poner el bit que le corresponde a 1.

De esta manera puedes saber las columnas que has cargado mirando los bits que estan a 1. Luego si conviene se transforma la posición del bit en los 14 signos o en los 3 bytes, pero sólo cuando convenga y de forma individualizada. Es decir nunca tendremos en memória todas las apuestas en formato de 3 bytes tan sólo la que se esté tratando en aquel momento.
josebalad
10
10
Mensajes: 6
Registrado: Mié 17 Dic, 2003 1:03 pm
Ubicación: Barcelona

Mensaje por josebalad »

Una pregunta Dr Pi. en el algoritmo que propones para pasar de char[5] a 1 byte, si des="XXXXX" el resultado en res no seria null?. Es solo una apreciación a lo mejor no entiendo bien los if .... else... else if... Bueno saludos a todos. Realmente el programa que se quiere conseguir que hace exactamente????.

Saludos y a ver si encontramos el mejor metodo de trabajar con columnas..
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

Aclaracion

Mensaje por Doctorpi »

Hola josebalad
El algoritmo calcula el numero que corresponderia a una cadena de 5 signos. En realidad el XXXXX corresponde al 0 y el 22222 al 243.
En esto todo el mundo se ha de poner de acuerdo o no se corresponderan las quinielas.El criterio es una convencion y viene de lejos.
Un saludo.
Dr.Pi
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

No se si estaré confundido pero si lo que hacemos, siguiendo con la idea de Dr. Pi, es asignar un byte para marcar a 256 columnas en lugar de 8, resulta que los 14 triples los puedo tener en 13,12 Kb
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Lo he pensado mejor y he llegado a la conclusión de que estoy confundido. Lo que acabo de escribir és una falacia. El mínimo es un bit por columna por lo tanto son 583,85 Kb
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

Justo

Mensaje por Doctorpi »

Son 8 columnas por byte no 256. Ahi la falacia.
Un saludo
Dr.Pi
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Que el valor 0 represente a las "X" és fruto de la optimización, como decia Félix, el "1" y el "2" se representan a sí mismos y por lo tanto sólo hace falta convertir las "X", Dr. Pi lo hace así, Coarma tambien cambia sólo las "X" y yo no lo hice al principio por considerar que era mas didáctico que el todo "unos" fuera el 0, que ahora me arrepiento, pero me da mucha pereza rehacer todas las utilidades que tengo hechas.

Josebalad pregunta sobre el programa que se quiere conseguir. La verdad es que yo ya lo he conseguido. Se trataba de hacer un programa que hiciera la simplificación de columnas imponiendo una diferéncia minima de signos entre todas ellas. Para mi el resultado es bueno ya que un programa que tardaba dias en procesar los 14 triples, ahora lo hace en dos minutos. Lo que pasa és que no és instantáneo como el NesQuick y aquí estamos todos dandole vueltas a ver si se nos ocurre como mejorar todavia mas. Y la verdad es que me gusta que Dr. Pi nos cuente alguna cosilla aunque, no lo pueda explicar todo, algo es algo.
[Nomada]

Mensaje por [Nomada] »

Ya me gustaria a mi saber programar de esa maneraa, sigo con lo tradicional, comparación de caracteres. Lento. lento.

Algo aprendo en este campo de la informatica, poco a poco iremos puliendo las cosas y ganado en Mhz de velocidad.

Seguid con el tema, que voy coguiendo la onda.

Un saludo
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Ahora supongamos que tenemos 4.782.969 bits en memória. Como no existe la variable de typo bit. Tenemos que dimensionar un array de tipo Byte en VB o de tipo Char en C++.

La dimensión del array deberá ser de: 4.782.969/8 = 597.872 elementos.

Ahora se trata de que dada una columna quinielista cuyo valor decimal es conocido, por ejemplo 1.384.538:

- ¿como obtenemos el byte que contiene el bit nº 1.384.538?
- ¿cómo ponemos a 1 este bit sin alterar los otros 7 bits?
- ¿Cómo podemos saber si un determinado bit està a 1 ó a 0?

Cuando sepamos hacer todo esto. Nos tendremos que preguntar ¿como hacer los cálculos de forma super rápida?.

Dejo las preguntas en el aire. Yo me voy a dormir que tengo sueño. Buenas noches.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

BITS EN BINARIO I EN BASE 10

Mensaje por JoanD »

Ya me he levantado. No tengo tiempo para responder a todas mis preguntas pero de momento pongo aquí las equivalencias entre los valores binarios de cada bit con el equivalente número decimal.

00000001 = 2^0 = 1
00000010 = 2^1 = 2
00000100 = 2^2 = 4
00001000 = 2^3 = 8
00010000 = 2^4 = 16
00100000 = 2^5 = 32
01000000 = 2^6 = 64
10000000 = 2^7 = 128

Ahora me tengo que ir a trabajar. Pero continuará !!
Responder