On Tuesday, July 1, 2014 1:37:00 PM UTC-4, andy hayden wrote: > > I recently ported Norvig's Solve Every Sudoku Puzzle > <http://norvig.com/sudoku.html> to Julia: > https://github.com/hayd/Sudoku.jl > > Some simple benchmarks suggest my Julia implementation solves around 20% > slower* than the Python version >
A few things that pop out at first glance: You probably want to use a different data structure than an array of strings. Your array of strings approach requires you call the replace() function in your innermost loop body, which allocates a new string. It would be better to use some mutable data structure (e.g. an array of 10 bools, one per digit? I would actually tend to use bit tricks here to use one bit per digit in a single Uint16) The allocation of a new dictionary (poss) in every call to search(...) seems unnecessary. A dictionary is total overkill here because the only things you do with the dictionary are to call length and minimum on it, both of which can be computed much more cheaply just by a single loop over vals. Probably your globals should be made const ... non-const globals are a performance sink. Your search(...) function calls copy(vals) in its innermost loop, which seems horrendously wasteful. Rather than copying the whole data structure, I would do the assign! in-place, then do the search, and then undo the assignment if the search did not succeed. Many of your functions are not type-stable because they return "false" to signal failure and some other value on success. You should be able to do things in a type-stable way. For example, I would suggest that you change search(vals) to search!(vals), changing vals to the solution in-place (see above), and then return true or false depending upon whether the search succeeds.
