for Schleife dauert zu viel Zeit zu beenden

Question

der folgende Code funktioniert gut. Das einzige Problem ist, wenn ich einen Array-Wert der Länge 200.000 gebe, dauert es zu lange, um ca. 1 Stunde abzuschließen. Unten ist mein Code.

Ich habe die Datendatei here, die Daten und Daten2 Zeichenfolge Werte enthält. Daten-Array ist in absteigender Reihenfolge angeordnet und Daten2 in aufsteigender Reihenfolge.

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

Sortiere sie, dann arbeite einfach mit indeces! Wenn Sie wissen, dass Ihre Arrays sortiert sind, können Sie die Position jedes aliceScore in distinctScores überprüfen. Dann werden Sie wissen, wie viele distinctScores sind nach oben oder unten, und tun, was Sie wollen.

Answer 2

Ersetzen rank = distinctScores.IndexOf(distinctScores[i]); mit rank = i würde Ihren Code vereinfachen und bessere Leistung geben.

Benötigen Sie weitere Erläuterungen zu Ihrem Ziel für andere Änderungen, falls vorhanden.

Answer 3

dies leicht und effizient mit einer Kombination aus durchgeführt werden kann:

Array.Sort (Array): https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

Array.BinarySearch (T [] array, T-Wert): https://msdn.microsoft.com/en-us/library/2cy9f6wb(v=vs.110).aspx

Dies gibt Ihnen O (log n) Leistung (auf der Suche).

Kombinieren Sie dies mit Linq und Sie haben sich einen ziemlich schnellen Algorithmus.

UPDATE:

Ich war einzuschlafen gestern Nacht sorry. Hier ist eine Implementierung:

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

ich es lokal getestet und es dauerte 1,05 Sekunden Ihre Daten zu verarbeiten, einschließlich der Konsole schreibt und die verstrichene Zeit Berechnung :-)

Answer 4

Die einzige Änderung, die ich tun musste, erhöhen Die Performance stellte sicher, dass die innere Schleife von ihrem letzten Schleifenindex fortfährt.

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

Hier ist eine andere nicht-linq Version. Ich bin mir nicht sicher über den Rang + = 2, also ist das vielleicht nicht genau für Ihre Anforderung. Ich habe die Elemente des Data/Scores-Arrays umgekehrt. Sicherlich nicht so schnell wie die binäre Suchmethode, aber nur ein paar Sekunden in einer Konsolen-App.

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