"Finding number of factors" efficiency

Question

I have two functions to find the number of factors of a given number. I was wondering which one will be more efficient to use?

def nu_of_factors2(n):    
    return len(set(reduce(list.__add__, 
            ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

---

def nu_of_factors1(n):
    result_set = set()
    sqrtn = int(n**0.5)
    for i in range(1,sqrtn+1):
        q, r = n/i, n%i
            if r == 0:
            result_set.add(q)
            result_set.add(i)
    return len(result_set)

Answer 1

Both algorithms appear to be O(sqrt(n)), so there isn't anything to choose between them in terms of algorithmic complexity. The only significant difference I see is between a one-off conversion from list to set and a series of calls to add(). I would guess that the former will be quicker (i.e. your first implementation will be quicker), but this is definitely in the realm of things you should benchmark rather than attempting to guess. It depends on the particular implementation of the data structure in Python, and it may even depend on factors like the order in which you insert the elements (though I believe Python implements sets using a hash table rather than a binary tree, which should mean order of insertion doesn't matter).

A bigger question is whether you should be using a set at all. Your algorithm doesn't require a set to ensure uniqueness of factors. When you return the collection from the function the code that uses it might convert it straight to a list, in which case you've wastefully converted it to a set and back again. If you do the minimum of conversions necessary to get a result, then you avoid overhead and the caller can always convert it to a set if they need that.

On the other hand, returning a set clarifies the API by imposing two additional requirements on the returned value: it is a collection for which ordering is unimportant, and it has only unique elements. The second of these is certainly appropriate here. There is a natural ordering of the factors (namely numerical ordering), but it would take extra effort to arrange the results in this order. It might be cleaner to return a set (for which the caller can't rely on any ordering) than an order that exposes the internal implementation to the caller.

Speaking of ordering, the naive way to return a sorted list of factors would be to sort the list at the end, which is of course O(n*log(n)). A better way might be to invert the order in which you process the range and use a deque as the output collection. Then each time you discover a factor pair you can put the large factor on one end and the small factor on the other, returning a sorted list with O(1) insertion overhead.

Returning to your original question: I assume this is code you're writing as an exercise rather than as production code? The right thing to do depends a lot on where the code is to be used, and you don't give any context. If you're trying to build your skills at optimisation then by all means micro-optimise and return the collection in a list to save set overhead. If you're writing high-performance library code then maybe you need to pay more attention to the API. If this is for a production system where it's not time-critical, you should stop trying to optimise for speed and go for whichever solution will be easiest to maintain, which is probably the one that's easiest to read.

Answer 2

Both functions implement essentially the same algorithm. Therefore, their algorithmic complexity should be the same. The only difference would be in the details. The best way to answer your question is to examine concrete evidence.

Before we proceed, I'd like to point out a few issues with nu_of_factors1():

def nu_of_factors1(n):
    result_set = set()
    sqrtn = int(n**0.5)          # Misnomer - it's a rounded-down square root
    for i in range(1,sqrtn+1):
        q, r = n/i, n%i          # If r != 0, then q is wasted
                                 # Should use // (integer division) instead
        if r == 0:               # Fixed indentation
            result_set.add(q)
            result_set.add(i)
    return len(result_set)

Addressing those issues…

def nu_of_factors1b(n):
    result_set = set()
    for i in range(1, 1+int(n**0.5)):
        if n % i == 0:
            result_set.add(n // i)
            result_set.add(i)
    return len(result_set)

---

One analysis method would be to inspect the Python bytecode. I won't reproduce the results here, except to say that nu_of_factors2 produces bytecode that is about half the length of nu_of_factors1.

import dis
dis.dis(nu_of_factors1)      # Longest bytecode
dis.dis(nu_of_factors1b)     # Slightly shorter
dis.dis(nu_of_factors2)      # Much shorter

---

How does that translate to real-world performance? The only way to find out is to run it! Using the time command in Unix…

$ time python -c 'from cr32686 import *; print nu_of_factors1(28937489274598123)'
4

real        0m35.412s
user        0m33.358s
sys         0m2.052s
$ time python -c 'from cr32686 import *; print nu_of_factors1b(28937489274598123)'
4

real        0m17.277s
user        0m15.276s
sys         0m1.999s
$ time python -c 'from cr32686 import *; print nu_of_factors2(28937489274598123)'
4

real        0m18.552s
user        0m16.492s
sys         0m2.057s

As you can see, the difference between the two approaches is dwarfed by the inefficiency caused by one implementation detail: the fact that nu_of_factors1() performs many superfluous divisions and discards the results when the remainder is non-zero.

Of course, you can also perform the benchmarking using Python itself.