Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <b3o6bkFtc39U4@mid.dfncis.de>
References: <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de> <b3o6bkFtc39U4@mid.dfncis.de>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Fri, 5 Jul 2013 16:38:43 +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.4302.1373038751.3114.python-list@python.org>
Lines: 85
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:49996

On 5 July 2013 16:17, Helmut Jarausch <jarausch@igpm.rwth-aachen.de> wrote:
>
> I've tried the following version
>
> def find_good_cell() :
>   Best= None
>   minPoss= 10
>   for r,c in Grid :
>     if  Grid[(r,c)] > 0 : continue

Sorry, I think what I meant was that you should have a structure
called e.g. Remaining which is the set of all (r, c) pairs that you
want to loop over here. Then there's no need to check on each
iteration whether or not Grid[(r, c)] > 0. When I said "sparse" I
meant that you don't need to set keys in Grid unless you actually have
a value there so the test "Grid[(r, c)] > 0" would look like "(r, c)
in Grid". Remaining is the set of all (r, c) pairs not in Grid that
you update incrementally with .add() and .remove().

Then this

   for r,c in Grid :
     if  Grid[(r,c)] > 0 : continue

becomes

    for r, c in Remaining:

>     Sq_No= (r//3)*3+c//3
>     Possibilities= 9-len(Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No])
>     if ( Possibilities < minPoss ) :
>       minPoss= Possibilities
>       Best= (r,c)
>
>   if minPoss == 0 : Best=(-1,-1)
>   return Best
>
> All_digits= set((1,2,3,4,5,6,7,8,9))

All_digits= set(range(1, 10))

or

All_digits = {1,2,3,4,5,6,7,8,9}

>
> def Solve(R_Cells) :
>   if  R_Cells == 0 :
>     print("\n\n++++++++++ S o l u t i o n ++++++++++\n")
>     Print_Grid()
>     return True
>
>   r,c= find_good_cell()
>   if r < 0 : return False
>   Sq_No= (r//3)*3+c//3
>
>   for d in All_digits - (Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No]) :
>     # put d into Grid
>     Grid[(r,c)]= d
>     Row_Digits[r].add(d)
>     Col_Digits[c].add(d)
>     Sqr_Digits[Sq_No].add(d)
>
>     Success= Solve(R_Cells-1)
>
>     # remove d again
>     Grid[(r,c)]= 0
>     Row_Digits[r].remove(d)
>     Col_Digits[c].remove(d)
>     Sqr_Digits[Sq_No].remove(d)
>
>     if Success :
>       Zuege.append((d,r,c))
>       return True
>
>   return False
>
> which turns out to be as fast as the previous "dictionary only version".
> Probably,  set.remove is a bit slow

No it's not and you're not using it in your innermost loops anyway.
Probably the loop I referred to isn't your bottleneck.


Oscar