C/Visual C - Optimización de una ED

   
Vista:

Optimización de una ED

Publicado por Jdrap (3 intervenciones) el 29/10/2008 21:52:47
Hola, tengo una duda acerca de como hacer más eficiente una estructura de datos.
La cosa es que quiero hacer una matriz 9x9 donde cada elemento sea a su vez, una lista de elementos posibles del 1 al 9 (vamos, para representar un sudoku...). Mi problema es que quiero hacerlo lo más eficiente posible, en cuestión de añadir elementos posibles o eliminarlos dentro de cada celda de elementos.
He pensado en utilizar una variable de tipo unsigned short (2B) para representar bit a bit la presencia o no de un elemento dentro de los elementos posibles (utilizaría los 9b menos significativos).
Para hacer set o unset de cada bit utilizaría una función a la que le paso el elemento que quiero modificar y en un switch según el elemento aplicar una máscara determinada en cada posición.
Mi pregunta es: ¿Penáis que esto sería mas eficiente que utilizar un array para representar cada celda de elementos posibles y mantener los elementos que quedan en el array?
Gracias, un saludo.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:Optimización de una ED

Publicado por AntonioG (42 intervenciones) el 30/10/2008 19:26:24
Hola,

Pues asi estarias guardan por cada celda del sudoku por lo menos 9b, o sea 9x9x9b=729b

Mira, pensandolo poquito (la verdad solo lo que tarde en leer tu mensaje :D), a fin de cuentas en cada renglon del sudoku no se pueden repetir numeros, lo mismo por columnas. Entonces, para cada numero del 1 al 9 debemos guardar en que renglon (9b) y en que columna (9b) est'a. Claro que falta un valor que indica que no se ha asignado renglon o columna (en tu planteamiento tambien lo deberias considerar, diciendo que a una casilla no se le ha asignado un numero aun, por lo que t'u en realidad necesitarias 9x9x10b=810b), y entonces por cada numero del a 1 al 9 necesitamos 10b (renglon asignado) y otros 10b mas (columna asigna), por lo que se usarian
9x(10+10)b=180b. Seria una reduccion al 22.2% en el uso de bits.

Bueno, como no hay una variable con 20b, pues usariamos 3 char (8 bits cada uno), asi tendriamos 24b por numero del 1 al 9, en total 216b. En tu caso, con 2B por casilla, tendrias 9x9x16b=1296b, por lo que en realidad la reduccion en bits es al 16.6%.

Bueno, que te parece mi planteamiento?

Saludos
P.D. para que ahorrar bits si la compu tiene muchos? :D
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Optimización de una ED

Publicado por jdrap (3 intervenciones) el 30/10/2008 22:26:11
Hola de nuevo, gracias por tu contestación, pero creo que no me explique bien cuando escribí el primer mensaje.
Cuando hablo de optimización no es en cuestión de tamaño sino de eficiencia en tiempo, el hecho de utilizar bits es para ahorrarme el tener que recorrer vectores para consultar si un valor está como elemento disponible o no.
De esta manera, solo tendría que aplicar una mascara para consultar si un elemento se encuentra como posible. La duda es si de esta manera ahorraria tiempo o si en verdad el ahorro no sería casi significativo.
Este empeño en conseguir un método tan eficiente es porque el programa en cuestión va a ser un resolutor de sudokus usando heurísticas que van a ser bastante complejas en tiempo por lo que quizás un ahorro en esta etapa si sea importante.
Espero haberme explicado bien en lo que quiero conseguir porque es verdad que en el primer mensaje no lo dejé claro.
Espero que puedas ayudarme, un saludo.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar