多数の要素を持つリストを使用した場合、時間制限を超えましたか？

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^2）ではなくO（n）を持っています。

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

これは、余分な作業の膨大な量のように見えるんが、私の驚きに、それは20,000,000要素のアレイ上のハッシュアルゴリズムよりも性能が優れています。

下記のテストプログラムを投稿しています。批判のためです。私はFindTwoSumInSortedList()アルゴリズムのサンプルデータをできるだけ厄介なものにしようとしました。私は私のPC上でリリースビルドから取得

結果は以下のとおりです。

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