Two sum algorithm variant

Question

I need to compute the number of target values \$t\$ in the range: \$-10000 \le t \le 10000\$ (inclusive) such that there are distinct numbers \$x, y\$ in the input file that satisfy \$t= x+y\$. I have the code which does work and would like to optimize it to run it faster.

Also, we'll count the sum \$t\$ only once. If there are two \$x,y\$ pairs that add to 55, you will only increment the result once.

public static int Calculate(int start, int finish, HashSet<long> numbers)
{
    int result = 0;
    for (int sum = start; sum <= finish; sum++)
    {
        foreach (long n in numbers)
        {
            if (numbers.Contains(sum - n) && n != (sum - n))
            {
                result++;
                break;
            }
        }
    }

    return result;
}

This is an assignment and I completed it with full marks. My code is taking like 30 minutes to run against the data set of 1 million numbers. I tried to think a way to optimize my code, but couldn't get to the right thought and would appreciate some help.

Answer 1

See my .NET fiddle: https://dotnetfiddle.net/34jkmD

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
   public static void Main()
   {
      //initialize variables for setup
      var numberHashSet = new HashSet<int>();
      var rangeBottom = -10000;
      var rangeTop = 10000;
      var hashSetLowerBoundNumber = -100000;
      var hashSetUpperBoundNumber = 100000;
      var hashSetSize = 1000;

      //initiate hashset of random nums
      Random rnd = new Random();
      for (var i = 0; i < hashSetSize ; i++){
         numberHashSet.Add(rnd.Next(hashSetLowerBoundNumber, hashSetUpperBoundNumber));
      }

      Stopwatch stopwatch = new Stopwatch();
      stopwatch.Start();

      var result = slowCalculate(rangeBottom, rangeTop, numberHashSet);

      var slowTime = stopwatch.ElapsedMilliseconds;
      stopwatch.Restart();

      var result2 = fastCalculate(rangeBottom, rangeTop, numberHashSet);

      var fastTime = stopwatch.ElapsedMilliseconds;

      Console.WriteLine("Slow: " + result + " in " + slowTime + " milliseconds.");
      Console.WriteLine("Fast: " + result2 + " in " + fastTime + " milliseconds.");
   }

   public static int slowCalculate(int start, int finish, HashSet<int> numbers)
   {
      int result = 0;
      for (int sum = start; sum <= finish; sum++)
      {
         foreach (int n in numbers)
         {
            if (numbers.Contains(sum - n) && n != (sum - n))
            {
               result++;
               break;
            }
         }
      }

      return result;
   }

   public static int fastCalculate(int start, int finish, HashSet<int> numbers)
   {
      int result = 0;

      int[] numbersArray = new int[numbers.Count];
      numbers.CopyTo(numbersArray);
      Array.Sort(numbersArray);

      Dictionary<int, bool> valueAlreadyCounted = new Dictionary<int, bool>();

      for (var i = 0; i < numbersArray.Length; i++){
         int val = numbersArray[i];
         int maxValue = finish - val;
         int minValue = start - val;

         int indexOfUpperBound = Array.BinarySearch(numbersArray, maxValue);
         int indexOfLowerBound = Array.BinarySearch(numbersArray, minValue);

         if (indexOfUpperBound < 0){
            indexOfUpperBound = ~indexOfUpperBound - 1;
         }
         if (indexOfLowerBound < 0){
            indexOfLowerBound = ~indexOfLowerBound;
         }
         for (var j = indexOfLowerBound; j<=indexOfUpperBound; j++){
            var sum = numbersArray[j] + numbersArray[i];
            if (!valueAlreadyCounted.ContainsKey(sum) && i != j){
               valueAlreadyCounted.Add(sum, true);
               result ++;
            }
         }
      }
      return result;
   }
}

Prints (approx, some variation from random nums):

Slow: 18191 in 353 milliseconds.
Fast: 18191 in 29 milliseconds.

The fast method is sort of based off vnp's answer, although needed some major tweaks to make it correct.

Fast calculate breakdown:

Sort of numbers array: O(n log n)

For loop over numbers array: O(n)

Binary search for lower and upper bound indexes: O(log n)

--This binary search finds the range of numbers which will sum with numbersArray[i] to fit between start and finish

I'm pretty sure this next part could be done better. Anyone know the optimal way to check a set of numbers if any of them have been used before without iterating one at a time over the entire set? I don't know of any...

The next for loop loops over this range of valid numbers: This can be up to O(n) but typically shouldn't cover the entire array of numbers. It then adds numbersArray[i] to numbersArray[j] and checks if that value has already been counted in the dictionary: O(1).

So worst case is also O(n^2) (same as yours) but will perform far better on data sets with larger ranges of x for -x <= t <= x, but possibly worse if x is low and the number of values in the hashset is very high. Jump on the fiddle and have a play around with the initialization vars at the top to see what I mean.

Answer 2

There is no need to iterate over the range. Consider a pseudocode:

sort numbers from the input file into an array A
N = size of collection
result = 0
for i in [0..N)
    find largest j (j > i) such that A[i] + A[j] < start
    find smallest k (k > i) such that A[i] + A[k] > finish
    result += k - j

Each find is \$O(\log N)\$ at worst. Overall complexity is \$O(N \log N)\$ regardless of the target range.