5
\$\begingroup\$

I'm new to Python and curious what looks good and what doesn't. The function I have defined looks for pairs in a list of integers and tells the user whether or not any possible pair equals the target number. How can this code be more efficient or fast?

import datetime
from itertools import combinations

def csop(*params):
    t1 = datetime.datetime.now()
    print params[0], params[1]
    for c in combinations(params[0],2):
        print sum(c)
        if sum(c) == params[1]:
            print 'Target number reached'
            t2 = datetime.datetime.now()
            print t2-t1
            exit()
        else:
            pass

To run:

import csop
csop.csop([1,2,3,4],5)

The output should look something like this:

[1, 2, 3, 4] 5
3
4
5
Target number reached
0:00:00.000071
\$\endgroup\$
3
\$\begingroup\$

As a style note, this is a bit of an abuse:

def csop(*params):

The point of *params is to allow things to be passed that cannot be known when the code is written. This is not the case here. There are only two parameters, and you know what they are. So you should give them names.

This:

exit()

is also bad form. Exiting the program from the middle of a function is great way to make bugs that are really hard to find. In this case simply return

this:

else:
    pass

is completely dead code. pass is used to mark a block that is empty. It is a by product of everything in Python being indent sensitive. But the else is optional so just leave it and the pass off.

And performance wise, you perform the sum() twice. If it matters to you, this result could be saved instead of evaluating it twice.

\$\endgroup\$
  • \$\begingroup\$ I'm having trouble with your first suggestion. Receiving the following error: TypeError: 'int' object has no attribute '__getitem__' \$\endgroup\$ – tyluRp Jan 16 '17 at 4:02
  • \$\begingroup\$ Done, I added the modifications in my original post. \$\endgroup\$ – tyluRp Jan 16 '17 at 4:04
3
\$\begingroup\$

Aside from stylistic issues, your solution is \$O(n^2)\$, but a linear solution exists. You just have to traverse the array once and store, for each number, the complement to reach the target sum. When iterating over an element, if it is stored, you know there is an other element you already passed that, when summed to it, reach the target.

To store elements efficiently, and especialy test for existence efficiently, you should use a set:

def csop(sequence, target):
    complements = set()
    for element in sequence:
        if element in complements:
            return True
        complements.add(target - element)
    return False

I also changed the behaviour slightly as formating information should be the responsibility of the caller. Something like this in the same file should do:

if __name__ == '__main__':
    t1 = datetime.datetime.now()
    found = csop([1, 2, 3, 4], 5)
    t2 = datetime.datetime.now()
    print('Target sum reached:', found, 'in', t2 - t1)

I also advise you to use better timing primitives, such as the timeit module or the time.perf_counter() function.

\$\endgroup\$
  • \$\begingroup\$ I'm using the time.it module and I like it. However, the rest is over my head. I don't understand how the code you sent me works without using the combinations function from the itertools module. Also, big O notation is over my head as well. How were you able to look at my code and say it's \$O(n^2)\$? Is it because of the for loop? \$\endgroup\$ – tyluRp Jan 16 '17 at 22:43
  • \$\begingroup\$ @LCDR-Data The combinations function is O(n2) because for each element, it has to iterate over the array again to make pairs. Each of the n elements is (roughtly) asociated to the other n element. Hence n^2. I iterate only once over the n elements (and other operations does not depend on n), hence O(n) for my code. For the rest, as I said, we're just storing the missing elements to reach the sum, and if the current element is one of those stored, we can conclude that the sum is reachable. \$\endgroup\$ – Mathias Ettinger Jan 17 '17 at 7:16
  • \$\begingroup\$ Thank you, the code is much faster. My code was averaging ~0.002 seconds. With your code I am averaging ~0.0007 seconds. \$\endgroup\$ – tyluRp Jan 18 '17 at 1:17

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.