Algoritmos para eliminar columnas por diferencias

Algoritmos, fórmulas, estadísticas...
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Yo no veo que falte nada.

no entiendo que queres decir con que le faltan 9 unos a los 5 primeros triples.

Con 242 bits representas los 5 triples. No falta nada.
Al contrario, sobran bits.
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Si a lo que te refieres es que no puedes operar con los bytes de forma tradicional entonces te doy la razon.

Hay que crear un array en memoria con los 5 triples y asignarlo al codigo asci correspondiente.

Un char o codigo asci nos ocupará 1 byte.
Y con 242 bytes construimos un array para los 5 triples.

Cojemos una linia, los 5 primero signos y buscamos el codigo asci correspondiente dentro del array.

Imaginemonos.

21X22 - 1122X- 2111
227 153 2


buscamos dentro del array el " 21X22 " nos da el 227
luego buscamos el " 1122X " nos da el 153
y luego el "2111" y nos da el 2

Guardamos esto en otro array que se llame " apuestas "
y CADA COLUMNA nos ocupa 3 bytes;

Luego para descifrar la columnas se utiliza el metodo a la inversa, que es sensiblemente mas rapido, solo hay que apuntar a la posicon de array que nos indica el char ( 227 , 153 , 2 )

Juntamos las 3 posiciones de array y nos da una columna.


Espero haberme explicado lo suficientemente bien.
coarma
10
10
Mensajes: 53
Registrado: Sab 18 Oct, 2003 7:49 pm

Mensaje por coarma »

Esto

12X22

no es una columna de quinielas, no es una apuesta, no es una columna del desarrollo de 5 triples. Una apuesta es esto

12X22 11111 1111 o esto
11111 12X22 1111 o esto
11111 11111 2X22.

La respresentación de 14 triples no son
243+243+81 sino
243*243*81 o sea 18 Kb, no 3 bytes.
Aun así la idea sigue siendo muy buena, imagino que así trabajan los programas en ensamblador.
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Vamos a ver Coarma

Esto és una columna de quinielas.

21X221122X2111

Luego la divides en 5+5+4 y queda así.

21X22 - 1122X- 2111


Luego cojes el primer " 21X22 ", 5 triples = 243 apuestas

Como todos los programadores sabreis, 1 byte son 256 bits;

Por lo tanto, con 1 byte se pueden representar 256 VALORES DISTINTOS, por lo tanto se pueden representar 256 APUESTAS DINSTINTAS.
Pero nosotros sólo necesitamos 243 VALORES DISTINTOS que son las apuestas de 5 triples.

signos - (INT)char

21X22 - 1122X- 2111

21X22 - 227
1122X - 153
2111 - 2
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Se necesitan 1.594.323 bytes o sea 1,6 MB para poder guardar en memoria todas las columnas que componen los 14 triples.

Con el metodo tradicional se necesitan 76.527.504 bytes o que es los mismo 77MB de memoria.

Metodo Binario : 1,6 MB
Metodo Tradicional : 77 MB
coarma
10
10
Mensajes: 53
Registrado: Sab 18 Oct, 2003 7:49 pm

Mensaje por coarma »

Pinfly, mi último post lo puse sin leer el anterior tuyo.

Veamos, que nos estamos liando un poco. O te entendí mal o no te explicaste bien, lo mismo da.

En tu primer post pusiste

******************************
**** 3 bytes para 14 triples. ******
******************************

Creí que tenías un método para meter en memoria los 14 triples en 3 bytes, aunque no fuera así en 18Kb ya sería genial.

pero en otro post posterior pones

"y CADA COLUMNA nos ocupa 3 bytes"

que no es lo mismo, claro. En fin, lo dicho no nos hemos entendido aunque quien sabe a lo mejor si es posible meter 14 triples en 18Kb.

En cuanto a representar una columna por tres números lo entiendo perfectamente y así lo hago en mis programas. En visual Basic son 3 enteros, o sea 6 bytes, un ahorro considerable sobre los 14 bytes en memoria de una columna.

Insisto, la idea es muy buena, gracias por tu aportación, aunque 3 bytes por columna por 4,8 millones de columnas ya no son 18 Kb.

Un saludo.
[Nomada]

Mensaje por [Nomada] »

Muy interesante eso de los 0 y 1

A lo mejor es una tonteria de las mias, pero para represntar las los 4 millones y pico de columnas solo necesito un array con 16.384 posicones osea los 14 dobles desarrollados.

Mi inconveniete es poner velocidad y hay es donde uno no sabe como hacerlo.

Habia pensado en poner la suma que me da la columna al completo, inconveneite que hay con la misma cantidad y no hay manera de hacerlo.

Ventaja que cada una tiene su contraria.

Un saludo
coarma
10
10
Mensajes: 53
Registrado: Sab 18 Oct, 2003 7:49 pm

Mensaje por coarma »

De hecho se puede representar cada columna por un número inequívoco sin más que multiplicar los tres grupos de 243*243*81

Lo edito porque lo anterior es un error, por ejemplo
la columna (1,2,1) es distinta a (2,1,1) sin embargo el producto es 2 en ambos casos.

Pondré un código similar al que he puesto más abajo para numerar los 14 triples, cuando revise mis notas, que ahora estoy con un fuerte gripazo.
Última edición por coarma el Lun 23 Feb, 2004 10:41 pm, editado 1 vez en total.
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

Me entendereis si me mantengo al margen!!!

Mensaje por Doctorpi »

A buen entendedor pocas palabras bastan :lol: :lol: :lol:
Felicidades
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 »

Coarma, en Visual Basic 6 existe la variable de typo byte, no se si ya existía en Visual Basic 5, pero ocupa 1 byte y puede tener valores comprendidos entre 0 y 255 por lo tanto una columna se puede almacenar en 3 bytes que frente a los 14 ó 15, que puede tener su representación alfanumérica, és un ahorro importante de memória.

La conversión de la cadena alfanumérica en los tres bytes es muy simple: se cogen los 5 primeros caracteres y mediante la función que convierte base 3 a base 10 obtenemos el valor del primer byte, hacemos lo mismo para los 5 del medio y para los 5 del final (digo 5 por si contiene el pleno al 15). Así de simple.
coarma
10
10
Mensajes: 53
Registrado: Sab 18 Oct, 2003 7:49 pm

Mensaje por coarma »

OK, yo utilizaba este código para transformar una columna a los tres números:

Line Input #1, columna 'lee columna, hacer bucle para combinación.

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


For x = 1 To 3

colTrans(1, x) = 0
parcial = 5 * (x - 1)

'genera los tres números(x,x,x)

For n = 5 To 2 Step -1
parcialNum = (3 ^ (n - 1)) * (Mid(columna, parcial + (5 - (n - 1)), 1) - 1)
colTrans(1, x) = colTrans(1, x) + parcialNum
Next
colTrans(1, x) = colTrans(1, x) + Mid(columna, parcial + (5 - (n - 1)), 1)
Next

que hace lo mismo que tu función, (no sé cual será más rápido)
pero lo mejor es leer de una tabla ya preparada y meterla en memoria, no hace falta usar tu función ni el código.

De todas formas la memoria no es problema, pero imagino que se trabajará más rápido con bytes que con integer, esto tengo que probarlo. Lo que pasa es que para mí manejar datos binarios es peor que tener una novia casquivana. (:-))
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Alguien ha probado nunca el RAMDISKXP.

Es un programa que permite crear una unidad de DISCO VIRTUAL con la memoria RAM sobrante.

La unidad està almacenada en RAM. Acceso rapidissimo a disco(RAM).

Si el problema és la lentidud de la transferencia en disco, pues está és una buena solucion.

Lo he estado probando, y aumenta bastante la velocidad, aunque un buen coprocesador matematico ayuda mas.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Al reeler el hilo de este tema he visto que hay cierta confusión en el concepto "bit". Pinfly dijo: "1 byte tiene 256 bits". En realidad 1 byte tiene tan solo 8 bits. Estos 8 bits los podemos representar en binario como ceros o unos. Poniendo ceros o unos a estos bits podemos generar 256 (2^8) valores distintos. En binario irían desde el valor 00000000 hasta el valor 11111111. En decimal irian desde el valor 0 hasta el 255.

Para representar 5 triples necesitamos 3^5 valores, es decir 243.
Por lo tanto los valores comprendidos entre 0 y 242 pueden representar univocamente al desarrollo de los 5 triples.

Ahora bien, nos sobran 255-242 = 13 valores que nunca vamos a usar. ¿significa eso que nos sobra algún bit de los 8 que forman el byte?. Pues NO.

Si usamos sólo 7 bits únicamente podriamos representar 2^7= 128 valores. Por lo tanto para representar 5 triples necesitamos 8 bits (1 byte).

Sin embargo, sí és cierto que si descomponemos 14 partidos en 5 + 5 + 4, el grupo de 4 requiere 3^4 = 81 valores y eso se puede hacer con 7 bits. Sobra por lo tanto 1 bit para cada columna y nada mas.

Tan sólo és una idea, este bit que sobra se puede usar como valor booleano para marcar la columna. Eso puede ser útil en algunos procesos que requieran saber si una columna ha sido analizada o no.

En algunos procesos como por ejemplo el que nos ocupa de eliminación de columnas por diferencias sólo se necesita un array de 3^14 bits (sí bits y no bytes) para indicar que ya fue procesada. La posición del bit dentro del array de bits nos indica univocamente la columna que representa, solo hay que convertir la posición a base 3. En este caso los 14 triples ocupan 3^14/8/1024 = 584 Kb.

Una cosa que he podido comprobar personalmente es que reduciendo la memória necesaria y evitando trabajar con cadenas (al menos en Visual Basic) la velocidad de los programas aumenta enormemente. Si además se programan en C++, la velocidad puede ser de vértigo. Seguro que Dr Pi consigue hacer programas veloces por los algoritmos que usa pero tambien por el lenguage que emplea para desarrollarlos.
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Quizas si dije que 1 byte eran 256 bits, però fue un error. Realmente se que un byte son 8 bits.

Y por el tema de velocidad se refiere, me gustaria que alguien me contará cual es la manera más rapida de processar columnas en C++.

Tengo entendido, que si los contadores del BUCLE se declaran como registros internos de la CPU " register INT " aumenta considerablemente la velocidad.
Però no se si luego las operaciones a nivel de BIT que contabamos, haran reducir la velocidad al tener que poner en BASE3 el conjunto de BITS.

Pido sugerencias para determinar el mejor mètodo para ganar velocidad. No me importaria crear una libreria para hacer las funciones de BASE3 y pasar columnas a BITS en un array, pero primero desearia saber la manera de aumentar la velocidad y luego me pongo a ello.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

No hace falta manipular bits. Si logras hacer una DLL en C con las funciones que te convierten una columna (o fragmento de columna) a base 10 y su contraria seguro que la conversión seria muy rápida. Estaria bien que las funciones se pudieran llamar desde Visual Basic.

Las funciones que tengo en VB son estas. Me gustaria tener mas tiempo para convertirlas a C pero tengo poca practica. Si tu Pinfly, que veo que dominas el lenguaje C, quieres y puedes, te pongo las funciones que uso en VB para que las puedas traducir mas rápido.

Public pot(13) As Long
Private SignoQuini(3) As String

Public Sub IncializarPotenciasDe3()

      For z = 0 To 13
           pot(z) = 3 ^ z
      Next z

      SignoQuini(0) = "1"
      SignoQuini(1) = "X"
      SignoQuini(2) = "2"

End Sub

Public Function ConvBase3aBase10(ByVal Cadena As String) As Long

      Dim z As Integer
      Dim n As Integer
      Dim L As Long

      L = 0

      For z = 0 To Len(Cadena) - 1
           Select Case Mid$(Cadena, z + 1, 1)
                Case "1": n = 0
                Case "2": n = 2
                Case Else: n = 1
            End Select

           L = L + n * pot(z)
      Next z

      ConvBase3aBase10 = L

End Function

Public Function
ConvBase10aBase3(ByVal Numero As Long, ByVal Longitud) As String

      Dim Divisor As Long
      Dim Resto As Integer
      Dim L As Long
      Dim Resultado As String

      L = Numero
      Do
           Divisor = L \ 3
           Resto = L Mod 3
           Resultado = Resultado & SignoQuini(Resto)
           L = Divisor
      Loop Until L = 0

      ConvBase10aBase3 = Left$(Resultado & String(Longitud, "1"), Longitud)

End Function
Última edición por JoanD el Sab 19 Nov, 2005 1:11 pm, editado 1 vez en total.
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

No domino VB lo siento. Ya se que estoy un poco desfasado en este aspecto, pero no tengo tiempo para aprender.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Desfasado no, el C o, mejor aún, el C++ son mucho mas potentes que el Visual Basic y también mas dificiles de programar, al menos para mí.

Así que si sabes C estas en mejor disposición de realizar programas super-rápidos.

Cambiando de tema creo que había quedado un cálculo, que propuso Coarma, sin resolver. Se trata de convertir los tres bytes en un valor únivoco dentro del rango de 0 a 47829698. Supongamos que los valores de los tres bytes son respectivamente a, b y c

Valor = a + b*3^5+c*3^10

es decir los bytes segundo y tercero hay que multiplicarlos por la potencia de 3 adecuada para que el resultado sea correcto.
Pinfly
10
10
Mensajes: 60
Registrado: Mié 12 Nov, 2003 11:48 pm
Ubicación: Olot

Mensaje por Pinfly »

Si quereis convertir los 3 bytes a valor único vamos por mal camino, porque estamos retrocediendo dentro del concepto de utilizar cuantos menos bytes posibles.
De 0 a 47829698 es un numero del tipo LONG o FLOAT. Eso ya ocupa mas de 3 bytes, no os parece que volvemos para atras ?

Creo que seria mejor una rutina para convertir los 3 bytes a columnas y viceversa.
Una buena idea seria colocar 5 triples en memoria con su correspondiente valor representado por 1 byte. Esto se haria con un bucle al principio del programa. Creamos columnas para 5 triples y vamos dandole valor correlativamente para su representacion en byte " 0,1,2,3.... " Eso lo dejamos en memoria.
Cuando queramos passar una columna a byte, buscamos en memoria (mas rapido) la columna, haciendo un barrido de 0 a 243, y cuando la encontremos guardamos su valor de byte en A, luego en B y luego en C para los 4 primeros triples.


Si , al contrario, queremos pasar los 3 bytes a columnas, solo tenemos que ponernos en la direccion de memoria que nos indica cada byte, y aparecerá la columna.


COLUMNA[0]="11111"; (byte 0);
COLUMNA[1]="X1111"; (byte 1);
COLUMNA[2]="21111"; (byte 2);
......
......


Un concepto que quiero dejar claro, es que hacer barridos de 0 a 243 consume tiempo (ms), y habria que buscar un metodo mejor. Seguro que lo hay.
Se podria por ejemplo indexar la busqueda diciendole que si el ultimo signo es X empiece a partir de 81 y si es 2 que empiece a partir de 162.
Todo eso habria que verlo sobre la marcha.

Todas formas yo pienso que Dr.Pi sabe algo mas al respecto sobre eso. Seguro que utiliza un sistema similar. Y si no lo hace, seguro que tiene ideas como solucionar esto, por lo tanto, Dr.Pi, pido tu colaboracion.

Acias !! :)
Avatar de Usuario
Doctorpi
12
12
Mensajes: 2660
Registrado: Mié 15 Oct, 2003 6:14 pm
Contactar:

De ascii a bytes y viceversa

Mensaje por Doctorpi »

Hola
Si quereis convertir una cadena de 5 caracteres "1XX21" a su equivalente en 1 byte.
Precondiciones :
en des esta "1XX21"
char des[5];
xalay es la tabla de las potencias de 3.
int xalay[5];
xalay[0]=1;
xalay[1]=3;
xalay[2]=9;
xalay[3]=27;
xalay[4]=81;
En res se guardara el resultado.
char res; // Un char es un byte o sea un valor de 0-255

for ( i=0;i<5;i++ )
{
if ( des=='X' ) ;
else if ( des=='1' ) res+=xalay[4-i];
else res+=(2*xalay[4-i]);
}

El resultado es nuestros cinco primeros signos en un byte que se guarda en res.

De byte a ASCII la propuesta de Pinfly es sin duda la mas rapida
cadena[byte]="1XX21" ya que es un solo acceso a memoria.

Un saludo
Dr.Pi
Última edición por Doctorpi el Dom 28 Mar, 2004 10:23 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:

Mensaje por JoanD »

Para convertir una columna en 3 bytes sin necesidad de realizar el bucle que propones se puede hacer directamente convirtiendo cada tercio de la columna a base 10.

Eso que dices lo he probado, pero en Visual Basic obtengo mejor rendimiento metiendo los 14 partidos en una variable de tipo LONG que gastar tiempo en partirlo en tres trozos. La variable de tipo LONG ocupa sólo 4 bytes por lo que la diferencia no es tanta. En C++ seguro que es mejor plantearlo como tu dices.

Una cuestión importante es evitar las comparaciones de cadenas, partir los 14 signos en 3 grupos permite tener una matriz bidimensional en memória de 243 * 243 que contiene la diferencia de signos entre 2 columnas de 5 signos y por lo tanto si hay que hacer muchas comparaciones se puede reducir el tiempo enormemente. Pero otro camino es pensar en algoritmos que eviten las comparaciones y este es el camino que he emprendido y con buenos resultados teniendo en cuenta que mi ordenador es lento (Pentiun II) y que el lenguaje no es el más rápido (Visual Basic) estoy consiguiendo resultados muy aceptables.

Para que el cálculo sea instántaneo no se me ocurre otra cosa que tenerlos precalculados en memória, no sé como, ya que las condiciones son de diversa indole, por ejemplo el numero de interrupciones no se puede obtener por la suma de las interrupciones de los 3 fragmentos. Pero este es el gran segreto de Dr. Pi. No se si algún dia nos lo explicará. Seguro que se nos cae la baba.
Última edición por JoanD el Dom 28 Mar, 2004 9:44 am, editado 1 vez en total.
Responder