forループの終了に多くの時間がかかります

Question

以下のコードは正常に動作します。唯一の問題は、長さが200,000の配列値を与えると、約1時間で完了するのに時間がかかりすぎるということです。以下は私のコードです。

データファイルhereには、dataとdata2の文字列値が含まれています。 データ配列は降順に並べ替えられ、data2は昇順に並べ替えられます。

public void GetInputs() 
{ 
    string data; 
    string data2; 
    string[] scores_temp = data.Split(' '); 
    int[] scores = Array.ConvertAll(scores_temp, Int32.Parse); 

    string[] alice_temp = data2.Split(' '); 
    int[] aliceScore = Array.ConvertAll(alice_temp, Int32.Parse); 

    var distinctScores = scores.Distinct().ToList(); 
    int rank = 0; 
    for (int j = 0; j <= aliceScore.Length-1; j++) 
    { 
     for (int i = distinctScores.Count-1; i >= 0; i--) 
     { 
      if (aliceScore[j] >= distinctScores[i]) 
      { 
       rank = distinctScores.IndexOf(distinctScores[i]); 
      } 
      else if (aliceScore[j] < distinctScores[i]) 
      { 
       rank = distinctScores.IndexOf(distinctScores[i]); 
       rank += 2; 
       break; 
      } 
     } 
     if (rank.ToString() == "0") { 
      Console.WriteLine(rank.ToString().Replace("0", "1")); 
     } else { 
      Console.WriteLine(rank); }; 
     } 
     Console.ReadLine(); 
    } 

Answer 1

これらを並べ替え、次にindecesで作業してください。あなたの配列がソートされていることがわかっている場合は、それぞれのaliceScoreの位置をdistinctScoresにチェックすることができます。次に、あなたは何個の数字が上向きか下位かを知り、あなたが何をしたいのかを知ります。

Answer 2

rank = distinctScores.IndexOf(distinctScores[i]);をrank = iに変更すると、コードが簡素化され、パフォーマンスが向上します。

もしあれば、あなたの目標をさらに明確にする必要があります。

Answer 3

これは容易かつ効率的に組み合わせて行うことができる。

のArray.sort（アレイ）： https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

Array.BinarySearch（T []配列、T値）：

https://msdn.microsoft.com/en-us/library/2cy9f6wb(v=vs.110).aspx

これにより、（検索上の）O（ログn）のパフォーマンスが得られます。

これをLinqと組み合わせれば、かなり高速なアルゴリズムが得られます。

UPDATE：

私は申し訳ありませんが、昨日の夜眠りに落ちるました。

var sortedScores = Array.ConvertAll(data.Split(' '), int.Parse); 
Array.Sort(sortedScores); 

var ranks = aliceScore.Select(
    a => 
    { 
     var result = Array.BinarySearch(sortedScores, a); 
     if (result < 0) 
     { 
      //Did not find it in array 
      var index = ~result; 
      if (index > sortedScores.Length - 1) 
      { 
       //It's greater than all 
       return index; 
      } 
      else 
      { 
       //Return one up to position it after the larger value 
       return index++; 
      } 
     } 
     else 
     { 
      //Found it, return index 
      return result; 
     } 
    }); 

foreach (int rankFound in ranks) 
{ 
    Console.WriteLine("Rank: {0}", rankFound); 
} 

私はそれをローカルにテストし、それがコンソールを含む、あなたのデータを処理するために1.05秒を要した書き込み、時間経過計算私が増加しなければならなかった

Answer 4

のみ変更:-)：ここでは実装がありますパフォーマンスは内側のループが最後のループインデックスから継続していることを確認していました。

string[] scores_temp = data.Split(' '); 
int[] scores = Array.ConvertAll(scores_temp, Int32.Parse); 

string[] alice_temp = data2.Split(' '); 
int[] aliceScore = Array.ConvertAll(alice_temp, Int32.Parse); 

var distinctScores = scores.Distinct().ToList(); 
int rank = 0; 
int innerLoop = distinctScores.Count - 1; 
for (int j = 0; j <= aliceScore.Length-1; j++) 
{ 
    for (int i = innerLoop; i >= 0; i--) 
    { 
     innerLoop = i; 
     if (aliceScore[j] >= distinctScores[i]) 
     { 
      rank = i; 
     } 
     else if (aliceScore[j] < distinctScores[i]) 
     { 
      rank = i; 
      rank += 2; 
      break; 
     } 
    } 
    if (rank.ToString() == "0") { 
     Console.WriteLine(rank.ToString().Replace("0", "1")); 
    } else { 
     Console.WriteLine(rank); }; 
    } 
    Console.ReadLine(); 
} 

Answer 5

別の非リニアバージョンです。私はランク+ = 2が分からないので、おそらくこれはあなたの要求に正確ではありません。私はdata/score配列の要素を逆にしました。確かに、バイナリ検索方法ほど高速ではありませんが、コンソールアプリケーションではほんの数秒です。

public static void GetInputs() 
    { 
     string[] scores_temp = data.Split(' '); 
     var distinctScores = scores_temp.Distinct().ToArray(); 
     int[] scores = (Array.ConvertAll(distinctScores, Int32.Parse)).Reverse().ToArray(); 

     string[] alice_temp = data2.Split(' '); 
     int[] aliceScores = Array.ConvertAll(alice_temp, Int32.Parse); 

     int rank = 0; 
     for (int i = 0, j = 0; i < aliceScores.Length && j < scores.Length; ++i) 
     { 
      while (aliceScores[i] > scores[j]) 
       rank = j++; 
      Console.WriteLine(String.Format("Rank {0}: alice {1} -- Index {2}: score {3}", rank, aliceScores[i], j, scores[j])); 
     } 
     Console.ReadLine(); 
    }