Я скептически отношусь к утверждению , что чистый функционал - это, как правило, O (log n). См. Также ответ Эдварда Кметта, который делает это утверждение. Хотя это может применяться к случайному доступу к изменяемым массивам в теоретическом смысле, но доступ к случайным изменяемым массивам, вероятно, не тот, который требуется большинству любого алгоритма, когда он должным образом изучен для повторяемой структуры, то есть не является случайным. Я думаю, что Эдвард Кметт ссылается на это, когда пишет «эксплуатировать локальность обновлений».
Я думаю, что O (1) теоретически возможно в чисто функциональной версии алгоритма n-queens, добавив метод отмены для DiffArray, который запрашивает просмотр различий, чтобы удалить дубликаты и избежать их воспроизведения.
Если я правильно понимаю, как работает алгоритм возврата n-ферзей, то замедление, вызванное DiffArray, связано с сохранением ненужных различий.
В реферате «DiffArray» (не обязательно Haskell) имеет (или может иметь) метод элемента set, который возвращает новую копию массива и сохраняет разностную запись с оригинальной копией, включая указатель на новую измененная копия. Когда исходная копия должна получить доступ к элементу, этот список различий необходимо воспроизвести в обратном порядке, чтобы отменить изменения в копии текущей копии. Обратите внимание, что есть даже издержки, что этот односвязный список нужно пройти до конца, прежде чем его можно будет воспроизвести.
Представьте, что вместо этого они были сохранены в виде двойного списка, и была выполнена операция отмены следующим образом.
На абстрактном концептуальном уровне алгоритм обратного отслеживания n-ферзей рекурсивно работает с некоторыми массивами логических значений, постепенно перемещая положение ферзя вперед в этих массивах на каждом рекурсивном уровне. Смотрите эту анимацию .
Работая с этим только в моей голове, я представляю, что причина, по которой DiffArray такой медленный, заключается в том, что когда ферзь перемещается из одной позиции в другую, тогда логический флаг для исходной позиции устанавливается обратно в ложь, а новый position устанавливается в true, и эти различия записываются, но они не нужны, потому что при обратном воспроизведении массив заканчивается теми же значениями, которые он имел до начала воспроизведения. Таким образом, вместо использования операции set для возврата к значению false, необходим вызов метода отмены, необязательно с входным параметром, сообщающим DiffArray, какое значение «отменять до» следует искать в вышеупомянутом двусвязном списке различий. Если это значение «отменить к» найдено в записи различий в двойном списке, нет конфликтующих промежуточных изменений в том же элементе массива, найденном при переходе назад в поиске по списку, и текущее значение равно «отменить из» значение в этой записи разницы, то запись может быть удалена, и эта старая копия может быть перенаправлена на следующую запись в двойном списке.
Для этого необходимо удалить ненужное копирование всего массива при возврате. По сравнению с императивной версией алгоритма все еще есть некоторые дополнительные издержки для добавления и отмены добавления записей различий, но это может быть ближе к постоянному времени, то есть O (1).
Если я правильно понимаю алгоритм n-queen, просмотр операции отмены только один, поэтому обхода нет. Таким образом, даже не нужно сохранять различие элемента set при перемещении положения ферзя, поскольку оно будет отменено до обращения к старой копии. Нам просто нужен способ безопасного выражения этого типа, что достаточно легко сделать, но я оставлю это как упражнение для читателя, так как этот пост уже слишком длинный.
ОБНОВЛЕНИЕ: я не написал код для всего алгоритма, но в моей голове n-королевы могут быть реализованы с каждой повторяющейся строкой, сгиб на следующем массиве диагоналей, где каждый элемент - триплетный кортеж из: (индекс строки занят или None, массив индексов строк, пересекающих диагональ влево-вправо, массив индексов строк, пересекающих диагональ вправо-влево). Строки можно повторять с помощью рекурсии или сгиба массива индексов строк (сгиб выполняет рекурсию).
Здесь приведены интерфейсы для структуры данных, которую я представляю. Синтаксис ниже - Copute, но я думаю, что он достаточно близок к Scala, чтобы вы могли понять, для чего он предназначен.
Обратите внимание, что любая реализация DiffArray будет неоправданно медленной, если она многопоточная, но алгоритм возврата n-queens не требует, чтобы DiffArray был многопоточным. Спасибо Эдварду Кметту за то, что он указал на это в комментариях к этому ответу.
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:
// /1329309/n-korolev-v-haskele-bez-obhoda-spiska
// 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.
ОБНОВЛЕНИЕ: я работаю над реализацией Scala , которая имеет улучшенный интерфейс по сравнению с тем, что я предлагал выше. Я также объяснил, как оптимизация для складок приближается к тем же постоянным издержкам, что и изменяемый массив.