私は、純粋汎関数が一般に O(log n) であるという主張に懐疑的になりつつあります。その主張をするEdward Kmettの回答も参照してください。それは理論的な意味でのランダムな可変配列アクセスに当てはまるかもしれませんが、反復可能な構造、つまりランダムではない構造について適切に研究されている場合、ランダムな可変配列アクセスはおそらくほとんどのアルゴリズムが必要とするものではありません。Edward Kmett は、「更新の局所性を悪用する」と書いているときにこれに言及していると思います。
O(1) は、n-queens アルゴリズムの純粋な関数型バージョンで理論的に可能であると考えています。DiffArray に元に戻すメソッドを追加することで、重複を削除し、それらの再生を回避するために差分を振り返ることを要求します。
バックトラッキング n-queens アルゴリズムの動作に関する私の理解が正しければ、DiffArray によって引き起こされる速度低下は、不要な差異が保持されているためです。
要約すると、「DiffArray」(必ずしも Haskell のものである必要はありません) には、配列の新しいコピーを返し、新しい変更されたコピーへのポインターを含む、元のコピーとの差分レコードを格納する set 要素メソッドがあります (または持つことができます)。元のコピーが要素にアクセスする必要がある場合、現在のコピーのコピーの変更を元に戻すために、この相違点のリストを逆に再生する必要があります。この単一リンクのリストは、再生する前に最後までたどらなければならないというオーバーヘッドさえあることに注意してください。
代わりに、これらが二重リンクされたリストとして保存され、次のように元に戻す操作があったと想像してください。
抽象的な概念レベルから、バックトラッキング n-queens アルゴリズムが行うことは、ブーリアンのいくつかの配列を再帰的に操作し、再帰レベルごとにそれらの配列内でクイーンの位置を段階的に前方に移動することです。このアニメーションを参照してください。
これを頭の中で考えてみると、DiffArray が非常に遅い理由は、クイーンがある位置から別の位置に移動すると、元の位置のブール値フラグが false に戻され、新しい位置が設定されるためだと思います。これらの違いは記録されますが、逆に再生すると、配列は再生開始前と同じ値になるため不要です。したがって、set 操作を使用して false に戻す代わりに、undo メソッドの呼び出しが必要です。必要に応じて、前述の二重リンクされた差分リストで検索する「元に戻す」値を DiffArray に指示する入力パラメーターを使用します。その「元に戻す」値が二重リンク リストの差分レコードにある場合、
これにより、バックトラッキングで配列全体の不要なコピーが削除されます。アルゴリズムの命令型バージョンと比較して、差分レコードの追加と追加の取り消しのためにまだ余分なオーバーヘッドがありますが、これは定数時間、つまり O(1) に近くなる可能性があります。
n-queen アルゴリズムを正しく理解していれば、元に戻す操作のルックバックは 1 つだけなので、ウォークはありません。したがって、古いコピーがアクセスされる前に元に戻されるため、クイーンの位置を移動するときにセット要素の違いを保存する必要さえありません。このタイプを安全に表現する方法が必要なだけで、これは簡単に実行できますが、この記事はすでに長すぎるため、読者の演習として残しておきます。
更新: アルゴリズム全体のコードを書いたわけではありませんが、頭の中で n-queens は、反復される各行で、次の対角線の配列の折り畳みで実装できます。ここで、各要素はのトリプレットタプルです: (占有されている行のインデックスまたは None、左右の対角線と交差する行インデックスの配列、左右の対角線と交差する行インデックスの配列)。行は、再帰または行インデックスの配列の折り畳みで反復できます (折り畳みは再帰を行います)。
以下は、私が思い描くデータ構造のインターフェースです。以下の構文は Copute ですが、Scala に十分近いので、意図が理解できると思います。
マルチスレッド化されている場合、DiffArray の実装は不当に遅くなることに注意してください。ただし、n-queens バックトラッキング アルゴリズムでは、DiffArray をマルチスレッド化する必要はありません。この回答のコメントで指摘してくれた Edward Kmett に感謝します。
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 の実装に取り組んでいます。これは、上記で提案したものと比較してインターフェイスが改善されています。また、折り畳みの最適化が可変配列と同じ一定のオーバーヘッドにどのように近づくかについても説明しました。