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

Ahmed Omar spawn.think@REDACTED
Sun Mar 27 20:58:33 CEST 2011 

Sorry diff was inverted :)
-eliminate({Dict, Count}, [Square|T], Digit) ->
+eliminate(Puzzle, [Square|T], Digit) ->
     %% Eliminate the specified Digit from all specified Squares.
-    Puzzle = {Dict, Count+1},

 eliminate({ValuesDict, Eliminations}, Square, Digit, NewValues, _) ->
     NewDict = dict:store(Square, NewValues, ValuesDict),
-    NewPuzzle = peer_eliminate({NewDict, Eliminations}, Square, NewValues),
+    NewPuzzle = peer_eliminate({NewDict, Eliminations+1}, Square,
NewValues),


On Sun, Mar 27, 2011 at 8:56 PM, Ahmed Omar <spawn.think@REDACTED> wrote:

> Regarding the eliminations number, i believe you have a bug in counting
> them (correct me if i'm wrong. You shouldn't increment the counter until an
> actual elimination occurs.
>
> -eliminate(Puzzle, [Square|T], Digit) ->
> +eliminate({Dict, Count}, [Square|T], Digit) ->
>      %% Eliminate the specified Digit from all specified Squares.
> +    Puzzle = {Dict, Count+1},
>
>  eliminate({ValuesDict, Eliminations}, Square, Digit, NewValues, _) ->
>      NewDict = dict:store(Square, NewValues, ValuesDict),
> -    NewPuzzle = peer_eliminate({NewDict, Eliminations+1}, Square,
> NewValues),
> +    NewPuzzle = peer_eliminate({NewDict, Eliminations}, Square,
> NewValues),
>
>
>
> On Sun, Mar 27, 2011 at 5:49 PM, Evans, Matthew <mevans@REDACTED>wrote:
>
>>
>> Good call on using atoms instead of lists. I wouldn't have imagined it
>> would be that much faster. So on my computer the new Erlang implementation
>> is much faster than python:
>>
>> Erlang with parse transforms and HiPE:
>>
>> [mevans@REDACTED ~]$ ./sudoku
>> expanding...
>> expanding...
>> expanding...
>> expanding...
>> Solved 50 of 50 puzzles from easy50.txt in 0.059767 secs (836.58 Hz)
>> (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
>> Solved 95 of 95 puzzles from top95.txt in 0.344457 secs (275.80 Hz)
>> (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> Solved 11 of 11 puzzles from hardest.txt in 0.025747 secs (427.23 Hz)
>> (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
>>
>>
>> Python:
>>
>> [mevans@REDACTED ~]$ ./sudoku.py
>> All tests pass.
>> Solved 50 of 50 puzzles from easy50.txt in 0.530000 secs (94.34 Hz)
>>  (33059 total eliminations, avg 661.00, median 648, max 830, min 648).
>> Solved 95 of 95 puzzles from top95.txt in 3.980000 secs (23.87 Hz)
>>  (221997 total eliminations, avg 2336.00, median 1492, max 11512, min
>> 648).
>> Solved 11 of 11 puzzles from hardest.txt in 0.150000 secs (73.33 Hz)
>>  (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).
>> [mevans@REDACTED ~]$
>>
>>
>> The initial implementation in Erlang:
>>
>> [mevans@REDACTED ~]$ ./sudoku
>> ./sudoku:4: Warning: variable 'Args' is unused
>> Solved 50 of 50 puzzles from easy50.txt in 0.492551 secs (101.51 Hz)
>> (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
>> Solved 95 of 95 puzzles from top95.txt in 3.120420 secs (30.44 Hz)
>> (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> Solved 11 of 11 puzzles from hardest.txt in 0.147977 secs (74.34 Hz)
>> (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
>>
>> ________________________________________
>> From: Kresten Krab Thorup [krab@REDACTED]
>> Sent: Sunday, March 27, 2011 9:28 AM
>> To: Evans, Matthew
>> Cc: Ahmed Omar; erlang-questions@REDACTED; Andreas Pauley
>> Subject: Re: [erlang-questions 41] Re: A sudoku solver in Erlang compared
>> to Python
>>
>> For reference, I tried to run this with Erjang and R14B01 (with BEAN and
>> HiPE/o3) on my machine ...
>>
>> Oh, and I changed the square names to be atoms in stead of [X,Y] pairs,
>> which speeds up things quite a lot too ... e.g. :
>>
>> squares() ->
>>   %% Returns a list of 81 square names, including "A1" etc.
>>    [erlang:list_to_atom([X,Y]) || X <- "ABCDEFGHI", Y <- "123456789"].
>>
>>
>> BEAM
>> > sudoku_main:run_solver(["solve"]).
>> Solved 50 of 50 puzzles from easy50.txt in 0.678921 secs (73.65 Hz)
>>  (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
>> Solved 95 of 95 puzzles from top95.txt in 4.373277 secs (21.72 Hz)
>>  (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> Solved 11 of 11 puzzles from hardest.txt in 0.198780 secs (55.34 Hz)
>>  (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
>> ok
>>
>> Erjang
>> > sudoku_main:run_solver(["solve"]).
>> Solved 50 of 50 puzzles from easy50.txt in 0.653891 secs (76.47 Hz)
>>  (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
>> Solved 95 of 95 puzzles from top95.txt in 4.354102 secs (21.82 Hz)
>>  (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> Solved 11 of 11 puzzles from hardest.txt in 0.208266 secs (52.82 Hz)
>>  (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
>> ok
>>
>> r14b01 / HiPE / o3
>> > sudoku_main:run_solver(["solve"]).
>> Solved 50 of 50 puzzles from easy50.txt in 0.611918 secs (81.71 Hz)
>>  (92538 total eliminations, avg 1850.76, median 1811, max 2628, min 1767).
>> Solved 95 of 95 puzzles from top95.txt in 3.759281 secs (25.27 Hz)
>>  (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> Solved 11 of 11 puzzles from hardest.txt in 0.169039 secs (65.07 Hz)
>>  (33653 total eliminations, avg 3059.36, median 3023, max 5346, min 1786).
>> ok
>>
>> This version does not use pmap (Erjang's scheduler still needs some work),
>> but does use atoms for square names, and ct_expand.
>>
>> Cheers,
>>
>> Kresten
>>
>>
>> On Mar 26, 2011, at 23:33 , Evans, Matthew wrote:
>>
>> > Awesome point, I was going to actually suggest that since this is all
>> calculating static data he just pre-calculates it and puts it in a -define.
>> Or even better, if he is brave he could write a parse transform.
>> >
>> > Using Ulf's ct_expand module (
>> http://forum.trapexit.org/viewtopic.php?p=20260) I get even better
>> performance:
>> >
>> > Without the parse transform (but using native):
>> >
>> > 4> sudoku:print_results("top95.txt", "\n").
>> > Solved 95 of 95 puzzles from top95.txt in 0.827966 secs (114.74 Hz)
>> > (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> > ok
>> >
>> >
>> > With a parse transform:
>> >
>> > 2>  sudoku:print_results("top95.txt", "\n").
>> > Solved 95 of 95 puzzles from top95.txt in 0.469908 secs (202.17 Hz)
>> > (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> 1792).
>> >
>> >
>> > The code looks like:
>> >
>> > -compile({parse_transform, ct_expand}).
>> >
>> >
>> > squares() ->
>> >    %% Returns a list of 81 square names, including "A1" etc.
>> >    ct_expand:term(
>> >        [[X,Y] || X <- "ABCDEFGHI", Y <- "123456789"]
>> >    ).
>> > col_squares() ->
>> >    %% All the square names for each column.
>> >    ct_expand:term(
>> >        [[[X,Y] || X <- "ABCDEFGHI", Y <- [C]] || C <- "123456789"]
>> >      ).
>> > row_squares() ->
>> >    %% All the square names for each row.
>> >    ct_expand:term(
>> >        [[[X,Y] || X <- [R], Y <- "123456789"] || R <- "ABCDEFGHI"]
>> >    ).
>> > box_squares() ->
>> >    %% All the square names for each box.
>> >    ct_expand:term(
>> >        [[[X,Y] || X <- R, Y <- C] || R <- ["ABC", "DEF", "GHI"], C <-
>> ["123", "456", "789"]]
>> >    ).
>> >
>> >
>> > ________________________________________
>> > From: Ahmed Omar [spawn.think@REDACTED]
>> > Sent: Saturday, March 26, 2011 4:39 PM
>> > To: Evans, Matthew
>> > Cc: Andreas Pauley; erlang-questions@REDACTED
>> > Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang
>> compared to Python
>> >
>> > 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
>> <mailto: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
>> <mailto: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<mailto:spawn.think@REDACTED>]
>> > Sent: Saturday, March 26, 2011 3:08 PM
>> > To: Andreas Pauley
>> > Cc: Evans, Matthew; erlang-questions@REDACTED<mailto:
>> 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><mailto: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><mailto: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>> [mailto:
>> 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
>> ><mailto: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
>> ><mailto: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><mailto:
>> 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>
>> >
>> > _______________________________________________
>> > 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>
>
>


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

More information about the erlang-questions mailing list