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-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions
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).
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 :-)
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 [apa...@gmail.com]
Sent: Saturday, March 26, 2011 4:41 AM
To: Evans, Matthew
Cc: erlang-q...@erlang.org
Subject: Re: [erlang-questions 4] A sudoku solver in Erlang compared to Python
9> sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.810156 secs (117.26 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
ok
________________________________________
From: Ahmed Omar [spawn...@gmail.com]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; erlang-q...@erlang.org
Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python
using gb_sets instead of sets could decrease eliminations a bit and give u some boost. However, i didn't dive deeper into the code or the algorithm.
On Sat, Mar 26, 2011 at 9:41 AM, Andreas Pauley <apa...@gmail.com<mailto:apa...@gmail.com>> wrote:
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 :-)
> erlang-q...@erlang.org<mailto:erlang-q...@erlang.org>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org<mailto:erlang-q...@erlang.org>
http://erlang.org/mailman/listinfo/erlang-questions
--
Best Regards,
- Ahmed Omar
http://nl.linkedin.com/in/adiaa
Follow me on twitter
@spawn_think<http://twitter.com/#!/spawn_think>
NonUniquePeers = shallow_flatten([S || S <- units(Square)]),PeerSet = sets:from_list(NonUniquePeers),PeersWithSelf = sets:to_list(PeerSet),
can't u just doPeersWithSelf = lists:usort(NonUniquePeers).?
Using Ulf's ct_expand module (http://forum.trapexit.org/viewtopic.php?p=20260) I get even better performance:
Without the parse transform (but using native):
4> sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.827966 secs (114.74 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
ok
With a parse transform:
2> sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.469908 secs (202.17 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
The code looks like:
-compile({parse_transform, ct_expand}).
squares() ->
%% Returns a list of 81 square names, including "A1" etc.
ct_expand:term(
[[X,Y] || X <- "ABCDEFGHI", Y <- "123456789"]
).
col_squares() ->
%% All the square names for each column.
ct_expand:term(
[[[X,Y] || X <- "ABCDEFGHI", Y <- [C]] || C <- "123456789"]
).
row_squares() ->
%% All the square names for each row.
ct_expand:term(
[[[X,Y] || X <- [R], Y <- "123456789"] || R <- "ABCDEFGHI"]
).
box_squares() ->
%% All the square names for each box.
ct_expand:term(
[[[X,Y] || X <- R, Y <- C] || R <- ["ABC", "DEF", "GHI"], C <- ["123", "456", "789"]]
).
________________________________________
From: Ahmed Omar [spawn...@gmail.com]
Sent: Saturday, March 26, 2011 4:39 PM
To: Evans, Matthew
Cc: Andreas Pauley; erlang-q...@erlang.org
Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python
BTW, beside looking into reducing eleminations (which requires deep dive), if u do some time profiling using eprof u will find that most of the time spent actually in the cross functions
sudoku:'-cross/2-lc$^1/1-1-'/4 96558660 37.46 35024918 [ 0.36]
On Sat, Mar 26, 2011 at 9:33 PM, Ahmed Omar <spawn...@gmail.com<mailto:spawn...@gmail.com>> wrote:
actually instead of doing
NonUniquePeers = shallow_flatten([S || S <- units(Square)]),
PeerSet = sets:from_list(NonUniquePeers),
PeersWithSelf = sets:to_list(PeerSet),
can't u just do
PeersWithSelf = lists:usort(NonUniquePeers).
?
On Sat, Mar 26, 2011 at 9:14 PM, Evans, Matthew <mev...@verivue.com<mailto:mev...@verivue.com>> wrote:
Good call....gb_sets should be faster. Compiled to native it runs faster still
9> sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.810156 secs (117.26 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
ok
________________________________________
From: Ahmed Omar [spawn...@gmail.com<mailto:spawn...@gmail.com>]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; erlang-q...@erlang.org<mailto:erlang-q...@erlang.org>
Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python
using gb_sets instead of sets could decrease eliminations a bit and give u some boost. However, i didn't dive deeper into the code or the algorithm.
On Sat, Mar 26, 2011 at 9:41 AM, Andreas Pauley <apa...@gmail.com<mailto:apa...@gmail.com><mailto:apa...@gmail.com<mailto:apa...@gmail.com>>> wrote:
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 :-)
> erlang-q...@erlang.org<mailto:erlang-q...@erlang.org><mailto:erlang-q...@erlang.org<mailto:erlang-q...@erlang.org>>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org<mailto:erlang-q...@erlang.org><mailto:erlang-q...@erlang.org<mailto:erlang-q...@erlang.org>>
http://erlang.org/mailman/listinfo/erlang-questions
--
Best Regards,
- Ahmed Omar
http://nl.linkedin.com/in/adiaa
Follow me on twitter
@spawn_think<http://twitter.com/#!/spawn_think>
--
Best Regards,
- Ahmed Omar
http://nl.linkedin.com/in/adiaa
Follow me on twitter
@spawn_think<http://twitter.com/#!/spawn_think>
--
Best Regards,
- Ahmed Omar
http://nl.linkedin.com/in/adiaa
Follow me on twitter
@spawn_think<http://twitter.com/#!/spawn_think>
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://www.erlang-solutions.com/section/47/2006-competition#FirstPrizeB
:)
--
Olivier
Oh, and I changed the square names to be atoms in stead of [X,Y] pairs, which speeds up things quite a lot too ... e.g. :
squares() ->
%% Returns a list of 81 square names, including "A1" etc.
[erlang:list_to_atom([X,Y]) || X <- "ABCDEFGHI", Y <- "123456789"].
BEAM
> sudoku_main:run_solver(["solve"]).
Solved 50 of 50 puzzles from easy50.txt in 0.678921 secs (73.65 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 4.373277 secs (21.72 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.198780 secs (55.34 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
ok
Erjang
> sudoku_main:run_solver(["solve"]).
Solved 50 of 50 puzzles from easy50.txt in 0.653891 secs (76.47 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 4.354102 secs (21.82 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.208266 secs (52.82 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
ok
r14b01 / HiPE / o3
> sudoku_main:run_solver(["solve"]).
Solved 50 of 50 puzzles from easy50.txt in 0.611918 secs (81.71 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 3.759281 secs (25.27 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.169039 secs (65.07 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
ok
This version does not use pmap (Erjang's scheduler still needs some work), but does use atoms for square names, and ct_expand.
Cheers,
Kresten
Erlang with parse transforms and HiPE:
[mevans@scream ~]$ ./sudoku
expanding...
expanding...
expanding...
expanding...
Solved 50 of 50 puzzles from easy50.txt in 0.059767 secs (836.58 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 0.344457 secs (275.80 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.025747 secs (427.23 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
Python:
[mevans@scream ~]$ ./sudoku.py
All tests pass.
Solved 50 of 50 puzzles from easy50.txt in 0.530000 secs (94.34 Hz)
(33059 total eliminations, avg 661.00, median 648, max 830, min 648).
Solved 95 of 95 puzzles from top95.txt in 3.980000 secs (23.87 Hz)
(221997 total eliminations, avg 2336.00, median 1492, max 11512, min 648).
Solved 11 of 11 puzzles from hardest.txt in 0.150000 secs (73.33 Hz)
(9436 total eliminations, avg 857.00, median 817, max 1198, min 648).
[mevans@scream ~]$
The initial implementation in Erlang:
[mevans@scream ~]$ ./sudoku
./sudoku:4: Warning: variable 'Args' is unused
Solved 50 of 50 puzzles from easy50.txt in 0.492551 secs (101.51 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 3.120420 secs (30.44 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.147977 secs (74.34 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
________________________________________
From: Kresten Krab Thorup [kr...@trifork.com]
Sent: Sunday, March 27, 2011 9:28 AM
To: Evans, Matthew
Cc: Ahmed Omar; erlang-q...@erlang.org; Andreas Pauley
Subject: Re: [erlang-questions 41] Re: A sudoku solver in Erlang compared to Python
https://github.com/apauley/sudoku-in-erlang/commit/a02fbcd001a9fbd876725008d58c52fcff9872d9
Thanks, done:
https://github.com/apauley/sudoku-in-erlang/commit/1852c68baf525524d21ea508dead3f51820141b5
> (don't forget to check the rest of the thread too ;))
Yes, thanks everyone, all the suggestions are awesome, I'm going
through them one by one :-)
Ok, so to try this I copied lists.erl etc. into my own source dir, and
then I compiled it to beams using the native flag.
Is that what you meant?
Because that will be cool for a once-off experiment, but not so cool
in the long run.
Doing that means I'm taking responsibility for doing it every time I
upgrade my Erlang version etc.
Is there a way to do it with less maintenance?
These are the changes I made to use multiple processors:
https://github.com/apauley/sudoku-in-erlang/commit/306333757e3df2fcafdb94604b8963dd2b7c79e0
https://github.com/apauley/sudoku-in-erlang/commit/58a5ac65b83219f85b34bb955e75c7e0db6f5122
You're right, not much changed :-)
Feel free to show me if there is a cleaner way to do this.
Regards,
Andreas
But when I run ./configure, it says it can not find the wx/stc/stc.h
file, and so can not link the wx interface.
I have all the wx components installed that ought to include that, so I
went looking for the file. It is there, in /include. But ./configure
is looking for it somewhere else. How do I convince it to look in the
right place?
I installed wxWidgets using the Ubuntu package tool, which runs apt-get
behind the scenes.
I had this working on Ubuntu 9.04 with a previous Erlang release, but do
not remember how I did it.
Maybe have a look at my "mental note" for installing Erlang/OTP from
source on Ubuntu systems at for comparison:
http://boris.muehmer.de/2010/10/16/installing-erlangotp-r14b-on-ubuntu-from-source/
Hopefully this helps...
- boris
2011/3/28 Mojito Sorbet <mojit...@gmail.com>:
Solved 50 of 50 puzzles from easy50.txt in 1.277456 secs (39.14 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 8.024644 secs (11.84 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.384212 secs (28.63 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
Previously:
Solved 50 of 50 puzzles from easy50.txt in 1.960654 secs (25.50 Hz)
(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
Solved 95 of 95 puzzles from top95.txt in 13.472294 secs (7.05 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820,
min 1792).
Solved 11 of 11 puzzles from hardest.txt in 0.600741 secs (18.31 Hz)
(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
I don't see the same speeds as other people, but I guess it's because
my Macbook only has 2 cores.
This reduces the elimination count significantly :-)
Solved 50 of 50 puzzles from easy50.txt in 1.286811 secs (38.86 Hz)
(32833 total eliminations, avg 656.66, median 648, max 808, min 648).
Solved 95 of 95 puzzles from top95.txt in 8.572484 secs (11.08 Hz)
(210794 total eliminations, avg 2218.88, median 1536, max 10664, min 648).
Solved 11 of 11 puzzles from hardest.txt in 0.391032 secs (28.13 Hz)
(9516 total eliminations, avg 865.09, median 813, max 1227, min 648).
I'd love to use atoms as square names, just because it looks cleaner.
However, I'm getting a severe performance hit when I use
list_to_atom/1 on each square name.
Can you show me how you did it in conjunction with ct_expand?
Thanks!
Andreas
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
I tried the code in your repo, but it wasn't significantly faster on my machine.
It was interesting though to go through your refactorings.
I see you changed the signature for solve so that the empty puzzle and
the list of square names are passed in from the start.
Maybe I should try this approach in conjunction with the conversion to atoms...
Regards,
Andreas
Is there a definition of "Erlang core"?
bengt
_______________________________________________
Luckily the unit tests pointed this out.
But all is not lost, I still got a simplification out of the deal.
We still need to check the non-unique length of UnitValues in that
function, but the second clause does not need to use sets anymore:
https://github.com/apauley/sudoku-in-erlang/commit/f092e55df292d1f12ff8406ce60bb435e7a83667
On Mar 28, 2011, at 15:22 , Andreas Pauley wrote:
> I'd love to use atoms as square names, just because it looks cleaner.
> However, I'm getting a severe performance hit when I use
> list_to_atom/1 on each square name.
>
> Can you show me how you did it in conjunction with ct_expand?
These are the changed functions, [and then the unit tests need to be updated accordingly]... ct_expand doesn't like function applications, so the function unitlist() needs to have the other definitions inlined.
Kresten
squares() ->
%% Returns a list of 81 square names, including "a1" etc.
ct_expand:term([erlang:list_to_atom([X,Y]) || X <- ?rows, Y <- ?cols]).
col_squares() ->
%% All the square names for each column.
([[erlang:list_to_atom([X,Y]) || X <- ?rows, Y <- [C]] || C <- ?cols]).
row_squares() ->
%% All the square names for each row.
ct_expand:term([[erlang:list_to_atom([X,Y]) || X <- [R], Y <- ?cols] || R <- ?rows]).
box_squares() ->
%% All the square names for each box.
ct_expand:term([[erlang:list_to_atom([X,Y]) || X <- R, Y <- C] ||
R <- ["abc", "def", "ghi"],
C <- ["123", "456", "789"]]).
unitlist() ->
%% A list of all units (columns, rows, boxes) in a grid.
ct_expand:term( [[erlang:list_to_atom([X,Y]) || X <- ?rows, Y <- [C]] || C <- ?cols]
++ [[erlang:list_to_atom([X,Y]) || X <- [R], Y <- ?cols] || R <- ?rows]
++ [[erlang:list_to_atom([X,Y]) || X <- R, Y <- C] ||
R <- ["abc", "def", "ghi"],
C <- ["123", "456", "789"]]).
_______________________________________________
The 3 inlined functions are now dead, so I just removed them.