Wo ist wahrscheinlich der Performance Bug hier?

Question

Viele der Testfälle sind zeitlich begrenzt. Ich habe sichergestellt, dass ich überall faule Bewertungen verwende, lineare (oder bessere) Routinen usw. Ich bin schockiert, dass dies immer noch nicht den Leistungs-Benchmarks entspricht.

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 

class Mine 
{ 
    public int Distance { get; set; } // from river 
    public int Gold { get; set; } // in tons 
} 

class Solution 
{ 
    static void Main(String[] args) 
    { 
     // helper function for reading lines 
     Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse); 

     int[] line1 = LineToIntArray(Console.ReadLine()); 
     int N = line1[0], // # of mines 
      K = line1[1]; // # of pickup locations 

     // Populate mine info 
     List<Mine> mines = new List<Mine>(); 
     for(int i = 0; i < N; ++i) 
     { 
      int[] line = LineToIntArray(Console.ReadLine()); 
      mines.Add(new Mine() { Distance = line[0], Gold = line[1] }); 
     } 

     // helper function for cost of a move 
     Func<Mine, Mine, int> MoveCost = (mine1, mine2) => 
      Math.Abs(mine1.Distance - mine2.Distance) * mine1.Gold; 

     int sum = 0; // running total of move costs 

     // all move combinations on the current list of mines, 
     // given by the indicies of the mines 
     var indices = Enumerable.Range(0, N); 
     var moves = from i1 in indices 
        from i2 in indices 
        where i1 != i2 
        select new int[] { i1, i2 }; 

     while(N != K) // while number of mines hasn't been consolidated to K 
     {   
      // get move with the least cost 
      var cheapest = moves.Aggregate(
       (prev, cur) => MoveCost(mines[prev[0]],mines[prev[1]]) 
            < MoveCost(mines[cur[0]], mines[cur[1]]) 
           ? prev : cur 
      ); 

      int i = cheapest[0], // index of source mine of cheapest move 
       j = cheapest[1]; // index of destination mine of cheapest move 

      // add cost to total 
      sum += MoveCost(mines[i], mines[j]); 

      // move gold from source to destination   
      mines[j].Gold += mines[i].Gold; 

      // remove from moves any that had the i-th mine as a destination or source 
      moves = from move in moves 
        where move[0] == i || move[1] == i 
        select move; 

      // update size number of mines after consolidation 
      --N;  
     } 

     Console.WriteLine(sum); 
    } 
} 

Answer 1

Eine faule Auswertung wird nicht dazu führen, dass schlechte Algorithmen besser funktionieren. Es wird nur Verzögerung, wenn diese Leistungsprobleme Sie beeinflussen werden. Was für eine faule Bewertung kann helfen, ist die Komplexität des Platzes, d. H. Verringerung der Menge an Speicher, die Sie benötigen, um Ihren Algorithmus auszuführen. Da die Daten träge erzeugt werden, haben Sie nicht (notwendigerweise) alle Daten gleichzeitig im Speicher.

Wenn Sie sich jedoch auf faule Auswertungen verlassen, um Ihre Probleme mit Platz- (oder Zeit-) Komplexität zu beheben, können Sie leicht in den Fuß schießen. Schauen Sie den folgenden Beispielcode:

var moves = Enumerable.Range(0, 5).Select(x => { 
    Console.WriteLine("Generating"); 
    return x; 
}); 

var aggregate = moves.Aggregate((p, c) => { 
    Console.WriteLine("Aggregating"); 
    return p + c; 
}); 

var newMoves = moves.Where(x => { 
    Console.WriteLine("Filtering"); 
    return x % 2 == 0; 
}); 

newMoves.ToList(); 

Wie Sie sehen können, sowohl die aggregate und die newMoves verlassen sich auf die träge moves enumerable ausgewertet. Da die ursprüngliche Anzahl von moves 5 ist, werden wir 4 "aggregierende" Zeilen in der Ausgabe und 5 "Filtering" Zeilen sehen. Aber wie oft erwarten Sie, dass "Generating" in der Konsole erscheint?

Die Antwort ist 10. Das ist, weil moves ein Generator ist und wird träge ausgewertet. Wenn mehrere Orte es anfordern, wird für jedes ein Iterator erstellt, was letztendlich bedeutet, dass der Generator mehrere Male ausgeführt wird (um unabhängige Ergebnisse zu erzeugen).

Dies ist nicht unbedingt ein Problem, aber in Ihrem Fall wird es sehr schnell zu einem. Angenommen, wir gehen über Beispielcode mit einer weiteren Aggregationsrunde hinaus. Dieses zweite Aggregat wird newMoves verbrauchen, was wiederum das Original moves verbrauchen wird. Also, um zu aggregieren, werden wir den ursprünglichen moves Generator und den newMoves Generator erneut ausführen. Und wenn wir eine weitere Ebene der Filterung hinzufügen würden, würde die nächste Aggregationsrunde drei gekoppelte Generatoren durchlaufen, die den ursprünglichen Generator erneut ausführen würden.

Da Ihr Original moves Generator eine zählbare der quadratischen Größe schafft, und hat eine tatsächliche Komplexität Zeit von O(n²), dann ist dies ein tatsächliches Problem. Mit jeder Iteration fügen Sie eine weitere Filterungsrunde hinzu, die linear zur Größe des aufzählbaren Werts moves ist, und Sie verbrauchen das Enumerable tatsächlich vollständig für die Aggregation. Sie enden also mit , was schließlich die Summe n^j für j sein wird, beginnend bei 2 bis zu N-K. Das ist eine sehr schlechte Zeit Komplexität, und alles nur, weil Sie versucht haben, Speicher durch die Auswertung der Bewegungen träge zu speichern.

Der erste Schritt, um dies besser zu machen, ist eine faule Auswertung zu vermeiden. Sie durchlaufen ständig moves und filtern es, also sollten Sie es im Speicher haben. Ja, das bedeutet, dass Sie ein Array mit quadratischer Größe haben, aber Sie brauchen nicht mehr als das. Dies begrenzt auch die Zeitkomplexität, die Sie haben. Ja, Sie müssen die Liste immer noch in linearer Zeit filtern (also O(n²) da die Größe n² ist) und Sie tun dies innerhalb einer Schleife, so dass Sie mit kubischer Zeit enden (O(n³)), aber das wäre schon Ihre obere Grenze (iterierend die Liste eine konstante Anzahl von Malen innerhalb der Schleife wird nur die Zeit Komplexität um eine Konstante erhöhen, und das ist egal).

Sobald Sie das getan haben, sollten Sie Ihr ursprüngliches Problem betrachten, darüber nachdenken, was Sie tatsächlich tun. Ich glaube, dass Sie die Rechenkomplexität wahrscheinlich weiter reduzieren können, wenn Sie die Informationen verwenden, die Sie besser haben, und Datenstrukturen (z. B. Hash-Sätze oder Diagramme, in denen die Umzugskosten bereits gespeichert sind) verwenden, die Sie bei der Filterung und Aggregation unterstützen. Ich kann Ihnen keine genauen Ideen geben, da ich Ihr ursprüngliches Problem nicht kenne, aber ich bin sicher, dass Sie etwas tun können.

Schließlich, wenn Sie Leistungsprobleme haben, denken Sie immer daran, Ihren Code zu profilieren. Der Profiler wird Ihnen sagen, welche Teile Ihres Codes am teuersten sind, damit Sie eine klare Vorstellung davon bekommen, was Sie optimieren sollten und worauf Sie sich bei der Optimierung nicht konzentrieren müssen (da die Optimierung bereits schneller Teile nicht hilft) komme schneller).