CODEWITHSUNDEEP
pythonpython-3.xalgorithmperformance
Aayush Lakhotia
Aayush Lakhotia

Reputation: 13

Improve performance on divisor finding function

I have made a function that finds all divisors that runs decently fast but for what I am trying to do I want it to run faster. I have also already created a primeFactors function. What I am doing is finding all possible powers that can be made and multiplying them.

from functools import reduce
from itertools import product

def divisors(n):
    x = sorted(primeFactors(n))
    r = []
    for values in set(x):
        t = list(range(0, x.count(values) + 1))
        r.append(t)
    comb = list(product(*r))
    divisors = []
    for sets in comb:
        n = [a**b for a, b in zip(set(x), sets)]
        divisors.append(reduce(lambda x, y: x*y, n))
    return sorted(divisors)

Is there another approach that is faster or any improvements that can be made to this code to make it faster? For the sake of the problem lets assume my primeFactors is the fastest in the world.

Upvotes: 0

Views: 114

Answers (2)

Stefan Pochmann
Stefan Pochmann

Reputation: 28636

Almost three times as fast as @kaya3's solutions and about 13 times as fast as your original (on kaya3's example number 3333960000):

def divisors(n):
    divisors = [1]
    for p in primeFactors(n):
        if divisors[-1] % p:
            divs = divisors
        divs = [d * p for d in divs]
        divisors += divs
    return sorted(divisors)

For example if the prime factors are [2, 2, 2, 3, 3], then you can multiply the initial 1 with the prime factor 2 up to three times, giving you the divisors [1, 2, 4, 8]. All of which you can then multiply with prime factor 3 up to two times. Multiplying with it once gives you [3, 6, 12, 24] and multiplying with it twice you [9, 18, 36, 72]. These additional divisor lists are my divs. At each new prime factor, I set divs to the divisors producible by the previous prime factors, and then keep multiplying it with the current prime factor and adding to the overall result.

This needs equal prime factors to appear consecutively, which is highly likely (once the factorization finds a prime factor, it likely extracts it completely so that the remaining factorization is faster). If that's not the case, just use sorted(primeFactors(n)).

Benchmark results (times in seconds for 10,000 calls with n=3333960000):

 0.22 primeFactors
95.43 divisors_aayush
15.28 divisors_kaya3_1
17.91 divisors_kaya3_2
 5.40 divisors_stefan

 0.21 primeFactors
89.29 divisors_aayush
17.91 divisors_kaya3_1
18.79 divisors_kaya3_2
 6.81 divisors_stefan

 0.20 primeFactors
94.21 divisors_aayush
21.28 divisors_kaya3_1
22.48 divisors_kaya3_2
 7.36 divisors_stefan

Btw, just in case the result doesn't really have to be sorted: Without sorting the result it takes about 2.4 seconds. So that sorting is responsible for most of the time.

Upvotes: 1

kaya3
kaya3

Reputation: 51122

There are quite a lot of ways to make small efficiency gains in your function:

  • There is no need to sort the list of prime factors. This doesn't have any effect on your algorithm.
  • You are converting the list of factors to a set many times, including within a loop; just do it once.
  • You are using .count to count each factor separately; the .count method loops over the list each time it's called. You can count occurrences of all factors in one pass using a Counter.
  • List comprehensions are usually a tiny bit faster than calling append in a loop.
  • The range objects and the product generator don't need to be converted to lists.
  • You are computing a**b many times for each b in the range for the factor a; you could take the product over a list of a**b instead of just the range for b.
  • Using reduce with operator.mul is faster than with a lambda.
  • The .sort method should be a little bit faster than sorted.

Some of these improvements involve removing or changing enough of the code that the other improvements are moot. Here's the resulting code:

from functools import reduce
from itertools import product
from collections import Counter
from operator import mul

def divisors2(n):
    factors = primeFactors(n)
    r = [
        [ a ** b for b in range(t + 1) ]
        for a, t in Counter(factors).items()
    ]
    d = [ reduce(mul, sets) for sets in product(*r) ]
    d.sort()
    return d

Overall this gives a modest to large improvement in running time, depending on the number of divisors:

  • For 1234567891 which is a prime number, the time saved is about 1%.
  • For 1234567890 == 2 * 3 * 3 * 5 * 3607 * 3803 the time saved is about 10%.
  • For 3333960000 == 2**6 * 3**5 * 5**4 * 7**3 the time saved is about 75%.

To do a bit better, we can save multiplying the same numbers over and over in the reduce stage by redesigning the implementation to use a recursive function instead of itertools.product: this allows us to do fewer multiplications overall.

def divisors3(n):
    factors = primeFactors(n)
    factor_counts = list(Counter(factors).items())

    def helper(x, i):
        if i < 0:
            d.append(x)
        else:
            a, t = factor_counts[i]
            for b in range(t + 1):
                helper(x, i - 1)
                x *= a

    d = []
    helper(1, len(factor_counts) - 1)
    d.sort()
    return d

This improves the time saved from 75% to 80% for the number with many prime factors. The difference for the other test cases is too small to matter.

I compared all three functions using the following fairly basic primeFactors implementation (from this post):

def primeFactors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

Upvotes: 2

Related Questions