Yes u r correct :) sorry i missed that point, i didn't dig enough :)<div><br></div><div><br><div class="gmail_quote">On Tue, Mar 29, 2011 at 12:02 PM, Andreas Pauley <span dir="ltr"><<a href="mailto:apauley@gmail.com">apauley@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Unfortunately it's not that easy this time.<br>
The major reduction in eliminations happens because is_unit_solved/2<br>
always returns true after the proposed change.<br>
If you open any of the .out files (eg hardest.out) you'll see that the<br>
puzzles aren't really solved.<br>
<br>
Luckily the unit tests pointed this out.<br>
<br>
But all is not lost, I still got a simplification out of the deal.<br>
We still need to check the non-unique length of UnitValues in that<br>
function, but the second clause does not need to use sets anymore:<br>
<a href="https://github.com/apauley/sudoku-in-erlang/commit/f092e55df292d1f12ff8406ce60bb435e7a83667" target="_blank">https://github.com/apauley/sudoku-in-erlang/commit/f092e55df292d1f12ff8406ce60bb435e7a83667</a><br>
<div><div></div><div class="h5"><br>
<br>
On Mon, Mar 28, 2011 at 4:39 PM, Ahmed Omar <<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a>> wrote:<br>
> Hi Andreas,<br>
> For some reason, lists:usort is your friend again!<br>
> Looking into the code deeper, one line can give u huge boost!<br>
> You compare the unit values with digits with<br>
> (length(UnitValues) == 9)<br>
> and (gb_sets:from_list(UnitValues) == gb_sets:from_list(digits())).<br>
> I understand (correct me if i'm wrong) u check first the length to make sure<br>
> it's 9 digits then u convert to sets to make sure they r unique and compare<br>
> them. But if you think about it, if the unique list of values is of length<br>
> 9, u don't need more comparisons!<br>
> so u can actually just do<br>
> (length(lists:usort(UnitValues)==9)<br>
> before the change:<br>
> sudoku:print_results("top95.txt").<br>
> Solved 95 of 95 puzzles from top95.txt in 1.937175 secs (49.04 Hz)<br>
> (210794 total eliminations, avg 2218.88, median 1536, max 10664, min 648).<br>
> after the change :<br>
> sudoku:print_results("top95.txt").<br>
> Solved 95 of 95 puzzles from top95.txt in 0.382337 secs (248.47 Hz)<br>
> (45002 total eliminations, avg 473.71, median 479, max 518, min 427).<br>
><br>
> On Mon, Mar 28, 2011 at 3:32 PM, Andreas Pauley <<a href="mailto:apauley@gmail.com">apauley@gmail.com</a>> wrote:<br>
>><br>
>> Hi Tristan,<br>
>><br>
>> I tried the code in your repo, but it wasn't significantly faster on my<br>
>> machine.<br>
>><br>
>> It was interesting though to go through your refactorings.<br>
>> I see you changed the signature for solve so that the empty puzzle and<br>
>> the list of square names are passed in from the start.<br>
>> Maybe I should try this approach in conjunction with the conversion to<br>
>> atoms...<br>
>><br>
>> Regards,<br>
>> Andreas<br>
>><br>
>> On Sat, Mar 26, 2011 at 10:56 PM, Tristan Sloughter<br>
>> <<a href="mailto:tristan.sloughter@gmail.com">tristan.sloughter@gmail.com</a>> wrote:<br>
>> > With a few refactorings (<a href="https://github.com/tsloughter/sudoku-in-erlang" target="_blank">https://github.com/tsloughter/sudoku-in-erlang</a><br>
>> > --<br>
>> > note I used ewl_plists just to make the code simpler:<br>
>> > <a href="https://github.com/erlware/erlware/tree/master/lib/ewlib" target="_blank">https://github.com/erlware/erlware/tree/master/lib/ewlib</a>) and compile<br>
>> > with<br>
>> > native, hipe o3 it beats python's:<br>
>> > $ ./sudoku.py<br>
>> > All tests pass.<br>
>> > Solved 50 of 50 puzzles from easy50.txt in 0.529119 secs (94.50 Hz)<br>
>> > (33059 total eliminations, avg 661.00, median 648, max 830, min 648).<br>
>> > Solved 95 of 95 puzzles from top95.txt in 3.889944 secs (24.42 Hz)<br>
>> > (221997 total eliminations, avg 2336.00, median 1492, max 11512, min<br>
>> > 648).<br>
>> > Solved 11 of 11 puzzles from hardest.txt in 0.157520 secs (69.83 Hz)<br>
>> > (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).<br>
>> > $ ./sudoku<br>
>> > All tests passed :-)<br>
>> > Solved 50 of 50 puzzles from easy50.txt in 0.556385 secs (89.87 Hz)<br>
>> > (92538 total eliminations, avg 1850.76, median 1811, max 2628, min<br>
>> > 1767).<br>
>> > Solved 95 of 95 puzzles from top95.txt in 3.593476 secs (26.44 Hz)<br>
>> > (901201 total eliminations, avg 9486.33, median 6267, max 56820, min<br>
>> > 1792).<br>
>> > Solved 11 of 11 puzzles from hardest.txt in 0.162107 secs (67.86 Hz)<br>
>> > (33653 total eliminations, avg 3059.36, median 3023, max 5346, min<br>
>> > 1786).<br>
>> > I ran a number of times, those are pretty much what it always comes out<br>
>> > to.<br>
>> > But I haven't really tried a full refactoring, I think a number of<br>
>> > things<br>
>> > can be reduced to less iterations.<br>
>> ><br>
>> > Tristan<br>
>> > On Sat, Mar 26, 2011 at 3:39 PM, Ahmed Omar <<a href="mailto:spawn.think@gmail.com">spawn.think@gmail.com</a>><br>
>> > wrote:<br>
>> >><br>
>> >> BTW, beside looking into reducing eleminations (which requires deep<br>
>> >> dive),<br>
>> >> if u do some time profiling using eprof u will find that most of the<br>
>> >> time<br>
>> >> spent actually in the cross functions<br>
>> >> sudoku:'-cross/2-lc$^1/1-1-'/4 96558660 37.46<br>
>> >> 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>><br>
>> >> wrote:<br>
>> >>><br>
>> >>> actually instead of doing<br>
>> >>><br>
>> >>> NonUniquePeers = shallow_flatten([S || S <- units(Square)]),<br>
>> >>><br>
>> >>><br>
>> >>> PeerSet = sets:from_list(NonUniquePeers),<br>
>> >>><br>
>> >>><br>
>> >>> PeersWithSelf = sets:to_list(PeerSet),<br>
>> >>><br>
>> >>><br>
>> >>><br>
>> >>><br>
>> >>><br>
>> >>><br>
>> >>><br>
>> >>> can't u just do<br>
>> >>> PeersWithSelf = lists:usort(NonUniquePeers).<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>><br>
>> >>> wrote:<br>
>> >>>><br>
>> >>>> Good call....gb_sets should be faster. Compiled to native it runs<br>
>> >>>> faster<br>
>> >>>> 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<br>
>> >>>> 1792).<br>
>> >>>> ok<br>
>> >>>><br>
>> >>>> ________________________________________<br>
>> >>>> From: Ahmed Omar [<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><br>
>> >>>> Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang<br>
>> >>>> compared to Python<br>
>> >>>><br>
>> >>>> using gb_sets instead of sets could decrease eliminations a bit and<br>
>> >>>> give<br>
>> >>>> u some boost. However, i didn't dive deeper into the code or the<br>
>> >>>> algorithm.<br>
>> >>>><br>
>> >>>> On Sat, Mar 26, 2011 at 9:41 AM, Andreas Pauley<br>
>> >>>> <<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>
>> >>>><br>
>> >>>><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<br>
>> >>>> <<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<br>
>> >>>> > the<br>
>> >>>> > 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,<br>
>> >>>> > min<br>
>> >>>> > 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,<br>
>> >>>> > min<br>
>> >>>> > 1797).<br>
>> >>>> ><br>
>> >>>> ><br>
>> >>>> ><br>
>> >>>> > -----Original Message-----<br>
>> >>>> > From:<br>
>> >>>> ><br>
>> >>>> > <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>><br>
>> >>>> ><br>
>> >>>> > [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>>]<br>
>> >>>> > 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>><br>
>> >>>> > Subject: [erlang-questions 4] A sudoku solver in Erlang compared to<br>
>> >>>> > 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<br>
>> >>>> > 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<br>
>> >>>> > 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<br>
>> >>>> > 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<br>
>> >>>> > 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,<br>
>> >>>> > min<br>
>> >>>> > 1797).<br>
>> >>>> > Solved 11 of 11 puzzles from hardest.txt in 0.851678 secs (12.92<br>
>> >>>> > Hz)<br>
>> >>>> > (32339 total eliminations, avg 2939.91, median 2894, max 4779, min<br>
>> >>>> > 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<br>
>> >>>> > 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,<br>
>> >>>> > min<br>
>> >>>> > 648).<br>
>> >>>> > Solved 11 of 11 puzzles from hardest.txt in 0.237532 secs (46.31<br>
>> >>>> > Hz)<br>
>> >>>> > (9436 total eliminations, avg 857.00, median 817, max 1198, min<br>
>> >>>> > 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<br>
>> >>>> > 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>><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>><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<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<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>
>> ><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<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>