2番目の記事の終わりに、馬のコースに関連する別の問題を解決し、長方形mxn内の閉じたルートの数をカウントしようとしましたが、6x6の正方形を超えて移動しませんでした。 一連の最適化の後、計算を6桁加速しました。 約100万回、8x8の正方形に近づき、7x8の長方形のサイクル数を計算します。
8x8の正方形はいまだにブルートフォースにアクセスできないように見えますが、このような加速は、言語とタスク全体の両方の良い可能性を物語っています。 そして実際、これらの可能性を発見した経験を読者と共有したいと思います。
そこでは、前回の記事の最後で、2つのアイデアに言及しました。 最初の、そしておそらく、主なものは、行き止まりのブランチがないかどうかのチェックです。 各構築ステップで、残りのグラフには、孤立した中間の垂れ下がった頂点がありません。 言い換えれば、現在のセルと最終セルを除くすべての空きセルには、（騎士の動きの観点から）少なくとも2つの空きセルが必要です。
このチェックだけでも、計算を2桁以上減らすことができます。 これは、リストバージョンでは非常に洗練されており、接続テストのように2次の複雑さを持っているという事実にもかかわらずです。 そして、この複雑さは、各セルについて、ほぼ同時に同じ近隣リストを検索するという事実によるものです。
2番目のアイデア-すべてのセルについて、接続リストを一度事前に計算し、必要に応じて変更するだけです。 同じリストであっても、 キーと値のペアをさまざまな方法で保存できますが、リストを使用すると、検索と削除の操作はO（n）複雑になります。 バランスの取れたバイナリツリーなど、より最適なデータ構造があり、Haskellでは、そのような構造がData.Mapモジュールに長い間実装されてきました。 この構造を持つすべての基本的な操作はO（log n）以下の複雑さであり、最も重要なことは、分離された頂点と垂れ下がった頂点の検索機能がエレガントに見えることです。
deadlocks = keys . filter ((<2).length)
そして、その複雑さはO（n）に改善されます。
準備アクションの量のために、インターフェイス関数は非常に強く変換されます
kNCircles mn = kNFromTo [(2,3)] (3,2) $ prepare $ tail [(x,y) | x <- [1..m], y <- [1..n]] where prepare xs = M.fromList [(x, filter (near x) xs) | x <- xs] near (x1,y1) (x2,y2) = abs ((x2-x1)*(y2-y1)) == 2
主な再帰に関しては、ルート自体は今では面白くないので、それらの数だけに興味があり、チェーンを構築してから、成功の数の単純な計算に進むことができます。 新しいデータ構造を考慮して、関数は次の形式を取ります
kNFromTo ks s xs | size xs == 1 = 1 | otherwise = sum [kNFromTo (xs ! k) s (kDel k xs) | k <- filter (/= s) ks, null $ deadlocks xs \\ [k,s]]
入り口には、可能な動きのリスト、最終的なセル、未使用の頂点のグラフがあります。
さて、グラフから頂点を削除するとき、隣接リストからその言及を削除する必要もあるため、削除関数は個別に説明する必要があります。
kDel x xs = delete x $ foldr (adjust (delete x)) xs (xs ! x)
それはだまされているように見えますが、十分に大きな係数ではありますが、全体の複雑さはO（log n）のままです
ところで、前回の記事で使用した接続性テストが不要になったと言うのを忘れていました。 現在の頂点と最終頂点を除く、他の垂れ下がった頂点が存在しないことが必要な場合、アルゴリズムは他のセルで計算を終了できません。 はい、これは、パスに沿ってすぐに除去されない孤立したサイクルの発生を除外しません。 この場合の接続性テストは有用かもしれませんが、実際にはこのような状況はまれであり、今回は追加の利点によって追加の複雑さが中断されることはありません。
さらに、垂れ下がった頂点の出現のプロセスを分析すると、グラフ内の頂点の次数が減少するのは、隣の頂点が削除されたときだけであることがわかります。 したがって、次数フィルタリングは、グラフ全体ではなく、隣接する頂点のリストに従ってのみ実行できます。
deadlocks xs = filter ((<2).length.(xs !))
そして、それによりO（log n）へのチェックの複雑さを改善します 。
すべて、弱点はありません。わずかにねじれているだけです。 より正確には、理論的には、アレイに移動して、さらに数回加速することができます。 長方形自体の配列は、一般的に最も明白なデータ構造です。 また、要素の検索にはO（1）時間かかり、これが最も要求される操作です。 しかし、Haskellでは、要素を変更するときに純度を保持するために、配列の新しいコピーが作成されます。これはO（n）です。 その結果、加速の代わりに1.5倍遅くなります。
しかし！ これまで、私たちは問題を深く掘り下げてきました。そして、いわば「幅広さ」に行くことができます。 Haskell言語のすべての計算は、デフォルトで1つのコアでシングルスレッドで実行されます。 また、いくつかのコアがありますが、仮想のものもあります。 そして、生産のための闘争が始まったので、それらすべてをダウンロードしたいと思います。これにより、計算を一桁（プラスまたはマイナス）スピードアップできます。
計算を並列化するための資料を探して、Haskell言語での純粋な計算は単なる並列化ではなく、非常に簡単に並列化されるという興味深い記事に出会いました。 そして、このためのほとんどすべてがすでにあります。 Control.Parallel.Strategiesモジュールをロードし、リストコンストラクターの後に再帰でマジックリスト「using」parList rdeepseqを追加するだけで十分です。
以下に最終バージョンを示します。 プログラムは-threadedスイッチを使用してコンパイルし、起動時に、パラメーターで、四角形の寸法に加えて、キー+ RTS -Nを指定する必要があります（たとえば、 knc 7 6 + RTS -N） 。
knc.hs
import Data.List(delete, (\\)) import qualified Data.Map.Lazy as M import Control.Parallel.Strategies import System.Environment type Cell = (Int, Int) type Pool = M.Map Cell [Cell] kDel :: Cell -> Pool -> Pool kDel x xs = M.delete x $ foldr (M.adjust (delete x)) xs (xs M.! x) deadlocks :: Pool -> [Cell] -> [Cell] deadlocks xs = filter ((<2).length.(xs M.!)) kNFromTo :: [Cell] -> Cell -> Pool -> Int kNFromTo ks s xs | M.size xs == 1 = 1 | otherwise = sum ( [kNFromTo (xs M.! k) s (kDel k xs) | k <- ks, k /= s, null $ deadlocks xs ks \\ [k,s]] `using` parList rdeepseq ) kNCircles :: Int -> Int -> Int kNCircles mn = kNFromTo [(2,3)] (3,2) $ prepare $ tail [(x,y) | x <- [1..m], y <- [1..n]] where prepare xs = M.fromList [(x, filter (near x) xs) | x <- xs] near (x1,y1) (x2,y2) = abs ((x2-x1)*(y2-y1)) == 2 main = do [m,n] <- getArgs print $ kNCircles (read m) (read n)
並列処理のシンプルさとその結果は、もちろん印象的です。 理論的には、プログラムは分岐の数に等しいスレッドの数で並列化できます。 閉じたルートの総数。 残念ながら、そのようなコアの数はまだありませんが、使用可能な8（試行済みおよび24）は複数の加速で100％でロードされます。 そして、この最終的な加速により、1週間の計算で7x8の長方形を分割することが可能になり、34 524 432 316サイクルが見つかりました。 これは予想をはるかに上回ることが判明し、今では8x8の正方形に対するWikipediaの評価は非常に現実的です。
要約すると、馬の動きの問題は予想外に多用途であることが判明し、言語を学ぶ上での良い習慣として役立ったと言いたいと思います。 さて、道に沿って、長方形の馬のコースによって閉じられた無方向ルートの数に対応するいくつかの新しい数値シーケンスを作成することが判明しました：
3x2n：
0, 0, 0, 0, 16, 176, 1536, 15424, 147728, 1448416, 14060048, 136947616, 1332257856, 12965578752, …
5x2n：
0, 0, 8, 44202, 13311268, 4557702762, …
6xn：
0, 0, 0, 0, 8, 9862, 1067638, 55488142, 3374967940, 239187240144, …
7x2n：
0, 0, 1067638, 34524432316, …
タイトルに「結論」という言葉を書きましたが、タスク自体にポイントを置くのは時期尚早です。
PSタスクはまだ手放しませんでした...
...計算をさらに最適化するために、定期的にアイデアが生まれました。 もちろん、すべてが機能したわけではありませんが、微調整によってさらに3回加速することができました。 1台のマシンで8x8の正方形を整理するのに3年の作業が必要になりましたが、2ダースのノードのファームでは、2、2か月で結果を達成することができました。 この結果はウィキペディアと完全に一致しました。8x8の正方形には13,267,364,410,532の閉じたルートが含まれています。 感覚がなかった、彼は5年遅れていたが、今、彼は彼を手放すことを望みます）
import Data.List (delete) import qualified Data.Map.Lazy as M import Control.Parallel.Strategies import System.Environment (getArgs) type Cell = Int type Pool = M.Map Cell [Cell] kDel :: Cell -> Pool -> Pool kDel x xs = M.delete x $ foldr (M.adjust (delete x)) xs (xs M.! x) kNC :: [Cell] -> Pool -> Integer kNC ks xs | M.size xs == 4 = 1 | otherwise = let ds = filter (null.tail.(xs M.!)) ks in if null ds then sum ( [ kNC (xs M.! k) (kDel k xs) | k <- ks, k /= 1 ] `using` parList rseq ) else let k = head ds in if null (tail ds) && k /= 1 then kNC (xs M.! k) (kDel k xs) else 0 kNCircles :: Int -> Int -> Integer kNCircles mn = kNC [m] $ prepare $ tail [(x,y) | x <- [1..m], y <- [1..n]] where prepare xs = M.adjust (++[1]) 1 $ M.fromList [(enc x, enc <$> filter (near x) xs) | x <- xs] near (x1,y1) (x2,y2) = abs ((x2 - x1) * (y2 - y1)) == 2 enc (x,y) = (y - 2) * m + x - 2 main = do [m,n] <- getArgs print $ kNCircles (read m) (read n)
→ パート1
→ パート2