Me estoy volviendo escéptico sobre the claim que el funcional puro es generalmente O (log n). Ver también la respuesta de Edward Kmett que hace esa afirmación.Aunque eso puede aplicarse al acceso de matriz mutable aleatoria en el sentido teórico, pero el acceso de matriz mutable aleatoria probablemente no es lo que la mayoría de los algoritmos requieren, cuando se estudia adecuadamente para una estructura repetible, es decir, no aleatoria. Creo que Edward Kmett se refiere a esto cuando escribe, "explota la localidad de las actualizaciones".
Estoy pensando que O (1) es teóricamente posible en una versión funcional pura del algoritmo n-queens, agregando un método de deshacer para DiffArray, que solicita una revisión de las diferencias para eliminar duplicados y evitar reproducirlos.
Si tengo razón en mi comprensión de la forma en que funciona el algoritmo n-queens de retroceso, entonces la desaceleración causada por DiffArray se debe a que se conservan las diferencias innecesarias.
En resumen, un "DiffArray" (no necesariamente Haskell's) tiene (o podría tener) un método de elemento conjunto que devuelve una nueva copia de la matriz y almacena un registro de diferencia con la copia original, incluyendo un puntero al nueva copia modificada. Cuando la copia original necesita acceder a un elemento, esta lista de diferencias debe reproducirse a la inversa para deshacer los cambios en una copia de la copia actual. Tenga en cuenta que incluso existe la sobrecarga de que esta lista de un solo enlace debe irse hasta el final, antes de poder volver a reproducirse.
Imagine en su lugar que se almacenaron como una lista de doble enlace, y hubo una operación de deshacer de la siguiente manera.
Desde un nivel conceptual abstracto, lo que hace el algoritmo n-queens de retroceso es operar recursivamente en algunas matrices de booleanos, moviendo la posición de la reina progresivamente hacia adelante en esas matrices en cada nivel recursivo. Ver this animation.
Al resolver esto solo en mi cabeza, visualizo que el motivo por el que DiffArray es tan lento es porque cuando la reina se mueve de una posición a otra, entonces la bandera booleana para la posición original vuelve a falsa y el la nueva posición se establece en verdadero, y estas diferencias se registran, sin embargo, son innecesarias porque cuando se reproducen al revés, la matriz termina con los mismos valores que tenía antes de que comenzara la reproducción. Por lo tanto, en lugar de utilizar una operación set para volver a false, lo que se necesita es una llamada al método deshacer, opcionalmente con un parámetro de entrada que indique a DiffArray qué valor "deshacer para" buscar en la lista de diferencias de enlaces dobles antes mencionada. Si ese valor de "deshacer a" se encuentra en un registro de diferencia en la lista de doble enlace, no hay cambios intermedios conflictivos en ese mismo elemento de matriz encontrado al retroceder en la búsqueda de lista, y el valor actual es igual a "deshacer desde" valor en ese registro de diferencia, luego se puede eliminar el registro y esa vieja copia se puede volver a apuntar al siguiente registro en la lista de doble enlace.
Lo que esto logra es eliminar la copia innecesaria de toda la matriz en el retroceso. Todavía hay una sobrecarga adicional en comparación con la versión imperativa del algoritmo, para agregar y deshacer los registros de adición de diferencia, pero esto puede estar más cerca del tiempo constante, es decir, O (1).
Si entiendo correctamente el algoritmo de n-queen, el retroceso de la operación de deshacer es solo uno, por lo que no hay andar. Por lo tanto, ni siquiera es necesario almacenar la diferencia del elemento establecido al mover la posición reina, ya que se deshará antes de acceder a la copia anterior. Solo necesitamos una forma de expresar este tipo de manera segura, lo cual es bastante fácil de hacer, pero lo dejaré como un ejercicio para el lector, ya que esta publicación ya es demasiado extensa.
UPDATE: no he escrito el código para todo el algoritmo, pero en mi cabeza las n-reinas puede ser implementado con en cada fila iterado, un pliegue en la siguiente matriz de diagonales, donde cada elemento es la tupla de triplete de: (el índice de la fila está ocupado o Ninguno, la matriz de índices de filas se cruzan con la diagonal izquierda-derecha, la matriz de índices de filas se cruzan con la diagonal derecha-izquierda).Las filas se pueden iterar con recursión o un pliegue de una matriz de índices de filas (el doblez realiza la recursión).
Aquí se muestran las interfaces para la estructura de datos que imagino. La siguiente sintaxis es Copute, pero creo que está lo suficientemente cerca de Scala, que puedes entender lo que se pretende.
Tenga en cuenta que cualquier implementación de DiffArray será irrazonablemente lenta si es multiproceso, pero el algoritmo de retroceso de n-queens no requiere que DiffArray sea multiproceso. Gracias a Edward Kmett por señalar eso en los comentarios para esta respuesta.
interface Array[T]
{
setElement : Int -> T -> Array[T] // Return copy with changed element.
setElement : Int -> Maybe[T] -> Array[T]
array :() -> Maybe[DiffArray[T]]// Return copy with the DiffArray interface, or None if first called setElement() before array().
}
// An immutable array, typically constructed with Array().
//
// If first called setElement() before array(), setElement doesn't store differences,
// array will return None, and thus setElement is as fast as a mutable imperative array.
//
// Else setElement stores differences, thus setElement is O(1) but with a constant extra overhead.
// And if setElement has been called, getElement incurs an up to O(n) sequential time complexity,
// because a copy must be made and the differences must be applied to the copy.
// The algorithm is described here:
// http://stackoverflow.com/questions/1255018/n-queens-in-haskell-without-list-traversal/7194832#7194832
// Similar to Haskell's implementation:
// http://www.haskell.org/haskellwiki/Arrays#DiffArray_.28module_Data.Array.Diff.29
// http://www.haskell.org/pipermail/glasgow-haskell-users/2003-November/005939.html
//
// If a multithreaded implementation is used, it can be extremely slow,
// because there is a race condition on every method, which requires internal critical sections.
interface DiffArray[T] inherits Array[T]
{
unset :() -> Array[T] // Return copy with the previous setElement() undone, and its difference removed.
getElement : Int -> Maybe[T] // Return the the element, or None if element is not set.
}
// An immutable array, typically constructed with Array(...) or Array().array.
ACTUALIZACIÓN: Estoy trabajando en la Scala implementation, que tiene una mejorada interface en comparación con lo que había sugerido anteriormente. También he explicado cómo una optimización para pliegues se acerca a la misma sobrecarga constante que una matriz mutable.
¿Se han implementado matrices de remolques en alguna parte para Haskell? – is7s