Я скептически отношусь к утверждению о том, что чистый функционал обычно является O (log n) . См. Также ответ Эдварда Кметта, в котором говорится об этом. Хотя это может относиться к случайному доступу к изменяемому массиву в теоретическом смысле, но случайный доступ к изменяемому массиву, вероятно, не то, что требуется большинству любого алгоритма, когда он должным образом изучен для повторяющейся структуры, то есть не случайный. Я думаю, что Эдвард Кметт ссылается на это, когда пишет: «использовать локальность обновлений».
Я думаю, что O (1) теоретически возможен в чисто функциональной версии алгоритма n-queens, путем добавления метода отмены для DiffArray, который запрашивает обратный взгляд на различия, чтобы удалить дубликаты и избежать их повторного воспроизведения.
Если я правильно понимаю, как работает алгоритм обратного отслеживания n-ферзей, то замедление, вызванное DiffArray, вызвано сохранением ненужных различий.
Говоря абстрактно, «DiffArray» (не обязательно Haskell) имеет (или мог бы иметь) метод набора элементов, который возвращает новую копию массива и сохраняет запись разницы с исходной копией, включая указатель на новую измененную копию. Когда исходной копии требуется доступ к элементу, этот список различий необходимо воспроизвести в обратном порядке, чтобы отменить изменения в копии текущей копии. Обратите внимание, что есть даже накладные расходы, связанные с тем, что этот односвязный список нужно пройти до конца, прежде чем его можно будет воспроизвести.
Представьте, что вместо этого они были сохранены как список с двойной связью, и выполнялась следующая операция отмены.
С абстрактного концептуального уровня алгоритм обратного отслеживания n-ферзей рекурсивно работает с некоторыми массивами логических значений, постепенно перемещая положение ферзя вперед в этих массивах на каждом рекурсивном уровне. См. эту анимацию.
Обдумывая это только в голове, я представляю, что причина того, что DiffArray такой медленный, заключается в том, что когда ферзь перемещается из одной позиции в другую, тогда логический флаг для исходной позиции устанавливается обратно в false и устанавливается новая позиция. значение true, и эти различия записываются, но в них нет необходимости, потому что при обратном воспроизведении массив имеет те же значения, что и до начала воспроизведения. Таким образом, вместо использования операции set для возврата к false необходим вызов метода отмены, необязательно с входным параметром, сообщающим DiffArray, какое значение «отменить» нужно искать в вышеупомянутом двойном списке различий. Если это значение «отменить до» обнаружено в разностной записи в двусвязном списке, то при возвращении в поиск по списку не обнаружено конфликтующих промежуточных изменений в том же самом элементе массива, а текущее значение равно «отменить от» значение в этой разностной записи, то запись может быть удалена, а старая копия может быть перенаправлена на следующую запись в двусвязном списке.
Это позволяет удалить ненужное копирование всего массива при возврате. По сравнению с императивной версией алгоритма по-прежнему существуют дополнительные накладные расходы на добавление и отмену добавления разностных записей, но это может быть ближе к постоянному времени, то есть O (1).
Если я правильно понимаю алгоритм n-queen, ретроспективный анализ для операции отмены только один, поэтому обхода нет. Таким образом, нет необходимости даже сохранять разницу заданного элемента при перемещении позиции ферзя, так как она будет отменена до того, как будет доступна старая копия. Нам просто нужен способ безопасно выразить этот тип, что довольно легко сделать, но я оставлю это в качестве упражнения для читателя, поскольку этот пост уже слишком длинный.
ОБНОВЛЕНИЕ: я не написал код для всего алгоритма, но в моей голове 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:
// 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.
ОБНОВЛЕНИЕ. Я работаю над реализацией Scala, которая имеет улучшенный интерфейс по сравнению с тем, что я предложил выше. Я также объяснил, как оптимизация складок приближается к тем же постоянным накладным расходам, что и изменяемый массив.
person
Shelby Moore III
schedule
25.08.2011
