LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 11-20-2011, 09:58 PM   #1
ColInvictus
Member
 
Registered: Apr 2009
Posts: 42

Rep: Reputation: 15
Python: equivalent programs with different runtimes


I'm have two programs which calculate the sum of all numbers which are expressible as the sum of two abundant numbers. They are (1):
Code:
from mytools import factors

ab = []
for n in range(12, 28124):
    if sum(factors(n)[:-1])>n:
        ab.append(n)

nums = []
for n in range(len(ab)):
    for m in range(n, len(ab)):
        v = ab[n]+ab[m]
        if v > 28123: break
        nums.append(v)

print sum(range(28124))-sum(list(set(nums)))
and (2):
Code:
from mytools import factors

def ab(lim):
    nums = []
    for n in range(12, lim+1):
        if sum(factors(n)[:-1])>n:
            nums.append(n)
    return nums

def nm(lst):
    nums = []
    for n in range(len(lst)):
        for m in range(n, len(lst)):
            v = lst[n]+lst[m]
            if v > 28123: break
            nums.append(v)
    return nums

abundants = ab(28123)
nums = nm(abundants)

print sum(range(28124))-sum(list(set(nums)))
They are basically equivalent, except that the loops are enclosed in functions in (2). (2) runs in <10 seconds, whereas (1) takes almost a minute. Can anyone tell me why this is?
 
Old 11-21-2011, 12:00 AM   #2
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
Hi.
It's strange -- on my machine both scripts take about 0.350s and return 395465626. To compute factors I use code from here:
Code:
"""
  Generator for getting factors for a number
"""
def factor(n):
  yield 1
  i = 2
  limit = n**0.5
  while i <= limit:
    if n % i == 0:
      yield i
      n = n / i
      limit = n**0.5
    else:
      i += 1
  if n > 1:
    yield n

def factors(n):
	return [i for i in factor(n)]
      
if __name__ == "__main__":
  import sys
  for index in xrange(1,len(sys.argv)):
    print "Factors for %s : %s" %(sys.argv[index], [i for i in factor(int(sys.argv[index]))])
How do you compute factors?
 
Old 11-22-2011, 04:39 PM   #3
ColInvictus
Member
 
Registered: Apr 2009
Posts: 42

Original Poster
Rep: Reputation: 15
Behold, my factors function!
Code:
def factors(n):
    """Returns an ordered list of factors of n"""
    sqrtn = sqrt(n)
    facts = not sqrtn%1 and [int(sqrtn)] or []
    for i in range(int(ceil(sqrtn))-1, 0, -1):
        if n%i == 0:
            facts = [i] + facts + [n/i]
    return facts
Anyhoo, it turns out that the problem is with the Spyder IDE; running the scripts from the command line results in much more similar timings. The first one still takes a couple of seconds longer for reasons I don't quite understand, but at least it's not several times as long.

Time for a new IDE I guess...
 
Old 12-01-2011, 01:44 PM   #4
ColInvictus
Member
 
Registered: Apr 2009
Posts: 42

Original Poster
Rep: Reputation: 15
In case anyone's interested, it was the variable explorer in Spyder trying yo keep track of large lists as the code was running. The developer has fixed the problem in the next release, apparently.
 
Old 12-01-2011, 02:04 PM   #5
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
Hi.
Glad to hear you found the root of all evil.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Python equivalent of -Wall. j_voorhees Programming 2 11-25-2010 03:01 PM
How do I make python programs run without entering the command python? trist007 Programming 5 03-22-2009 08:21 PM
Python equivalent to bash's $* wapcaplet Programming 2 10-30-2005 12:30 AM
Are these programs - or equivalent programs - available for Linux? voly Linux - Software 12 07-29-2005 02:44 AM
What is the Python equivalent of #include? vharishankar Programming 2 07-21-2005 05:24 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:32 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration