Hace un par de meses, finalmente tuve que admitir que no era lo suficientemente inteligente como para pasar por algunos niveles del rompecabezas
Snakebird . La única forma de recuperar parte de la autoestima era escribir un solucionador. Entonces podría pretender que crear un programa para resolver el rompecabezas es casi lo mismo que resolverlo yo mismo. El código para el programa C ++ resultante está disponible en
Github . La parte principal del código considerado en el artículo se implementa en
search.h y
compress.h . En esta publicación, hablaré principalmente sobre la optimización de una búsqueda de amplitud que requeriría 50-100 GB de memoria para caber en 4 GB.
Más tarde escribiré otra publicación, que describirá los detalles del juego. En esta publicación, debes saber que no pude encontrar buenas alternativas a la fuerza bruta, porque ninguno de los trucos habituales funcionó. El juego tiene muchos estados, porque hay muchos objetos en movimiento o empujados, y la forma de algunos de ellos es importante, lo que puede cambiar con el tiempo. No existía una heurística conservadora adecuada para algoritmos como A * para reducir el espacio de búsqueda. El gráfico de búsqueda se orientó y se especificó implícitamente; por lo tanto, la búsqueda simultánea en las direcciones hacia adelante y hacia atrás era imposible. El único movimiento podría cambiar el estado de muchas maneras no relacionadas, por lo que nada podría ser útil como hacer
hash a Zobrist .
Estimaciones aproximadas han demostrado que en el rompecabezas más grande, después de eliminar todas las posiciones simétricas, habrá alrededor de 10 mil millones de estados. Incluso después de empacar descripciones de estado con densidad máxima, el tamaño del estado era de 8-10 bytes. Con 100 GB de memoria, la tarea sería trivial, pero no para mi máquina doméstica con 16 GB de memoria. Y dado que Chrome necesita 12 GB de ellos, mi suministro de memoria real está más cerca de 4 GB. Todo lo que exceda este volumen deberá guardarse en el disco (disco duro viejo y oxidado).
¿Cómo ajustar 100 GB de datos en 4 GB de RAM? Ya sea a) los estados deben exprimirse 1/20 de su tamaño original, ya optimizado, o b) el algoritmo debe ser capaz de guardar estados efectivamente desde y hacia el disco, o c) una combinación de los dos métodos anteriores, o d) necesito comprar más RAM o alquilar una potente máquina virtual durante varios días. No consideré la opción D, porque es demasiado aburrida. Las opciones A y B se excluyeron después de la prueba de concepto utilizando gzip: un fragmento de una descripción de estado de 50 MB se comprimió a solo 35 MB. Esto es aproximadamente 7 bytes por estado, y mi memoria es de aproximadamente 0.4 bytes por estado. Es decir, la opción B permaneció, aunque la búsqueda de amplitud parecía bastante incómoda para el almacenamiento en unidades secundarias.
Contenido
Esta es una publicación bastante larga, así que aquí hay una breve descripción de las siguientes secciones:
- Búsqueda de amplitud primero de amplitud: ¿cuál es la redacción habitual de búsqueda de amplitud primero (BFS) y por qué no es adecuada para almacenar porciones de un estado en el disco?
- BFS con clasificación y fusión : un cambio en el algoritmo para la eliminación por lotes eficiente de datos redundantes.
- Compresión : reduce la cantidad de memoria utilizada cien veces debido a la combinación de compresión estándar y nativa.
- ¡Oh, oh, hice trampa! - en las primeras secciones me quedé callado sobre algo: no es suficiente para nosotros saber dónde está la solución, pero necesitamos entender exactamente cómo lograrla. En esta sección, actualizamos el algoritmo básico para que transfiera suficientes datos para recrear la solución desde el último estado.
- Ordenar + fusionar con múltiples salidas : almacenar más estados niega por completo los beneficios de la compresión. El algoritmo de clasificación + fusión debe cambiarse para que almacene dos conjuntos de datos de salida: uno, bien comprimido, se usa durante la búsqueda, y el otro se usa solo para recrear la solución después de encontrar el primero.
- Swap - Swap en Linux es mucho peor de lo que pensaba.
- Compresión de nuevos estados antes de la fusión : hasta ahora, las optimizaciones de memoria solo funcionaban con muchos estados visitados. Pero resultó que la lista de nuevos estados generados es mucho más grande de lo que piensas. Esta sección muestra un diagrama para una descripción más eficiente de los nuevos estados.
- Ahorro de espacio en estados primarios : explore las compensaciones entre el uso de CPU / memoria para recrear la solución al final.
- Lo que no funcionó o no funcionó : algunas ideas parecían prometedoras, pero como resultado tuvieron que revertirse, mientras que otras, que se suponía que eran investigadores, intuitivamente me parecen inapropiadas en este caso.
Amplia búsqueda "por libro de texto"
¿Cómo se ve la búsqueda de amplitud y por qué no debería usar un disco? Antes de este pequeño proyecto, consideraba solo las opciones de redacción “de los libros de texto”, por ejemplo, como:
def bfs(graph, start, end): visited = {start} todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False
En el proceso de crear nuevos nodos candidatos por el programa, cada nodo se verifica con una tabla hash de nodos ya visitados. Si ya está en la tabla hash, se ignora el nodo. De lo contrario, se agrega a la cola y a la tabla hash. A veces, en implementaciones, la información "visitada" se ingresa en los nodos, y no en una tabla ajena; pero esta es una optimización arriesgada y es completamente imposible si el gráfico se especifica implícitamente.
¿Por qué es problemático usar una tabla hash? Debido a que las tablas hash tienden a crear un patrón de acceso a memoria completamente aleatorio. Si no lo hacen, entonces esta es una mala función hash, y la tabla hash probablemente tendrá un bajo rendimiento debido a colisiones. Este patrón de acceso aleatorio puede causar problemas de rendimiento, incluso si los datos se ajustan en la memoria: es probable que el acceso a una gran tabla hash cause errores de caché y búferes de traducción asociativa (TLB). Pero, ¿qué sucede si una porción significativa de los datos está en el disco y no en la memoria? Las consecuencias serán catastróficas: algo del orden de 10 ms por operación de búsqueda.
Con 10 mil millones de estados únicos, solo acceder a la tabla hash nos llevará unos cuatro meses esperar la E / S del disco. Esto no nos conviene; la tarea definitivamente debe convertirse para que el programa pueda procesar grandes paquetes de datos en una sola pasada.
BFS con clasificación y fusión
Si quisiéramos integrar las operaciones de acceso a datos en los paquetes tanto como sea posible, ¿cuál sería la aproximación máxima alcanzable? Dado que el programa no sabe qué nodos procesar en una capa de profundidad N + 1 hasta que la capa N se procese por completo, parece obvio que es necesario deduplicar estados al menos una vez por profundidad.
Si estamos trabajando con una capa completa al mismo tiempo, podemos abandonar las tablas hash y describir el conjunto de estados visitados y nuevos como algunas secuencias ordenadas (por ejemplo, como secuencias de archivos, matrices, listas). Podemos encontrar trivialmente el nuevo conjunto visitado combinando los conjuntos de flujos y es igualmente trivial encontrar el conjunto todo utilizando la diferencia de conjuntos.
Se pueden combinar dos operaciones con conjuntos para que funcionen en una sola pasada con ambos hilos. De hecho, observamos ambas corrientes, procesamos el elemento más pequeño y luego avanzamos a lo largo de la corriente de la que se tomó el elemento (o a lo largo de ambos flujos si los elementos al principio son los mismos). En ambos casos, agregamos el elemento al nuevo conjunto visitado. Luego avanzamos a lo largo de la secuencia de nuevos estados, y también agregamos un elemento al nuevo conjunto de tareas:
def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False
El patrón de acceso a datos ahora es completamente lineal y predecible; no hay accesos arbitrarios en toda la fusión. Por lo tanto, la demora en las operaciones de disco no es importante para nosotros, y lo único que sigue siendo importante es el ancho de banda.
¿Cómo será el rendimiento teórico con una distribución simplificada de datos en más de 100 niveles de profundidad, cada uno de los cuales tiene 100 millones de estados? El estado promedio será leído y escrito 50 veces. Esto da 10 bytes / estado * 5 mil millones de estados * 50 = 2.5 TB. Mi disco duro supuestamente puede leer y escribir a una velocidad promedio de 100 MB / s, es decir, en promedio, la E / S tomará (2 * 2.5 TB) / (100 MB / s) = ~ 50k / s = ~ 13 horas . ¡Esto es un par de pedidos menos que el resultado anterior (cuatro meses)!
También vale la pena señalar que este modelo simplificado no tiene en cuenta el tamaño de los nuevos estados generados. Antes del paso de fusión, deben almacenarse en la memoria para la clasificación + deduplicación. Cubriremos esto en las secciones a continuación.
Compresión
En la introducción, dije que en los experimentos iniciales, la compresión de estado no parecía prometedora, y la relación de compresión era solo del 30%. Pero después de realizar cambios en el algoritmo, los estados se racionalizaron. Deberían ser mucho más fáciles de comprimir.
Para probar esta teoría, utilicé zstd con un rompecabezas de 14,6 millones de estados, cada uno de los cuales tenía un tamaño de 8 bytes. Después de ordenar, se comprimieron en promedio a 1,4 bytes por estado. Parece un serio paso adelante. No es suficiente ejecutar todo el programa en la memoria, pero puede reducir el tiempo de E / S del disco a solo un par de horas.
¿Es posible mejorar de alguna manera el resultado del algoritmo moderno de compresión de propósito general si sabemos algo sobre la estructura de datos? Puedes estar casi seguro de ello. Un buen ejemplo de esto es el formato PNG. Teóricamente, la compresión es solo un pase Deflate estándar. Pero en lugar de comprimir datos sin procesar, la imagen se convierte primero con
filtros PNG . El filtro PNG es esencialmente una fórmula para predecir el valor de un byte de datos sin procesar en función del valor del mismo byte en la línea anterior y / o el mismo byte del píxel anterior. Por ejemplo, el filtro "arriba" convierte cada byte restando los valores de la línea anterior al comprimir, y realizando la operación opuesta al desempacar. Dados los tipos de imágenes para las que se usa PNG, el resultado casi siempre consistirá en ceros o números cercanos a cero. Deflate puede comprimir esos datos mucho mejor que los datos sin procesar.
¿Se puede aplicar este principio a los registros de estado BFS? Parece que esto debería ser posible. Al igual que con PNG, tenemos un tamaño de línea constante y podemos esperar que las líneas adyacentes sean muy similares. Las primeras muestras con el filtro de resta / suma, seguido de zstd, condujeron a una mejora en la relación de compresión en otro 40%: 0,87 bytes por estado. Las operaciones de filtrado son triviales, por lo tanto, desde el punto de vista del consumo de CPU, son prácticamente "gratuitas".
No estaba claro para mí si se podían hacer otras mejoras, o si esto era un límite práctico. En los datos de la imagen, puede esperar lógicamente que los bytes adyacentes de la misma línea sean similares. Pero en estos estados no existe tal cosa. Pero en realidad, los filtros ligeramente más sofisticados aún pueden mejorar los resultados. Al final, llegué a este sistema:
Supongamos que tenemos filas adyacentes R1 = [1, 2, 3, 4] y R2 = [1, 2, 6, 4]. Al generar R2, comparamos cada byte con el mismo byte de la línea anterior, y 0 indicará una coincidencia, y 1 indicará una falta de coincidencia: diff = [0, 0, 1, 0]. Luego pasamos este mapa de bits, codificado como VarInt, seguido de solo bytes que no coinciden con la línea anterior. En este ejemplo, obtenemos dos bytes 0b00000100 6. Por sí mismo, este filtro comprime los datos de referencia a 2,2 bytes / estado. Pero al combinar el filtro + zstd, redujimos el tamaño de los datos a 0,42 bytes / estado. O, para decirlo de otra manera, esto equivale a 3.36 bits por estado, que es solo un poco más que nuestros indicadores calculados aproximados necesarios para garantizar que todos los datos encajen en la RAM.
En la práctica, las relaciones de compresión mejoran porque los conjuntos ordenados se vuelven más densos. Cuando la búsqueda llega al punto donde la memoria comienza a causar problemas, las tasas de compresión pueden mejorar mucho. El mayor problema es que al final obtenemos 4.600 millones de estados visitados. Después de la clasificación, estos estados ocupan 405 MB y se comprimen de acuerdo con el esquema presentado anteriormente. Esto nos da
0.7 bits por estado . Al final, la compresión y la descompresión ocupan aproximadamente el 25% del tiempo de CPU del programa, pero este es un excelente compromiso para reducir el consumo de memoria en cien veces.
El filtro anterior parece un poco costoso debido al encabezado VarInt en cada línea. Parece que es fácil de actualizar a costa de bajos costos de CPU o un ligero aumento en la complejidad. Probé varias opciones diferentes, transponiendo datos en orden por columnas, o escribiendo máscaras de bits en bloques más grandes, etc. Estas opciones solo produjeron relaciones de compresión mucho más altas, pero no funcionaron tan bien cuando la salida del filtro fue comprimida por zstd. Y no fue algún tipo de error zstd, los resultados con gzip y bzip2 resultaron ser similares. No tengo ninguna teoría particularmente ingeniosa sobre por qué este tipo particular de codificación resultó ser mucho mejor en compresión que otras opciones.
Otro misterio: la tasa de compresión resultó ser mucho mejor cuando los datos se ordenan por little-endian, en lugar de big-endian. Inicialmente, pensé que sucedió porque en la clasificación little-endian hay más ceros a la izquierda con la máscara de bits codificada por VarInt. Pero esta diferencia persiste incluso con filtros que no tienen tales dependencias.
(Hay mucha investigación sobre la compresión de conjuntos de enteros ordenados, porque son los componentes básicos de los motores de búsqueda. Sin embargo, no encontré mucha información sobre la compresión de registros ordenados de longitud constante, y no quería adivinar, presentando los datos como valores enteros con precisión arbitraria).
¡Oh, oh, hice trampa!
Es posible que haya notado que las implementaciones BFS anteriores en pseudocódigo devuelven solo valores booleanos: la solución se encuentra / no se encuentra. Esto no es particularmente útil. En la mayoría de los casos, necesitaremos crear una lista de los pasos exactos de la solución, y no solo informar la disponibilidad de la solución.
Al principio parece que este problema es fácil de resolver. En lugar de recopilar conjuntos de estados, debe recopilar las relaciones de estado con los estados primarios. Luego, después de encontrar una solución, simplemente puede volver de la lista de soluciones parentales de principio a fin. Para una solución basada en tablas hash, esto se vería así:
def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state]
Desafortunadamente, esto destruirá todos los beneficios de compresión obtenidos en la sección anterior; se basan en el supuesto de que las líneas adyacentes son muy similares. Cuando solo miramos los estados mismos, esto es cierto. Pero no hay razón para creer que esto sea cierto para los estados parentales; de hecho, son datos aleatorios. En segundo lugar, una solución sort + merge debería leer y escribir todos los estados vistos en cada iteración. Para guardar la vinculación del estado / estado primario, tenemos que leer y escribir en el disco en cada iteración todos estos datos mal comprimidos.
Ordenar + fusionar con salida múltiple
Al final, cuando regrese a la solución, el programa solo necesitará paquetes de estados / estados primarios, por lo tanto, podemos almacenar dos estructuras de datos en paralelo. Visitado continuará siendo el conjunto de estados visitados, como se recalculó previamente durante la fusión. Los padres son al menos una lista ordenada de pares de estado / estado primario que no se sobrescriben. Después de cada operación de fusión, el par "estado + estado padre" se agrega a los padres.
def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None
Esto nos permite aprovechar ambos enfoques en términos de tiempo de ejecución y conjuntos de trabajo, pero requiere más espacio de almacenamiento secundario. Además, resulta que en el futuro, por otras razones, será útil una copia separada de los estados visitados, agrupados por profundidad.
Intercambiar
Otro detalle se ignora en el pseudocódigo: no existe un código explícito para la E / S del disco, sino solo la interfaz Stream abstracta. La secuencia puede ser una secuencia de archivos o una matriz dentro de la memoria, pero ignoramos este detalle de implementación. En cambio, el pseudocódigo está creando un patrón de acceso a la memoria que permite un uso óptimo del disco. En un mundo ideal, esto sería suficiente, y el resto podría ser ocupado por el subsistema de memoria virtual del sistema operativo.
Pero esto no sucede, al menos en Linux. En algún momento (antes de que el conjunto de datos de trabajo pudiera comprimirse a tamaños de memoria), pude ejecutar el programa en aproximadamente 11 horas, y los datos se guardaron principalmente en el disco. Luego hice que el programa usara páginas anónimas en lugar de almacenarlas en archivos, y seleccioné un archivo de intercambio de tamaño suficiente en la misma unidad. Sin embargo, tres días después, el programa fue solo una cuarta parte y, con el tiempo, se hizo más lento. Según mis estimaciones optimistas, se suponía que ella terminaría el trabajo en 20 días.
Lo aclararé: era el mismo código y
exactamente el mismo patrón de acceso . Lo único que ha cambiado es que la memoria se guardó no como un archivo de disco explícito, sino como un intercambio. Casi no se necesita evidencia de que el intercambio destruya completamente el rendimiento de Linux, mientras que las E / S de archivos normales no. Siempre supuse que esto se debe al hecho de que los programas tienden a considerar la RAM como memoria de acceso aleatorio. Pero este no es el caso.
Resulta que las páginas para guardar archivos y las páginas anónimas son manejadas de manera diferente por el subsistema de máquina virtual. Se almacenan en cachés LRU separadas con diferentes políticas de vencimiento; Además, parece que tienen diferentes propiedades de lectura / carga de lectura anticipada.
Ahora lo sé: el intercambio en Linux probablemente no funcionará bien incluso en condiciones óptimas. Si es probable que partes del espacio de direcciones se descarguen durante un tiempo en el disco, es mejor guardarlas manualmente en archivos que confiar en el intercambio. Lo logré implementando mi propia clase de vectores, que inicialmente solo funciona en la memoria, y después de exceder un cierto umbral de tamaño, cambia a mmap en un archivo temporal separado.
Compresión de nuevos estados antes de fusionarse
En un modelo de rendimiento simplificado, asumimos que ocurrirían 100 millones de nuevas condiciones en cada profundidad. Resultó que esto no está muy lejos de la realidad (en el rompecabezas más complejo, un máximo de más de 150 millones de nuevos estados únicos en una capa de profundidad). Pero esto no se puede medir; el conjunto de trabajo antes de la fusión está asociado no solo con estados únicos, sino también con todos los estados deducidos para esta iteración. Esta cifra alcanza los 880 millones de estados de salida por capa de profundidad. Estos 880 millones de estados a) necesitan ser procesados con un patrón de acceso aleatorio para la clasificación, b) no pueden comprimirse efectivamente debido a la falta de clasificación, c) deben almacenarse junto con el estado padre. Este conjunto de trabajo es de aproximadamente 16 GB.
La solución obvia: usar algún tipo de clasificación externa. Simplemente escriba todos los estados en el disco, realice una clasificación externa, deduplica y luego combine como de costumbre. Al principio usé esta solución, y aunque en la mayoría de los casos eliminó el problema A, no pude hacer frente a B y C.
Al final, tomé un enfoque alternativo: reuní los estados en una matriz en la memoria. Si la matriz se vuelve demasiado grande (por ejemplo, más de 100 millones de elementos), entonces se ordena, deduplica y comprime. Esto nos da un paquete de ejecuciones de estado ordenadas, y no hay duplicados dentro de cada ejecución, pero son posibles entre ejecuciones. Básicamente, el código para fusionar estados nuevos y visitados sigue siendo el mismo; todavía se basa en un paso gradual a través de las corrientes. La única diferencia es que, en lugar de simplemente pasar por dos flujos, hay un flujo separado para cada una de las ejecuciones ordenadas de nuevos estados.
Por supuesto, las tasas de compresión de estas ejecuciones de 100 millones de estados no son tan buenas como la compresión del conjunto de todos los estados visitados. Pero incluso con tales indicadores, reduce significativamente el volumen del conjunto de trabajo y los requisitos de E / S de disco. Necesita un poco más de recursos de CPU para procesar la cola prioritaria de subprocesos, pero sigue siendo un gran compromiso.
Ahorro de espacio en estados primarios
En esta etapa, la gran mayoría del espacio ocupado por el programa se gasta en almacenar los estados primarios, de modo que después de encontrar la solución podamos recrear su proceso. Lo más probable es que apenas puedan exprimirse bien, pero ¿quizás haya algún tipo de compromiso entre la CPU y la memoria?
Necesitamos conectar el estado S 'en la profundidad D + 1 con su estado padre S en la profundidad D. Si podemos iterar sobre todos los estados parentales posibles S', entonces podemos verificar si alguno de ellos aparece en la profundidad D en el conjunto visitado . (Ya hemos creado muchas visitas, agrupadas por profundidad como un subproducto conveniente de la derivación de paquetes de estado / estado parental durante la fusión). Desafortunadamente, este enfoque no funcionará para esta tarea; es simplemente demasiado difícil para nosotros generar todos los estados posibles de S para un S 'dado. Sin embargo, para muchas otras tareas de búsqueda, tal solución podría funcionar.Si solo podemos generar transiciones entre estados hacia adelante, pero no hacia atrás, ¿por qué no hacer esto? Recorramos iterativamente todos los estados en profundidad D y veamos qué tipo de estados de salida obtienen. Si algún estado en la salida da S ', entonces encontramos un S. adecuado. El problema con este plan es que aumenta el consumo total de recursos del procesador por parte del programa en un 50%. (No 100%, porque en promedio encontraremos S al observar la mitad de los estados en profundidad D).Por lo tanto, no me gusta ninguno de los casos limitantes, pero aquí, al menos, es posible un compromiso entre la CPU / memoria. ¿Hay una solución más aceptable en algún punto intermedio? Al final, decidí no almacenar el par (S ', S), sino el par (S', H (S)), donde H es una función hash de 8 bits. Para encontrar S para una S 'dada, nuevamente recorremos iterativamente todos los estados en profundidad D. Pero antes de hacer cualquier otra cosa, calculamos el mismo hash. Si la salida no coincide con H (S), entonces este no es el estado que estamos buscando, y simplemente podemos omitirlo. Esta optimización significa que los costosos recálculos deben realizarse solo para 1/256 estados, lo que representa un ligero aumento en la carga de la CPU, y al mismo tiempo reduce la cantidad de memoria para almacenar estados primarios de 8-10 bytes a 1 byte.Lo que no funcionó o puede no funcionar
En las secciones anteriores, observamos la secuencia de optimizaciones de alto nivel que funcionó. Intenté otras cosas que no funcionaron, o que encontré en la literatura, pero decidí que en este caso particular no funcionarían. Aquí hay una lista parcial.En este punto, no recalculo todo el conjunto visitado en cada iteración. En cambio, se almacenó como muchas ejecuciones ordenadas, y estas ejecuciones se comprimieron de vez en cuando. La ventaja de este enfoque es que se utilizan menos escrituras en disco y recursos de CPU para la compresión. La desventaja es una mayor complejidad del código y una tasa de compresión reducida. Inicialmente, pensé que tal esquema tiene sentido, porque en mi caso, las operaciones de escritura son más caras que la lectura. Pero al final, la relación de compresión resultó ser el doble. Las ventajas de tal compromiso no son obvias, por lo tanto, como resultado, volví a una forma más simple.Ya se ha realizado poca investigación sobre cómo realizar una búsqueda volumétrica de amplitud para gráficos definidos implícitamente en el almacenamiento secundario, puede comenzar a explorar este temade este artículo de 2008 . Como puede suponer, la idea de hacer deduplicación junto con ordenar + fusionar en el almacenamiento secundario no es nueva. Lo sorprendente de esto es que se abrió solo en 1993. Bastante tarde! Hay sugerencias posteriores para la búsqueda de amplitud en el almacenamiento secundario que no requieren un paso de clasificación.Una de ellas era unir estados a enteros y almacenar en la memoria un mapa de bits de estados visitados. En mi caso, esto es completamente inútil, porque los tamaños del estado codificado son muy diferentes en comparación con los espacios de estado realmente accesibles. Y dudo mucho que haya problemas interesantes en los que tal enfoque funcionaría.Otra alternativa seria se basa en tablas hash temporales. Los estados visitados se almacenan sin ordenar en un archivo. Guardamos el resultado obtenido de la profundidad D en la tabla hash. Luego, recorra iterativamente los estados visitados y búsquelos en la tabla hash. Si el elemento se encuentra en la tabla hash, elimínelo. Después de recorrer iterativamente todo el archivo, solo quedarán elementos no duplicados en él. Luego se agregan al archivo y se utilizan para inicializar la lista de tareas pendientes para la próxima iteración. Si la cantidad de salida es tan grande que la tabla hash no cabe en la memoria, los archivos y las tablas hash se pueden dividir en partes utilizando los mismos criterios (por ejemplo, los bits de estado superiores), y cada parte debe procesarse por separado.Aunque hay puntos de referenciamostrando que el enfoque basado en hash es aproximadamente un 30% más rápido que la clasificación + fusión, pero parece que no tienen en cuenta la compresión. Simplemente no vi cómo el rechazo de los beneficios de la compresión puede justificarse, por lo que ni siquiera experimenté con tales enfoques.Otra área de investigación digna de atención fue la optimización de las consultas de la base de datos. Parece que que la tarea de deduplicación está fuertemente relacionada con la unión a la base de datos, que también tiene exactamente el mismo dilema de clasificación versus hash. Obviamente, algunos de estos estudios se pueden aplicar al problema de búsqueda. La diferencia puede ser que la salida de la base de datos de unión es temporal, mientras que la salida de deduplicación BFS se almacena hasta el final del cálculo. Parece que esto está cambiando el equilibrio de compromisos: ahora se trata no solo del procesamiento más eficiente de una iteración, sino también de la creación del formato de datos de salida más óptimo para la próxima iteración.Conclusión
Esto concluye mi relato de lo que aprendí de un proyecto que generalmente es aplicable a otras tareas de búsqueda por fuerza bruta. La combinación de estos trucos permitió reducir el volumen de soluciones a los acertijos más complejos del juego de 50-100 GB a 500 MB y aumentar sin problemas los costos si la tarea excede la memoria disponible y se escribe en el disco. Además, mi solución es un 50% más rápida que una ingenua deduplicación de estados basada en tablas hash, incluso para acertijos que caben en la memoria.Snakebird se puede comprar en Steam , Google Play y App Store . Se lo recomiendo a cualquiera que esté interesado en acertijos muy complejos pero honestos.