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

[Evans, Matthew]

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