[Tutor] List comprehension question

[Richard D. Moores]

On Tue, Nov 9, 2010 at 05:51, Martin A. Brown <martin at linux-ip.net> wrote:
>
> Hello,
>
>  : def proper_divisors_sum(n):
>  :     pd_list = []
>  :     for x in range(1, int(n**.5)+1):
>  :         if n % x == 0:
>  :             factor = int(x)
>  :             pd_list.append(factor)
>  :             factor2 = int(n/factor)
>  :             pd_list.append(factor2)
>  :     pd_list = list(set(pd_list))
>  :     pd_list.sort()
>  :     pd_list = pd_list[:-1]
>  :     return sum(pd_list)
>
> A few questions--noting, of course, that I'm not reading this with
> an eye toward performance, which it seems you are, but these occur
> to me:
>
>  * Why use a list (pd_list = []), when you want unique divisors?
>    Why not, pd = set() ?  Then, instead of pd_list.append(factor),
>    pd.add(factor) or something like pd.update((factor,factor2))?
>    (See also my suggestion below.)
>
>  * Also, since you are throwing away the divisor n, anyway,
>    why not skip it from the beginning?  Like this:
>
>      pd_list = [1,]
>      for x in range(2, int(n**.5)+1):
>
>  * So, I'm not terribly math aware, but I don't think I have
>    substantially changed the meaning of your program.  I find
>    breaking out the functions makes things a bit clearer to
>    somebody who might be reading my code later.
>
> Combining these suggestions and splitting into separate functions
> (you don't really need to sort before summing), I end up with the
> below.  Note, that I stuff the proper divisor 1 in the set at
> creation time.  This is probably not worth it from an optimization
> perspective, but as I have learned, the only way to know is to time
> it (and I didn't time it).
>
>      def proper_divisors_sum(n):
>          return sum(proper_divisors(n))
>
>      def proper_divisors_sorted(n):
>          return sorted(proper_divisors(n))
>
>      def proper_divisors(n):
>          pd = set((1,))
>          for x in range(2, int(n**.5)+1):
>              factor, mod = divmod(n,x)
>              if mod == 0:
>                  pd.update((x,factor))
>          return list(pd)

Thanks for your ideas, Martin. I adopted your idea of starting at 2,
with an initial list of [1].  It resulted in a small increase in
speed. And you're right, I don't need to sort.

Speed is important, because the function is the heart of my amiable
numbers script. Did you happen to see that post of mine?

#Here's my fastest version before seeing Martin's post:
def proper_divisors_sum1(n):
    pd_list = []
    for x in range(1, int(n**.5)+1):
        if n % x == 0:
            pd_list.append(x)
            pd_list.append(n//x)
    pd_list = list(set(pd_list))
    pd_list.sort()
    pd_list = pd_list[:-1]
    return sum(pd_list)

#This uses several of Martin's ideas
# It's now my fastest version
def proper_divisors_sum2(n):
    pd = set((1,))
    for x in range(2, int(n**.5)+1):
        if n % x == 0:
            pd.update((x, n//x))
    return sum(list(pd))

Here's what I put together from all your points, except for the
splitting off of several small functions:

# This incorporates all of Martin's ideas
# Seems that divmod() is a speed killer
def proper_divisors_sum3(n):
    pd = set((1,))
    for x in range(2, int(n**.5)+1):
        factor, mod = divmod(n,x)
        if mod == 0:
            pd.update((x,factor))
    return sum(list(pd))

It may be that I've haven't done your suggestions justice, but that
function is 76% slower than proper_divisors_sum2().

See <http://tutoree7.pastebin.com/R82876Eg> for a speed test with n =
100,000 and 100,000 loops

Thanks again, Martin.

Dick