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

Andreas Pauley apauley@REDACTED
Mon Mar 28 15:32:20 CEST 2011 

Hi Tristan,

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

On Sat, Mar 26, 2011 at 10:56 PM, Tristan Sloughter
<tristan.sloughter@REDACTED> wrote:
> With a few refactorings (https://github.com/tsloughter/sudoku-in-erlang --
> note I used ewl_plists just to make the code simpler:
> https://github.com/erlware/erlware/tree/master/lib/ewlib) and compile with
> native, hipe o3 it beats python's:
> $ ./sudoku.py
> All tests pass.
> Solved 50 of 50 puzzles from easy50.txt in 0.529119 secs (94.50 Hz)
>   (33059 total eliminations, avg 661.00, median 648, max 830, min 648).
> Solved 95 of 95 puzzles from top95.txt in 3.889944 secs (24.42 Hz)
>   (221997 total eliminations, avg 2336.00, median 1492, max 11512, min 648).
> Solved 11 of 11 puzzles from hardest.txt in 0.157520 secs (69.83 Hz)
>   (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).
> $ ./sudoku
> All tests passed :-)
> Solved 50 of 50 puzzles from easy50.txt in 0.556385 secs (89.87 Hz)
>   (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
> Solved 95 of 95 puzzles from top95.txt in 3.593476 secs (26.44 Hz)
>   (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
> 1792).
> Solved 11 of 11 puzzles from hardest.txt in 0.162107 secs (67.86 Hz)
>   (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
> I ran a number of times, those are pretty much what it always comes out to.
> But I haven't really tried a full refactoring, I think a number of things
> can be reduced to less iterations.
>
> Tristan
> On Sat, Mar 26, 2011 at 3:39 PM, Ahmed Omar <spawn.think@REDACTED> wrote:
>>
>> 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
>>
>>
>>
>> --
>> Best Regards,
>> - Ahmed Omar
>> http://nl.linkedin.com/in/adiaa
>> Follow me on twitter
>> @spawn_think
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
>

More information about the erlang-questions mailing list