Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #49958

Re: How to make this faster

References <b3ne2rFojnkU1@mid.dfncis.de>
Date 2013-07-05 10:38 +0100
Subject Re: How to make this faster
From Fábio Santos <fabiosantosart@gmail.com>
Newsgroups comp.lang.python
Message-ID <mailman.4287.1373017118.3114.python-list@python.org> (permalink)

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

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 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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 08:22 +0000
  Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 10:38 +0100
  Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:07 +0000
  Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 11:13 +0100
  Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:53 +0000
    Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 12:02 +0000
    Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 13:44 +0100
    Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 14:41 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:28 +0000
      Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 15:45 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:48 +0000
      Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:26 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:54 +0000
      Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 16:18 +0100
      Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:24 +0000
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:17 +0000
      Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:38 +0100
      Re: How to make this faster MRAB <python@mrabarnett.plus.com> - 2013-07-05 17:25 +0100
      Re: How to make this faster Joshua Landau <joshua.landau.ws@gmail.com> - 2013-07-06 02:45 +0100
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:47 +0000
      Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:52 +0000
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 16:07 +0000
      Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:50 +0000
        Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:39 +0000
          Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-06 03:05 +0000
          Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-06 07:25 +0000
    Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:42 +0000

csiph-web