Improve speed of for loop in python

Question

I am trying to calculate the number of partitions of numbers from 1 to 10^7. I am using the pentagonal number theorem to achieve that, which provides a way to calculate the number of partitions of n, let's call it P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + ... So P(n) depends on different P(n-x), where x goes from 1 to n. Anyway, long story short, I am using two loops, one that goes from 1 to 10^7 and the other one that uses the x's defined and calculate after a specific formula. As you can imagine, the code goes quite slow. Is there any way I can improve the speed of these for loops?

P.S. I have tried using numpy arrays, but I am not really comfortable with them and unfortunately it made the code even slower.

def build_list(new_limit, k):
   list_of_p_minus = list()
   while k < new_limit:
       list_of_p_minus.append(k*(2*k-1))
       list_of_p_minus.append(k*(2*k+1))
       k = k+1
   return list_of_p_minus


def counter(low, high):
   current = low
   while current <= high:
      yield current
      current += 1

def loop_through_numbers(limit, list_of_p_minus):
   p_dict = dict()
   p_dict[0] = 1
   p_dict[1] = 1
   aux = 2
   aux_index = 1
   for number in counter(2, limit+1):
      if aux == number:
         if aux_index % 4 == 1 or aux_index % 4 == 2:
            p_dict[number] = -1
         else:
            p_dict[number] = 1
         aux = aux + (aux_index + 1) * 2
         aux_index += 1
      else:
         p_dict[number] = 0
      for element in counter(0, len(list_of_p_minus)):
          if element % 4 == 0 or element % 4 == 1:
             try:
                p_dict[number] += p_dict[number-list_of_p_minus[element]]
             except KeyError:
                break
          else:
             try:
                p_dict[number] -= p_dict[number-list_of_p_minus[element]]
             except KeyError:
                break
return

As you can see, I tried implementing iterators and, while that made the code run faster, it still takes a significant amount of time. Any ideas would be more than welcome at this point...

why did you implement counter ? can't you use range for your loops? — Jean-François Fabre
– Jean-François Fabre ♦, Commented Nov 29, 2017 at 20:26
Well for starters, I'd replace all your while-loops with for-loops. And yea, as @Jean-FrançoisFabre said, stop re-inveting range. Fundamentally, though, I think the crux of your problem is going to be your algorithm — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Nov 29, 2017 at 20:31
@Jean-FrançoisFabre - I was trying to make use of generators. — Radu Iordache
– Radu Iordache, Commented Nov 29, 2017 at 20:32
@RaduIordache why? Generators tend to be slower, and certainly will be slower than a built-in function (which are implemented in C) — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Nov 29, 2017 at 20:32
@juanpa.arrivillaga - That is a good idea, however that is not where the program takes long. The while loop goes insanely fast compared to the eternity spent on the nested for loops. — Radu Iordache
– Radu Iordache, Commented Nov 29, 2017 at 20:33

blues · Accepted Answer · 2017-11-29 20:35:55Z

2

m = a % 4
if m == 1 or m == 2:

is faster than evaluating the mod twice. there is two places in your code where this can be improved but that will not increase speed by a lot. The problem is that there simply isn't much to be done except restructuring the whole thing. But than the question belongs to codereview.SE

Alternatively you can use C instead of python if you really want to shave of milliseconds with specific implementation details.

answered Nov 29, 2017 at 20:35

blues

5,2743 gold badges26 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jean-François Fabre Over a year ago

if a % 4 < 2: is probably even better.

Radu Iordache Over a year ago

I was afraid that restructuring might be necessary. Thank you for the feedback on the modulo.

Collectives™ on Stack Overflow

Improve speed of for loop in python

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related