[Haskell-cafe] Code Review: Sudoku solver
haskell at list.mightyreason.com
Sat Apr 8 04:21:07 EDT 2006
Daniel Fischer wrote:
> But, lo and behold, I also tried how plai Array fared in comparison to
> DiffArray and ... reduced the running time to under ten minutes (a little
> above for the list version), 5% GC time without -AxM, 1.2% with -A8M.
> And I thought, DiffArrays were supposed to be fast!
No. DiffArray's are faster for the usual imperative single threaded usage
pattern. The haddock documentation explains:
> Diff arrays have an immutable interface, but rely on internal updates in
> place to provide fast functional update operator //.
> When the // operator is applied to a diff array, its contents are physically
> updated in place. The old array silently changes its representation without
> changing the visible behavior: it stores a link to the new current array
> along with the difference to be applied to get the old contents.
> So if a diff array is used in a single-threaded style, i.e. after //
> application the old version is no longer used, a'!'i takes O(1) time and a //
> d takes O(length d). Accessing elements of older versions gradually becomes
> Updating an array which is not current makes a physical copy. The resulting
> array is unlinked from the old family. So you can obtain a version which is
> guaranteed to be current and thus have fast element access by a // .
I assume the usage in a Sudoku solver involves a non-trivial amount of
back-tracking. So as the solver backs up and goes forward again it ends up
being much more work than having used a plain Array.
And as was pointed out by someone else on this list: to be thread safe the
DiffArray uses MVar's (with locking) instead of IOVars.
But I expect the main problem is that a DiffArray is simply not the right
mutable data structure for the job.
I have had the flu this week, so I did not finish cleaning up my port of Knuth's
mutable dancing links based Sudoku solver. But it uses a much more lightweight
way to alter a mutable data structure both going forward and backwards while
backtracking. And I can use STRef's to build it, instead of MVars.
More information about the Haskell-Cafe