[erlang-questions 4] A sudoku solver in Erlang compared to Python

classic Classic list List threaded Threaded
39 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[erlang-questions 4] A sudoku solver in Erlang compared to Python

Andreas Pauley
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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Evans, Matthew
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: [hidden email] [mailto:[hidden email]] On Behalf Of Andreas Pauley
Sent: Friday, March 25, 2011 8:15 AM
To: [hidden email]
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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Andreas Pauley
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 <[hidden email]> 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: [hidden email] [mailto:[hidden email]] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ahmed Omar
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 <[hidden email]> 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 <[hidden email]> 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: [hidden email] [mailto:[hidden email]] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Evans, Matthew
In reply to this post by Andreas Pauley
Cool...

Might also want to look at what happens if all the other Erlang modules (esp. lists, sets and dict for your app) are made native:

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}
>  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).
ok

Dict/lists/sets native too:
5>  sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.996860 secs (95.30 Hz)
(922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
ok

Over a 2x boost in performance with zero re-factoring of your original code....maybe I'll put a question to the group out there. Seems that they should be shouting this sort of improvement from the roof-tops...

Matt

________________________________________
From: Andreas Pauley [[hidden email]]
Sent: Saturday, March 26, 2011 4:41 AM
To: Evans, Matthew
Cc: [hidden email]
Subject: Re: [erlang-questions 4] A sudoku solver in Erlang compared to Python

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 <[hidden email]> 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: [hidden email] [mailto:[hidden email]] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Evans, Matthew
In reply to this post by Ahmed Omar
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 [[hidden email]]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; [hidden email]
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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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: [hidden email]<mailto:[hidden email]> [mailto:[hidden email]<mailto:[hidden email]>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]<mailto:[hidden email]>
> 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
> [hidden email]<mailto:[hidden email]>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]<mailto:[hidden email]>
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>

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Kenny Stone
Are you solving the puzzles in parallel?  It might be revealing to see the implementation differences  in python and erlang for solving a lot of puzzles when the code parallelized.  The erlang code won't change much.

On Sat, Mar 26, 2011 at 3:14 PM, Evans, Matthew <[hidden email]> 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 [[hidden email]]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; [hidden email]
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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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: [hidden email]<mailto:[hidden email]> [mailto:[hidden email]<mailto:[hidden email]>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]<mailto:[hidden email]>
> 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
> [hidden email]<mailto:[hidden email]>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]<mailto:[hidden email]>
@spawn_think<http://twitter.com/#!/spawn_think>

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ahmed Omar
In reply to this post by Evans, Matthew
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 <[hidden email]> 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 [[hidden email]]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; [hidden email]
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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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: [hidden email]<mailto:[hidden email]> [mailto:[hidden email]<mailto:[hidden email]>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]<mailto:[hidden email]>
> 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
> [hidden email]<mailto:[hidden email]>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]<mailto:[hidden email]>
@spawn_think<http://twitter.com/#!/spawn_think>




--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ahmed Omar
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 <[hidden email]> 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 <[hidden email]> 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 [[hidden email]]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; [hidden email]
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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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: [hidden email]<mailto:[hidden email]> [mailto:[hidden email]<mailto:[hidden email]>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]<mailto:[hidden email]>
> 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
> [hidden email]<mailto:[hidden email]>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]<mailto:[hidden email]>
@spawn_think<http://twitter.com/#!/spawn_think>




--
Best Regards,
- Ahmed Omar
Follow me on twitter




--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Tristan Sloughter
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 [[hidden email]]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; [hidden email]
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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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: [hidden email]<mailto:[hidden email]> [mailto:[hidden email]<mailto:[hidden email]>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]<mailto:[hidden email]>
> 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
> [hidden email]<mailto:[hidden email]>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]<mailto:[hidden email]>
@spawn_think<http://twitter.com/#!/spawn_think>




--
Best Regards,
- Ahmed Omar
Follow me on twitter




--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Evans, Matthew
In reply to this post by Ahmed Omar
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 [[hidden email]]
Sent: Saturday, March 26, 2011 4:39 PM
To: Evans, Matthew
Cc: Andreas Pauley; [hidden email]
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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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 [[hidden email]<mailto:[hidden email]>]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; [hidden email]<mailto:[hidden email]>
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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>> [mailto:[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
> 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
> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Olivier Girondel
Surely totally unrelated, but the words "erlang" and "sudoku" always make
me remember of

http://www.erlang-solutions.com/section/47/2006-competition#FirstPrizeB

:)

--
Olivier
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ulf Wiger (AL/EAB)

On 27 Mar 2011, at 04:26, Olivier Girondel wrote:

> http://www.erlang-solutions.com/section/47/2006-competition#FirstPrizeB

?or this one:

http://www.erlang-solutions.com/section/48/2005-competition#SecondPrize

Surely the most beautiful Erlang program ever written!

BR,
Ulf W

Ulf Wiger, CTO, Erlang Solutions, Ltd.
http://erlang-solutions.com



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20110327/0610cdf0/attachment.html>

Reply | Threaded
Open this post in threaded view
|

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

Kresten Krab Thorup (Trifork)
In reply to this post by Evans, Matthew
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 [[hidden email]]
> Sent: Saturday, March 26, 2011 4:39 PM
> To: Evans, Matthew
> Cc: Andreas Pauley; [hidden email]
> 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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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 [[hidden email]<mailto:[hidden email]>]
> Sent: Saturday, March 26, 2011 3:08 PM
> To: Andreas Pauley
> Cc: Evans, Matthew; [hidden email]<mailto:[hidden email]>
> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>> [mailto:[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>] On Behalf Of Andreas Pauley
>> Sent: Friday, March 25, 2011 8:15 AM
>> To: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> 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
>> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Evans, Matthew

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@scream ~]$ ./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@scream ~]$ ./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@scream ~]$


The initial implementation in Erlang:

[mevans@scream ~]$ ./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 [[hidden email]]
Sent: Sunday, March 27, 2011 9:28 AM
To: Evans, Matthew
Cc: Ahmed Omar; [hidden email]; 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 [[hidden email]]
> Sent: Saturday, March 26, 2011 4:39 PM
> To: Evans, Matthew
> Cc: Andreas Pauley; [hidden email]
> 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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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 [[hidden email]<mailto:[hidden email]>]
> Sent: Saturday, March 26, 2011 3:08 PM
> To: Andreas Pauley
> Cc: Evans, Matthew; [hidden email]<mailto:[hidden email]>
> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>> [mailto:[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>] On Behalf Of Andreas Pauley
>> Sent: Friday, March 25, 2011 8:15 AM
>> To: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> 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
>> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ahmed Omar
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 <[hidden email]> 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@scream ~]$ ./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@scream ~]$ ./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@scream ~]$


The initial implementation in Erlang:

[mevans@scream ~]$ ./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 [[hidden email]]
Sent: Sunday, March 27, 2011 9:28 AM
To: Evans, Matthew
Cc: Ahmed Omar; [hidden email]; 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 [[hidden email]]
> Sent: Saturday, March 26, 2011 4:39 PM
> To: Evans, Matthew
> Cc: Andreas Pauley; [hidden email]
> 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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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 [[hidden email]<mailto:[hidden email]>]
> Sent: Saturday, March 26, 2011 3:08 PM
> To: Andreas Pauley
> Cc: Evans, Matthew; [hidden email]<mailto:[hidden email]>
> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>> [mailto:[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>] On Behalf Of Andreas Pauley
>> Sent: Friday, March 25, 2011 8:15 AM
>> To: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> 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
>> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions




--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ahmed Omar
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 <[hidden email]> 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 <[hidden email]> 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@scream ~]$ ./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@scream ~]$ ./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@scream ~]$


The initial implementation in Erlang:

[mevans@scream ~]$ ./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 [[hidden email]]
Sent: Sunday, March 27, 2011 9:28 AM
To: Evans, Matthew
Cc: Ahmed Omar; [hidden email]; 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 [[hidden email]]
> Sent: Saturday, March 26, 2011 4:39 PM
> To: Evans, Matthew
> Cc: Andreas Pauley; [hidden email]
> 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 <[hidden email]<mailto:[hidden email]>> 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 <[hidden email]<mailto:[hidden email]>> 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 [[hidden email]<mailto:[hidden email]>]
> Sent: Saturday, March 26, 2011 3:08 PM
> To: Andreas Pauley
> Cc: Evans, Matthew; [hidden email]<mailto:[hidden email]>
> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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 <[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>> 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: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>> [mailto:[hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>] On Behalf Of Andreas Pauley
>> Sent: Friday, March 25, 2011 8:15 AM
>> To: [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> 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
>> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]<mailto:[hidden email]><mailto:[hidden email]<mailto:[hidden email]>>
> 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
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions




--
Best Regards,
- Ahmed Omar
Follow me on twitter




--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Andreas Pauley
In reply to this post by Ahmed Omar
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
>> 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: [hidden email]
>> > [mailto:[hidden email]] On Behalf Of Andreas Pauley
>> > Sent: Friday, March 25, 2011 8:15 AM
>> > To: [hidden email]
>> > 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
>> > [hidden email]
>> > http://erlang.org/mailman/listinfo/erlang-questions
>> >
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> http://erlang.org/mailman/listinfo/erlang-questions
>
>
>
> --
> Best Regards,
> - Ahmed Omar
> http://nl.linkedin.com/in/adiaa
> Follow me on twitter
> @spawn_think
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

[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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
>> 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: [hidden email]
>> > [mailto:[hidden email]] On Behalf Of Andreas Pauley
>> > Sent: Friday, March 25, 2011 8:15 AM
>> > To: [hidden email]
>> > 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
>> > [hidden email]
>> > http://erlang.org/mailman/listinfo/erlang-questions
>> >
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> 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
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

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

Ahmed Omar
running test after fixing the counter gives the following 
Solved 95 of 95 puzzles from top95.txt in 2.235227 secs (42.50 Hz)
(210794 total eliminations, avg 2218.88, median 1536, max 10664, min 648).


On Sun, Mar 27, 2011 at 11:21 PM, Ahmed Omar <[hidden email]> wrote:
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]>
>> 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: [hidden email]
>> > [mailto:[hidden email]] On Behalf Of Andreas Pauley
>> > Sent: Friday, March 25, 2011 8:15 AM
>> > To: [hidden email]
>> > 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
>> > [hidden email]
>> > http://erlang.org/mailman/listinfo/erlang-questions
>> >
>> _______________________________________________
>> erlang-questions mailing list
>> [hidden email]
>> 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
Follow me on twitter




--
Best Regards,
- Ahmed Omar
Follow me on twitter


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
12