N-queens в Haskell без обхода списка

Ответ 1

В целом вы, вероятно, собираетесь завязать налог на сложность O(log n) для функциональной неразрушающей реализации, иначе вам придется отказаться и использовать (IO|ST|STM)UArray.

Строгие чистые языки, возможно, должны заплатить налог O(log n) за нечистый язык, который может писать ссылки, реализуя ссылки через картографическую структуру; ленивые языки иногда могут уклониться от этого налога, хотя нет никаких доказательств в любом случае, достаточно ли дополнительной силы, предлагаемой лень, чтобы всегда уклоняться от этого налога - даже если его сильно подозревают, что лень недостаточно сильна.

В этом случае трудно увидеть механизм, с помощью которого лень можно было бы использовать, чтобы избежать ссылочного налога. И, в конце концов, именно поэтому у нас есть монада ST.;)

Тем не менее, вы можете исследовать, можно ли использовать какую-либо панель-диагональную молнию для использования локальности обновлений - использование локальности в застежке-молнии является обычным способом, чтобы попытаться сбросить логарифмический термин.

Ответ 2

Вероятно, самым простым способом было бы использовать UArray (Int, Int) Bool для записи безопасных/небезопасных бит. Хотя копирование это O (n ²), при малых значениях N это самый быстрый доступный метод.

При больших значениях N существуют три основных варианта:

• Data.DiffArray удаляет накладные расходы на копирование, если вы никогда не используете старые значения после их изменения. То есть, если вы всегда выбрасываете старое значение массива после его изменения, модификация O (1). Если, однако, вы получаете доступ к старому значению массива позже (даже для чтения), то O (N ²) оплачивается полностью.
• Data.Map и Data.Set разрешить модификации и поиск O (lg n). Это изменяет алгоритмическую сложность, но часто достаточно быстро.
• Data.Array.ST STUArray s (Int, Int) Bool даст вам императивные массивы, позволяющие реализовать алгоритм в классическом (нефункциональный) ) способ.

Ответ 3

Основная потенциальная проблема с этим подходом заключается в том, что массивы для диагоналей необходимо модифицировать каждый раз, когда помещается королева. Небольшое улучшение постоянного времени поиска для диагоналей может не стоить дополнительной работы по постоянному созданию новых модифицированных массивов.

Но лучший способ узнать реальный ответ - попробовать, поэтому я немного поиграл и придумал следующее:

import Data.Array.IArray (array, (//), (!))
import Data.Array.Unboxed (UArray)
import Data.Set (Set, fromList, toList, delete)

-- contains sets of unoccupied columns and lookup arrays for both diagonals
data BoardState = BoardState (Set Int) (UArray Int Bool) (UArray Int Bool)

-- an empty board
board :: Int -> BoardState
board n
   = BoardState (fromList [0..n-1]) (truearr 0 (2*(n-1))) (truearr (1-n) (n-1))
   where truearr a b = array (a,b) [(i,True) | i <- [a..b]]

-- modify board state if queen gets placed
occupy :: BoardState -> (Int, Int) -> BoardState
occupy (BoardState c s d) (a,b)
   = BoardState (delete b c) (tofalse s (a+b)) (tofalse d (a-b))
   where tofalse arr i = arr // [(i, False)]

-- get free fields in a row
freefields :: BoardState -> Int -> [(Int, Int)]
freefields (BoardState c s d) a = filter freediag candidates
   where candidates = [(a,b) | b <- toList c]
         freediag (a,b) = (s ! (a+b)) && (d ! (a-b))

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

-- all possibilities to place n queens on a n*n board
queens :: Int -> [[(Int, Int)]]
queens n = place (board n) n

Это работает и для n = 14 примерно на 25% быстрее, чем упомянутая вами версия. Основное ускорение исходит от использования массивов unboxed, рекомендованных bdonian. С обычным Data.Array он имеет примерно такое же время исполнения, что и версия в вопросе.

Возможно, также стоит попробовать другие типы массивов из стандартной библиотеки, чтобы убедиться, что их использование может повысить производительность.

Ответ 4

Я скептически отношусь к к заявлению, что чистым функционалом обычно является O (log n). См. Также ответ Эдварда Кмета, который делает это утверждение. Хотя это может относиться к случайному доступу к изменяемым массивам в теоретическом смысле, но случайный доступ к изменяемым массивам, вероятно, не соответствует большинству любого алгоритма, когда он правильно изучается для повторяемой структуры, то есть не является случайным. Я думаю, что Эдвард Кметт ссылается на это, когда пишет: "Эксплуатировать локальность обновлений".

Я думаю, что O (1) теоретически возможно в чистой функциональной версии алгоритма n-queens, добавив метод undo для DiffArray, который просит оглянуться назад, чтобы удалить дубликаты и избежать повторного воспроизведения.

Если я правильно понимаю, как работает алгоритм back-слежения n-queens, то замедление, вызванное DiffArray, связано с тем, что ненужные различия сохраняются.

В реферате "DiffArray" (не обязательно Haskell's) имеет (или может иметь) метод набора элементов, который возвращает новую копию массива и сохраняет запись разницы с исходной копией, включая указатель на новую измененная копия. Когда исходная копия должна получить доступ к элементу, этот список различий должен быть воспроизведен в обратном порядке, чтобы отменить изменения на копии текущей копии. Обратите внимание, что есть даже накладные расходы, что этот односвязный список должен быть доведен до конца, прежде чем его можно будет воспроизвести.

Предположим, что они были сохранены как список с двойной связью, и была операция отмены, как показано ниже.

С абстрактного концептуального уровня, что делает алгоритм backtracking n-queens, рекурсивно работает на некоторых массивах логических элементов, перемещая позицию королевы постепенно вперед в этих массивах на каждом рекурсивном уровне. См. эту анимацию.

Работая с этим только в моей голове, я вижу, что причина DiffArray настолько медленная, потому что, когда королева перемещается из одной позиции в другую, тогда логический флаг для исходной позиции возвращается к false, а новый position установлено в true, и эти различия записаны, но они не нужны, потому что, когда они воспроизводятся в обратном порядке, массив заканчивается теми же значениями, которые были у него до начала повтора. Таким образом, вместо того, чтобы использовать операцию set для возврата к false, требуется вызов метода отмены, необязательно с входным параметром, указывающим DiffArray, что "отменять" значение для поиска в вышеупомянутом двойном списке различий. Если это значение "отменить для" найдено в записи различий в двойном списке, нет никаких противоречивых промежуточных изменений в том же элементе массива, который обнаруживается при повторном поиске в списке, а текущее значение равно "отменить", значение в этой разностной записи, тогда запись может быть удалена и эта старая копия может быть указана на следующую запись в двойном списке.

Что это значит - удалить ненужное копирование всего массива при обратном трассировке. Есть еще некоторые дополнительные накладные расходы по сравнению с императивной версией алгоритма, для добавления и отмены добавления разностных записей, но это может быть ближе к постоянному времени, т.е. O (1).

Если я правильно понимаю алгоритм n-queen, обратная связь для операции отмены является только одной, поэтому нет ходьбы. Таким образом, даже при сохранении разности заданного элемента при перемещении позиции королевы даже не нужно сохранять, так как оно будет отменено до того, как будет получен доступ к старой копии. Нам просто нужен способ выразить этот тип безопасно, что достаточно легко сделать, но я оставлю его как упражнение для читателя, поскольку этот пост слишком длинный.

UPDATE: я не написал код для всего алгоритма, но в моей голове n-queens можно реализовать с каждой итерированной строкой, сгибом на следующем массиве диагоналей, где каждый элемент является триплетным кортежем of: (индекс строки занят или 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 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.

UPDATE: Я работаю над Scala реализация, у которой есть улучшенный по сравнению с тем, что я предложил выше. Я также объяснил, как оптимизация для складок приближается к одинаковым постоянным издержкам, как измененный массив.

Ответ 5

У меня есть решение. Тем не менее, константа может быть большой, поэтому я действительно не надеюсь на что-то избивать.

Вот моя структура данных:

-- | Zipper over a list of integers
type Zipper = (Bool,  -- does the zipper point to an item?
               [Int], -- previous items
                      -- (positive numbers representing
                      --   negative offsets relative to the previous list item)
               [Int]  -- next items (positive relative offsets)
               )

type State =
  (Zipper, -- Free columns zipper
   Zipper, -- Free diagonal1 zipper
   Zipper  -- Free diagonal2 zipper
   )

Позволяет выполнять все необходимые операции в O (1).

Код можно найти здесь: http://hpaste.org/50707

Скорость плохая - она ​​медленнее, чем исходное решение, размещенное в вопросе на большинстве входов. Я сравнивал их друг с другом на входах [1,3 .. 15] и получил следующие временные отношения ((время решения решения/время решения) в%):

[24,66%, 19,89%, 23,74%, 41,22%, 42,54%, 66,19%, 84,13%, 106,30%]

Обратите внимание, почти линейное замедление эталонного раствора по отношению к шахте, показывая разницу в асимптотической сложности.

Мое решение, вероятно, ужасно с точки зрения строгости и подобных вещей и должно быть подано в очень хороший оптимизирующий компилятор (например, Дон Стюарт, например), чтобы получить лучшие результаты.

Во всяком случае, я думаю, что в этой задаче O (1) и O (log (n)) в любом случае неразличимы, поскольку log (8) составляет всего 3, а константы, подобные этому, являются объектом микрооптимизации, а не алгоритма.