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:

Algoritmos para eliminar columnas por diferencias

Mensaje por JoanD »

Este tema va dirigido para los que hacemos nuestros "pinitos" en programación. Me gustaria recoger y aportar algunos algoritmos que sirvan para eliminar columnas por el método de las diferencias de signos.

Voy a presentar un par de métodos y me gustaria que si alguien tiene algún otro que lo añada.

Partimos, en ambos métodos, de una combinación inicial que préviamente hemos ordenado según nuestras preferencias (alfabeticamente, por esperanza matemática, por probabilidad, etc.)

METODO 1:

1- Definimos la diferència mínima = DIFMIN
2- leemos la primera columna y la guardamos en una matriz que denominaremos "ACEPTADAS".
3- leemos la siguiente columna y calculamos las diferencias de signos con todas las que hay en "ACEPTADAS".
4- Si encontramos una diferencia menor de DIFMIN la deshechamos.
5- Si las diferencias con todas las columnas aceptadas son mayores o iguales a DIFMIN la añadimos a la matriz de aceptadas.
6- Volvemos al paso 3 hasta leer todas las apuestas del fichero.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Segundo método

Mensaje por JoanD »

METODO 2:

1- Definimos la diferéncia mínima = DIFMIN
2- cargamos todas las apuestas en memória
3- La primera columna la guardamos en un fichero de disco.
4- Memorizamos la posicion, dentro del array, de la columna elegida y la guardamos en la variable POSICION.
5- Recorremos desde POSICION todas las apuestas que tenemos en memoria y calculamos las diferencias con ella.
6- Si la diferencia es menor que DIFMIN se marca como RECHAZADA.
7- Leemos la siguiente columna a partir de POSICION que no esté marcada como rechazada la guardamos en el disco y volvemos al paso 4 hasta que no se encuentran mas apuestas sin la marca de RECHAZADA
Avatar de Usuario
PacoHH
15
15
Mensajes: 21149
Registrado: Lun 20 Oct, 2003 8:03 pm
Ubicación: Almería
Contactar:

Mensaje por PacoHH »

Estoy usando el método 1 para encontrar la combinación con distancia 3 a partir de la directa al 14.

No puedo volcar a memoria las 480.000 columnas porque Qbasic no tiene semejante capacidad.

Con un compilador bastante majete he conseguido tener en memoria un máximo de 32.500 columnas, así que lo estoy haciendo leyendo de disco una a una las columnas de la combinación directa rentable y guardando en memoria las apuestas seleccionadas.

Conforme el conjunto de apuestas seleccionadas aumenta en memoria las comprobaciones se hacen cada vez más lentas porque tiene que comparar con más y más columnas.

48 horas calculando, va por 16.250 aceptadas, en 24 horas ha encontrado unas 4.000 nuevas y lo estoy haciendo con un Pentium apañadete de 1,6 Ghz y con Qbasic compilado que para otras cosas me va como un cañón.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Tienes razón Paco, el método 1 es muy rápido al principio y se va ralentizando a medida que aumenta el número de columnas aceptadas.

El segundo le pasa al contrario: es lento al principio y a medida que avanza se va acelerando ya que cada vez hay menos columnas a recorrer. Pero con este algoritmo se necesita mucha memória como bien dices. A mi particularmente me gusta el primero.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

¿Hay algún método mas?

¿Es posible evitar la enorme cantidad de veces que calculamos las diferencias entre dos apuestas distintas?

En el primer método no siempre hay que realizar la comparación con todas ya que cuando encontramos una diferencia por debajo de la exigida podemos ahorrarnos la comparación con el resto.

Podemos hacer los bucles como nos ha indicado Pinfly pero, ¿se puede optimizar mas aún?

Proximamente en sus pantallas ...
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

CONCEPTO DE BASE 3

Mensaje por JoanD »

Para avanzar un poco más es preciso realizar un poco de recordatorio de aquella parte de las matemáticas que nos permitía operar con otras bases diferentes a la base decimal que, dicho sea de paso, justifica que haya puesto el tema en el foro de Matemáticas en lugar del de Informática.

Curiosamente una columna consta de 14 signos realizada únicamente con uno, dos o tres signos que son el “1” el “X” y el “2” eso permite tratarla en base 3 en lugar de la base 10.

En base 10 usamos 10 caracteres (0,1,2,3,4,5,6,7,8 y 9)
En base 3 usamos 3 caracteres (0,1, y 2) pero también podemos usar (1,X y 2) respectivamente.

Equivalencias del 1 al 11

Base10 Base3
0 -------- 0
1 -------- 1
2 -------- 2
3 -------- 10
4 -------- 11
5 -------- 12
6 -------- 20
7 -------- 21
8 -------- 22
9 --------100
10 -------101
11 -------102

observar que en base 3 los valores 10, 100, 1000, 10000 se corresponden a potencias de 3 en base 10, es decir a 3, 9, 27 y 81 respectivamente o, lo que es lo mismo, a 3^1, 3^2, 3^3 y 3 ^4 . Estas potencias de 3 marcan la posición en la que aparece un nuevo dígito.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

CAMBIOS DE BASE

Mensaje por JoanD »

DE BASE 3 A BASE 10
Para convertir un numero de base 3 a base 10 hay que hacer lo siguiente:

Cada digito del número en base 3 empezando por la derecha hay que multiplicarlo por 3^0 el primer dígito; 3^1 el segundo dígito; 3^2 el tercer dígito y así sucesivamente hasta llegar al último digito. Sumamos todos estos valores y el resultado es el numero convertido a base 10.

Por ejemplo:
Si tenemos 21X12 es equivalente a tener 20102 (cambiamos 1 por 0 y X por 1). Para convertirlo a base 10 haríamos:

2*3^0 + 0*3^1 + 1*3^2 + 0*3^3+ 2*3^4 = 2 + 0 + 9 + 0 + 162 = 173


DE BASE 10 A BASE 3

Para convertir un numero de base 10 a base 3 hay que hacer lo siguiente:

Dividimos el numero entre 3, obtenemos el cociente y el resto. El resto es el primer dígito para el número en base 3.
Dividimos el cociente otra vez entre 3 y el resto de la división es el siguiente digito para la base 3 y así sucesivamente hasta que el cociente sea 0.

Por ejemplo:
Si tenemos 93124, procedemos a realizar las divisiones entre 3:

93124 / 3 = 31041 resto = 1
31041 / 3 = 10347 resto = 0
10347 / 3 = 3449 resto = 0
3449 / 3= 1149 resto =2
1149 / 3 = 383 resto =0
383 / 3 = 127 resto =2
127 / 3 = 42 resto =1
42 / 3= 14 resto =0
14 / 3 = 4 resto =2
4 / 3 = 1 resto = 1
1/3= 0 Final

El número en base 3 poniendo los dígitos obtenidos uno al lado de otro es: 1201202001 que en formato quinielístico equivale a X21X21211X (cambiamos 0 por 1 y 1 por X)
Última edición por JoanD el Sab 14 Feb, 2004 7:45 am, editado 1 vez en total.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

USO DE LA BASE 3

Mensaje por JoanD »

GENERAR LOS 14 TRIPLES

Se puede usar la base 3 para muchos de nuestros algoritmos que trabajan con quinielas.

Una primera aplicación del uso de la base 3 es la generación de todas las apuestas correspondientes a los 14 triples. Mi algoritmo preferido en BASIC es el siguiente:

FOR i = 0 to 3^14-1
     Apuesta$ = ConvierteBase10aBase3 (i)
NEXT i


mas sencillo, ¡IMPOSIBLE!

¿Qué hemos hecho? hemos generado 4782969 números del 0 al 4782968 y cada uno de ellos al convertirlo a base 3 nos ha devuelto una columna distinta.

Conclusión: cada número comprendido entre 0 y 4782968 representa a una columna. Conociendo el número en base 10 podemos determinar de forma univoca a que columna representa.

Eso lo podemos usar en muchos algoritmos, concretamente en los de eliminación de columnas que difieren en menos de un valor dado. Se trata del método nº 3.
Última edición por JoanD el Sab 19 Nov, 2005 1:02 pm, editado 1 vez en total.
[Nomada]

Mensaje por [Nomada] »

Joan eres una mina.
Ahora me explico por que no acierto ni una en las quinielas.

Gracias por la aclaracion de como converitir a base 3. Lo desconocia por completo.

Un saludo

P.D. A mañana mismo me pongo a ver eso de la distancia 3 a 5 entre columnas. Me parece que me sirve, ya comentare.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Nomada, si te sirve de consuelo yo tampoco acierto ni una en las quinielas, ni usando la base 3, ni la base 10, ni la metabase.

Así que no será por eso que no acertamos, pero el aspecto lúdico de todo ello me llena bastante. Ahora bien, si algún dia me toca, ¡¡¡ tiene que ser... la OSTIA !!!!
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

Sugerencia

Mensaje por Doctorpi »

Hola amigos,
Lamento no poder ayudaros mucho en estos temas debido a que los metodos de calculo que se emplean en MQ son TOP SECRET y los de MQWin (en desarrollo) aun mas, pero cuando teneis millones de columnas a comparar una opcion buena ha de ser que la comparacion sea lo mas rapido posible, porque los milllones de comparaciones no os lo quita nadie.
La pregunta es : cuantas comparaciones hago por cada dos columnas (14?) puedo hacerlo en menos codificando cada columna de alguna manera?
No os doy mas pistas, a ver si se os ilumina la idea feliz.
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 »

Grácias Doctor Pi por estimularnos a ideas nuevas a pesar del secreto profesional.

Está claro: no hace falta comparar los 14 signos si el contador de diferencias ha sobrepasado antes el limite que buscamos. El caso mas favorable sería, si buscamos diferencias de 3, que los 4 primeros signos sean diferentes. En este caso nos podemos ahorrar la comparación con los 10 restantes.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

METODO 3

En lugar de recorrer todas las apuestas mirando el numero de diferencias lo que podemos hacer es encontrar directamente las apuestas que se diferencian en un número de signos predeterminado. Con este método evitamos las comparaciones de columnas con el consiguiente ahorro de tiempo. A diferencia de los métodos 1 y 2, el tiempo que se tarda no es exponencial sino proporcional al numero de columnas leídas.

Los pasos a seguir son los siguientes:

1- Definimos la diferencia mínima = DIFMIN
2- Asignar un indicador de tipo byte para cada una de las 4782969 columnas posibles. Quizás eso no sea posible en Qbasic ya que creo que está limitado a un valor inferior. Asignamos memoria haciendo DIM Indicador(4782969) as Byte. No se trata de meter en memoria todas las apuestas sino sólo el valor de tipo byte que indica si está pendiente de analizar o no (podría ser también de tipo booleano)
3- Para cada apuesta calculamos su valor en base 10. Ese valor lo usaremos cómo índice dentro del vector “Indicador”.
4- Si el Indicador de esta apuesta tiene valor 0 la guardamos en el fichero de columnas aceptadas. Ponemos su indicador a valor 1.
5- Generamos todas las apuestas que se diferencian en un numero de signos menor a DIFMIN y ponemos su Indicador a valor 1
6- Leemos o generamos la siguiente apuesta y repetimos el paso 3 hasta finalizar todas las apuestas

He hecho la prueba con diferencia mínima = 3, contra los 14 triples. El procedimiento me ha encontrado 70.642 apuestas, ha tardado 58 minutos en un Pentium II con 192 Mb de RAM, ejecutando el programa en modo interpretado (sin compilar) y veo puntos donde se puede optimizar, pero primero intentaré hacer una versión que permita hacer algo parecido pero en lugar de hacerlo con los 14 triples hacerlo a partir de un fichero de entrada que seguro que tendrá un menor numero de columnas y por tanto se reducirá el tiempo de proceso. Cuando tenga eso miraré qué optimizaciones puedo hacer. Os tendré informados.
Avatar de Usuario
Felix Perez
12
12
Mensajes: 1620
Registrado: Mar 28 Oct, 2003 6:52 pm
Ubicación: Madrid
Contactar:

Mensaje por Felix Perez »

Joan, en relación a la base 3, yo tb lo utilizo, la generación es natural como comentas, facil y práctica.

En mi caso solo replanzo los 0 por X, el 1 y el 2 ya se representan ellos mismos.

Y respecto de las comparaciones cada columna de base3, se corresponde con el orden natural de los numeros de base 3 del 00000000000000 al 22222222222222 (XXXXXXXXXXXXXX al 22222222222222). Posiblemente algún calculo matematico pueda ayudar,
Resta?, esto no lo utilizo, hago comparaciones caracter a caracter, por lo que mis programas tardan algo mas.

¿La diferencia entre dos números de base 3 seria igual a la distancia entre ellos? en base 10.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Tienes razón Félix cambiando sólo los "0" por "X" se puede optimizar un "pelin" pero me pareció mas didáctico y entenedor que la columna de todo unos tuviera el valor 0.

Estoy mirando de descubir la aritmetica que se produce en base 3 y como se repercute en la base 10 para optimizar, estoy en ello.

Por cierto ya he realizado los cambios en el programa. Las columnas se leen de un fichero y las columnas aceptadas se guardan en otro. He añadido unos marcadores que indican el número de apuestas aceptadas y el numero de procesadas a sabiendas que eso incrementa el tiempo total pero como me ha salido un tiempo aceptable lo voy a dejar así puesto que de este modo se puede ir viendo como progresa y tener idea del tiempo que queda.

He hecho la prueba con las 839.726 apuestas de los 14 triples al directo (pendiente del filtro de Paco) ha tardado 32 minutos y lo ha reducido en 28.477 columnas que, si las primeras garantizan el 14, estas garantizan el 13.
Avatar de Usuario
Gott
11
11
Mensajes: 366
Registrado: Mar 21 Oct, 2003 12:30 am
Ubicación: Ferrol

Mensaje por Gott »

Tambien podría realizarse de la siguiente manera el estudio.

Supongamos un individuo que habitualmente tiene la siguiente estadísitca

5-6-6-6-7-5-5-6-6-6.

Si cogemos su columna base y obtenemos todas las que se diferencien de ella en 8 elementos. Si sigue la progresión tendríamos unos 14 bastante habituales no os parece?
Avatar de Usuario
PacoHH
15
15
Mensajes: 21149
Registrado: Lun 20 Oct, 2003 8:03 pm
Ubicación: Almería
Contactar:

Mensaje por PacoHH »

Algo parecido sugerí cuando presenté el Universo 1X2, es también una buena opción a la que se podría aplicar los filtros que estamos usando.
Avatar de Usuario
oscar1x2
10
10
Mensajes: 38
Registrado: Sab 07 Feb, 2004 12:31 pm
Contactar:

Mensaje por oscar1x2 »

Hola,soys unos genios de las matematicas,etc...os voy siguiendo como puedo.
PacoHH,el programa que me enviaste esta muy bien (a ver si me trae suerte) y ademas tambien salen unas buenas combinaciones reducidas,incluso alguna superando los porcentajes de wreductor y quiniwin (que es el que yo utilizo)
Saludos y enhorabuena por vuestros estudios intentare colaborar pero en tema de combinaciones reducidas.
Avatar de Usuario
Gott
11
11
Mensajes: 366
Registrado: Mar 21 Oct, 2003 12:30 am
Ubicación: Ferrol

Mensaje por Gott »

Paco de esta manera podríamos obtener unos resultados rentables. Si aún encima le decimos que nos de las que diferenciandose en X elementos de la base tengan Y variantes. Obtendremos un coste no tan alto y con una rentabilidad supuestamente buena. Estariamos hablando de tener DOCES en jornadas malas del pronosticador. Y el CATORCE bastante elevado.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

OBTENER LAS COLUMNAS QUE DIFIEREN EN UN SIGNO

Mensaje por JoanD »

El paso 5 del tercer método se puede mejorar a partir de la aritmética. Se trata del paso en que, dada una columna, debemos calcular los indices de todas las que columnas que se diferencian en un signo.

Si tenemos el siguiente número 6932 en base 10 y queremos generar números que sólo tengan un dígito diferente ¿qué haríamos?

Pues si queremos variar el segundo dígito comenzando por la derecha (el valor 3, en este caso), deberíamos restar 3*10 y a continuación sumarle 0 ó 10 ó 20 ó 40 ó 50 ... ó 90. Es decir:

6932 –30 +10*0 = 6902
6932 –30 +10*1 = 6912
6932 –30 +10*2 = 6922
6932 –30 +10*4 = 6942
6932 –30 +10*5 = 6952
6932 –30 +10*6 = 6962
6932 –30 +10*7 = 6972
6932 –30 +10*8 = 6982
6932 –30 +10*9 = 6992

Si queremos variar el tercer dígito comenzando por la derecha (el valor 9, en este caso), deberíamos restar 900 y a continuación sumarle 0 ó 100 ó 200 ó 400 ó 500 ... ó 800. Es decir:

6932 –900 +100*0 = 6032
6932 –900 +100*1 = 6132
6932 –900 +100*2 = 6232
6932 –900 +100*4 = 6332
6932 –900 +100*5 = 6432
6932 –900 +100*6 = 6532
6932 –900 +100*7 = 6632
6932 –900 +100*8 = 6732
6932 –900 +100*9 = 6832

La formula general para base decimal seria:

N + 10^(pos-1)*(i– ValorDigito)

Siendo:
N = número inicial
Pos = posición del digito contando desde la derecha
ValorDigito = valor del dígito
i = variable que va desde el valor 0 hasta la base –1. En base 10 va del 0 al 9, en base 3 va del 0 al 2

En base 3 ocurre algo similar, sea por ejemplo el número 210 en base 3
Si queremos variar el segundo dígito deberíamos restar 10^(pos-1) y sumarle 10*(i-digito).

Sean:

N=210
ValorDigito =1
Pos =2

Los valores obtenidos son:
210 + 10^(2-1)*(0-1) = 200
210 + 10^(2-1)*(1-1) = 210
210 + 10^(2-1)*(2-1) = 220

Todos los valores numéricos están expresados en base 3. Si quisiéramos expresar los mismos valores en base 10 deberíamos hacerlo así:

210 en base 10 es igual a 2*3^2 + 1*3^1 + 0 = 21

21 + 3^(2-1)*(0-1) = 18
21 + 3^(2-1)*(1-1) = 21
21 + 3^(2-1)*(2-1) = 24

La formula general para base 3 seria:

N + 3^(pos-1)*(i-Valordigito)

Como observación hay de aclarar que la variable ValorDigito debe estar en base 3 a diferencia del resto de valores.

La formula general para cualquier base seria:

N + Base^(pos-1)*(i-Valordigito)

Obteniendo los indices de esta manera nos ahorramos tener que convertir de base 3 a base 1
Última edición por JoanD el Dom 18 Abr, 2004 11:36 am, editado 3 veces en total.
Responder