c# - 使用大量元素的列表时超过时间限制？

Question

函数在运行大量元素时无法通过性能测试:超出时间限制。 如何通过性能测试？

 //Function finds indices of two elements whose sum is equal to as passed in the parameter
 public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
 {
     for (int i = 0; i < list.Count; i++)
     {
         int sum2 = sum - list[i];
         int index = list.IndexOf(sum2);
         if (index > 0 )
         {
             return new Tuple<int, int>(i, index);
         }
     }
     return null;
 }

 //Main function to call FindTwoSum method
 public static void Main(string[] args)
 {
  Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 },12);
  Console.WriteLine(indices.Item1 + " " + indices.Item2);
 }

Answer 1

从表面上看，散列解决方案应该是最快的 - 实际上，它可能适用于大小超过 2GB 的非常大的数组。

然而(令人惊讶的是)对于大小高达 50,000,000 个元素的 int 数组，对数组进行排序并使用适用于已排序数组的优化算法会更快。

这是一个可以在排序数组上使用的算法(请注意，它需要一个额外的数组，该数组仅用于在排序前指示元素的原始索引):

public static Tuple<int, int> FindTwoSumInSortedList(IList<int> list, int[] indices, int sum)
{
    for (int i = 0, j = list.Count - 1; i < j;)
    {
        int s = list[i] + list[j];

        if (s == sum)
            return new Tuple<int, int>(indices[i], indices[j]);
        else if (s < sum)
            ++i;
        else
            --j;
    }

    return null;
}

对原始列表进行排序需要一些额外的工作:

int n = 10000000;
int[] array = new int[n];
...
var indices = Enumerable.Range(0, n).ToArray();
Array.Sort(array, indices);
result = FindTwoSumInSortedList(array, indices, target);

这看起来确实需要大量的额外工作，但令我惊讶的是，它在包含 20,000,000 个元素的数组上的表现优于哈希算法。

我把我的测试程序贴在下面，以供批评。对于 FindTwoSumInSortedList() 算法，我已尝试使样本数据尽可能地难看。

我在 PC 上从 RELEASE 构建中获得的结果是:

n = 10,000,000 

3031
(5000000, 5000001)
1292
(5000000, 5000001)

n = 20,000,000

6482
(10000000, 10000001)
2592
(10000000, 10000001)

n = 50,000,000

17408
(25000000, 25000001)
5653
(25000000, 25000001)

所以你可以看到排序算法的速度是原来的两倍多。这真让我吃惊!

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;

namespace ConsoleApplication1
{
    class Program
    {
        public static void Main()
        {
            int n = 10000000;
            int[] array = new int[n];
            var rng = new Random(18789);

            for (int i = 0; i < n; ++i)
                array[i] = rng.Next(0, n);

            array[n/2] = n;
            array[n/2 + 1] = n+1;

            var sw = Stopwatch.StartNew();

            // This is too slow to test:
            //var result = FindTwoSum(array, n*2+1);
            //Console.WriteLine(sw.ElapsedMilliseconds);
            //Console.WriteLine(result);

            sw.Restart();
            var result = FindTwoSumFaster(array, n*2 + 1);
            Console.WriteLine(sw.ElapsedMilliseconds);
            Console.WriteLine(result);

            sw.Restart();
            var indices = Enumerable.Range(0, n).ToArray();
            Array.Sort(array, indices);
            result = FindTwoSumInSortedList(array, indices, n*2+1);
            Console.WriteLine(sw.ElapsedMilliseconds);
            Console.WriteLine(result);
        }

        public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
        {
            for (int i = 0; i < list.Count; i++)
            {
                int sum2 = sum - list[i];
                int index = list.IndexOf(sum2);
                if (index > 0)
                {
                    return new Tuple<int, int>(i, index);
                }
            }
            return null;
        }

        public static Tuple<int, int> FindTwoSumInSortedList(IList<int> list, int[] indices, int sum)
        {
            for (int i = 0, j = list.Count - 1; i < j;)
            {
                int s = list[i] + list[j];

                if (s == sum)
                    return new Tuple<int, int>(indices[i], indices[j]);
                else if (s < sum)
                    ++i;
                else
                    --j;
            }

            return null;
        }

        public static Tuple<int, int> FindTwoSumFaster(IList<int> list, int sum)
        {
            if (list == null)
                throw new NullReferenceException("Null list");

            // constructing a hashset to have O(1) operations
            var listSet = new HashSet<int>();

            // number -> index mapping
            // O(n) complexity
            var listReverseSet = new Dictionary<int, int>();
            int i = 0;
            foreach (var elem in list)
            {
                if (!listSet.Contains(elem))
                    listSet.Add(elem);

                listReverseSet[elem] = i++;
            }

            // O(n) complexity
            int listCount = list.Count;
            for (int index = 0; index < listCount; index++)
            {
                var elem = list[index];

                if (listSet.Contains(sum - elem))
                    return new Tuple<int, int>(index, listReverseSet[sum - elem]);
            }

            return null;
        }
    }
}