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

Ahmed Omar spawn.think@REDACTED
Tue Mar 29 12:31:45 CEST 2011 

Yes u r correct :) sorry i missed that point, i didn't dig enough :)


On Tue, Mar 29, 2011 at 12:02 PM, Andreas Pauley <apauley@REDACTED> wrote:

> Unfortunately it's not that easy this time.
> The major reduction in eliminations happens because is_unit_solved/2
> always returns true after the proposed change.
> If you open any of the .out files (eg hardest.out) you'll see that the
> puzzles aren't really solved.
>
> Luckily the unit tests pointed this out.
>
> But all is not lost, I still got a simplification out of the deal.
> We still need to check the non-unique length of UnitValues in that
> function, but the second clause does not need to use sets anymore:
>
> https://github.com/apauley/sudoku-in-erlang/commit/f092e55df292d1f12ff8406ce60bb435e7a83667
>
>
> On Mon, Mar 28, 2011 at 4:39 PM, Ahmed Omar <spawn.think@REDACTED> wrote:
> > 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
> >
>



-- 
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/20110329/efdc9e9d/attachment.htm>

More information about the erlang-questions mailing list