6
\$\begingroup\$

For example, given [10, 15, 3, 7] and a number k of 17, return True since 10 + 7 is 17.

How can I improve the below solution?

from itertools import combinations

def add_up_to(numbers, k):

 c_k_2 = list(combinations(numbers, 2))

 return any([True for pair in c_k_2 if sum(pair) == k])
\$\endgroup\$
6
  • \$\begingroup\$ consider sorting and using two pointers for quick performance \$\endgroup\$
    – user62030
    Commented Apr 20, 2021 at 19:03
  • 2
    \$\begingroup\$ @HereToRelax Consider writing an answer and providing some more explanation for contributors that are looking to learn and improve \$\endgroup\$ Commented Apr 20, 2021 at 19:17
  • \$\begingroup\$ I have an answer on two pointers here codereview.stackexchange.com/a/219139/62030 \$\endgroup\$
    – user62030
    Commented Apr 20, 2021 at 19:25
  • \$\begingroup\$ Thanks for sharing. I implemented your proposed approach (my interpretation of course, as there's not a lot of information provided), sorted the list and used two pointers to run across the array. I used a numpy array to get good sorting performance. While there was a sweet spot (list length around 1.000) where this approach slightly outperformed my proposed algortihm using a set, it was significantly slower for long lists. If you actually know of a faster approach, I'd be interested to learn, so please do share! \$\endgroup\$ Commented Apr 20, 2021 at 20:17
  • \$\begingroup\$ How do you get a list of 10^10 elements and how long does it take once the list is loaded? \$\endgroup\$
    – user62030
    Commented Apr 20, 2021 at 20:33

2 Answers 2

3
\$\begingroup\$

We can take your approach even further than riskypenguin did by pushing the work pretty much entirely into C-code:

def add_up_to(numbers, k):
    return k in map(sum, combinations(numbers, 2))

Takes \$O(1)\$ space instead of your \$O(n^2)\$, and best case time is \$O(1)\$ instead of your \$O(n^2)\$. And it's nice and short. Plus the C code is faster.

Benchmark with a worst case, numbers, k = [0] * 1000, 1:

546.63 ms  original
386.11 ms  riskypenguin
229.90 ms  Manuel

Benchmark with a "best case", numbers, k = [0] * 1000, 1:

594.35 ms  original
  0.02 ms  riskypenguin
  0.02 ms  Manuel

Why did I put quotes around "best case"? Because for you it's a worst case. Note your increased time. You treat all pairs in any case, and you do the most work when they all have the desired sum: then you build the longest possible list, full of True values. The other solutions see the first pair and right away stop, hence their tiny times.

Those are of course all moo points, as this problem should be solved in \$O(n)\$ time (as riskypenguin did later) or at most \$O(n \log n)\$ time. Unless you're only allowed \$O(1)\$ space and forbidden to modify the given list, which is rather unrealistic.

Benchmark code:

from timeit import repeat
from functools import partial
from itertools import combinations

def original(numbers, k):
    c_k_2 = list(combinations(numbers, 2))
    return any([True for pair in c_k_2 if sum(pair) == k])

def riskypenguin(numbers, k):
    return any(sum(pair) == k for pair in combinations(numbers, 2))

def Manuel(numbers, k):
    return k in map(sum, combinations(numbers, 2))

def benchmark(numbers, k, reps):
    print(f'{len(numbers)=} {k=} {reps=}')
    funcs = original, riskypenguin, Manuel
    for _ in range(3):
        for func in funcs:
            t = min(repeat(partial(func, numbers, k), number=reps))
            print('%6.2f ms ' % (t * 1e3), func.__name__)
        print()

# benchmark([10, 15, 3, 7], 17, 10**5)
benchmark([0] * 1000, 1, 5)
benchmark([0] * 1000, 0, 5)
\$\endgroup\$
7
  • \$\begingroup\$ That's a really clean solution compared to my first version, +1! Could you include my proposed approach using a set in your benchmarks? I would hope it performs pretty well, especially in worst case scenarios \$\endgroup\$ Commented Apr 21, 2021 at 11:37
  • \$\begingroup\$ @riskypenguin Hmm, I left it out intentionally, as I don't find it interesting to confirm the obvious :-P. I really just wanted to compare the combinations+sum versions, didn't even include another O(1) space non-modifying solution of mine that's about four times faster. But I ran your set solution now, takes about 0.4 to 0.5 ms for that "worst case", although that's not quite fair as it additionally unrealistically benefits from its set remaining a single element. \$\endgroup\$
    – Manuel
    Commented Apr 21, 2021 at 12:07
  • 1
    \$\begingroup\$ @riskypenguin I think it's the map vs the generator expression. With the latter, you're still interpreting Python code all the time. And maybe all the "context switches" between any and the generator also hurt. I'm kinda disappointed the speed difference isn't bigger :-) \$\endgroup\$
    – Manuel
    Commented Apr 21, 2021 at 12:29
  • 1
    \$\begingroup\$ @TobySpeight Bah, that was intentional :-( \$\endgroup\$
    – Manuel
    Commented Apr 21, 2021 at 12:45
  • 1
    \$\begingroup\$ "Bah" - or "Baa"? ;-) \$\endgroup\$ Commented Apr 21, 2021 at 14:33
9
\$\begingroup\$

Indents

PEP 8: Use 4 spaces per indentation level.


True if condition else False

The pattern True if condition else False can be replaced by condition if it evaluates to a bool. If you are checking for truthy and falsey values you can replace the pattern by bool(condition).

While this lets us simplify the return statement

return any([sum(pair) == k for pair in c_k_2])

it actually performs worse (as pointed out by Manuel in the comments) without implementing further improvements (see the next point). While you originally create a list of only True values, this simplification will create a list that also includes all the False values, which we do not need at all.


Drop the list

You convert to a list twice in your code, once explicitly by calling the list(...) constructor and once implicitly by wrapping a generator expression with [...]. In your particular use case, both are unnecessary.

When dropping the call to the list constructor, combinations(numbers, 2) will provide an itertools.combinations object, which I would assume behaves similiarly to a generator, which is a lazily evaluated iterable. This way we don't compute and store all possible combinations of numbers in advance, which is perfect for us because we

  1. only need one pair of numbers at a time
  2. want to stop evaluating the expression once we find a pair that matches our criteria

Dropping the brackets [] around our generator expression follows the same logic.

Generator expressions vs. list comprehensions on StackOverflow


Applying these improvements will make the code more efficient, more readable and more concise:

def any_two_elements_add_up_to(numbers, k):
    pairs = combinations(numbers, 2)
    return any(sum(pair) == k for pair in pairs)

# or as a one-liner

def any_two_elements_add_up_to(numbers, k):
    return any(sum(pair) == k for pair in combinations(numbers, 2))

EDIT: Algorithm

I've tried my hand at a faster approach, this is the first solution I came up with. Although it's really simple it still outperforms the above solution by orders of magnitude as it runs in O(n).

Here's the code:

def new_approach(numbers, target):
    counterparts = set()

    for num in numbers:
        if num in counterparts:
            return True

        counterparts.add(target - num)

    return False

Since every number only has one counterpart k - x that would make it add up to k, we can keep a set of all possible counterparts that we've identified so far. Once we come across a number that is in our set of counterparts (i.e. adds up to k with a previous number) we return True. If we don't come across one such number, we simply return False.

\$\endgroup\$
2
  • \$\begingroup\$ They don't have the pattern True if condition else False, though, and that first simplification of yours actually makes the code slower when there are a lot of False values that then get added to the list (for example in my answer's "worst case" input). You also make it sound too general, for example if condition is a string, then it doesn't evaluate to True or False, so it's not equivalent to the True if condition else False pattern. \$\endgroup\$
    – Manuel
    Commented Apr 21, 2021 at 11:06
  • \$\begingroup\$ Very good points, thank you! I will update my answer accordingly \$\endgroup\$ Commented Apr 21, 2021 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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