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

Sat Mar 26 21:39:13 CET 2011

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.think@REDACTED> 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 <mevans@REDACTED>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.think@REDACTED]
>> Sent: Saturday, March 26, 2011 3:08 PM
>> To: Andreas Pauley
>> Cc: Evans, Matthew; erlang-questions@REDACTED
>> 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 <apauley@REDACTED
>> <mailto:apauley@REDACTED>> 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 :-)
>>
>>
>> On Sat, Mar 26, 2011 at 12:16 AM, Evans, Matthew <mevans@REDACTED
>> <mailto:mevans@REDACTED>> wrote:
>> > 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> [mailto:
>> 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<mailto: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<mailto:erlang-questions@REDACTED>
>> > http://erlang.org/mailman/listinfo/erlang-questions
>> >
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED<mailto:erlang-questions@REDACTED>
>> 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>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20110326/2ea42ff0/attachment.htm>