Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #87940 > unrolled thread

Sudoku solver

Back to article view | Back to comp.lang.python

Contents

  Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-25 13:39 +0200
    Re: Sudoku solver John Ladasky <john_ladasky@sbcglobal.net> - 2015-03-25 11:44 -0700
      Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 13:05 -0600
      Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-25 21:37 +0200
        Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 14:09 -0600
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-25 22:31 +0200
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-26 09:40 +1100
            Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 18:07 -0600
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-27 20:04 +0000
            Re: Sudoku solver Abhiram R <abhi.darkness@gmail.com> - 2015-03-26 08:26 +0530
            Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-25 21:24 -0600
            Re: Sudoku solver Abhiram R <abhi.darkness@gmail.com> - 2015-03-26 08:58 +0530
              Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 14:13 +0200
                Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 16:15 +0200
            Re: Sudoku solver albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 23:10 +0000
        Re: Sudoku solver Sayth <flebber.crue@gmail.com> - 2015-03-27 20:39 -0700
          Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-28 23:50 +0000
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-29 11:12 +1100
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 21:59 +0100
                Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-29 22:19 +0100
                  Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 22:59 +0100
            Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-29 14:06 +1100
              Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-29 15:10 +1100
                Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-29 21:35 +1100
                  Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-29 21:54 +1100
                  Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 13:01 +0100
                    Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 16:23 +0100
              Re: Sudoku solver Christian Gollwitzer <auriocus@gmx.de> - 2015-03-29 09:57 +0200
                Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-30 11:54 +0100
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 12:25 +0100
                Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-29 21:03 +0300
                  Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-29 19:26 +0100
                    Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-29 21:33 +0300
                  Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 22:11 +0100
                  Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-30 00:50 -0600
                    Re: Sudoku solver Christian Gollwitzer <auriocus@gmx.de> - 2015-03-30 09:13 +0200
                      Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-30 01:29 -0600
                        Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-30 12:16 +0300
                      Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-30 04:16 -0400
                      Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-30 02:57 -0600
                      Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-30 20:13 +1100
            Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-29 22:21 +0100
              Re: Sudoku solver BartC <bc@freeuk.com> - 2015-03-29 23:17 +0100
                Re: Sudoku solver Seymore4Head <Seymore4Head@Hotmail.invalid> - 2015-03-29 21:40 -0400
    Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-26 09:50 +1100
      Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-25 23:04 +0000
        Re: Sudoku solver Christian Gollwitzer <auriocus@gmx.de> - 2015-03-27 07:40 +0100
    Re: Sudoku solver "Frank Millman" <frank@chagford.com> - 2015-03-26 10:19 +0200
      Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 14:26 +0200
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-26 23:37 +1100
        Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-26 07:15 -0600
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 16:23 +0200
            Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-26 09:06 -0600
              Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 17:48 +0200
                Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-26 10:20 -0600
                  Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 18:47 +0200
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-26 10:14 -0400
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-27 01:41 +1100
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-26 11:03 -0400
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-26 17:42 +0200
            Re: Sudoku solver Pete Forman <petef4+usenet@gmail.com> - 2015-03-26 22:24 +0000
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-27 02:21 +1100
        Re: Sudoku solver Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-03-26 20:42 -0400
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 09:14 -0400
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 00:25 +1100
        Re: Sudoku solver "Frank Millman" <frank@chagford.com> - 2015-03-27 15:35 +0200
          Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-27 15:56 +0200
            Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 10:09 -0400
              Re: Sudoku solver sohcahtoa82@gmail.com - 2015-03-27 11:18 -0700
                Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-28 12:46 +1100
              Re: Sudoku solver Larry Hudson <orgnut@yahoo.com> - 2015-03-27 16:48 -0700
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 01:07 +1100
            Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 01:19 +1100
              Re: Sudoku solver Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-03-28 14:13 +1300
              Re: Sudoku solver Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-28 12:40 +1100
                Re: Sudoku solver Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-28 02:24 -0600
            Re: Sudoku solver Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-03-27 16:03 +0000
            Re: Sudoku solver Virgil Stokes <vs@it.uu.se> - 2015-03-28 19:36 +0100
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 09:48 -0400
        Re: Sudoku solver Dave Angel <davea@davea.name> - 2015-03-27 09:52 -0400
        Re: Sudoku solver Chris Angelico <rosuav@gmail.com> - 2015-03-28 00:58 +1100
    Re: Sudoku solver mr.smittye@gmail.com - 2015-03-29 16:39 -0700
      Re: Sudoku solver Marko Rauhamaa <marko@pacujo.net> - 2015-03-30 12:24 +0300

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#88287

On 29/03/2015 22:19, Mark Lawrence wrote:
> On 29/03/2015 21:59, BartC wrote:
>> On 29/03/2015 00:12, Chris Angelico wrote:
>>> On Sun, Mar 29, 2015 at 10:50 AM, BartC <bc@freeuk.com> wrote:
>>>> Using the OP's algorithm, and testing with the 'hard' puzzle posted
>>>> by Ian
>>>> Kelly, I got these approximate results:
>>>>
>>>> Python 3.1:     1700 seconds     (normal Python interpreter)
>>>> PyPy:           93 seconds
>>>> C unoptimised:  17 seconds       (gcc -O0 32-bit)
>>>> C optimised:    3.3 seconds      (gcc -O3 32-bit)
>>>> (X:             170 seconds)
>>>
>>> Nice stats. Any chance you can add CPython 3.4 or 3.5 to that? That's
>>> a pretty old CPython you're using.
>>
>> I've tried 3.4.3 and it's nearer 1900 seconds!
>>
>> Which wasn't too surprising as you don't expect new releases to be
>> faster, they tend to be slower.

> I simply do not believe those figures, that's roughly 12% slower.  If
> that happened in the real world you'd be able to hear the screams of
> anguish around the world.

You're right, it's wasn't 12% slower. It was 16%!

I didn't have time to run this very long benchmark so ran a different 
algorithm using 3.1, averaging 14.1 seconds for 3 runs. And ran the same 
code with 3.4.3, average 16.4 seconds.

Maybe most people don't run intensively computational benchmarks like these.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#88242

On Sun, 29 Mar 2015 10:50 am, BartC wrote:


> (X is my own interpreted language, which is where my interest in this
> is. This had been generally faster than Python until PyPy came along. It
> does however use a pure byte-code interpreter, so the result is not too
> bad.
> 
> But using X *and* my own brute-force algorithm, the same puzzle took 2
> seconds to solve - faster than C!


I'm not one of those people who think that C is by definition the fastest
language conceivable. (People who believe this sometimes make an exception
for hand-crafted assembly, which is ironic since these days the best C
optimizing compilers can generate faster, tighter code than human assembly
programmers.) I know that program speed depends on the implementation of
the language, not necessarily the language itself. I know that Fortran can
beat C for numeric work, and that with a tiny fraction of the work put into
optimization that C has seen, modern languages like Scala, Eiffel, Haskell
and D can get to a factor of 2-6 times as slow as C. And I know that PyPy
has managed to beat C in some (quite restrictive, but not completely
unrealistic) benchmarks:

http://morepypy.blogspot.com.au/2011/02/pypy-faster-than-c-on-carefully-crafted.html
http://morepypy.blogspot.com.au/2011/08/pypy-is-faster-than-c-again-string.html


So beating C is not impossible.

But, when you tell me that your very own personal interpreted language,
which I assume nobody else has worked on, is 40% faster than optimized C,
my first reaction is to expect that you've probably made a mistake
somewhere. I would have the same reaction if somebody casually dropped into
a conversation that they happened to beat Usain Bolt's 100m personal best
of 9.58 seconds by almost four seconds. While carrying a 20kg backpack.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#88244

On Sun, Mar 29, 2015 at 2:06 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Sun, 29 Mar 2015 10:50 am, BartC wrote:
>
>> (X is my own interpreted language, which is where my interest in this
>> is. This had been generally faster than Python until PyPy came along. It
>> does however use a pure byte-code interpreter, so the result is not too
>> bad.
>>
>> But using X *and* my own brute-force algorithm, the same puzzle took 2
>> seconds to solve - faster than C!
>
> But, when you tell me that your very own personal interpreted language,
> which I assume nobody else has worked on, is 40% faster than optimized C,
> my first reaction is to expect that you've probably made a mistake
> somewhere. I would have the same reaction if somebody casually dropped into
> a conversation that they happened to beat Usain Bolt's 100m personal best
> of 9.58 seconds by almost four seconds. While carrying a 20kg backpack.

I think you're misreading the stats. The first table compares
languages, all using the same algorithm, and in that, C beat X ten to
one, unoptimized. The second figure, when X took only 2 seconds, was
demonstrating the massive improvement that the algorithmic change
(from "the OP's algorithm" to "[BartC's] own brute-force algorithm")
achieved. For comparison, that's like casually dropping into
conversation that you happened to drive a car faster than Usain Bolt's
personal best. :)

ChrisA

[toc] | [prev] | [next] | [standalone]

#88256

On Sun, 29 Mar 2015 03:10 pm, Chris Angelico wrote:

> On Sun, Mar 29, 2015 at 2:06 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> On Sun, 29 Mar 2015 10:50 am, BartC wrote:
>>
>>> (X is my own interpreted language, which is where my interest in this
>>> is. This had been generally faster than Python until PyPy came along. It
>>> does however use a pure byte-code interpreter, so the result is not too
>>> bad.
>>>
>>> But using X *and* my own brute-force algorithm, the same puzzle took 2
>>> seconds to solve - faster than C!
>>
>> But, when you tell me that your very own personal interpreted language,
>> which I assume nobody else has worked on, is 40% faster than optimized C,
>> my first reaction is to expect that you've probably made a mistake
>> somewhere. I would have the same reaction if somebody casually dropped
>> into a conversation that they happened to beat Usain Bolt's 100m personal
>> best of 9.58 seconds by almost four seconds. While carrying a 20kg
>> backpack.
> 
> I think you're misreading the stats. The first table compares
> languages, all using the same algorithm, and in that, C beat X ten to
> one, unoptimized. The second figure, when X took only 2 seconds, was
> demonstrating the massive improvement that the algorithmic change
> (from "the OP's algorithm" to "[BartC's] own brute-force algorithm")
> achieved. For comparison, that's like casually dropping into
> conversation that you happened to drive a car faster than Usain Bolt's
> personal best. :)

Swapping from a clever algorithm to a brute force algorithm is not what I
would describe as swapping from running to driving a car. I would describe
it as swapping from running down the street to running through quicksand
while carrying a grand piano. I don't what sort of algorithm you think is
going to be *slower* than brute force.

Wait, I have one... randomly generate a grid of numbers. Is it a valid
sudoko that matches the clues given? If so, we're done, if not, generate
another random grid. Brute force will beat that.

That's why I can't help but feel that, *given the description we've seen*,
perhaps Bart's brute force code doesn't actually solve the problem, and
that's why it is so fast. I'm reminded of the recent thread where somebody
claimed to have a significant speed-up over Timsort by using a binary
search instead of linear search. Tim Peters investigated, and noticed that
the code wasn't actually sorting. It's easy to beat the performance of any
sort algorithm if you don't actually sort...

Anyway, we don't really know where the confusion lies. Perhaps the
description is misleading, or I'm just confused, or Bart's idea of brute
force is not the same as my idea of brute force, or perhaps he really is a
super-genius who has casually relegated C to the dust bin of historic
languages...


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#88258

On Sun, Mar 29, 2015 at 9:35 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Anyway, we don't really know where the confusion lies. Perhaps the
> description is misleading, or I'm just confused, or Bart's idea of brute
> force is not the same as my idea of brute force, or perhaps he really is a
> super-genius who has casually relegated C to the dust bin of historic
> languages...

Ah, I see what you mean.

I tend to describe an algorithm as "brute force" even if it has a few
simplifications and early cut-offs. A brute-force primality test, for
instance, might divide the target number by every counting number
since 1, looking for a remainder; does it cease to be brute-force if
you check only 2 and odd numbers? only those up to its square root?
Either of those tiny optimizations will give a dramatic speed
improvement, without representing a flaw; and I would still consider
them brute force. The purest form is a barbarian trying to lift a
gate; the slightly-optimized is a wizard trying to lift the same gate;
but neither algorithm is using a Knock spell to open it by magic. And
if you've seen "The Gamers", you'll know that brute force is as fickle
as a roll of the dice.....

Point is, "brute force" isn't a pure absolute from which there can be
no variation.

ChrisA

[toc] | [prev] | [next] | [standalone]

#88266

On 29/03/2015 11:35, Steven D'Aprano wrote:

> That's why I can't help but feel that, *given the description we've seen*,
> perhaps Bart's brute force code doesn't actually solve the problem, and
> that's why it is so fast. I'm reminded of the recent thread where somebody
> claimed to have a significant speed-up over Timsort by using a binary
> search instead of linear search. Tim Peters investigated, and noticed that
> the code wasn't actually sorting. It's easy to beat the performance of any
> sort algorithm if you don't actually sort...
>
> Anyway, we don't really know where the confusion lies. Perhaps the
> description is misleading, or I'm just confused, or Bart's idea of brute
> force is not the same as my idea of brute force, or perhaps he really is a
> super-genius who has casually relegated C to the dust bin of historic
> languages...

My solver definitely works, as the solutions produced by the two 
algorithms are identical.

I'm not clever enough to produce a properly analytical solver, but 
perhaps it is not quite as brute force as the Python one.

I've looked at my code and I don't really understand it (it's from a 
long time ago), and it would take quite a while to convert it to Python 
and post it. (Most of it seems to be preoccupied with multiple ways of 
indexing the board or grid.)

(If it's of any interest, this non-Python code is here:

http://pastebin.com/5cXd2Pef )

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#88270

On 29/03/2015 13:01, BartC wrote:
> On 29/03/2015 11:35, Steven D'Aprano wrote:

>> Anyway, we don't really know where the confusion lies. Perhaps the
>> description is misleading, or I'm just confused, or Bart's idea of brute
>> force is not the same as my idea of brute force, or perhaps he really
>> is a
>> super-genius who has casually relegated C to the dust bin of historic
>> languages...
>
> My solver definitely works, as the solutions produced by the two
> algorithms are identical.
>
> I'm not clever enough to produce a properly analytical solver, but
> perhaps it is not quite as brute force as the Python one.
>
> I've looked at my code and I don't really understand it (it's from a
> long time ago), and it would take quite a while to convert it to Python
> and post it. (Most of it seems to be preoccupied with multiple ways of
> indexing the board or grid.)
>
> (If it's of any interest, this non-Python code is here:
>
> http://pastebin.com/5cXd2Pef )

I've managed to create a Python version of my 'brute force' sudoku solver:

http://pastebin.com/CKmHmBKm

It was hard going as I don't normally write Python. But it worked 
practically first time, after building it bottom-up and then putting the 
solvepuzzle() routine in place.

The data for the 'hard' puzzle is hard-coded into it, so you just run it.

Python 3.1 (normal CPython) took 13 or 14 seconds to solve (previously 
1700 seconds with the OP's code).

PyPy took 1.3 seconds (previously 93 seconds). (Annoyingly, faster than 
the 1.7 seconds of my language...)

(The original code in my language that I posted has been simplified - 
which also made it faster, and the Python code was based on that 
version. The Pastebin code has been updated.)

I won't bother to test a C version of this, as it's a bit more awkward 
to translate (making use of strings and deep copies of arrays).

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#88248

Am 29.03.15 um 05:06 schrieb Steven D'Aprano:
> I'm not one of those people who think that C is by definition the fastest
> language conceivable. (People who believe this sometimes make an exception
> for hand-crafted assembly, which is ironic since these days the best C
> optimizing compilers can generate faster, tighter code than human assembly
> programmers.) I know that program speed depends on the implementation of
> the language, not necessarily the language itself. I know that Fortran can
> beat C for numeric work, and that with a tiny fraction of the work put into
> optimization that C has seen, modern languages like Scala, Eiffel, Haskell
> and D can get to a factor of 2-6 times as slow as C. And I know that PyPy
> has managed to beat C in some (quite restrictive, but not completely
> unrealistic) benchmarks:
>
> http://morepypy.blogspot.com.au/2011/02/pypy-faster-than-c-on-carefully-crafted.html
> http://morepypy.blogspot.com.au/2011/08/pypy-is-faster-than-c-again-string.html
>
>
> So beating C is not impossible.

Beating C is not impossible, but it is really hard. The compilation is 
usually excluded from such benchmarks. Then any langugage could in 
principle compile to the same instructions as the equivalent C program, 
and hence achieve the same speed. The reason that C is such a tough 
competitor is
	
1) the tools have been optimized over 40 years - just compare the 
sourcecode of gcc with a minimalistic compiler such as tcc, and then 
compare the execution speed of the programs compiled by it

2) the langugage is very easy to compile, since the programmer is forced 
to annotate the sourcecode with data types that usually map 1:1 into 
registers

If you can do type deduction for your variables that lead to the same 
result as the C program, then you can also compile to the same efficient 
code. In most cases the hand-crafted C program is more restricted, 
because the programmer does not make a promise to the compiler that 
things will never overflow (e.g., int is restricted to 32 bits instead 
of arbitrary integers).

Defeating a C compiler is possible in (rare) cases, I wouldn't really 
count the examples you've posted, since they don't actually compute 
anything useful. However, for instance the Intel C compiler is able to 
replace a loop like this:

for (int i=0; i<N; i++) {
	for (int j=0; j<N; j++) {
		for (int k=0; k<N; k++) {
			z[i][k]+=x[i][j]*y[j][k];
		}
	}
}

with a call to an optimized BLAS matrix multiplication in "some" 
(=impractical) cases. This can easily speed up the code by a factor of 
100. It would be much easier for a compiled numpy-language to do this 
for z=x*y and also correctly treat slices etc. Still practical compilers 
that do that and achieve *on average* faster programs than hand-crafted 
C do not exist.

Just look at the contrived PyPy benchmarks, for a very tuned selected 
sample you can be almost twice as fast as C - for a random algorithm 
like the Sudoku solver, not specifically tuned, C is 30x faster. It 
still boils down to the classic rules: static unboxed types and static 
or preallocated memory makes your code fast. In many cases, though, 
programming in Python can free programmer time, which can lead in turn 
to better algorithms that outperform the wisdom of the C compiler.

>
> But, when you tell me that your very own personal interpreted language,
> which I assume nobody else has worked on, is 40% faster than optimized C,
> my first reaction is to expect that you've probably made a mistake

I agree with Chris that this was a misunderstanding.


	Christian

[toc] | [prev] | [next] | [standalone]

#88332

On 29/03/2015 08:57, Christian Gollwitzer wrote:
> Am 29.03.15 um 05:06 schrieb Steven D'Aprano:

[OT: Competing with compiled C code]

>> I'm not one of those people who think that C is by definition the fastest
>> language conceivable. (People who believe this sometimes make an
>> exception
>> for hand-crafted assembly, which is ironic since these days the best C
>> optimizing compilers can generate faster, tighter code than human
>> assembly
>> programmers.)


> Defeating a C compiler is possible in (rare) cases, I wouldn't really
> count the examples you've posted, since they don't actually compute
> anything useful. However, for instance the Intel C compiler is able to
> replace a loop like this:
>
> for (int i=0; i<N; i++) {
>      for (int j=0; j<N; j++) {
>          for (int k=0; k<N; k++) {
>              z[i][k]+=x[i][j]*y[j][k];
>          }
>      }
> }
>
> with a call to an optimized BLAS matrix multiplication in "some"
> (=impractical) cases.

I have an interpreter for my language which has an implementation in C, 
and one in my own static language. That latter can also optionally make 
use of a byte-code dispatcher written in assembly (which tries to deal 
with each byte-code if it can, if not it passes it on to high-level code).

This combination of HLL+ASM can be up to double the speed of the 
C/gcc/O3 version (and which has to use gcc extensions), when executing 
benchmarks. On real programs, it can still be up to 40-50% faster (ie. 
the C version takes 40-50% longer to execute).

(My own static language by itself is 30% slower than C/gcc/O3 at the 
minute, when used for the interpreter, but I'm working on it... For 
small, tight benchmarks though it is still totally outclassed by gcc.)

> Just look at the contrived PyPy benchmarks, for a very tuned selected
> sample you can be almost twice as fast as C - for a random algorithm
> like the Sudoku solver, not specifically tuned, C is 30x faster. It
> still boils down to the classic rules: static unboxed types and static
> or preallocated memory makes your code fast. In many cases, though,
> programming in Python can free programmer time, which can lead in turn
> to better algorithms that outperform the wisdom of the C compiler.

I'm quite impressed with PyPy. While its implementation seems (to me) 
fantastically complicated compared with the very simple concept of a 
byte-code interpreter, it seems to do the job. For simple integer 
benchmarks, it can be double the speed of my HLL+ASM interpreter running 
the same algorithm (but not in Python).

However I believe that CPython could be a bit faster than it is, even 
with all the dynamic stuff that is what's supposed to keep it slow.

(If Python wasn't so huge, and if I understood it a lot more than I do, 
I'd be tempted to have a go myself. For example, I could change the 
syntax of my interpreted language so that it looks like Python. Then I 
can take a simple benchmark in this 'Python', and run it with both 
CPython and my interpreter, and mine is likely to be faster. Yet, it 
still uses a byte-code dispatch loop, and it is still dynamically typed.

So what extra stuff is going on in CPython?)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#88260

On 29/03/2015 04:06, Steven D'Aprano wrote:
> On Sun, 29 Mar 2015 10:50 am, BartC wrote:

>> But using X *and* my own brute-force algorithm, the same puzzle took 2
>> seconds to solve - faster than C!

> But, when you tell me that your very own personal interpreted language,
> which I assume nobody else has worked on, is 40% faster than optimized C,
> my first reaction is to expect that you've probably made a mistake
> somewhere. I would have the same reaction if somebody casually dropped into
> a conversation that they happened to beat Usain Bolt's 100m personal best
> of 9.58 seconds by almost four seconds. While carrying a 20kg backpack.

As Chris mentioned, when I say 'faster than C', I mean X running my 
algorithm was faster then C running Marko's algoritim (on Ian's data). 
This was just an illustration of algorithm being more important than 
language.

(As it happens, C using gcc was particularly good at this benchmark. 
Looking only at optimised code, Clang took 4.5 seconds, while a trio of 
lesser C compilers took from 14 to 22 seconds.

This is why I also showed the unoptimised figure, which indicates what 
raw native code could do, without taking account of the 
super-optimisations that gcc is capable of applying.

Because after all such optimisations could also be applied to the Python 
code, such as unrolling those nested loops in good().

And theoretically, a clever enough C compiler could have solved it in 0 
seconds since I'd hard-coded the board values within the source!

See: http://pastebin.com/RZE67TLy )

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#88273

BartC <bc@freeuk.com>:

> As Chris mentioned, when I say 'faster than C', I mean X running my
> algorithm was faster then C running Marko's algoritim (on Ian's data).
> This was just an illustration of algorithm being more important than
> language.

Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:

    884   s
      2.5 s
     13   s
    499   s
      5.9 s
    128   s
   1360   s
     36   s

(That suggests a slight modification to the original strategy: solve it
in each of the eight ways "in parallel" and the worst case should be
significantly alleviated.)

I'm actually fascinated by the Python modifications that were
conceptually insignificant but dramatically speeded up the execution
(7880 seconds to 884 seconds). That's something I'll have to keep in
mind in the future.


Marko

[toc] | [prev] | [next] | [standalone]

#88274

On 29/03/2015 19:03, Marko Rauhamaa wrote:
> BartC <bc@freeuk.com>:
>
>> As Chris mentioned, when I say 'faster than C', I mean X running my
>> algorithm was faster then C running Marko's algoritim (on Ian's data).
>> This was just an illustration of algorithm being more important than
>> language.
>
> Be careful with the benchmark comparisons. Ian's example can be solved
> with the identical algorithm in eight different ways (four corners, left
> or right). I ran the example with my recent Python solver and got these
> times in the eight cases:
>
>      884   s
>        2.5 s
>       13   s
>      499   s
>        5.9 s
>      128   s
>     1360   s
>       36   s
>
> (That suggests a slight modification to the original strategy: solve it
> in each of the eight ways "in parallel" and the worst case should be
> significantly alleviated.)
>
> I'm actually fascinated by the Python modifications that were
> conceptually insignificant but dramatically speeded up the execution
> (7880 seconds to 884 seconds). That's something I'll have to keep in
> mind in the future.
>
>
> Marko
>

One thing I have come to rely on over the years is never, ever trust 
your gut instincts about Python performance, you're almost inevitably 
wrong.  When I first came across the Norvig solver I made a change, 
purely for fun, to replace two calls to len() with a single call and 
save the result.  The run time to solve each puzzle dropped by around 
5%.  I believe this meets your "conceptually insignificant".

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#88275

Mark Lawrence <breamoreboy@yahoo.co.uk>:

> One thing I have come to rely on over the years is never, ever trust
> your gut instincts about Python performance, you're almost inevitably
> wrong. When I first came across the Norvig solver I made a change,
> purely for fun, to replace two calls to len() with a single call and
> save the result. The run time to solve each puzzle dropped by around
> 5%. I believe this meets your "conceptually insignificant".

Yes. It's kinda sad when you have to resort to such low-brow
optimizations. Mostly you don't have to, though. You mainly want to keep
the expression elegant.


Marko

[toc] | [prev] | [next] | [standalone]

#88282

On 29/03/2015 19:03, Marko Rauhamaa wrote:
> BartC <bc@freeuk.com>:
>
>> As Chris mentioned, when I say 'faster than C', I mean X running my
>> algorithm was faster then C running Marko's algoritim (on Ian's data).
>> This was just an illustration of algorithm being more important than
>> language.
>
> Be careful with the benchmark comparisons. Ian's example can be solved
> with the identical algorithm in eight different ways (four corners, left
> or right). I ran the example with my recent Python solver and got these
> times in the eight cases:
>
>      884   s
>        2.5 s
>       13   s
>      499   s
>        5.9 s
>      128   s
>     1360   s
>       36   s
>
> (That suggests a slight modification to the original strategy: solve it
> in each of the eight ways "in parallel" and the worst case should be
> significantly alleviated.)

Well, in this case all the benchmarks ran the same algorithm on the same 
data, which makes them a better test of the implementations than of the 
algorithm.

I've mentioned a (possibly) significantly faster algorithm which I 
believe to be still brute-force (now in Python here: 
http://pastebin.com/CKmHmBKm).

But I realise it could just be luck in approaching the solution from a 
literally different angle and encountering the answer sooner. (I think 
both stop as soon as they find any valid solution.)

What I've done is try it on 3 rotations as well as the original (+90, 
+180, +270 degrees, but haven't bothered with flips and reflections).

While the original took 13 seconds (using my algorithm in Python), the 
rotations took 18, 49 and 87 seconds respectively.

Since the original time in PyPy took 90-odd seconds, I was about to 
acknowledge that mine might not be that much faster after all. Then I 
realised I was using Python 3.1 not PyPy! Python 3.1 took 28 minutes on 
original hard puzzle using your code, and 13-87 seconds with mine.

So I think this other algorithm is still much faster. I've no idea why, 
especially since it messes about concatenating strings and converting 
them to and from integers.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#88319

On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> BartC <bc@freeuk.com>:
>
>> As Chris mentioned, when I say 'faster than C', I mean X running my
>> algorithm was faster then C running Marko's algoritim (on Ian's data).
>> This was just an illustration of algorithm being more important than
>> language.
>
> Be careful with the benchmark comparisons. Ian's example can be solved
> with the identical algorithm in eight different ways (four corners, left
> or right). I ran the example with my recent Python solver and got these
> times in the eight cases:
>
>     884   s
>       2.5 s
>      13   s
>     499   s
>       5.9 s
>     128   s
>    1360   s
>      36   s

That sounds to me like either a transcription error was made to the
puzzle at some point, or there's something wrong with your solver. The
whole point of that example was that it was a puzzle with the minimum
number of clues to specify a unique solution.

I tried entering that puzzle into the solver at
http://www.sudoku-solutions.com/. It confirms that there is a unique
solution, and the solution it gives matches the one given in the
article as well as the solution that I got from Norvig's solver.

Also, Frank Millman successfully ran the Eppstein solver on it
upthread, which purportedly should complain if the puzzle does not
have a unique solution.

[toc] | [prev] | [next] | [standalone]

#88320

Am 30.03.15 um 08:50 schrieb Ian Kelly:
> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Be careful with the benchmark comparisons. Ian's example can be solved
>> with the identical algorithm in eight different ways (four corners, left
>> or right). I ran the example with my recent Python solver and got these
>> times in the eight cases:
>>
>>      884   s
>>        2.5 s
>>       13   s
>>      499   s
>>        5.9 s
>>      128   s
>>     1360   s
>>       36   s
>
> That sounds to me like either a transcription error was made to the
> puzzle at some point, or there's something wrong with your solver. The
> whole point of that example was that it was a puzzle with the minimum
> number of clues to specify a unique solution.

I think Marko meant, that if he creates symmetrically equivalent puzzles 
by rotating / mirroring the grid, he gets vastly different execution 
times, but ends up with the same solution. This is not surprising. The 
brute force algorithm branches into different solutions first, then, 
because it fills the grid always in the same order. To compare different 
solvers, it would indeed make sense to average over all symmetric 
solutions to make sure that no solver wins the competition by sheer 
luck, i.e. choosing the right path immediately.

	Christian

[toc] | [prev] | [next] | [standalone]

#88321

On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>
>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>>
>>> Be careful with the benchmark comparisons. Ian's example can be solved
>>> with the identical algorithm in eight different ways (four corners, left
>>> or right). I ran the example with my recent Python solver and got these
>>> times in the eight cases:
>>>
>>>      884   s
>>>        2.5 s
>>>       13   s
>>>      499   s
>>>        5.9 s
>>>      128   s
>>>     1360   s
>>>       36   s
>>
>>
>> That sounds to me like either a transcription error was made to the
>> puzzle at some point, or there's something wrong with your solver. The
>> whole point of that example was that it was a puzzle with the minimum
>> number of clues to specify a unique solution.
>
> I think Marko meant, that if he creates symmetrically equivalent puzzles by
> rotating / mirroring the grid, he gets vastly different execution times, but
> ends up with the same solution.

That makes sense, but it is true for all puzzles that there are eight
possible orientations (since it's impossible for a puzzle solution to
be symmetric), and the wording made it sound like he was describing a
property specific to the puzzle that I posted.

[toc] | [prev] | [next] | [standalone]

#88329

Ian Kelly <ian.g.kelly@gmail.com>:

> On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer <auriocus@gmx.de>
> wrote:
>> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>>
>>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko@pacujo.net>
>>> wrote:
>>>>
>>>> Be careful with the benchmark comparisons. Ian's example can be
>>>> solved with the identical algorithm in eight different ways (four
>>>> corners, left or right). I ran the example with my recent Python
>>>> solver and got these times in the eight cases:
>>>>
>>>>      884   s
>>>>        2.5 s
>>>>       13   s
>>>>      499   s
>>>>        5.9 s
>>>>      128   s
>>>>     1360   s
>>>>       36   s
>>>
>>>
>>> That sounds to me like either a transcription error was made to the
>>> puzzle at some point, or there's something wrong with your solver.
>>> The whole point of that example was that it was a puzzle with the
>>> minimum number of clues to specify a unique solution.
>>
>> I think Marko meant, that if he creates symmetrically equivalent
>> puzzles by rotating / mirroring the grid, he gets vastly different
>> execution times, but ends up with the same solution.
>
> That makes sense, but it is true for all puzzles that there are eight
> possible orientations (since it's impossible for a puzzle solution to
> be symmetric), and the wording made it sound like he was describing a
> property specific to the puzzle that I posted.

Thing is, if you are not careful in your comparisons, you might easily
get a good-looking time from one implementation and a lousy time from
another implementation because of a different traversal order.

That is why brute-force sudoku might not be as good for benchmark
testing as BertC was hoping.


Marko

[toc] | [prev] | [next] | [standalone]

#88323

On 03/30/2015 03:29 AM, Ian Kelly wrote:
> On Mon, Mar 30, 2015 at 1:13 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
>> Am 30.03.15 um 08:50 schrieb Ian Kelly:
>>>
>>> On Sun, Mar 29, 2015 at 12:03 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>>>
>>>> Be careful with the benchmark comparisons. Ian's example can be solved
>>>> with the identical algorithm in eight different ways (four corners, left
>>>> or right). I ran the example with my recent Python solver and got these
>>>> times in the eight cases:
>>>>
>>>>       884   s
>>>>         2.5 s
>>>>        13   s
>>>>       499   s
>>>>         5.9 s
>>>>       128   s
>>>>      1360   s
>>>>        36   s
>>>
>>>
>>> That sounds to me like either a transcription error was made to the
>>> puzzle at some point, or there's something wrong with your solver. The
>>> whole point of that example was that it was a puzzle with the minimum
>>> number of clues to specify a unique solution.
>>
>> I think Marko meant, that if he creates symmetrically equivalent puzzles by
>> rotating / mirroring the grid, he gets vastly different execution times, but
>> ends up with the same solution.
>
> That makes sense, but it is true for all puzzles that there are eight
> possible orientations (since it's impossible for a puzzle solution to
> be symmetric), and the wording made it sound like he was describing a
> property specific to the puzzle that I posted.
>

But for some puzzles, the 8 timings may be much closer.  Or maybe even 
further apart.

Incidentally, there are many other variants of the same puzzle that 
might matter, beyond those 8.

The digits can all be crypto'ed   Like replace all 4 with 8, etc. 
Probably won't matter for any realistic algorithm.

The columns can be reordered, in at least some ways.  For example, if 
the first and second columns are swapped, it's a new puzzle, equivalent. 
  Likewise certain rows.

The relationship between row, column and box can be rearranged.  Some of 
these are already covered by the rotations proposed earlier, where for a 
90 degree rotate, row becomes column and column becomes row.  But in a 
similar way each box could become a column, and so on.

All of these rearrangeements will change the order that an algorithm 
might choose to examine things, and thus affect timings (but not the 
solution).

When I made my own solver years ago, I considered the puzzle to have 9 
columns, 9 rows, and 9 boxes.  So these 27 lists of 9 could be analyzed. 
  I just came up with a fast way to map those 243 cells back and forth 
with the original 81.  At that point, it no longer mattered which things 
were rows and which were columns or boxes.


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#88327

On Mon, Mar 30, 2015 at 2:16 AM, Dave Angel <davea@davea.name> wrote:
> The relationship between row, column and box can be rearranged.  Some of
> these are already covered by the rotations proposed earlier, where for a 90
> degree rotate, row becomes column and column becomes row.  But in a similar
> way each box could become a column, and so on.

I don't think this one is valid. The intersection of a row and a
column is one cell. The intersection of a row and a box is three
cells. If you swap a column with a box, you're changing the
relationships between the squares and the result will not be
isomorphic to the original.

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.lang.python

csiph-web