How to make this faster

[Oscar Benjamin]

On 5 July 2013 09:22, Helmut Jarausch <jarausch at igpm.rwth-aachen.de> wrote:
> Hi,
>
> I have coded a simple algorithm to solve a Sudoku (probably not the first one).
> Unfortunately, it takes 13 seconds for a difficult problem which is more than 75 times slower
> than the same algorithm coded in C++.
> Is this to be expected or could I have made my Python version faster *** without *** sacrificing readability.

It is to be expected that this kind of processing is faster in C than
in straight Python. Where Python can win in these kind of problems is
if it makes it easier to implement a better algorithm but if your code
is just a transliteration from C to Python you should expect it to run
slower. Another way that Python can win is if you can express your
problem in terms of optimised operations from e.g. the numpy library
but you're not doing that here.

Of course that does depend on your Python implementation so you could
try e.g. using PyPy/nuitka/cython etc. to speed up the core
processing.

> Profiling shows that the function find_good_cell is called (only) 45267 times and this take 12.9 seconds
> CPU time (on a 3.2 GHz machine)
[snip]
>
> def find_good_cell() :
>   Best= None
>   minPoss= 10
>   for r in range(9) :
>     for c in range(9) :
>       if  Grid[r,c] > 0 : continue
>       Sq_No= (r//3)*3+c//3
>       Possibilities= 0
>       for d in range(1,10) :
>         if Row_Digits[r,d] or Col_Digits[c,d] or Sqr_Digits[Sq_No,d] : continue
>         Possibilities+= 1
>
>       if ( Possibilities < minPoss ) :
>         minPoss= Possibilities
>         Best= (r,c)
>
>   if minPoss == 0 : Best=(-1,-1)
>   return Best

My one comment is that you're not really making the most out of numpy
arrays. Numpy's ndarrays are efficient when each line of Python code
is triggering a large number of numerical computations performed over
the array. Because of their N-dimensional nature and the fact that
they are in some sense second class citizens in CPython they are often
not as good as lists for this kind of looping and indexing.

I would actually expect this program to run faster with ordinary
Python lists and lists of lists. It means that you need to change e.g.
Grid[r, c] to Grid[r][c] but really I think that the indexing syntax
is all you're getting out of numpy here.


Oscar