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 <div>sudoku:'-cross/2-lc$^1/1-1-'/4 96558660 37.46 35024918 [ 0.36]<br>
<br><div class="gmail_quote">On Sat, Mar 26, 2011 at 9:33 PM, Ahmed Omar <span dir="ltr"><<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
actually instead of doing <div><span style="font-family:helvetica, arial, freesans, clean, sans-serif;font-size:11px;line-height:14px"><pre style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;font-family:'Bitstream Vera Sans Mono', Courier, monospace;font-size:12px">
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">NonUniquePeers</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;font-weight:bold">=</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">shallow_flatten</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">([</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">S</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">||</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">S</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;font-weight:bold"><-</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">units</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">(</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">Square</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">)]),</span></div>
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">PeerSet</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;font-weight:bold">=</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(85, 85, 85)">sets</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">:</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">from_list</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">(</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">NonUniquePeers</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">),</span></div>
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">PeersWithSelf</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;font-weight:bold">=</span> <span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(85, 85, 85)">sets</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">:</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">to_list</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">(</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em;color:rgb(0, 128, 128)">PeerSet</span><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">),</span></div>
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em"><br>
</span></div><div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em">
<span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">can't u just do </span></div>
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">PeersWithSelf = lists:usort(NonUniquePeers). </span></div>
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em">?</span></div>
<div style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:1em;line-height:1.4em"><span style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;line-height:1.4em"><br>
</span></div></pre></span><div><div></div><div class="h5"><br><div class="gmail_quote">On Sat, Mar 26, 2011 at 9:14 PM, Evans, Matthew <span dir="ltr"><<a href="mailto:mevans@verivue.com" target="_blank">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">
Good call....gb_sets should be faster. Compiled to native it runs faster still<br>
<div><br>
9> sudoku:print_results("top95.txt", "\n").<br>
</div>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" target="_blank">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" target="_blank">erlang-questions@erlang.org</a><br>
Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python<br>
<div><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>
</div><div>On Sat, Mar 26, 2011 at 9:41 AM, Andreas Pauley <<a href="mailto:apauley@gmail.com" target="_blank">apauley@gmail.com</a><mailto:<a href="mailto:apauley@gmail.com" target="_blank">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>
</div><div>On Sat, Mar 26, 2011 at 12:16 AM, Evans, Matthew <<a href="mailto:mevans@verivue.com" target="_blank">mevans@verivue.com</a><mailto:<a href="mailto:mevans@verivue.com" target="_blank">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>
</div><div>> From: <a href="mailto:erlang-questions-bounces@erlang.org" target="_blank">erlang-questions-bounces@erlang.org</a><mailto:<a href="mailto:erlang-questions-bounces@erlang.org" target="_blank">erlang-questions-bounces@erlang.org</a>> [mailto:<a href="mailto:erlang-questions-bounces@erlang.org" target="_blank">erlang-questions-bounces@erlang.org</a><mailto:<a href="mailto:erlang-questions-bounces@erlang.org" target="_blank">erlang-questions-bounces@erlang.org</a>>] On Behalf Of Andreas Pauley<br>
> Sent: Friday, March 25, 2011 8:15 AM<br>
</div><div><div></div><div>> To: <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org" target="_blank">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>
</div></div>> <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a>><br>
<div>> <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>
</div><a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><mailto:<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a>><br>
<div><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>
</div>@spawn_think<<a href="http://twitter.com/#!/spawn_think" target="_blank">http://twitter.com/#!/spawn_think</a>><br>
<br>
</blockquote></div><br><br clear="all"><br></div></div>-- <br><div class="im">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></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>