Gfrktyl

Here is the problem description (from an algorithm course: https://www.coursera.org/learn/algorithm-design-analysis):

The goal of this problem is to implement a variant of the 2-SUM
algorithm (covered in the Week 6 lecture on hash table applications).

The file contains 1 million integers, both positive and negative
(there might be some repetitions!). This is your array of integers,
with the $i$th row of the file specifying the $i$th entry of the array.

Your task is to compute the number of target values $t$ in the interval
[-10000,10000] (inclusive) such that there are distinct numbers $x,y$ in
the input file that satisfy $x+y=t$.

I wrote the following Python program. It runs already 25 minutes and just calculated 6200 of 20000 numbers.
This is too slow.

import sys



def has_two_sum(n,num_set,nums):

  res = any(((n-x) in num_set) and 2*x !=n for x in nums)

  return res



with open(sys.argv[1], 'r') as fp:

  nums = [int(line) for line in fp]

  num_set = set(nums)



two_sum = sum(1  for n in range(-10000,10001) if has_two_sum(n,num_set,nums))

print(two_sum)

Your code runs instantly on my system with 1 million randomly generated numbers. are you sure you are searching for n - x in num_set and not in nums?

Anyway, a couple of Python style pointers:

1. 
   

   You can iterate over the set directly, no need to pass both the set and the list:

   
   
   

   def has_two_sum(n, num_set):
   
       res = any(((n-x) in num_set) and 2*x != n for x in num_set)
   
       return res
   
   

   
   


2. 
   

   Not much point in storing a value to immediuately return it:

   
   
   

   def has_two_sum(n, num_set):
   
       return any(((n-x) in num_set) and 2*x != n for x in num_set)
   
   

   
   


3. 
   

   Boolean values are converted to 0 or 1 when used in an integer setting, so your adding of values is typically written as:

   
   
   

   two_sum = sum(has_two_sum(n, num_set) for n in range(-10000, 10001))
   
   

   
   


4. 
   

   If you are going to have a function that contains a single liner, you better give it a great, descriptive name. I don't think that has_two_sum really fits the bill. Perhaps has_two_items_that_sum_to_n or has_two_that_sum_to_n? Alternatively, I think my preferred option here would be to get rid of the function altogether and let code speak by itself, writing the whole thing as two nested comprehensions:

   
   
   

   two_sum = sum(any(n - x in num_set and 2*x != n for x in num_set)
   
                 for n in range(-10000, 10001))
   
   

   
   
   

   There is a school of thought that considers nested comprehensions to be confusing (e.g. the Google Python style guide doesn't allow them), but I think this case is simple enough, YMMV.

   
   

To get a grasp of what to speedup I ran a profiler on your code.
To get the 1 million integers I made a function to generate them, with the following:

def generate_random_numbers(amount=1000000):

    import random

    n = [str(int(random.normalvariate(0, amount))) for _ in range(amount)]

    with open('data', 'w') as f:

        f.write('n'.join(n))

Yes I did put the sigma as one million too.
I then copied your code into a function, removed the file part, and ran the profiler over it.
Resulting in the following code:

import cProfile



def read_nums():

    with open('data', 'r') as fp:

        return [int(line) for line in fp]



def has_two_sum(n,num_set,nums):

    res = any(((n-x) in num_set) and 2*x !=n for x in nums)

    return res



def two_sum(nums):

    nums = [int(line) for line in nums]

    num_set = set(nums)

    return sum(1  for n in range(-10000,10001) if has_two_sum(n,num_set,nums))



nums = read_nums()

cProfile.run('two_sum({!r})'.format(nums))

Which resulted in the following profile of your code:

         166366 function calls in 6.966 seconds



   Ordered by: standard name



   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

        1    0.362    0.362    0.900    0.900 2sum.py:11(two_sum)

        1    0.395    0.395    0.395    0.395 2sum.py:12(<listcomp>)

    20002    0.015    0.000    0.139    0.000 2sum.py:14(<genexpr>)

    20001    0.025    0.000    0.124    0.000 2sum.py:7(has_two_sum)

   106356    0.052    0.000    0.052    0.000 2sum.py:8(<genexpr>)

        1    0.216    0.216    1.116    1.116 <string>:1(<module>)

    20001    0.047    0.000    0.095    0.000 {built-in method builtins.any}

        1    5.851    5.851    6.966    6.966 {built-in method builtins.exec}

        1    0.004    0.004    0.143    0.143 {built-in method builtins.sum}

        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Which is not 25 minuets for 6200 of the 20000.
Instead it's a lot less. It says it took 6.966, but cumtime of two_sums is 0.900.
I then used a timer on it, which says it runs in ~0.899s.
Using:

print(timeit('two_sum({!r})'.format(nums), 'from __main__ import two_sum', number=100)/100)

So performance wise, I'd say it's not Python's fault, and would be very hard to optimize.
Instead I'd change your code to be a 'three line' function, but format the comprehensions to be more readable.

• I'd remove un-needed brackets


• Use a set compression.


• Remove odd whitespace. ((1 for ...)

def two_sum(nums):

    nums = {int(n) for n in nums}

    return sum(

        1

        for n in range(-10000, 10001)

        if any(n - x in nums and 2 * x != n for x in nums)

    )

You aren't handling duplicates correctly, by my interpretation of the problem. Based on the sample code in the course notes, I interpret "distinct" to mean that you may not use the same entry twice, but you may use the same number twice if it occurs more than once in the file. That is, if the input file contains

3

3

… then I would expect it to be able to form a target sum of 6. Your program reports that 6 cannot be formed.

The answers to the question don't pay attention that the original array consists of a million of signed eleven digit integers (i.e. both positive and negative). That is the real reason for the poor performance of the Python code, even on a 64-bit architecture.

[EDIT] Integers in Python 3 have arbitrary precision by default (e.g. see this article for details of implementation). In short, they can be represented as

i = x*2^(30*0) + y*2^(30*1) + z*2^(30*2)...

For numbers > 2^31 (e.g. eleven digit numbers), they are manipulated as complex objects with >=2 parts, and therefore the performance of the code manipulating such numbers is much slower than on smaller numbers in a range -2^30 to 2^30 for which there is a "fast path" CPython implementation (they are treated as fixed 32-bit integers). The 2-SUM programming assignment in the Algo_Stanford course deliberately uses huge numbers in the input array to make brute force solutions unacceptably slow.