Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <b3o3gkFtc39U1@mid.dfncis.de>
References: <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de> <b3o3gkFtc39U1@mid.dfncis.de>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Fri, 5 Jul 2013 15:45:25 +0100
Subject: Re: How to make this faster
To: Helmut Jarausch <jarausch@igpm.rwth-aachen.de>
Content-Type: text/plain; charset=ISO-8859-1
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.4299.1373035554.3114.python-list@python.org>
Lines: 61
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:49989

On 5 July 2013 15:28, Helmut Jarausch <jarausch@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 <jarausch@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