当使用大量元素的列表时超出了时间限制？

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

卡洛斯说当复杂性可以大大降低到O（n），当使用散列集合是正确的。该代码应该是这样的：

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

Answer 2

您的时间限制被超过，可能是因为您正在执行O（n^2）操作。你可以在O（n）中解决它，无论是检查你的时间可能都知道这一点。

如果它只是一个寻找具有所需款项任何一对的事情，这样做：

• 对于每个项目，计算所需的数量。例如，如果sum = 10并且您看到7，则需要存储3.将其存储在散列集O（1）中。
• 当您浏览列表时，请检查散列集中的存在。再次，O（1）。
• 因此总共你有O（n）而不是O（n^2），就像你提交的那样。

Answer 3

这似乎在它的脸上可以看出，哈希解决方案应该是最快的 - 事实上，它可能是在大小超过2GB真正巨大的阵列。

但是（令人惊讶的是）对于int数组，其大小高达50,000,000个元素，对数组进行排序并使用优化算法可以更快地对排序后的数组进行操作。

这里有一个算法可以排序的阵列上使用（请注意，它需要它只是用来整理前，表示对元素的原始指标的额外阵列）：

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

这似乎像一个巨大的额外工作量，但令我惊讶的是，它优于20000000个元素的数组的哈希算法。

我发布我的测试程序下面，批评。我试图使FindTwoSumInSortedList()算法的样本数据尽可能地难以实现。

我从一个发布版本让我的电脑上的结果是：

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