[erlang-questions 32] Re: A sudoku solver in Erlang compared to Python

[Evans, Matthew]

Cool...

Might also want to look at what happens if all the other Erlang modules (esp. lists, sets and dict for your app) are made native:

Without native set:
18> c(sudoku).
 {ok,sudoku}
19>  sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 2.038825 secs (46.60 Hz)
(922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
ok


With native set:
20> c(sudoku,[native]).
{ok,sudoku}
>  sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 1.613416 secs (58.88 Hz)
 (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
ok

Dict/lists/sets native too:
5>  sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.996860 secs (95.30 Hz)
(922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
ok

Over a 2x boost in performance with zero re-factoring of your original code....maybe I'll put a question to the group out there. Seems that they should be shouting this sort of improvement from the roof-tops...

Matt

________________________________________
From: Andreas Pauley [apauley@REDACTED]
Sent: Saturday, March 26, 2011 4:41 AM
To: Evans, Matthew
Cc: erlang-questions@REDACTED
Subject: Re: [erlang-questions 4] A sudoku solver in Erlang compared to Python

Thanks, I've changed the compile options and this definitely makes it
somewhat faster:
https://github.com/apauley/sudoku-in-erlang/commit/b7ce2abb6ca013850ed8f3e8fd7f5f6be7004cbb

Strangely the native flag is not documented here:
http://www.erlang.org/doc/man/compile.html#file-2

The more interesting improvement would be to decrease the number of
eliminations performed, but for that I'll have to go deep into the
code :-)


On Sat, Mar 26, 2011 at 12:16 AM, Evans, Matthew <mevans@REDACTED> wrote:
> Without going deep into the code, one thing to try is compile with the native flag (running the tests from the VM shell here):
>
> Without native set:
> 18> c(sudoku).
> {ok,sudoku}
> 19>  sudoku:print_results("top95.txt", "\n").
> Solved 95 of 95 puzzles from top95.txt in 2.038825 secs (46.60 Hz)
> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
> ok
>
>
> With native set:
> 20> c(sudoku,[native]).
> {ok,sudoku}
> 21>  sudoku:print_results("top95.txt", "\n").
> Solved 95 of 95 puzzles from top95.txt in 1.613416 secs (58.88 Hz)
> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
>
>
>
> -----Original Message-----
> From: erlang-questions-bounces@REDACTED [mailto:erlang-questions-bounces@REDACTED] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: erlang-questions@REDACTED
> Subject: [erlang-questions 4] A sudoku solver in Erlang compared to Python
>
> Hi all,
>
> In my quest to learn Erlang I've translated Peter Norvig's sudoku
> solver into Erlang:
> https://github.com/apauley/sudoku-in-erlang
>
> For comparison, my slightly modified version of Norvig's Python code
> can be found here:
> https://github.com/apauley/sudoku-by-norvig
>
> I like the pattern matching, it was fun to do the entire solution
> without a single if or case statement :-)
> Something that bothers me though is that the Python solution seems to
> be faster, even after I've made the Erlang solution use multiple
> processors.
>
> In order to compare the two solutions I counted the number of
> eliminations each performed.
> The eliminate function is the core of the solution, for example
> assigning a single value to a square is implemented as the elimination
> of all other values.
>
> With the Erlang implementation I get:
> sudoku-in-erlang$ ./sudoku
> All tests passed :-)
> Solved 50 of 50 puzzles from easy50.txt in 2.890978 secs (17.30 Hz)
>  (93403 total eliminations, avg 1868.06, median 1810, max 2517, min 1770).
> Solved 95 of 95 puzzles from top95.txt in 22.004369 secs (4.32 Hz)
>  (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
> Solved 11 of 11 puzzles from hardest.txt in 0.851678 secs (12.92 Hz)
>  (32339 total eliminations, avg 2939.91, median 2894, max 4779, min 1781).
>
> And with the Python implementation:
> sudoku-by-norvig$ ./sudoku.py
> All tests pass.
> Solved 50 of 50 puzzles from easy50.txt in 0.792008 secs (63.13 Hz)
>  (33059 total eliminations, avg 661.00, median 648, max 830, min 648).
> Solved 95 of 95 puzzles from top95.txt in 5.903875 secs (16.09 Hz)
>  (221997 total eliminations, avg 2336.00, median 1492, max 11512, min 648).
> Solved 11 of 11 puzzles from hardest.txt in 0.237532 secs (46.31 Hz)
>  (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).
>
> So according to the stats above, the Python solution performs less
> computations when given exactly the same input.
> The Erlang code is as close to the Python as I could make it, I've
> done more or less a direct translation of the algorithms used.
>
> I suspect that there are some lazy evaluation happening in the Python
> version, possibly generators, although I haven't pinpointed it yet.
>
> How can I improve my Erlang code in this solution?
>
> Kind regards,
> Andreas
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>