當使用大量元素的列表時超出了時間限制？

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