Regarding the eliminations number, i believe you have a bug in counting them (correct me if i'm wrong. You shouldn't increment the counter until an actual elimination occurs.<div><br></div><div><div>-eliminate(Puzzle, [Square|T], Digit) -></div>
<div>+eliminate({Dict, Count}, [Square|T], Digit) -></div><div>     %% Eliminate the specified Digit from all specified Squares.</div><div>+    Puzzle = {Dict, Count+1},</div></div><div><br></div><div><div> eliminate({ValuesDict, Eliminations}, Square, Digit, NewValues, _) -></div>
<div>     NewDict = dict:store(Square, NewValues, ValuesDict),</div><div>-    NewPuzzle = peer_eliminate({NewDict, Eliminations+1}, Square, NewValues),</div><div>+    NewPuzzle = peer_eliminate({NewDict, Eliminations}, Square, NewValues),</div>
<div> </div></div><div><br></div><div><br><div class="gmail_quote">On Sun, Mar 27, 2011 at 5:49 PM, Evans, Matthew <span dir="ltr"><<a href="mailto:mevans@verivue.com">mevans@verivue.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
Good call on using atoms instead of lists. I wouldn't have imagined it would be that much faster. So on my computer the new Erlang implementation is much faster than python:<br>
<br>
Erlang with parse transforms and HiPE:<br>
<br>
[mevans@scream ~]$ ./sudoku<br>
expanding...<br>
expanding...<br>
expanding...<br>
expanding...<br>
Solved 50 of 50 puzzles from easy50.txt in 0.059767 secs (836.58 Hz)<br>
<div class="im">(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).<br>
</div>Solved 95 of 95 puzzles from top95.txt in 0.344457 secs (275.80 Hz)<br>
<div class="im">(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
</div>Solved 11 of 11 puzzles from hardest.txt in 0.025747 secs (427.23 Hz)<br>
<div class="im">(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).<br>
<br>
<br>
</div>Python:<br>
<br>
[mevans@scream ~]$ ./sudoku.py<br>
All tests pass.<br>
Solved 50 of 50 puzzles from easy50.txt in 0.530000 secs (94.34 Hz)<br>
<div class="im"> (33059 total eliminations, avg 661.00, median 648, max 830, min 648).<br>
</div>Solved 95 of 95 puzzles from top95.txt in 3.980000 secs (23.87 Hz)<br>
<div class="im"> (221997 total eliminations, avg 2336.00, median 1492, max 11512, min 648).<br>
</div>Solved 11 of 11 puzzles from hardest.txt in 0.150000 secs (73.33 Hz)<br>
<div class="im"> (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).<br>
</div>[mevans@scream ~]$<br>
<br>
<br>
The initial implementation in Erlang:<br>
<br>
[mevans@scream ~]$ ./sudoku<br>
./sudoku:4: Warning: variable 'Args' is unused<br>
Solved 50 of 50 puzzles from easy50.txt in 0.492551 secs (101.51 Hz)<br>
<div class="im">(92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).<br>
</div>Solved 95 of 95 puzzles from top95.txt in 3.120420 secs (30.44 Hz)<br>
<div class="im">(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
</div>Solved 11 of 11 puzzles from hardest.txt in 0.147977 secs (74.34 Hz)<br>
<div class="im">(33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).<br>
<br>
</div>________________________________________<br>
From: Kresten Krab Thorup [<a href="mailto:krab@trifork.com">krab@trifork.com</a>]<br>
Sent: Sunday, March 27, 2011 9:28 AM<br>
To: Evans, Matthew<br>
Cc: Ahmed Omar; <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>; Andreas Pauley<br>
Subject: Re: [erlang-questions 41] Re: A sudoku solver in Erlang compared to Python<br>
<div><div></div><div class="h5"><br>
For reference, I tried to run this with Erjang and R14B01 (with BEAN and HiPE/o3) on my machine ...<br>
<br>
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. :<br>
<br>
squares() -><br>
   %% Returns a list of 81 square names, including "A1" etc.<br>
    [erlang:list_to_atom([X,Y]) || X <- "ABCDEFGHI", Y <- "123456789"].<br>
<br>
<br>
BEAM<br>
> sudoku_main:run_solver(["solve"]).<br>
Solved 50 of 50 puzzles from easy50.txt in 0.678921 secs (73.65 Hz)<br>
  (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).<br>
Solved 95 of 95 puzzles from top95.txt in 4.373277 secs (21.72 Hz)<br>
  (901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
Solved 11 of 11 puzzles from hardest.txt in 0.198780 secs (55.34 Hz)<br>
  (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).<br>
ok<br>
<br>
Erjang<br>
> sudoku_main:run_solver(["solve"]).<br>
Solved 50 of 50 puzzles from easy50.txt in 0.653891 secs (76.47 Hz)<br>
  (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).<br>
Solved 95 of 95 puzzles from top95.txt in 4.354102 secs (21.82 Hz)<br>
  (901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
Solved 11 of 11 puzzles from hardest.txt in 0.208266 secs (52.82 Hz)<br>
  (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).<br>
ok<br>
<br>
r14b01 / HiPE / o3<br>
> sudoku_main:run_solver(["solve"]).<br>
Solved 50 of 50 puzzles from easy50.txt in 0.611918 secs (81.71 Hz)<br>
  (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).<br>
Solved 95 of 95 puzzles from top95.txt in 3.759281 secs (25.27 Hz)<br>
  (901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
Solved 11 of 11 puzzles from hardest.txt in 0.169039 secs (65.07 Hz)<br>
  (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).<br>
ok<br>
<br>
This version does not use pmap (Erjang's scheduler still needs some work), but does use atoms for square names, and ct_expand.<br>
<br>
Cheers,<br>
<br>
Kresten<br>
<br>
<br>
On Mar 26, 2011, at 23:33 , Evans, Matthew wrote:<br>
<br>
> Awesome point, I was going to actually suggest that since this is all calculating static data he just pre-calculates it and puts it in a -define. Or even better, if he is brave he could write a parse transform.<br>
><br>
> Using Ulf's ct_expand module (<a href="http://forum.trapexit.org/viewtopic.php?p=20260" target="_blank">http://forum.trapexit.org/viewtopic.php?p=20260</a>) I get even better performance:<br>
><br>
> Without the parse transform (but using native):<br>
><br>
> 4> sudoku:print_results("top95.txt", "\n").<br>
> Solved 95 of 95 puzzles from top95.txt in 0.827966 secs (114.74 Hz)<br>
> (901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
> ok<br>
><br>
><br>
> With a parse transform:<br>
><br>
> 2>  sudoku:print_results("top95.txt", "\n").<br>
> Solved 95 of 95 puzzles from top95.txt in 0.469908 secs (202.17 Hz)<br>
> (901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
><br>
><br>
> The code looks like:<br>
><br>
> -compile({parse_transform, ct_expand}).<br>
><br>
><br>
> squares() -><br>
>    %% Returns a list of 81 square names, including "A1" etc.<br>
>    ct_expand:term(<br>
>        [[X,Y] || X <- "ABCDEFGHI", Y <- "123456789"]<br>
>    ).<br>
> col_squares() -><br>
>    %% All the square names for each column.<br>
>    ct_expand:term(<br>
>        [[[X,Y] || X <- "ABCDEFGHI", Y <- [C]] || C <- "123456789"]<br>
>      ).<br>
> row_squares() -><br>
>    %% All the square names for each row.<br>
>    ct_expand:term(<br>
>        [[[X,Y] || X <- [R], Y <- "123456789"] || R <- "ABCDEFGHI"]<br>
>    ).<br>
> box_squares() -><br>
>    %% All the square names for each box.<br>
>    ct_expand:term(<br>
>        [[[X,Y] || X <- R, Y <- C] || R <- ["ABC", "DEF", "GHI"], C <- ["123", "456", "789"]]<br>
>    ).<br>
><br>
><br>
> ________________________________________<br>
> From: Ahmed Omar [<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a>]<br>
> Sent: Saturday, March 26, 2011 4:39 PM<br>
> To: Evans, Matthew<br>
> Cc: Andreas Pauley; <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
> Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python<br>
><br>
> 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<br>
> sudoku:'-cross/2-lc$^1/1-1-'/4                       96558660  37.46  35024918  [      0.36]<br>
><br>
> On Sat, Mar 26, 2011 at 9:33 PM, Ahmed Omar <<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a><mailto:<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a>>> wrote:<br>
> actually instead of doing<br>
><br>
><br>
><br>
>    NonUniquePeers = shallow_flatten([S || S <- units(Square)]),<br>
><br>
><br>
><br>
>    PeerSet = sets:from_list(NonUniquePeers),<br>
><br>
><br>
><br>
>    PeersWithSelf = sets:to_list(PeerSet),<br>
><br>
><br>
><br>
><br>
><br>
><br>
><br>
><br>
> can't u just do<br>
><br>
><br>
> PeersWithSelf = lists:usort(NonUniquePeers).<br>
><br>
><br>
><br>
> ?<br>
><br>
><br>
><br>
><br>
><br>
><br>
><br>
><br>
> On Sat, Mar 26, 2011 at 9:14 PM, Evans, Matthew <<a href="mailto:mevans@verivue.com">mevans@verivue.com</a><mailto:<a href="mailto:mevans@verivue.com">mevans@verivue.com</a>>> wrote:<br>
> Good call....gb_sets should be faster. Compiled to native it runs faster still<br>
><br>
> 9> sudoku:print_results("top95.txt", "\n").<br>
> Solved 95 of 95 puzzles from top95.txt in 0.810156 secs (117.26 Hz)<br>
> (901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).<br>
> ok<br>
><br>
> ________________________________________<br>
> From: Ahmed Omar [<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a><mailto:<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a>>]<br>
> Sent: Saturday, March 26, 2011 3:08 PM<br>
> To: Andreas Pauley<br>
> Cc: Evans, Matthew; <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>><br>
> Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python<br>
><br>
> 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.<br>
><br>
> On Sat, Mar 26, 2011 at 9:41 AM, Andreas Pauley <<a href="mailto:apauley@gmail.com">apauley@gmail.com</a><mailto:<a href="mailto:apauley@gmail.com">apauley@gmail.com</a>><mailto:<a href="mailto:apauley@gmail.com">apauley@gmail.com</a><mailto:<a href="mailto:apauley@gmail.com">apauley@gmail.com</a>>>> wrote:<br>

> Thanks, I've changed the compile options and this definitely makes it<br>
> somewhat faster:<br>
> <a href="https://github.com/apauley/sudoku-in-erlang/commit/b7ce2abb6ca013850ed8f3e8fd7f5f6be7004cbb" target="_blank">https://github.com/apauley/sudoku-in-erlang/commit/b7ce2abb6ca013850ed8f3e8fd7f5f6be7004cbb</a><br>

><br>
> Strangely the native flag is not documented here:<br>
> <a href="http://www.erlang.org/doc/man/compile.html#file-2" target="_blank">http://www.erlang.org/doc/man/compile.html#file-2</a><br>
><br>
> The more interesting improvement would be to decrease the number of<br>
> eliminations performed, but for that I'll have to go deep into the<br>
> code :-)<br>
><br>
><br>
> On Sat, Mar 26, 2011 at 12:16 AM, Evans, Matthew <<a href="mailto:mevans@verivue.com">mevans@verivue.com</a><mailto:<a href="mailto:mevans@verivue.com">mevans@verivue.com</a>><mailto:<a href="mailto:mevans@verivue.com">mevans@verivue.com</a><mailto:<a href="mailto:mevans@verivue.com">mevans@verivue.com</a>>>> wrote:<br>

>> Without going deep into the code, one thing to try is compile with the native flag (running the tests from the VM shell here):<br>
>><br>
>> Without native set:<br>
>> 18> c(sudoku).<br>
>> {ok,sudoku}<br>
>> 19>  sudoku:print_results("top95.txt", "\n").<br>
>> Solved 95 of 95 puzzles from top95.txt in 2.038825 secs (46.60 Hz)<br>
>> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).<br>
>> ok<br>
>><br>
>><br>
>> With native set:<br>
>> 20> c(sudoku,[native]).<br>
>> {ok,sudoku}<br>
>> 21>  sudoku:print_results("top95.txt", "\n").<br>
>> Solved 95 of 95 puzzles from top95.txt in 1.613416 secs (58.88 Hz)<br>
>> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).<br>
>><br>
>><br>
>><br>
>> -----Original Message-----<br>
>> From: <a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a><mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a>><mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a><mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a>>> [mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a><mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a>><mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a><mailto:<a href="mailto:erlang-questions-bounces@erlang.org">erlang-questions-bounces@erlang.org</a>>>] On Behalf Of Andreas Pauley<br>

>> Sent: Friday, March 25, 2011 8:15 AM<br>
>> To: <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>>><br>

>> Subject: [erlang-questions 4] A sudoku solver in Erlang compared to Python<br>
>><br>
>> Hi all,<br>
>><br>
>> In my quest to learn Erlang I've translated Peter Norvig's sudoku<br>
>> solver into Erlang:<br>
>> <a href="https://github.com/apauley/sudoku-in-erlang" target="_blank">https://github.com/apauley/sudoku-in-erlang</a><br>
>><br>
>> For comparison, my slightly modified version of Norvig's Python code<br>
>> can be found here:<br>
>> <a href="https://github.com/apauley/sudoku-by-norvig" target="_blank">https://github.com/apauley/sudoku-by-norvig</a><br>
>><br>
>> I like the pattern matching, it was fun to do the entire solution<br>
>> without a single if or case statement :-)<br>
>> Something that bothers me though is that the Python solution seems to<br>
>> be faster, even after I've made the Erlang solution use multiple<br>
>> processors.<br>
>><br>
>> In order to compare the two solutions I counted the number of<br>
>> eliminations each performed.<br>
>> The eliminate function is the core of the solution, for example<br>
>> assigning a single value to a square is implemented as the elimination<br>
>> of all other values.<br>
>><br>
>> With the Erlang implementation I get:<br>
>> sudoku-in-erlang$ ./sudoku<br>
>> All tests passed :-)<br>
>> Solved 50 of 50 puzzles from easy50.txt in 2.890978 secs (17.30 Hz)<br>
>> (93403 total eliminations, avg 1868.06, median 1810, max 2517, min 1770).<br>
>> Solved 95 of 95 puzzles from top95.txt in 22.004369 secs (4.32 Hz)<br>
>> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).<br>
>> Solved 11 of 11 puzzles from hardest.txt in 0.851678 secs (12.92 Hz)<br>
>> (32339 total eliminations, avg 2939.91, median 2894, max 4779, min 1781).<br>
>><br>
>> And with the Python implementation:<br>
>> sudoku-by-norvig$ ./sudoku.py<br>
>> All tests pass.<br>
>> Solved 50 of 50 puzzles from easy50.txt in 0.792008 secs (63.13 Hz)<br>
>> (33059 total eliminations, avg 661.00, median 648, max 830, min 648).<br>
>> Solved 95 of 95 puzzles from top95.txt in 5.903875 secs (16.09 Hz)<br>
>> (221997 total eliminations, avg 2336.00, median 1492, max 11512, min 648).<br>
>> Solved 11 of 11 puzzles from hardest.txt in 0.237532 secs (46.31 Hz)<br>
>> (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).<br>
>><br>
>> So according to the stats above, the Python solution performs less<br>
>> computations when given exactly the same input.<br>
>> The Erlang code is as close to the Python as I could make it, I've<br>
>> done more or less a direct translation of the algorithms used.<br>
>><br>
>> I suspect that there are some lazy evaluation happening in the Python<br>
>> version, possibly generators, although I haven't pinpointed it yet.<br>
>><br>
>> How can I improve my Erlang code in this solution?<br>
>><br>
>> Kind regards,<br>
>> Andreas<br>
>> _______________________________________________<br>
>> erlang-questions mailing list<br>
>> <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>>><br>

>> <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
>><br>
> _______________________________________________<br>
> erlang-questions mailing list<br>
> <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>>><br>

> <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
><br>
><br>
><br>
> --<br>
> Best Regards,<br>
> - Ahmed Omar<br>
> <a href="http://nl.linkedin.com/in/adiaa" target="_blank">http://nl.linkedin.com/in/adiaa</a><br>
> Follow me on twitter<br>
> @spawn_think<<a href="http://twitter.com/#!/spawn_think" target="_blank">http://twitter.com/#!/spawn_think</a>><br>
><br>
><br>
><br>
><br>
> --<br>
> Best Regards,<br>
> - Ahmed Omar<br>
> <a href="http://nl.linkedin.com/in/adiaa" target="_blank">http://nl.linkedin.com/in/adiaa</a><br>
> Follow me on twitter<br>
> @spawn_think<<a href="http://twitter.com/#!/spawn_think" target="_blank">http://twitter.com/#!/spawn_think</a>><br>
><br>
><br>
><br>
><br>
> --<br>
> Best Regards,<br>
> - Ahmed Omar<br>
> <a href="http://nl.linkedin.com/in/adiaa" target="_blank">http://nl.linkedin.com/in/adiaa</a><br>
> Follow me on twitter<br>
> @spawn_think<<a href="http://twitter.com/#!/spawn_think" target="_blank">http://twitter.com/#!/spawn_think</a>><br>
><br>
> _______________________________________________<br>
> erlang-questions mailing list<br>
> <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
> <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Best Regards,<br>- Ahmed Omar<div><a href="http://nl.linkedin.com/in/adiaa" target="_blank">http://nl.linkedin.com/in/adiaa</a></div><div>Follow me on twitter</div>
<div><a href="http://twitter.com/#!/spawn_think" target="_blank">@spawn_think</a></div><br>
</div>