3
\$\begingroup\$

I am trying to learn some basic Python and am trying to find tricks to write speedy code:

import sys
if len(sys.argv) < 3:
    print("You left out the arguments")
    sys.exit()
gcf = 0

numbers = []
collections = []
unique = False

for i in range(1,len(sys.argv)):
    numbers.append(int(sys.argv[i]))
for x in range(0,len(numbers)):
    collections.append([])  
    for s in range(1,numbers[x] + 1):
        if numbers[x] % s == 0:
            collections[x].append(s)
    print str(numbers[x]) + ": ",       
    print ','.join(map(str,collections[x]))
for i in collections[0]:
        for x in collections:
            if i in x:
                unique = True
            else:
                unique = False
        if unique:
            gcf = i
print "gcf is: "+str(gcf)                   
\$\endgroup\$
  • \$\begingroup\$ does this code work? I don't understand what yr trying to acheive here for i in collections[0]: for x in collections: if i in x: \$\endgroup\$ – user90823 Aug 6 '13 at 17:59
  • \$\begingroup\$ yes it works perfectly fine with python 2.7.3 \$\endgroup\$ – user2640586 Aug 6 '13 at 18:00
  • \$\begingroup\$ this will accept an infinite amount of arguments so i am comparing the factors of any random collection of factors (collections[0]) because the gcf has to be the greatest factor of all args given so any one will work for example if i have [1,3,5],[1,3,5,7],[1,3,5,7,9] i can use any one to compare to the other 2 and still get the right answer \$\endgroup\$ – user2640586 Aug 6 '13 at 18:05
  • \$\begingroup\$ thnx I was looking o see if you can get rid of the third for loop with s, but I can't figure it out,.. someone else will.. be good to see hey :) \$\endgroup\$ – user90823 Aug 6 '13 at 18:07
  • \$\begingroup\$ If you're only interested in finding the overall gcf/gcd, you should look at the function fractions.gcd and this gcd question on stackoverflow. If you also want to find the factors of the input numbers, check out this answer. And you can always come back and edit the code in this question when you've implemented some changes. :) \$\endgroup\$ – flornquake Aug 6 '13 at 20:33
1
\$\begingroup\$

You have written that you want to know tricks for writing speedy code. So I'll leave the algorithm as it is.

You should know that Python code runs faster in local scope than global scope. So putting all of it inside a function should be faster.

From your code it is clear that you don't know about List comprehension. It is faster than creating a list and then appending items to it. So thi

numbers = []
for i in range(1,len(sys.argv)):
    numbers.append(int(sys.argv[i]))

can be this

numbers = [int(sys.argv[i]) for i in range(1,len(sys.argv))]

and it would be faster and easier to read. Same goes for your collections list.

Do you need the unique for something else? I think no. So this

for i in collections[0]:
        for x in collections:
            if i in x:
                unique = True
            else:
                unique = False
        if unique:
            gcf = i

can be made this

for i in collections[0]:
    for x in collections:
        if i in x:
            gcf = i

Notice less spaces. Makes it easier to read.

\$\endgroup\$
  • \$\begingroup\$ thanks but for the last part i am looping through all of the collections and returning true only if it is the gcf in all of the collections so removing unique will not work. The var name unique makes no sense though so sorry for the confusion \$\endgroup\$ – user2640586 Aug 7 '13 at 20:38
3
\$\begingroup\$

You can use sets to whittle down the possible GCFs.

for i, argument in enumerate(sys.argv[1:]):
    factors = set(n for n in range(2, int(argument) + 1) if int(argument) & n is 0)
    print argument, factors
    if i is 0:
        possible_gcfs = factors
    else:
        possible_gcfs &= factors
print "gcf is:", max(possible_gcfs | {1})

Better, use reduce:

def get_factors(x):
    factors = set(n for n in range(2, int(x) + 1) if int(x) % n is 0)
    print x, ':', factors
    return factors

possible_gcfs = reduce(set.intersection, map(get_factors, sys.argv[1:]))
print "gcf is:", max(possible_gcfs | {1})

Or if you don't need it to print out the factors of each number you can make it a bit more efficient by noting that the GCF must be no larger than the lowest of the arguments entered.

arguments = map(int, sys.argv[1:])
possible_gcfs = range(2, min(arguments) + 1)
for argument in arguments:
    possible_gcfs = [n for n in possible_gcfs if argument % n is 0]
print "gcf is: ", max(possible_gcfs + [1])

... but this can again be simplified using reduce and noting that the gcf is associative

def gcf(a, b):
    a, b = int(a), int(b)
    return max(n for n in range(1, min(a, b) + 1) if a % n is 0 and b % n is 0)

print "gcf is:", reduce(gcf, sys.argv[1:])

(And as a comment pointed out there are plenty of other solutions posted to earlier questions and you could use fractions.gcd.)

\$\endgroup\$
1
\$\begingroup\$

I agree with Aseem above, a list comprehension is a good move in Python. In addition, I think you can dramatically reduce the number of loops you are doing.

If I understand it right, numbers is an integer representation of sys.argv -> I suggest using sys.argv itself, which reduces your memory overhead. Also, you can iterate over the values in sys.argv directly, you don't need to iterate over indexes. With this in mind, you reduce the number of loops you need to do:

-- Current code:

numbers, collections = [], []
for i in range(1,len(sys.argv)):
    numbers.append(int(sys.argv[i]))
for x in range(0,len(numbers)):
    collections.append([])  
    for s in range(1,numbers[x] + 1):
        if numbers[x] % s == 0:
            collections[x].append(s)

-- Revision, with less loops:

revised = []
for n in sys.argv[1:]:
    revised.append([i for i in range(1, int(n) + 1) if not int(n) % i])

-- Test that these are in fact equivalent:

collections == revised => True

You could go further to reduce the memory consumption, by consuming sys.argv as you went:

revised_2 = []
sys.argv.pop(0)
while sys.argv:
    n = int(sys.argv.pop(0))
    revised_2.append([i for i in range(1, n + 1) if not n % i])

You might want to do this if the lists are really large (but in this case, I imagine you would be reading in the values from a file and wouldn't be using sys.argv).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.