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

Ahmed Omar spawn.think@REDACTED
Mon Mar 28 16:39:36 CEST 2011 

Hi Andreas,
For some reason, lists:usort is your friend again!
Looking into the code deeper, one line can give u huge boost!
You compare the unit values with digits with
  (length(UnitValues) == 9)
    and (gb_sets:from_list(UnitValues) == gb_sets:from_list(digits())).

I understand (correct me if i'm wrong) u check first the length to make sure
it's 9 digits then u convert to sets to make sure they r unique and compare
them. But if you think about it, if the unique list of values is of length
9, u don't need more comparisons!

so u can actually just do
(length(lists:usort(UnitValues)==9)

before the change:
sudoku:print_results("top95.txt").
Solved 95 of 95 puzzles from top95.txt in 1.937175 secs (49.04 Hz)
  (210794 total eliminations, avg 2218.88, median 1536, max 10664, min 648).

after the change :
sudoku:print_results("top95.txt").
Solved 95 of 95 puzzles from top95.txt in 0.382337 secs (248.47 Hz)
  (45002 total eliminations, avg 473.71, median 479, max 518, min 427).


On Mon, Mar 28, 2011 at 3:32 PM, Andreas Pauley <apauley@REDACTED> wrote:

> 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
> >>
> >
> >
>



-- 
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/20110328/5f5c598d/attachment.htm>

More information about the erlang-questions mailing list