Parallel Algorithmus zur Berechnung der maximalen Differenz

Question

Ich implementiere derzeit einen parallelen Algorithmus zur Berechnung der maximalen Differenz zwischen zwei Elementen, so dass die kleinere Zahl vor der größeren Zahl erscheint. Ich verwende die parallel_invoke von der tbb-Bibliothek, um dies zu erreichen. Meine Implementierung ist wie folgt

int calculateMaxDiff(int *src, int start, int end){ 
    int maxVal = -1; 
    int maxRight = src[end -1]; 

    for(int i = end - 2; i >= start; i--){ 
     if(src[i] > maxRight){ 
      maxRight = src[i]; 
     }else{ 
      int diff = maxRight - src[i]; 
      if(diff > maxVal){ 
       maxVal = diff; 
      } 
     } 
    } 


    return maxVal; 
}; 

int compute_max_diff(int *src, int size) 
{ 
    int half1_diff; 
    int half2_diff; 

    parallel_invoke([&]{ half1_diff = calculateMaxDiff(src, 0, size/2);}, 
        [&]{ half2_diff = calculateMaxDiff(src, size/2, size);}); 


    int maxDiff = half1_diff + half2_diff; 

    return maxDiff; 
} 

nun für das obige Codesegment i die folgenden als Probe Array bin mit

int src[] = {12, 9, 18, 3, 7, 11, 6, 15, 6, 1, 10}; 
int size = 11; 

Für das obige Beispiel die Ausgabe oder maximale Differenz muss 12 sein, aber ich scheine 18. Ich habe den Algorithmus sequentiell ausgeführt und das erwartete Ergebnis erhalten. Aber sobald ich parallel_invoke vorstellen kann ich nicht scheinen, das richtige Ergebnis zu bekommen.

Answer 1

Sie erhalten 18 als Summe von 9 aus der ersten Hälfte (das ist 18-9) und 9 aus der zweiten Hälfte, die (15-6) ist. Wenn Sie sequentiell arbeiten, nehme ich an, dass Sie calculateMaxDif(src, 0, size) aufrufen, was gut funktionieren würde, weil es alle Elemente des Arrays durchläuft. Wenn Sie jedoch 2 Funktionen in Hälften aufrufen, erreicht es nicht das benötigte Paar (3, 15), weil 3 in der ersten Hälfte und 15 in einer anderen Hälfte ist.