On Tue, Nov 9, 2010 at 05:51, Martin A. Brown <mar...@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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
