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

[Ahmed Omar]

No problem, as said before u can also replace these lines :

PeerSet = gb_sets:from_list(NonUniquePeers),
PeersWithSelf = gb_sets:to_list(PeerSet),
lists:delete(Square, PeersWithSelf).

with just

lists:delete(Square, lists:usort(NonUniquePeers)).

(don't forget to check the rest of the thread too ;))

On Sun, Mar 27, 2011 at 11:02 PM, Andreas Pauley <apauley@REDACTED> wrote:

> Thanks!
> I didn't think about the sets at all :-)
>
>
> https://github.com/apauley/sudoku-in-erlang/commit/a02fbcd001a9fbd876725008d58c52fcff9872d9
>
> On Sat, Mar 26, 2011 at 9:08 PM, Ahmed Omar <spawn.think@REDACTED> wrote:
> > 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>
> 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>
> >> 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] On Behalf Of Andreas
> Pauley
> >> > Sent: Friday, March 25, 2011 8:15 AM
> >> > To: 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
> >> > http://erlang.org/mailman/listinfo/erlang-questions
> >> >
> >> _______________________________________________
> >> 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/20110327/b4efbbad/attachment.htm>