Ich denke, ich brauche Parallel.Für dieses Nest zu beschleunigen ... Aber wie?

Question

Ich erstelle eine Funktion, um eine Liste von Baseballspielern durchzublättern, um jede mögliche Kombination von Aufstellungen zu erstellen.

Ich habe Listen von Spielern für jede Position. Ie, Pitcher, Catcher, 1st-Base usw. ...

Die Herausforderung besteht darin, dass es Milliarden von Kombinationen gibt, also ist es ein langsamer Prozess. Ich habe gelesen, dass ich System.Threading für parallele Schleifen verwende, aber ich habe keine Erfahrung damit, und die Beispiele, die ich finden kann, sehen viel einfacher aus (im Allgemeinen zeigen sie eine verschachtelte Schleife), und Ich habe Probleme zu verstehen, wie man es mit mehreren verschachtelten Schleifen anwendet.

An der innersten geschachtelten Schleife ist, wo ich zu sehen bin testen, ob die Aufstellung mit der Methode validateAndAddToTopLineups gültig ist, das die Aufstellung nimmt, um eine Liste der gültigen Aufstellungen durch Bezugnahme eingeschlossen, und 2 andere Parameter, die konstant Grenzen sind, dass werden verwendet, um zu bestimmen, ob die Aufstellungen gültig sind oder nicht.

Sollte ich diesen Prozess anders angehen, oder kann mir jemand helfen, dies zu übersetzen, um die Parallel.For-Methode zu verwenden?

Hier ist meine verschachtelte Schleife, unten:

for (int p = 0; p < _myPitchers.Count; p++) //For each pitcher 
    for (int c = 0; c < _myCatchers.Count; c++) //For each catcher 
     for (int b1 = 0; b1 < _myBase1.Count; b1++) //For each 1st base player 
      for (int b2 = 0; b2 < _myBase2.Count; b2++) //For each 2nd base player 
       for (int b3 = 0; b3 < _myBase3.Count; b3++) //For each 3rd base player 
        for (int ss = 0; ss < _myShortStops.Count; ss++) //For each shortstop 
         for (int oF = 0; oF < OutfielderCombos.Count; oF++) //For each outfielder lineup combination 
         { 
          Lineup testLineup = new Lineup(); //create new lineup 
          testLineup.Pitcher1 = _myPitchers[p];     //pitcher 1 
          //testLineup.Pitcher1 = _myPitchers[p2];    //pitcher 2 
          testLineup.Catcher = _myCatchers[c];     //catcher 
          testLineup.Base1 = _myBase1[b1];      //1st base 
          testLineup.Base2 = _myBase2[b2];      //2nd base 
          testLineup.Base3 = _myBase3[b3];      //3rd base 
          testLineup.Shortstop = _myShortStops[ss];    //short stop 
          testLineup.Outfield1 = OutfielderCombos[oF].Outfield1; //outfielder 1 
          testLineup.Outfield2 = OutfielderCombos[oF].Outfield2; //outfielder 2 
          testLineup.Outfield3 = OutfielderCombos[oF].Outfield3; //outfielder 3 
           //determine if lineup is valid, and if so add it to List<Lineup> _ValidLineups 
          validateAndAddToTopLineups(testLineup, ref _ValidLineups, ref SalaryCap, ref SameTeamLimit); 
         } 

Answer 1

Sie haben ein Kartesisches Produkt erhalten. Es ist ein riesiges ein, aber das ist, wie Sie es tun würde:

var enumerator = 
    from p in _myPitchers 
    from c in _myCatchers 
    from b1 in _myBase1 
    from b2 in _myBase2 
    from b3 in _myBase3 
    from ss in _myShortStops 
    from of in OutfielderCombos 
    select new Lineup 
     { 
      Pitcher1 = p, 
      Catcher = c, 
      Base1 = b1, 
      Base2 = b2, 
      Base3 = b3, 
      Shortstop = ss, 
      Outfield1 = of.Outfield1, 
      Outfield2 = of.Outfield2, 
      Outfield3 = of.Outfield3 
     }; 

Dann können Sie durch diese Kombinationen parallel aufzählen:

var result = enumerator.AsParallel().Where(l => IsValid(l)).ToArray(); 

Sie werden Ihre Validierung müssen ändern geben eine boolesche Methode IsValid(), aber dies wird parallel durch Ihr riesiges Set.

Answer 2

Wird eine BlockingCollection https://msdn.microsoft.com/en-us/library/dd997371(v=vs.110).aspx Ihnen helfen? Außerhalb Ihrer Schleife erstellen Sie die Sammlung und eine Reihe von Aufgaben, die versuchen, einen Eintrag aus der Sammlung zu ziehen. Jede Aufgabe sollte warten, bis eine Aufgabe verfügbar ist, sie ausführen und dann auf eine andere warten. Bei Ihrem Aufruf von validateAndAddToTopLineups würden Sie versuchen, eine Aufgabe hinzuzufügen. Sie können Aufgaben bis zu Ihrem BlockingCollection-Limit hinzufügen. https://msdn.microsoft.com/en-us/library/dd267312(v=vs.110).aspx. Ich hoffe, du gewinnst.

Answer 3

Sowohl die Blocking-Sammlung als auch die Enumerator-Ansätze sind großartig, was bedeutet, dass ich sie zumindest zum Laufen brachte.

Ich konnte sie nicht mit meinen ursprünglichen verschachtelten Einzel-Thread-Loops vergleichen oder vergleichen, da ich erkannt habe, dass es hier einfach viele Wege zu vielen Wiederholungen gibt. Ich habe es sogar auf einer schnellen virtuellen Azure-Maschine mit 8 Kernen ausprobiert und es ist immer noch brutal.

Ich berechnete die Anzahl der Iterationen, zugeordnet zu einem Uint64 und die Zahl ist unverständlich. 18.446.744.071.628.531.200 oder 18 Trillionen! Etwas mehr als die ursprünglichen Milliarden, dachte ich.

Danke für die Hilfe und die Ideen, die blockierenden Sammlungen sind neato, und wirklich ziemlich einfach zu implementieren!

Wenn jemand einen Vorschlag hat, wie ich mein Problem auf eine überschaubare Größe reduzieren oder es anders angehen kann, lassen Sie es mich wissen!

... Aktualisieren ... FYI: Ich konnte dies mit einem linearen Optimierungsalgorithmus lösen. Ich habe lpsolve verwendet, die in jeder Programmierung IDE oder Sprache verwendet werden kann. Es hat die optimale Lösung in weniger als einer Sekunde gefunden!