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

Groups > comp.lang.python > #49992

Re: How to make this faster

Show all headers | View raw

On Fri, 05 Jul 2013 15:45:25 +0100, Oscar Benjamin wrote:

> 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.
> 
> It just takes practice. 

indeed

> 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

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

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

Thanks,
Helmut

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