[Orolhawion]

Hallo zusammen,

ich sitze gerade über einer Aufgabe für die Uni und komme gerade nicht so recht weiter.

es ist folgernder Algorithmus gegeben:

int a[10] = { -1, 5, -2, 0, 1, 4, 6, -4, 3, -6 };
int max_sum=0;
int cur_sum=0;
for( i=0; i<10; ++i ) {
      cur_sum += a[i];
      if( cur_sum < 0 ) cur_sum=0;
      if( cur_sum > max_sum ) max_sum = cur_sum;
}

gesucht ist das ergebnis für max_sum. mit diesen zahlen bekomme ich das ergebnis 14, (wenn ich mich nicht verrechnet hab)

das problem soll parallelisiert werden, also auf mehrere rechner verteilt werden und dazu soll ich mir einen passenden algorithmus überlegen der das problem an sich löst, muss nicht unbedingt dieser algorithmus sein.

wie man leicht feststellen kann, sind reihenfolge vertauschen und irgendwo aufsplitten nicht sinnvoll, da das ergebnis für max_sum damit verfälscht würde.

daher habe ich mir folgendes überlegt: gesucht ist quasi eine liste, die für max_sum das selbe ergebnis liefert, wie meine ausgangsliste.

1. ich kann alle aufeinanderfolgenden zahlen mit gleichem vorzeichen addieren, ohne das ergebnis zu verfälschen. dieser schritt kann also parallelisiert werden. danach sammle ich die ergebnisse der einzelnen nodes ein und bekomme folgende liste:

int b[7] = { -1, 5, -2, 11, -4, 3, -6 };
// ergebnis immernoch 14

wenn man sich die liste genauer ansieht fällt auf, dass sie alterniert (bzgl. des vorzeichens) weiterhin fällt auf, dass ich führende und schließende zahlen <= 0 von der listen entfernen kann, weil sie das ergebnis nicht für max_sum beeinflussen -> wieder gekürzt, wenn auch nicht parallel.

dann erhalte ich folgende liste:

int c[5] = { 5, -2, 11, -4, 3};
// ergebnis immernoch 14

nun kann ich unter bestimmten voraussetzungen pärchen bilden.
ich nehme die 5 als erstes und erhalte als temporäre max_sum=5. dann stelle ich fest, dass die -2 und die 11 addiert 9 ergeben und die -4 und die 3 zusammen -1. daraus erhalte ich folgende liste:

int d[3] = { 5, 9, -1};
// ergebnis immernoch 14

die -1 fällt wieder weg, weil sie am ende steht:

int e[2] = { 5, 9 };
// ergebnis immernoch 14

und letztendlich kommt wieder 14 raus.

in c darf ich -2 und 11 aber nur addieren, weil |-2| < |max_sum|. sonst würde das nicht funktionieren.

zusammenfassend kann ich also sagen, dass ich weiß wie man nicht-alternierende listen parallelisiert vereinfachen kann, und meine frage an euch lautet nun, wie kann ich die alternierende liste (also b) parallelisieren? und geht das überhaupt? da hakts gerade irgendwie..

[Artemis]

Zitat von Orolhawion

dann erhalte ich folgende liste:

int c[5] = { 5, -2, 11, -4, 3};
// ergebnis immernoch 14

nun kann ich unter bestimmten voraussetzungen pärchen bilden.
ich nehme die 5 als erstes und erhalte als temporäre max_sum=5. dann stelle ich fest, dass die -2 und die 11 addiert 9 ergeben und die -4 und die 3 zusammen -1. daraus erhalte ich folgende liste:

int d[3] = { 5, 9, -1};
// ergebnis immernoch 14

Dieser Schritt geht aber nur, wenn die negative Zahl kleiner ist, als das Ergebnis von vorher - hierbei ginge es nicht:

int c[5] = { 5, -6, 11, -4, 3};

[Orolhawion]

Zitat von Artemis

Dieser Schritt geht aber nur, wenn die negative Zahl kleiner ist, als das Ergebnis von vorher - hierbei ginge es nicht:

int c[5] = { 5, -6, 11, -4, 3};

Zitat von Orolhawion

in c darf ich -2 und 11 aber nur addieren, weil |-2| < |max_sum|. sonst würde das nicht funktionieren.

das sagte ich bereits..

[MrNiceGuy]

Ich habe das zwar jetzt nur überflogen und verstehe auch leider nichts von Parallelisierung, aber hast du einen Fehler im Code oder rechne ICH falsch?

int a[10] = { -1, 5, -2, 0, 1, 4, 6, -4, 3, -6 };
int max_sum=0;
int cur_sum=0;
for( i=0; i<10; ++i ) {
      cur_sum += a[i];
      if( cur_sum < 0 ) cur_sum=0;
      if( cur_sum > max_sum ) max_sum = cur_sum;
}

Ich komme auf ein Ergebnis von 7, nicht 14! Oder ist das "+=" nicht korrekt? Denn dann wäre die Reihenfolge meiner Meinung nach folgende:

-1 -> cur_sum < 0 -> 0
5 -> 0+5 -> 5
-2 -> 5+(-2) -> 3
0 -> 3+0 -> 3
1 -> 3+1 -> 4
4 -> 4+4 -> 8
6 -> 8+6 -> 14
-4 -> 14+(-4) -> 10
3 -> 10+3 -> 13
-6 -> 13+(-6) -> 7

Die Regel, dass bei negativen Zahlen in cur_sum dieses auf 0 gesetzt wird erfolgt ja nur ein Mal am Anfang!? Von daher verstehe ich gerade nicht, wie du auf 14 kommst!?

[Orolhawion]

Zitat von MrNiceGuy

Ich habe das zwar jetzt nur überflogen und verstehe auch leider nichts von Parallelisierung, aber hast du einen Fehler im Code oder rechne ICH falsch?

nicht wirklich, du betrachtest nur nicht max_sum sondern cur_sum.

Zitat von MrNiceGuy

Ich komme auf ein Ergebnis von 7, nicht 14! Oder ist das "+=" nicht korrekt? Denn dann wäre die Reihenfolge meiner Meinung nach folgende:

-1 -> cur_sum < 0 -> 0
5 -> 0+5 -> 5
-2 -> 5+(-2) -> 3
0 -> 3+0 -> 3
1 -> 3+1 -> 4
4 -> 4+4 -> 8
6 -> 8+6 -> 14
-4 -> 14+(-4) -> 10
3 -> 10+3 -> 13
-6 -> 13+(-6) -> 7

Die Regel, dass bei negativen Zahlen in cur_sum dieses auf 0 gesetzt wird erfolgt ja nur ein Mal am Anfang!? Von daher verstehe ich gerade nicht, wie du auf 14 kommst!?

nochmal genau den code ansehen. max_sum wird nie verringert, daher bleibt es bei 14.
es ist C-Code. x += y; ist gleichbedeutend mit x = x+y;

[MrNiceGuy]

Ups, alles klar, dann stimmt das natürlich doch, ich hatte nur auf cur_sum geachtet

EDIT: Was += bedeutet war mir schon klar, ich habe nur nicht beachtet, dass er explizit von max_sum sprach...

[mepeisen]

Mal von der Sache her macht das Parallelisieren in diesem Fall keinerlei Sinn, da sich die Performance nicht steigert. Aber wie dem auch sei.



Ein anderer Ansatz wäre, nicht den Algorithmus selbst zu verwenden um zu parallelisieren, sondern Teilaufgaben daraus. Beispielsweise das Zusammenfassen von zwei aufeinander folgende positive Zahlen. Jeder Node beginnt bei Position X und schaut, ob dort aufeinander folgende positive Zahlen sichtbar sind. Als Ergebnis kommt dann zurück: Ja/Nein (ggf. auch die Summer der beiden zusammengefassten Zahlen)

Sprich: Das was du oben beschrieben hast, die Teilschritte um die Liste zu verkürzen, die kannst du durch deine Nodes vorberechnen lassen. Wenn sich nichts zusammenfassen lässt, sind deine Nodes überflüssig. Wenn sich aber was zusammenfassen lässt, kann dein Node das tun in der Hoffnung, dass der Master mit seinem Algorithmus noch nicht so weit ist.
Sprich: Die Nodes erleichtern dem Master damit die Arbeit, denn je größer die Liste ist, desto eher werden die Nodes dieselbige verkürzen.



Zweite Alternative: Du lässt jeden Node an einer neuen Position auf Verdacht losrechnen. Beispiel:
Node 0 beginnt bei Index 0.
Node 1 beginnt bei Index 1
Node 2 beginnt bei Index 2 usw.
Sobald deine Nodes bei folgender Konstellation ankommen:

if( cur_sum < 0 ) cur_sum=0;

(btw. ich würde dies auf <= 0 ändern. Sieht im ersten Moment sinnlos aus aber wenn du diese Bedingung als Abbruchbedingung für einen Node definierst, macht das wieder Sinn)
brechen sie ihre Arbeit ab und haben ein Teilergebnis. Gleichzeitig weißt du, dass du ab dem nächsten Index wieder ein neues Teilergebnis brauchst.
Also etwa so:
10 Array-Elemente -> 10 Nodes -> 10 Teilergebnisse
Der erste Node rechnet die erste Zahl, bricht ab. Teilergebnis 0.
Der zweite Node rechnet die zweite Zahl bis zum Ende. Teilergebnis 14.
Alle übrigen Nodes rechnen zwar, werden aber ignoriert, da der zweite bereits bis zum Ende rechnete.

Das kannst du noch feintunen, dass der zweite Node Teilergebnisse der übrigen Nodes auch berücksichtigt, um selbst nicht zu viel rechnen zu müssen. Das ist aber ein Timing-Problem und erst bei hunderttausenden von Zahlenreihen sinnvoll.

Würde der zweite Node irgendwann bei der 5. Zahl oder so abbrechen (weils negativ oder 0 wird) wüsstest du, wieviele Nodes nicht berücksichtigt werden müssen. Und du hast dann sofort einen weiteren Node, der ab dieser fünften Zahl loslegt und dir die neuen Teilergebnisse liefert.

[Orolhawion]

Zitat von mepeisen

Mal von der Sache her macht das Parallelisieren in diesem Fall keinerlei Sinn, da sich die Performance nicht steigert. Aber wie dem auch sei.

naja, das ist wohl abhängig von dem was pro iteration so passiert, bei simplem addieren, wie in diesem fall, hast du natürlich recht.

danke für deine antworten.

ich habe noch ein wenig recherchiert und es handelt sich offenbar um Kadane's Algorithmus Dazu gibt es ein ellenlanges paper von der uni cantebury. das was in diesem paper steht sieht vielversprechend aus, ich setze mich da mal ran. :)

[mepeisen]

Jetzt wo dus verlinkt hast. Dem gleichen Problem liegt ein Div zugrunde.
*sich-selbst-an-die-Stirn-fasst*

Nun weiß ich auch, warum du so einen komischen Algorithmus hast :)