On 5 July 2013 09:22, Helmut Jarausch <jarau...@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 -- http://mail.python.org/mailman/listinfo/python-list