Variant Of Two Sum Solution Extremely Slow in Objective C
<p>I'm taking an algorithms design and analysis course, and was given programming question which is a variant of the two sum problem:</p>

<p><strong>The input is an array of 1 million integers, both positive and negative. 
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.</strong></p>

<p>I have written a solution in objective C which solves the problem correctly for smaller test cases:</p>

<pre><code>+ (BOOL)pairExistsForSum:(NSInteger)t dictionary:(NSDictionary *)dictionary
{
    __block BOOL exists = NO;

    [dictionary enumerateKeysAndObjectsUsingBlock:^(NSString *key, NSNumber *x, BOOL *stop) {

        NSInteger y = t - x.integerValue;
        NSString *yKey = [NSString stringWithFormat:@"%li", y];

        if (y != x.integerValue &amp;&amp; dictionary[yKey]) {
            exists = YES;
            *stop = YES;
        }
    }];

    return exists;
}

+ (NSInteger)twoSumProblem:(NSArray &lt;NSNumber *&gt; *)array interval:(NSInteger)min max:(NSInteger)max
{
    NSDictionary *dictionary = [self generateDictionaryOfValuesWithNumbersArray:array];
    NSInteger uniquePairs = 0;

    for (NSInteger i = min; i &lt;= max; i++) {
        uniquePairs += [self pairExistsForSum:i dictionary:dictionary];
    }

    return uniquePairs;
}
</code></pre>

<p>The issue is that each iteration of <code>pairExistsForSum</code> takes a little over 2 seconds to complete, meaning this entire process will require hours to complete. </p>

<p><strong>I tried some alternative approaches such as:</strong></p>

<p>1) Sorting the input and dividing it into a positive and negative array and using binary search to find the complimentary addend</p>

<p>2) Changing the outer for loop to only traverse the range 0 - 10000, then searched for the addend for the positive and negative sum value simultaneously</p>

<p>Nothing has improved performance significantly enough, not even breaking this into sub problems and running each on concurrent threads.</p>

<p>I finally found someone's python solution that looks like this:</p>

<pre><code>import time
import bisect

a = []
with open('2sum.txt', 'r') as f:
    for line in f:
        a.append(int(line.strip()))
a.sort()

ret = set()
for x in a:
    lower = bisect.bisect_left(a, -10000 - x)
    upper = bisect.bisect_right(a, 10000 - x)
    for y in a[lower:upper]:
        if x != y and x + y not in ret:
            ret.add(x + y)
print len(ret)
</code></pre>

<p>This solution runs in a matter of seconds or less. I'm not familiar with Python, but I believe this is using binary search and is not exploiting the data of the input array to improve speed. Although I would expect python code to run faster than Objective C, the difference between these solutions is vast.</p>

<p><strong>My questions are the following:</strong></p>

<ol>
<li>Is there something I'm missing about the difference between these two solutions that would explain such a vast difference in performance?</li>
<li>Is there something I'm overlooking as far as what I can do to make this run in a respectable amount of time (i.e. under an hour) in Objective c?</li>
</ol>

<p>(Someone asked the same question here: <a href="http://stackoverflow.com/questions/38971693/variant-of-the-2-sum-algorithm-with-a-range-of-sums">Variant of the 2-sum algorithm with a range of sums</a> but there is no answer given, and I believe mine is more specific).</p>

<p>Many thanks.</p>

<blockquote>
  <p>Is there something I'm missing about the difference between these two solutions that would explain such a vast difference in performance?</p>
</blockquote>

<p>You are solving the problem "backwards". You start with <em>t</em> and then search for a pair which sums to it. Think of the extreme example of your input containing just two numbers, you will perform 200001 tests to see if the sum is one of the possible values in the range [-100000, 100000].</p>

<p>The Python is driven by selecting <em>x</em> and <em>y</em>, so only the actual <em>t</em> values that can be produced by the data are considered. Further by sorting the data the solution is able to consider only those <em>x</em>, <em>y</em> pairs which sum to a value in range.</p>

<blockquote>
  <p>Is there something I'm overlooking as far as what I can do to make this run in a respectable amount of time (i.e. under an hour) in Objective c?</p>
</blockquote>

<p>Yes, just implement the same algorithm as the Python solution. A quick Google will produce both the specification of the bisect functions and their Python source. You will find they are trivial binary searches which you can easily implement. However for speed you might wish to try to use a standard Objective-C method. <code>NSArray</code> does not have direct equivalents, but look at <code>indexOfObject:inSortedRange:options:usingComparator:</code> and think a little about "abusing" the comparator's definition of equal values... </p>

<p>HTH</p>

python objective-c algorithm hashtable big-o