Filtering large lists and returning values that match a test I have been working on a quiz that I came across within a job application. I am not applying for the job, but I wanted to have a go at the problem.


  An input file contains integers, both positive and negative (there
  might be some duplicates). Each line on the file has one integer.
  
  Compute the number of y values within the range -10000 ≤ y ≤ 10000
  such that there are distinct numbers a, b in the file where a + b = y.
  
  You can download the file from
  http://s3.amazonaws.com/spacebalcony/cases.tar.bz2 (57MB). There
  are two test cases there for you to verify your program. Check the
  README file for the answers.


I came up with a solution using itertools but it is very slow.

from itertools import combinations, imap

with open('test1.txt', 'rU') as f:
    integers = sorted(list(set([int(item) for item in f])))

def check_item(x):
    item_total = sum(x)
    if all([item_total &gt;= -10000, item_total &lt;= 10000]):
        return True
    return False

print sum(imap(check_item, combinations(integers, 2)))


Does anyone have any suggestions to speed up the code?

For example, I have tried removing the largest and smallest numbers that could never be brought down within the range:

while (integers[0] + integers[-1]) &lt; -10000:
    integers = integers[1:]

while (integers[0] + integers[-1]) &gt; 10000:
    integers = integers[:-1]


This did not make much of a difference
The problem with the solution posted in the question is that it goes
through all the possible combinations of two elements in the array
when this is not really needed.

The pseudocode for a more efficient strategy would be as follows:


Read and sort the integers
For each integer (a), calculate the lowest and highest values of (b) that satisfy the inequality
Look for the position in the array for those values (take advantage of the values being ordered, use binary search)
Note that all the numbers between the two positions found satisfy the inequality since they are ordered


In python code, it should be something like this:

import bisect

MIN_SUM_VALUE = -10000
MAX_SUM_VALUE = 10000

with open('large.txt', 'rU') as f:
    integers = sorted(set(int(item) for item in f))

count = 0
for index, a in enumerate(integers):
    # Low and high values of b that still satisfy the inequality
    b_low = MIN_SUM_VALUE - a
    b_high = MAX_SUM_VALUE - a

    # Look for the index in the array for the values above
    b_low_index = bisect.bisect_left(integers, b_low, index + 1)
    b_high_index = bisect.bisect_right(integers, b_high, index + 1)

    # Increment count by the number of values found
    count += b_high_index - b_low_index

print count


Note that the way to avoid repetitions is to restrict the binary search to look for b values whose position is after the a values in the array (that's the index + 1 parameter).

Edit: To get the actual sums printed the following snippet can be used: 

for b_index in range(b_low_index, b_high_index):
    b = integers[b_index]
    print a, b, a + b