How can I optimize the execution time of my method?

Question

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);
        }
    }

This is too broad question and have many, many solutions to optimize it. First thing I would do in your place is to think other way of solving this problem, and only after that I would try optimizing it more using hardware and power of computers by parallelizing work (In your case checkout `Parallel.foreach()` and Threading/Tasks — Aleksa Ristic, Sep 17 '22 at 18:42
If you're looking for performance, your best bet would probably be to use a [HashSet](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1?view=net-6.0) rather than a list. — Jesse, Sep 17 '22 at 18:43
@Cid, the question needs a lot of work before it's suited to [codereview.se]. You should have pointed the asker at [A guide to Code Review for Stack Overflow users](//codereview.meta.stackexchange.com/a/5778), as some things are done differently over there - e.g. we need a good description of the *purpose* of the code to give context, and question titles should simply say what the code *does* (the question is always, "_How can I improve this?_"). It's important that the code works correctly; include the unit tests if possible. — Toby Speight, Sep 17 '22 at 19:23
Think about what `list.Contains(needed))` does. That's why the `Hashset` recommendation — Flydog57, Sep 17 '22 at 19:30

score 0 · Answer 1 · answered Sep 17 '22 at 19:18

I told what I think in comments but then I took it to test to see if I can show you what I mean by "thinking different" so I wrote fast solution which do not have much improvement, just two lines that came up to my head but did improve performance by a lot. Here is the code containing your function and code containing improved one.

Results are these:

Numbers in list: 1000000
Number range: 0 - 1000000
Number of tests per function: 10

Find sum of: 100
Improved function average: 46ms
Your function average: 18.000ms


Find sum of: 1000
Improved function average: 41ms
Your function average: 600ms

Find sum of: 10
Improved function average: 43ms
Your function average: Waited too long for first to finish, never did

Here is the code:

    internal class Program
    {
        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;

        }
        static Tuple<int, int> FindTwoSumImproved(IList<int> list, int sum)
        {
            int min = list.Min();
            int max = list.Max();
            for (int i = 0; i < list.Count; i++)
            {
                int needed = sum - list[i];
                if(needed < min || needed > max)
                    continue;

                int ind = list.IndexOf(needed);

                if(ind >= 0 && ind != i)
                    return new Tuple<int, int>(i, ind);
            }
            return null;
        }

        static void Main(string[] args)
        {
            Random rnd = new Random();
            List<int> list = new List<int>();

            int findSumOf = 10;

            for(int y = 0; y < 10; y++)
            {
                list.Clear();
                for (int i = 0; i < 1000000; i++)
                    list.Add(rnd.Next(0, 1000000));

                DateTime dt1 = DateTime.Now;
                Tuple<int, int> indicesImproved = FindTwoSumImproved(list, findSumOf);
                DateTime dt2 = DateTime.Now;
                Console.WriteLine($"{indicesImproved.Item1} {indicesImproved.Item2} - [{(dt2 - dt1).TotalMilliseconds}ms]");
            }
            Console.WriteLine("------------");
            for (int y = 0; y < 10; y++)
            {
                list.Clear();
                for (int i = 0; i < 1000000; i++)
                    list.Add(rnd.Next(0, 1000000));

                DateTime dt1 = DateTime.Now;
                Tuple<int, int> indices = FindTwoSum(list, findSumOf);
                DateTime dt2 = DateTime.Now;
                Console.WriteLine($"{indices.Item1} {indices.Item2} - [{(dt2 - dt1).TotalMilliseconds}ms]");
            }

            Console.Read();
        }
    }

FYI https://stackoverflow.com/questions/2923283/stopwatch-vs-using-system-datetime-now-for-timing-events — Rand Random, Sep 17 '22 at 19:33
@RandRandom Thank you, you are right and I am totally agreeing with you. Only reason I used `DateTime` here instead of `Stopwatch` is I am comparing results for myself inside same environment (both using `DateTime`) so results have same offset (precision). Since I did not need precise measurements (I wanted to show difference between 18-infinite seconds vs few milliseconds), I used less precise solution (less lines of code). TBS. you are right, `Stopwatch` should be used for these kind of tests if you want them to be precise and correct. — Aleksa Ristic, Sep 19 '22 at 06:35
@RandRandom Continued reading post you sent, found this interesting answer. Worth a look [https://stackoverflow.com/a/6986472/7874193](https://stackoverflow.com/a/6986472/7874193) — Aleksa Ristic, Sep 19 '22 at 06:39

How can I optimize the execution time of my method?

1 Answers1