6
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thq so much for the explanation and the solution. It took 358ms for processing 1 million dataset. \$\endgroup\$ – PushCode Aug 22 '15 at 23:50
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ A[i] and A[j] could be the same number (not allowed). A simple check here would be necessary. Removing duplicates from array A wouldn't work, as it seems this could produce a different output to his code (which is our definition of correct). Unless duplicates aren't allowed in the input file..? Nice solution though \$\endgroup\$ – RHok Aug 20 '15 at 0:09
  • \$\begingroup\$ @vnp can you pls elaborate a bit about \$find largest j (j > i) such that A[i] + A[j] < start\$ Its like assigning j = (input.lenght-1) and decrement till we find the largest and do the same for the next step? \$\endgroup\$ – PushCode Aug 20 '15 at 2:16
  • \$\begingroup\$ After you posted your answer, he edited to add "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." This breaks this solution. See my answer to see this solution semi-implemented + fixes \$\endgroup\$ – RHok Aug 21 '15 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.