Threading verschachtelte foreach-loops?

Question

Hello!

Ich versuche ein Programm zu erstellen, das die beste Punktzahl aus einer Vielzahl von Elementen mit Bruteforce berechnet. Und ich glaube, dass die Geschwindigkeit, mit der dies berechnet wird, auf Systemen mit Multicore-CPUs mit Hilfe von Threading verbessert werden kann. Korrigiere mich, wenn ich falsch liege. Aber wie erreiche ich das?

Hier ist ein Teil meines Codes, und es macht den Job gut (kein Threading).

private double _bestScore = 0.0; 

private void BruteForce() 
{ 
    foreach (Stats head in _heads) 
    foreach (Stats chest in _chests) 
     foreach (Stats leg in _legs) 
     foreach (Stats feet in _feets) 
     { 
      int stamina = head.sta + chest.sta + leg.sta + feet.sta; 
      int power = head.power + chest.power + leg.power + feet.power; 
      int armor = head.armor + chest.armor + leg.armor + feet.armor; 
      int hit = head.hit + chest.hit + leg.hit + feet.hit; 

      double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor; 

      if (total > _bestScore && hit >= 100) 
      { 
      _bestScore = total; 

      // Store best setup for output when done with bruteforce 
      _bestHead = head; 
      _bestChest = chest; 
      _bestLeg = leg; 
      _bestFeet = feet; 
      } 
     } 
} 

Also, gibt es sowieso, um dies mit Threading zu verbessern?

Edit: Typo korrigiert und aktualisiert, um einen anderen stat, Treffer zu enthalten. Treffer muss 100 erreichen, um ein möglicher Teil des "besten Ergebnisses" zu sein. Dies ist der Fall, da ich nicht jeden einzelnen Slot überprüfen kann, um die beste Ausrüstung zu finden. Treffer ist ein sehr wichtiger Wert bis 100, aber jeder Punkt nach 100 ist nutzlos. Auch dieser Teil meines Codes hat viel mehr foreach-Schleifen (28 statt 4). So ist die Anzahl der Iterationen eine Menge. Jede Liste (_heads, _chests usw.) enthält jedoch normalerweise maximal 2 Elemente.

Answer 1

Wenn Sie die einfache Möglichkeit des Hinzufügens von Multithreading wollen, schauen Sie in die Parallel Extensions for .NET. Aus Leistungsgründen möchten Sie nur einen Parallel.For() -Aufruf auf die äußerste Schleife setzen.

Answer 2

Sie werden wahrscheinlich feststellen, dass das Hinzufügen von mehreren Threads die Dinge verlangsamen wird. Ist diese Berechnung sehr langsam? Wie hoch sind Ihre erwarteten Durchschnittswerte für Kopf, Brust, Beine und Füße?

Sie sind vielleicht besser dran, die höchsten Werte für jeden der Köpfe, Truhen usw. zu finden und den Rest zu verwerfen, um die beste Kombination dieser ausgewählten zu finden.

Answer 3

Ich bin mir ziemlich sicher, dass dies es tun, keine Testdaten mit oder einen Compiler Hand macht mich nicht zu 100% sicher:

private void BestItems() 
{ 
    _bestHead = GetBestItem(_heads); 
    _bestChest = GetBestItem(_chests); 
    _bestLeg = GetBestItem(_legs); 
    _bestFeet = GetBestItem(_feets); 
} 


private Stats GetBestItem(List<Stats> items) 
{ 
    double best = 0.0; 
    Stats result = null; 

    foreach stats item in items 
    { 
     double total = item.stamina * _scaleSta + item.power * _scalePower + item.armor * _scaleArmor; 

     if (total > best) 
     { 
      result = item; 
     } 
    } 

    return result; 
} 

Edit:

Schritte:

1. Erstellen Sie eine Liste für jeden Steckplatz in der Reihenfolge der wichtigsten stat (kleinste zuerst)
2. Durchschleifen mit eine Art Gewichtung, um die kleinsten Trefferwerte zu finden, die deine Trefferwertung erfüllen. (yuo wird das pro Steckplatz für meinen nächsten Schritt benötigen)
3. Für jeden Slot wählen Sie den Punkt mit den besten Werten, die die Mindesttreffer-Werte für die Slots erfüllen.

Sie werden eine Menge von Schleifen nacheinander brauchen, aber es ist besser als 2^28 Ich denke: p

Edit2: Auch hier noch keine Compiler hier ... aber dies funktionieren könnte . Sie werden allerdings mit einem Eimer Belastung von Fäden am Ende ...

Für Anspinnen und see here (msdn) warten (auf Mutex schauen, Monitor, Manual, Autoreset)

private void BruteForce() 
{ 

    var threads = new List<Thread>; 
    foreach (Stats head in _heads) 
    foreach (Stats chest in _chests) 
     foreach (Stats leg in _legs) 
     foreach (Stats feet in _feets) 
     { 
      if (threads.Count <= 2) 


      thread worker = new thread(addressof Process, new object() {head, chest, leg, feet, ...}); 
      worker.start(); 
      threads.add(worker); 
     } 

    foreach (Thread t in threads) 
     t.join(); //this might not be the best as it might make the main thread wait for each thread one after the other, not when all finished. A manual/auto reset is probably better here. 
} 


private void Process(params...) 
{ 

    int stamina = head.sta + chest.sta + leg.sta + feet.sta; 
    int power = head.power + chest.power + leg.power + feet.power; 
    int armor = head.armor + chest.armor + leg.armor + feet.armor; 
    int hit = head.hit + chest.hit + leg.hit + feet.hit; 

    double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor; 

    lock _bestscore 
    { 
     if (total > _bestScore && hit >= 100) 
     { 
      _bestScore = total; 

      // Store best setup for output when done with bruteforce 
      _bestHead = head; 
      _bestChest = chest; 
      _bestLeg = leg; 
      _bestFeet = feet; 
     } 
    } 
} 

EDIT 4:, die noch Raten hat keinen Compiler in seiner Nähe? Etwas in dieser Richtung sollte sicherstellen, dass Sie nur 2 Fäden an irgendeinem Punkt am Leben haben.

var threads = new Dictionary<Guid, Thread>; 

private void BruteForce() 
{ 
    foreach (Stats head in _heads) 
    foreach (Stats chest in _chests) 
     foreach (Stats leg in _legs) 
     foreach (Stats feet in _feets) 
     { 
      while (threads.Count >= 2) {} //im sure thread.join or equivelent can do this instead of a nasty loop :p 

      var guid = Guid.NewGuid(); 
      thread worker = new thread(addressof Process, new object() {guid, head, chest, leg, feet, ...}); 
      worker.start(); 
      threads.add(guid, worker); 
     } 

    foreach (Thread t in threads) 
     t.join(); //this might not be the best as it might make the main thread wait for each thread one after the other, not when all finished. A manual/auto reset is probably better here. 
} 

private void Process(params...) 
{ 
    int stamina = head.sta + chest.sta + leg.sta + feet.sta; 
    int power = head.power + chest.power + leg.power + feet.power; 
    int armor = head.armor + chest.armor + leg.armor + feet.armor; 
    int hit = head.hit + chest.hit + leg.hit + feet.hit; 

    double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor; 

    lock _bestscore 
    { 
     if (total > _bestScore && hit >= 100) 
     { 
      _bestScore = total; 

      // Store best setup for output when done with bruteforce 
      _bestHead = head; 
      _bestChest = chest; 
      _bestLeg = leg; 
      _bestFeet = feet; 
     } 
    } 

    _threads.remove(guid) 
} 

Answer 4

Eine Lösung für dieses Problem besteht darin, einige der Schleifen zu verengen und so einige Arbeitselemente zu erstellen, die parallel verarbeitet werden können. Etwas wie folgt aus:

private struct Stat 
{ 
    int sta; 
    int power; 
    int armor; 
    int hit; 
}; 
private List<Stat[]> workItems = new List<Stat[]>(); 
private const int NUMBER_OF_CPUS = 4; 

private void BruteForce() 
{ 

    //create some work load to split into separate threads 
    //we do this by unnesting the first 3 loops. 
    //maybe more unnesting is needed to get some more work items 
    //for thread to process 
    //at least one item per thread/CPU makes sense 
    foreach (Stats head in _heads) 
     foreach (Stats chest in _chests) 
     foreach (Stats leg in _legs) 
     { 
      this.workItems .Add(new Stat[3] { head, chest, leg }); 
     } 

Als nächstes würde, dass die Arbeitselemente in Stücke zu zerlegen, die von einem einzigen Thread verarbeitet werden kann. Sie würden eine Anzahl von Threads auswählen, die der Anzahl der CPU-Kerne entspricht. Ihre Thread-Funktion hätte mindestens einen Parameter, der die Arbeitselemente der Threads bereitstellt.

Der Beginn der Thread-Funktion könnte wie folgt aussehen:

private void Process(object param) 
     { 
      List<Stat[]> threadWorkitems = (List<Stat[]>)param; 

      foreach (Stat workItem in threadWorkitems) 
      { 
       Stats head = threadWorkitems[0]; 
       Stats chest = threadWorkitems[1]; 
       Stats leg = threadWorkitems[2]; 

       foreach (Stats feet in _feets) 
       { 
        int stamina = head.sta + chest.sta + leg.sta + feet.sta; 
        int power = head.power + chest.power + leg.power + feet.power; 
        int armor = head.armor + chest.armor + leg.armor + feet.armor; 
        int hit = head.hit + chest.hit + leg.hit + feet.hit; 

        double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor; 

        if (total > _bestScore && hit >= 100) 
        { 

Was in diesem Snippet fehlt, ist, dass Sie die besten Ergebnisse aller Threads zu sammeln, und sie danach vergleichen Sie die aktuell besten Satz zu finden .

Ich hoffe, dies gibt ein paar Hinweise.

Grüße