On 5 July 2013 15:28, Helmut Jarausch <jarau...@igpm.rwth-aachen.de> wrote: > On Fri, 05 Jul 2013 14:41:23 +0100, Oscar Benjamin wrote: > >> On 5 July 2013 11:53, Helmut Jarausch <jarau...@igpm.rwth-aachen.de> wrote: >>> I even tried to use dictionaries instead of Numpy arrays. This version is a >>> bit >>> slower then the lists of lists version (7.2 seconds instead of 6 second) >>> but still >>> much faster than the Numpy array solution. >> >> When you switched to dictionaries did you take advantage of the >> sparseness by iterating over dictionary keys instead of indices? This >> is the kind of thing that I meant when I said that in Python it's >> often easier to implement a better algorithm than in C. What I mean is >> that if Grid is a dict so that Grid[(r, c)] is the entry at row r and >> column c (if it exists) then you can change a loop like: >> >> for r in range(9): >> for c in range(9): >> if Grid[r, c] > 0: continue >> # do stuff >> >> so that it looks like: >> >> for r, c in Grid: >> # do stuff >> >> If the grid is sparsely occupied then this could be a significant >> improvement. >> > This gives a big speedup. Now, the time is gone down to 1.73 seconds in > comparison to > original 13 seconds or the 7 seconds for the first version above.
Presumably then you're now down to the innermost loop as a bottle-neck: 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 you make it so that e.g. Row_Digits[r] is a set of indices rather than a list of bools then you can do this with something like Possibilities = len(Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No]) or perhaps Possibilities = len(set.union(Row_Digits[r], Col_Digits[c], Sqr_Digits[Sq_No])) which I would expect to be a little faster than looping over range since the loop is then performed under the hood by the builtin set-type. > Many thanks, > it seems hard to optimize a Python program, It just takes practice. It's a little less obvious in Python than in low-level languages where the bottlenecks will be and which operations are faster/slower but optimisation always involves a certain amount of trial and error anyway. Oscar -- http://mail.python.org/mailman/listinfo/python-list