0
\$\begingroup\$

I have a very simple method that returns a tuple of integers in a list that sum to a specific target sum. The method works as expected, however, with a large list, it is slow. I have looked for articles about optimizing for loops, but I have not found anything that makes sense or helps in the case. Is there a "standard" way of optimizing for loops? Is there any way to make this particular method faster? Here is my code:

 public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
    {

        for (int i = 0; i < list.Count; i++)
        {

            int needed = sum - list[i];

            if (list.Contains(needed))
            {
               
                var second = list.IndexOf(needed);
                if (second != i)
                    return new Tuple<int, int>(i, second);
            }
        }
        return null;

    }

    public static void Main(string[] args)
    {
        Tuple<int, int> indices = FindTwoSum(new List<int>() {1, 3, 7, 5, 9 }, 10);
        if (indices != null)
        {
            Console.WriteLine(indices.Item1 + " " + indices.Item2);
        }
    }
\$\endgroup\$
3
  • 2
    \$\begingroup\$ The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ Commented Sep 17, 2022 at 19:21
  • 6
    \$\begingroup\$ One reason could be for poor performance is that you might scan the entire collection twice (Contains, IndexOf) in every iteration. \$\endgroup\$ Commented Sep 17, 2022 at 19:41
  • 2
    \$\begingroup\$ Why does FindTwoSum assume to find only one result? In your example there are two possible results, for instance. Also: stackoverflow.com/questions/1075734/… , stackoverflow.com/questions/16987888/… \$\endgroup\$
    – BCdotWEB
    Commented Sep 18, 2022 at 10:26

4 Answers 4

6
\$\begingroup\$

Optimizing the loop

Is there a "standard" way of optimizing for loops?
Is there any way to make this particular method faster?

A few general ideas to consider off the top of my head, in this order:

  • Are there expensive operations in the loop body, for example an \$O(n)\$ computation that will increase the overall time complexity? Can we make that computation faster?
    • The list.Contains(needed) and list.IndexOf(needed). There are faster ways to find a matching element. See the next section.
  • Are there repeated computations in the loop body that could be performed just once before the loop starts?
    • Not in the posted code.
  • Are there duplicate or excessive computations that could be reduced?
    • list.Contains(needed) and list.IndexOf(needed) both perform a linear search to find the same element. You could drop list.Contains(needed) completely and use just list.IndexOf(needed) for your purpose.

Consider time complexity

When optimizing performance, Before thinking about a specific method, it's important to think about the overall algorithm.

The posted code has \$O(n^2)\$ time complexity: for every element of the list, it visits every element of the list to find a matching pair.

Faster algorithms exist, with tradeoffs:

  • You could sort the list, which will make it possible to change the linear inner loop to logarithmic binary search. This will improve the time complexity to \$O(n\log n)\$, at the expense of extra space \$O(n)\$ for tracking the original indexes before sorting.

  • You could use a hashtable to store the values you've seen so far, and their first index, let's call it seen

    • For each value, let's call it current:
      • Is target - current in seen?
        • If yes, return the pair of the index in the map and the current index
        • If not, and current is not yet in seen, then put current into seen and the current index
    • If you reached the end of the collection without returning, then there is no such pair that sum to target.
    • This will improve the time complexity to \$O(n)\$, at the expense of extra space \$O(n)\$ for the hashtable.

Now you can consider the various alternatives and their tradeoffs, and decide which approach will be most suitable for your use case.

If the extra space is not acceptable, then your original implementation is fine, and you can look into optimizing the loop, eliminating list.Contains(needed) as I explained in the other section.

\$\endgroup\$
1
\$\begingroup\$

Your question says you want to return

a tuple of integers in a list that sum to a specific target sum

, but your code actually returns the indices of those numbers rather than the actual numbers.

If you really just want the numbers rather than the indices, and assuming that each number in the list is unique, then I would use a HashSet.

Even though this has to convert the list to a hashSet, it will still be significantly faster for large lists.

There is one further optimisation that you can do. If you are returning two numbers that add up to sum, then it follows that one of those numbers must be less than (or equal to) half of sum. Hence you only need to test numbers that are less than half of sum.

Hence you can use something like.

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
{
    var hash = list.ToHashSet();

    foreach (var i in hash)
    {
        if ((i * 2) > sum)
            continue;

        int needed = sum - i;

        if (needed != i && hash.Contains(needed))
        {
            return new Tuple<int, int>(i, needed);
        }
    }
    return null;
}

If you are calling this function multiple times and list is not changing, then obviously it would be better to move the var hash = list.ToHashSet(); line outside of the function so that it is only called once.

If you really want to return the indices, then I would construct a dictionary e.g.

var reverseDict = new Dictionary<int, int>();
for (int i = 0; i < list1.Count; i++)
    reverseDict.Add(list1[i], i);

and then use this dictionary to lookup up the index for needed.

\$\endgroup\$
1
\$\begingroup\$

And example of what janos had a description of. I wrote this code before reading all his insights (+1 to him).

This will create a Dictionary to store values that have been previous iterated over and the index. Then use TryGetValue which uses a hashset for the values, internally, and will be a fast lookup. If matching value not in the dictionary add current value in. Did a TryAdd incase the values have duplicates.

public static (int index1, int index2) FindTwoSums(int sum, params int[] values)
{
    var cache = new Dictionary<int, int>();
    for (var i = 0; i < values.Length; i++)
    {
        var needed = sum - values[i];
        if (cache.TryGetValue(needed, out var index))
        {
            return (i, index);
        }
        
        cache.TryAdd(values[i], i);
    }

    return default;
}

This will use more memory as now we in worst case duplicating the list values one in the values array and again in the dictionary. Also this will return back different results from the original question. With values of

var indices = FindTwoSums(10, 1,3,7,5,9);

The original question would have return index 0 and 4 but this way would return 1 and 2, because the value of 9 hasn't be inserted into the dictionary yet.

\$\endgroup\$
0
\$\begingroup\$

The "standard" way to optimize for loops is Loop unrolling. However, be aware that compilers often apply such optimization themselves.

Another way to speed up loops is Sentinel value. With a lot of iterations, it's really efficient.

Replace the Tuple class with the ValueTuple structure. This will reduce memory allocation and speed up the code. See Tuple types.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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