6
\$\begingroup\$

I attempted an online Python test the other day. The function I wrote works fine however takes too long to complete.

Question:

From a list of numbers find the indexes of two numbers that total n and return as a tuple.

I tried using itertools but I don't know if there is a function that would out perform my original. I thought itertools.combinations may be able to.

Any suggestions as the best way to tackle this problem?

import numpy as np
from itertools import combinations

numbers = np.random.randint(1, 100, 1000000)


# used to time function run time
def timer_func(orig):
    import time
    def wrapper_func(*args):
        t1 = time.time()
        result = orig(*args)
        t2 = time.time() - t1
        print(f"{orig.__name__} ran in {t2}")
        return result

    return wrapper_func


# new combination test
@timer_func
def find_two_sum(numbers, target_sum):
    """
    :param numbers: (list of ints) The list of numbers.
    :param target_sum: (int) The required target sum.
    :returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
    """
    for perm in combinations(numbers, 2):
        if sum(perm) == target_sum:
            first = np.where(numbers == perm[0])
            second = np.where(numbers == perm[1])
            return (first[0][0], second[0][0])


# original function
@timer_func
def find_two_sum_original(numbers, target_sum):
    """
    :param numbers: (list of ints) The list of numbers.
    :param target_sum: (int) The required target sum.
    :returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
    """
    for i, x in enumerate(numbers):
        for ii, y in enumerate(numbers):
            if i != ii and x + y == target_sum:
                return (i, ii)


if __name__ == "__main__":
    print(find_two_sum(numbers, 25))
    print(find_two_sum_original(numbers, 25))
find_two_sum ran in 1.341470718383789
(2, 307)
find_two_sum_original ran in 1.0022737979888916
(2, 307)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @superbrain I think it's safe to assume that they missed out a word or two in the quote. The function names are two sum which is what the functions are doing. The tests are not wrong don't take "list" to literally mean list, a list can be a NumPy array or a sequence of words I jot down on a piece of paper. Rather than focusing on negatives "you're wrong in x and y" it'd be better if you cut the user some slack and phrased issues in a non-combative way. \$\endgroup\$
    – Peilonrayz
    Sep 14, 2020 at 22:35
  • \$\begingroup\$ @Peilonrayz Meh, the function name isn't mentioned in the quoted question, so that could be part of the misunderstanding. But yes, my answer did assume sum. I'd say "list" in the context of Python does mean list and shouldn't be a NumPy array. Although I didn't even care until my solution crashed because NumPy array's apparently don't have an index method :-) \$\endgroup\$ Sep 14, 2020 at 23:08

2 Answers 2

6
\$\begingroup\$

Your solutions might have to try all pairs, so you have up to quadratic runtime.

Let's use an allegedly not adequate set to keep track of the numbers we've already seen, so that for each number, we can check in constant time whether we've seen the needed partner:

def find_two_sum(numbers, target_sum):
    """
    :param numbers: (list of ints) The list of numbers.
    :param target_sum: (int) The required target sum.
    :returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
    """
    seen = set()
    for number in numbers:
        needed = target_sum - number
        if needed in seen:
            i = numbers.index(needed)
            j = numbers.index(number, i + 1)
            return i, j
        seen.add(number)

This only takes linear time.

Other points:

  • Your function signature seems a bit inappropriate. The question called the target sum "n", not "target_sum". Even your whole program doesn't use "n" anywhere. I always follow the specification (maybe unless the specification is really bad). A middle ground would be to define/read the input into variable n and then name your function parameter like you did. This way, a reader of the question and your code can see the connection.
  • The question says list of numbers (your docstring even repeats that), not a NumPy array. My code assumes it's indeed a list (I find using list.index a lot better here.)
  • Your benchmark can be improved. The test case contains a million ints from 1 to 100, and your target sum is 25. You're almost guaranteed to find something quickly, despite the large size and despite your quadratic runtime. Better test a worst case, like list(range(1000)) with target 1997 (the sum of the last two numbers).

Motivated by the comments, here's a benchmark comparing this set+index solution and a dict+enumerate solution (numbers are times, so lower=faster):

Round 1:
2.10 twosum_set
1.77 twosum_set_optimized
2.11 twosum_dict

Round 2:
2.05 twosum_set
1.75 twosum_set_optimized
2.08 twosum_dict

Round 3:
2.14 twosum_set
1.83 twosum_set_optimized
2.11 twosum_dict

They look about equally fast, although the optimized set solution is clearly faster.

That was with my above-mentioned list(range(1000)). Let's use a million instead (and fewer repetitions):

Round 1:
2.64 twosum_set
2.31 twosum_set_optimized
2.84 twosum_dict

Round 2:
2.70 twosum_set
2.36 twosum_set_optimized
2.88 twosum_dict

Round 3:
2.68 twosum_set
2.38 twosum_set_optimized
2.87 twosum_dict

Here the set solution does seem faster than the dict solution, and the optimized set solution is again clearly faster.

Benchmark code:

from timeit import repeat

def twosum_set(numbers, target_sum):
    seen = set()
    for number in numbers:
        needed = target_sum - number
        if needed in seen:
            i = numbers.index(needed)
            j = numbers.index(number, i + 1)
            return i, j
        seen.add(number)

def twosum_set_optimized(numbers, target_sum):
    seen = set()
    add = seen.add           # This is the optimization
    for number in numbers:
        needed = target_sum - number
        if needed in seen:
            i = numbers.index(needed)
            j = numbers.index(number, i + 1)
            return i, j
        add(number)          # This is the optimization

def twosum_dict(numbers, target_sum):
    index = {}
    for i, number in enumerate(numbers):
        needed = target_sum - number
        if needed in index:
            return index[needed], i
        index[number] = i

numbers = list(range(10**3))
repeat_number = 10**4

numbers = list(range(10**6))
repeat_number = 10**1

target_sum = sum(numbers[-2:])

for r in range(3):
    print(f'Round {r+1}:')
    for twosum in twosum_set, twosum_set_optimized, twosum_dict:
        t = min(repeat(lambda: twosum(numbers, target_sum), number=repeat_number))
        print('%.2f' % t, twosum.__name__)
    print()
\$\endgroup\$
10
  • 1
    \$\begingroup\$ At least for me, the correctness and linearity of this answer were both counterintuitive at first – so I enjoyed it for being surprising! (Also, very good point about the benchmark.) But ... why? If we know we'll need the seen-index eventually, why not store it in a dict? And if we know we'll need the current-index, why not use enumerate() to drive the loop? With those changes, the code shortens, simplifies, and becomes non-counterintuitive -- admittedly, a bit boring. \$\endgroup\$
    – FMc
    Sep 14, 2020 at 23:13
  • 1
    \$\begingroup\$ @FMc Why not dict and enumerate? Four reasons: (1) Like you said, boring :-). (2) Because Peilonrayz called set not adequate :-P. (3) The set takes less space than the dict, and also doesn't cause extra space to keep the index objects in memory. (4) it might be faster. Most of the indexes will not be used. Remember this. \$\endgroup\$ Sep 14, 2020 at 23:21
  • \$\begingroup\$ Yes, I do remember that one – talk about counter-intuitive. I still think that question should be moved to the bigger audience of StackOverflow to find the expert able to explain WTF is going on there. \$\endgroup\$
    – FMc
    Sep 14, 2020 at 23:33
  • 1
    \$\begingroup\$ @FMc Added some benchmarks now. \$\endgroup\$ Sep 15, 2020 at 0:17
  • \$\begingroup\$ @FMc I don't see how it's counter-intuitive: enumerate, an \$O(n)\$ operation, is slower than list.index, another \$O(n)\$ operation, and Python is slower than C. I have written up an answer highlighting that it's really this basic. \$\endgroup\$
    – Peilonrayz
    Sep 15, 2020 at 14:19
5
\$\begingroup\$

There are two key points to this challenge:

  1. Figuring out that you can determine what you need to search for by rearranging the given equation \$a + b = c\$ therefore you need to find if \$b = c - a\$ is in numbers.

  2. Use a datatype that has \$O(1)\$ indexing - datatype[index]. \$O(1)\$ means it runs in constant time, where your current np.where runs in \$O(n)\$ time as you iterate through the entire of list (worst case). Python has a few datatypes that exhibit this property:

    • str - This wouldn't be great here as we're working with numbers.
    • list - Whilst usable making it work with negative values and have a correct bound isn't simple. It is also likely to waste space.
    • set - This is the go to for two sum, however as you need the index of the second value it's not adequate here.
    • dict - This stores both a key and a value and so we can assign the value to the index of the key.

The dictionary can be made by using the following. I'll leave solving the rest of the challenge, from the above, as an exercise to improve your ability.

values = {
    value: index
    for index, value in enumerate(numbers)
}
\$\endgroup\$
1
  • \$\begingroup\$ @FMc Please read the OPs code that is a problem this wouldn't introduce. \$\endgroup\$
    – Peilonrayz
    Sep 14, 2020 at 22:06

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.