java - permutar - Bases de datos de patrones almacenando todas las permutaciones

permutaciones java recursivo

Question

Estoy buscando algunos consejos sobre el almacenamiento de todas las permutaciones posibles para la base de datos de patrones marginales.

Así que el problema de quince baldosas tiene 16! posibles permutaciones, sin embargo almacenando los valores para la fringe por lo que el 0 (mosaico en blanco), 3,7,11,12,13,14,15 es 16! / (16-8)! = 518,918,400 permutaciones.

Estoy buscando almacenar todas estas permutaciones en una estructura de datos junto con el valor de la función heurística (que se incrementa cada vez que se realiza una iteración de la primera búsqueda de amplitud), hasta ahora lo estoy haciendo pero muy lentamente y me llevó 5 minutos. para almacenar 60,000 que es tiempo que no tengo!

En este momento tengo una estructura que se parece a esto.

Value Pos0 Pos3 Pos7 Pos11 Pos12 Pos13 Pos14 Pos15

Donde almaceno la posición de los números dados. Tengo que usar estas posiciones como la ID cuando calculo el valor heurístico que puedo rastrear rápidamente a la composición dada y recuperar el valor.

Estoy bastante inseguro de esto. El estado del rompecabezas está representado por un ejemplo de matriz:

int[] goalState = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Mi pregunta es ¿cuál sería la mejor estructura de datos para almacenar estos valores? Y la mejor manera de recuperarlos.

(Esta pregunta originalmente se basaba en el almacenamiento en una base de datos, pero ahora quiero almacenarlos en algún tipo de estructura de datos local, ya que la recuperación de una base de datos es lenta)

Answer 1

Cada número 0-15 es un número de 4 bits. Debe representar 7 de estos números, con un requisito mínimo de 28 bits, que se encuentra dentro del espacio de 31 bits con signo de un int . Así, todas las permutaciones pueden ser asignadas, y derivadas de, un int .

Para calcular este número, dadas las variables a hasta g :

int key = a | (b << 4) | (c << 8) | (d << 12) | (e << 16) | (f << 20) | (g << 24);

Para decodificar (si es necesario):

int a = key & 0xF;
int b = key & 0xF0;
int c = key & 0xF00; // etc

El almacenamiento de ints en una base de datos es muy eficiente y utilizará un espacio de disco mínimo:

create table heuristics (
key_value int not null,
heuristic varchar(32) not null -- as small as you can, char(n) if all the same length
);

Después de insertar todas las filas, cree un índice de cobertura para una búsqueda súper rápida:

create unique index heuristics_covering heuristics(key_value, heuristic);

Si crea este índice antes de la inserción, las inserciones serán muy, muy lentas.

Crear los datos e insertarlos es una codificación relativamente sencilla.

Answer 2

Entonces, ¿tengo entendido que está calculando un valor heurístico para cada posible estado de rompecabezas, y desea poder buscarlo más tarde en función de un estado de rompecabezas determinado? ¿Para que no tengas que calcularlo sobre la marcha? Presumiblemente debido al tiempo que lleva calcular el valor heurístico.

Así que estás repasando todos los estados de rompecabezas posibles, calculando la heurística y luego almacenando ese resultado. Y está tomando mucho tiempo para hacer eso. Parece que su suposición es que está demorando mucho tiempo en almacenar el valor, pero ¿qué pasa si el intervalo de tiempo que está viendo no es el tiempo que toma almacenar los valores en el almacén de datos, sino el tiempo que está demorando? ¿Generar los valores heurísticos? Eso me parece mucho más probable.

En ese caso, si desea acelerar el proceso de generación y almacenamiento de los valores, sugeriría dividir la tarea en secciones y utilizar varios subprocesos a la vez.

La estructura de datos en ayunas que creo que va a ser una tabla hash en memoria, con la clave hash en tu estado de rompecabezas y el valor en tu valor heurístico. Otros ya han sugerido formas razonables de generar claves hash de estado de rompecabezas. Se puede acceder a la misma estructura de tabla hash por cada uno de los subprocesos que generan y almacenan valores heurísticos para secciones del dominio de estado de rompecabezas.

Una vez que haya llenado la tabla hash, simplemente puede serializarla y almacenarla en un archivo binario en el sistema de archivos. Luego, haga que su servidor de valores heurísticos lo cargue en la memoria (y deserialícelo en la tabla hash de la memoria) cuando se inicie.

Si mi premisa es incorrecta, está demorando mucho tiempo en generar los valores heurísticos, entonces parece que estás haciendo algo extremadamente subóptimo cuando vas a almacenarlos. Por ejemplo, volver a conectarse a una base de datos remota cada vez que almacene un valor. Eso podría potencialmente explicar los 5 minutos. Y si se está reconectando cada vez que va a buscar un valor, eso también podría explicar por qué eso lleva demasiado tiempo.

Dependiendo de qué tan grandes sean sus valores heurísticos, una tabla hash de memoria podría no ser práctica. Un archivo binario de registros de acceso aleatorio (con cada registro simplemente conteniendo el valor heurístico) podría lograr lo mismo, potencialmente, pero necesitaría alguna forma de mapear matemáticamente el dominio de clave hash al dominio de índice de registro (que consiste en secuencial enteros). Si está repasando todos los estados de rompecabezas posibles, parece que ya tiene una forma de asignar estados de rompecabezas a números enteros secuenciales; sólo tienes que averiguar las matemáticas.

El uso de una tabla de base de datos local con cada fila simplemente tiene una clave y un valor no es irrazonable. Definitivamente, debería poder insertar 518 millones de filas en el espacio de unos minutos; solo necesita mantener una conexión durante el proceso de carga de datos y construir su índice una vez que finalice la carga de datos. Una vez que haya creado el índice en su clave, una búsqueda utilizando el índice (número entero de clave primaria agrupada) debe ser bastante rápida siempre que no tenga que volver a conectarse para cada búsqueda.

Además, si está comprometiendo filas en una base de datos, no desea comprometerse después de cada fila, querrá confirmar cada 1.000 o 10.000 filas. Si se compromete después de insertar cada fila, se degradará sustancialmente el rendimiento de carga de datos.

Answer 3

Realmente no puedo entender, qué significado especial tiene 0,3,7,11,12,13,14,15 en tu caso. ¿Es su posición inmutable? ¿Es su posición suficiente para identificar todo el estado del rompecabezas?

De todos modos, aquí hay un enfoque general, puede restringirlo en cualquier momento:

Como tiene 16 estados posibles al máximo, trataría de usar números hexadecimales para representar sus permutaciones. Entonces el estado {1,2,3,6,5,4,7,8,9,10,11,12,13,14,15,0} se vería como 0x123654789ABCDEF0 = 1312329218393956080 . El mayor número posible sería 0xFEDCBA9876543210 , que aún puede almacenarse en un largo sin firmar (solo desde Java 8) o alternativamente en BigInteger (hay muchos ejemplos, preferiría esto). Dicho número sería único para cada permutación y podría usarse como clave principal y, si tiene todo el estado, recuperarlo de la base de datos sería bastante rápido.

//saving your permutation
String state = "0xFEDCBA9876543210";
BigInteger permutationForDatabase = new BigInteger(state, 16);
//and then you can insert it into database as a number
//reading your permutation
char searchedCharacter = ''A'';//lets say you look for tile 10
BigInteger permutation = ...;//here you read the number from the database
int tilePosition = permutation.toString(16).indexOf(searchedCharacter);

Puede haber una solución más elegante / con mejor rendimiento para obtener la posición del mosaico (quizás algo de magia de operación de bits).