Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.049 X-Spam-Evidence: '*H*': 0.90; '*S*': 0.00; 'algorithm': 0.04; 'assign': 0.07; 'variables': 0.07; 'subject:How': 0.10; 'cc:addr :python-list': 0.11; 'python': 0.11; 'def': 0.12; '(below)': 0.16; 'c++.': 0.16; 'globals': 0.16; 'numpy': 0.16; 'subject:make': 0.16; 'wrote:': 0.18; '<': 0.19; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; '>': 0.26; 'header:In-Reply-To:1': 0.27; 'function': 0.29; 'array': 0.29; 'message-id:@mail.gmail.com': 0.30; '(on': 0.31; '3.2': 0.31; 'coded': 0.31; 'could': 0.34; 'problem': 0.35; 'knows': 0.35; 'received:google.com': 0.35; 'version': 0.36; 'accessing': 0.36; 'shows': 0.36; 'hi,': 0.36; 'should': 0.36; 'seconds': 0.37; 'performance': 0.37; 'expected': 0.38; 'short': 0.38; 'called': 0.40; 'skip:u 10': 0.60; 'solve': 0.60; 'simple': 0.61; 'first': 0.61; 'times': 0.62; 'more': 0.64; 'jul': 0.74; 'subject:this': 0.83; '(only)': 0.84; '(probably': 0.84; 'one).': 0.84; 'sacrificing': 0.84; '***': 0.95; '2013': 0.98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=fyWpRN7qm75vvgcxmPQpVbok1Vyz3ML+vwjWU8LFPHs=; b=zSQ+yXY+S6wYEqoHxOEaUakYlMappkh5ZShktOJuGwYN591jpr9ixAcRNHs6GEbsXO 80FG3a7tsCJWl0C+Lc7aGgtRqF20dY8M+lEdzVcBiDtssZzjQy8R6v6ngUy9n8MguObb vKT5bQUPWbPix/0+8+qfHX4kX1F8rl7zmJ6UiH4reO4qe0yaNZYk6e7CfbAAe8kjDaXc M/AHr308JHhRX/WivVjhOSeN9no5gk2rdp04UMOVlr10BrWi2Jo91hFSl2xSwwIa7ibc Zq5AyLxSp8850sZ+2o1F4LQMT6Q59KYq1cyUkybWaSPqADhc1rddM3hvrhL8wkl9XFa4 SxaA== MIME-Version: 1.0 X-Received: by 10.224.26.7 with SMTP id b7mr8600352qac.102.1373017115325; Fri, 05 Jul 2013 02:38:35 -0700 (PDT) In-Reply-To: References: Date: Fri, 5 Jul 2013 10:38:35 +0100 Subject: Re: How to make this faster From: =?ISO-8859-1?Q?F=E1bio_Santos?= To: Helmut Jarausch Content-Type: multipart/alternative; boundary=047d7bdc8ce66dfa4a04e0c075c9 Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 104 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1373017118 news.xs4all.nl 15906 [2001:888:2000:d::a6]:33765 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:49958 --047d7bdc8ce66dfa4a04e0c075c9 Content-Type: text/plain; charset=ISO-8859-1 On 5 Jul 2013 09:29, "Helmut Jarausch" 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. --047d7bdc8ce66dfa4a04e0c075c9 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable


On 5 Jul 2013 09:29, "Helmut Jarausch" <jarausch@igpm.rwth-aachen.de> wrote:
>
> Hi,
>
> I have coded a simple algorithm to solve a Sudoku (probably not the fi= rst one).
> Unfortunately, it takes 13 seconds for a difficult problem which is mo= re 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) 4526= 7 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.

> =A0 Best=3D None
> =A0 minPoss=3D 10
> =A0 for r in range(9) :
> =A0 =A0 for c in range(9) :
> =A0 =A0 =A0 if =A0Grid[r,c] > 0 : continue
> =A0 =A0 =A0 Sq_No=3D (r//3)*3+c//3
> =A0 =A0 =A0 Possibilities=3D 0
> =A0 =A0 =A0 for d in range(1,10) :

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

> =A0 =A0 =A0 =A0 if Row_Digits[r,d] or Col_Digits[c,d] o= r Sqr_Digits[Sq_No,d] : continue
> =A0 =A0 =A0 =A0 Possibilities+=3D 1
>
> =A0 =A0 =A0 if ( Possibilities < minPoss ) :
> =A0 =A0 =A0 =A0 minPoss=3D Possibilities
> =A0 =A0 =A0 =A0 Best=3D (r,c)
>
> =A0 if minPoss =3D=3D 0 : Best=3D(-1,-1)
> =A0 return Best

Well I think that is as far as I go with my knowledge. Someo= ne who knows numpy arrays' performance traits should be able to help yo= u more.

--047d7bdc8ce66dfa4a04e0c075c9--