How to make this faster

[Fábio Santos]

On 5 Jul 2013 09:29, "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.
> 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)

[Skipping to bottleneck]

> def find_good_cell() :

In this function you are accessing global variables a lot of times. Since
accessing globals takes much more time than accessing locals, I advise you
to assign them to local names, and use them.

>   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) :

On this condition (below) you can try to check which condition is True more
often and put that condition first in order to take advantage of short
circuiting and minimize array access.

>         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

Well I think that is as far as I go with my knowledge. Someone who knows
numpy arrays' performance traits should be able to help you more.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130705/1b5a3b89/attachment.html>