Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Das kaputte (¼) Osterei
Thema eröffnet 2020-04-01 10:31 von viertel
Seite 3   [1 2 3 4 5 6]   6 Seiten
Autor
Kein bestimmter Bereich * Das kaputte (¼) Osterei
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.80, eingetragen 2020-04-20

\quoteon(2020-04-20 19:25 - StrgAltEntf in Beitrag No. 78) Aber hier wird lediglich an einem vergleichbar winzigen Detail optimiert, das sich sicher nicht in dem Maße auf die Gesamtlaufzeit durchschlägt. Deshalb meine Frage danach, was es letztlich gebracht hat. \quoteoff Auf meinem Netbook (und nur auf dem habe ich das probiert) kam mit beiden Schritten eine Laufzeiteinsparung im Fall n=12 von 5 auf 4 Minuten heraus. \quoteon Das gleiche sehe ich übrigens für den nun betrachteten Sonderfall n = 2. Da wurde so viel Code zusätzlich erzeugt, der das ganze Programm unübersichtlich macht und potenziell Fehler erzeugen kann. Auch hier die Frage: Was hat es letztlich gebracht? \quoteoff Hier kam ich auf ein paar der eben genannten 20%, ca. 5%. Den Code kann man natürlich schöner schreiben, i.W. durch eine inline-Funktion, die die 6 verbleibenden Zahlen in die beiden solution-Tripel schreibt. Das ist bei Weitem der zeilenmäßig größte Code-Bestandteil. Was die eigentliche "Intelligenz" der n=2-Betrachtung betrifft, so bitte ich gern ums Nachrechnen, dass keine mögliche Zerlegung übersehen wurde. Da hier alle Möglichkeiten, die eben nicht zu Lösungen führen können, direkt "von Hand" weggestrichen wurden, fallen ein paar sonst durchgeführte Überprüfungen (mit definitivem Ergebnis) weg. Insofern sollte das schon sinnvoll sein. \quoteon Der früher einmal gemachte Vorschlag, die Prüfung sum1 > sum2 nur für kleinere n durchzuführen, habe ich ausprobiert. Es konnte die Laufzeit leider nicht merklich verbessern. \quoteoff Das ist interessant: Wo schlägt denn diese Auswertung an, d.h., in welcher Rekursionstiefe wird hier der Baum beschnitten? Wenn man das weiß, dann kann man auch besser optimieren... \quoteon Ebenso hat es die Laufzeit nicht messbar verbessert, die Zuweisung der Variablen solution erst nach einem erfolgreichen Test in reduce durchzuführen. \quoteoff Das glaube ich mittlerweile auch: Was man einspart, ist ja nur das Schreiben dieses einen Tripels im Fall eines Fehlschlags. Das passiert aber eben deutlich seltener, als sich der Baum dann zu einzelnen Partitionen auffächert. \quoteon Von hyperG kam noch der Vorschlag, die rekursive Suche durch eine andere, nicht-rekursive Suche zu ersetzen, die dann schneller ist. Ich weiß aber nicht, wie das aussehen könnte. Zudem glaube ich gar nicht, dass sich eine rekursive Suche tatsächlich so schlecht auf die Laufzeit auswirkt, denn die Rekursionstiefe ist ja maximal n, und bei jedem Aufruf wird lediglich ein Integer und ein Zeiger übergeben sowie ein zusätzlicher Speicher der Größe 3*Nmax reserviert. \quoteoff Ich vermute, dass es hier eher um die Parallelisierbarkeit geht, die in der aktuellen Variante nicht sehr groß ist. Man könnte aber z.B. mal überlegen, die obersten ein oder zwei Rekursionsebenen "abzuwickeln". Dann könnten zumindest verschiedene Threads verschiedene Durchläufe der einzelnen for-j-Schleifen berechnen, da diese Zweige nicht voneinander abhängig sind. \quoteon Vielleicht bringt es ja was, Nmax auf 17 herunter zu setzen oder aber statt auf einem temporären Array auf einem globalen zweidimensionalen Array zu arbeiten. Letzteres werde ich mal ausprobieren. \quoteoff Wenn die laufende Speicher-Allokation tatsächlich immer neu ausgeführt wird, dürfte dein Vorgehen mit dem globalen 2-d-Array Verbesserungen bringen. Aber evtl. wird das eh schon durch den Compiler rausoptimiert. Wovon ich mir wenig bis nichts erwarte, ist ein Versuch auf Mikro-Ebene zu parallelisieren. Wir haben hier kaum vektor-artige Berechnungen, für die solche Prozessor-Optimierungen wie MMX, SSE und Nachfolger groß was bringen würden. Aber ich lasse mich natürlich gern positiv überraschen. :)


   Profil
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8028
Wohnort: Milchstraße
  Beitrag No.81, eingetragen 2020-04-20

Hallo! Mein Versuch, die Liste in ein globales zweidimensionales Array zu verlagern hat leider überhaupt nichts gebracht. Vielleicht optimiert der Compiler das alles schon für sich. @hyperG: Doch, ich bin noch motiviert! Dass ich auf deine letzten Beiträge nicht so richtig eingegangen bin, hängt auch damit zusammen, dass ich sie größtenteils nicht verstanden habe. Kannst du bitte noch einmal in Kurzform darlegen, was auszuprobieren ist? @Ixx: 20% Ersparnis ist in der Tat ein toller Erfolg, den ich jetzt nicht erwartet hätte. Zum Abbruchkriterium: Ich habe mal gezählt, in welcher Stufe das Kriterium wie häufig anschlägt. Hier die Ergebnisse für N = 12: \sourceon abort[n] = ... abort[0] = 0 abort[1] = 0 abort[2] = 3609722 abort[3] = 34880478 abort[4] = 78213140 abort[5] = 71829314 abort[6] = 32210311 abort[7] = 7811701 abort[8] = 1073192 abort[9] = 82550 abort[10] = 3140 abort[11] = 34 abort[12] = 0 \sourceoff Zu Beginn (n = 12) ist es also tatsächlich überflüssig, sich drum zu kümmern. Aber da die Funktion reduce mit n = 12 nur sehr selten aufgerufen wird, ergibt es letztendlich keine messbare Ersparnis. Erst bei n = 11 könnte es etwas bringen. Aber ob ich hier prüfe oder nicht prüfe, macht ebenfalls im Endergebnis keinen Unterschied, da n = 11 so selten auftritt. Wird auf die Prüfung bei n = 10 verzichtet, wird das Programm langsamer. 5 bzw. 4 Minuten für n = 12 auf dem Laptop ist allerdings sehr langsam. Bei meinem Aldi-Recher (3 GHz Taktrate), der auch nicht mehr der jüngste ist, bin ich bei n = 12 in 1 Minute durch. Um das Programm besser parallelisieren zu können, könnte man eventuell statt eines Tripels auch zwei Tripel vorgeben. Wenn jemand viele Kerne hat aber den Rechner nicht so lange laufen lassen möchte, wäre das vielleicht hilfreich.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8028
Wohnort: Milchstraße
  Beitrag No.82, eingetragen 2020-04-20

Nachtrag: Dass unser Ergebnis für n = 16 so schnell den Review-Prozess bei OEIS durchlaufen hat, liegt möglicherweise am auch übersichtlichen C-Code. Auch deshalb ist mir daran so viel gelegen. (Von den potenziellen Fehlerquellen mal abgesehen.) Selbst wenn es anders vielleicht um 1 % schneller gehen könnte.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.83, eingetragen 2020-04-20

\quoteon(2020-04-20 20:03 - Ixx in Beitrag No. 80) ... Wovon ich mir wenig bis nichts erwarte, ist ein Versuch auf Mikro-Ebene zu parallelisieren. Wir haben hier kaum vektor-artige Berechnungen, für die solche Prozessor-Optimierungen wie MMX, SSE und Nachfolger groß was bringen würden. Aber ich lasse mich natürlich gern positiv überraschen. :) \quoteoff Also habe ich das gleich als erstes meiner vielen Vorschläge getestet: \sourceon cpp if(2*n-2 ==16) sum1 = SumAVX(&newlist[0], 16); else { sum1 = 0; for (i = 0; i < 2 * n - 2; i++) sum1 += newlist[i]; } \sourceoff Obwohl dieser Sonderfall recht selten passiert, und bei sum2 wegen n=13 nie zum Einsatz kommt, bringt es doch fast 1 s pro 4 Mio.: \sourceon DreierPartitionenSumAVX.exe 13 10 20 30 exe \ CPU; Zeit in s | ? | i7 | i9 ------------------------+--------+-------+------ Borland CB6 | 35 | | DreierPartitionen32 | | 20,49 | 17,3 DreierPartitionen | | 17,42 | 14,5 Ixx+hyperG | | 16,18 | 13,47 Ixx+hyperG+SumAVX | | | 12,7 \sourceoff Bei n=17 reicht es nicht für einen 2. Fall, da (17-1)*2-2 < 32 :-(


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.84, eingetragen 2020-04-20

Ok, am meisten passiert wohl, wenn n im Bereich 3 bis 6 liegt. Das, was da gerechnet wird, ist der Hauptanteil. Das heißt, wir reden hier über Arrays der Länge 9 bis 18. Tatsächlich sollte hier binäre Suche nicht mehr viel gegenüber linearer bringen. Eventuell lohnt es sich aber dennoch, hier "von Hand" zu optimieren. [Die Antwort wurde nach Beitrag No.82 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.85, eingetragen 2020-04-20

\quoteon(2020-04-20 21:54 - StrgAltEntf in Beitrag No. 81) ... Ergebnisse für N = 12: ... 5 bzw. 4 Minuten für n = 12 auf dem Laptop ist allerdings sehr langsam. Bei meinem Aldi-Recher (3 GHz Taktrate), der auch nicht mehr der jüngste ist, bin ich bei n = 12 in 1 Minute durch. ... \quoteoff \sourceon SumAVX.exe i9 10567748 in 22.9 s i7 10567748 in 27.2 s \sourceoff [Die Antwort wurde nach Beitrag No.83 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.86, eingetragen 2020-04-20

Wenn Ihr schon nicht meine EXE testen wollt, habt Ihr dann wenigstens Eure, um CPU & Compiler relativ zu vergleichen?


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.87, eingetragen 2020-04-20

Was mir gerade auffällt -- ob lineare Suche oder binär -- ist, dass man ja nicht für list[0]+list[j] beim Index j+1 anfangen muss zu suchen, sondern da weitermachen kann, wo man vorher aufgehört hat: Wenn list[0]+list[j]=list[k] ist, kann frühestens list[k+1] ein Treffer für list[0]+list[j+1] sein. (Ist dagegen k der kleinste Index mit list[0]+list[j]


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.88, eingetragen 2020-04-21

Ich habe mal ein bisschen gespielt: Wenn man jeweils bei der Suche nach einem k, sodass list[0]+list[j]=list[k] gilt, "von hinten beginnt", aber auch beachtet, dasss man nicht "weiter hinten" starten muss als beim Treffer bezüglich list[0]+list[j+1], so ist die lineare Suche der binären überlegen, weil der Treffer aufgrund der Randlage schnell gefunden wird. Dies habe ich mal in folgendem Code umgesetzt: (angepasst 13.57 Uhr) \showon Quelltext \sourceon C void search(const int list[3*Nmax], const int n) { int newlist[3*Nmax]; int j, k; if(n == 2) { if ((list[0]+list[4]==list[5]) && (list[1]+list[2]==list[3])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[4]; solution[1][2]=list[5]; solution[0][0]=list[1]; solution[0][1]=list[2]; solution[0][2]=list[3]; printsolution(); return; } if ((list[0]+list[3]==list[5]) && (list[1]+list[2]==list[4])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[3]; solution[1][2]=list[5]; solution[0][0]=list[1]; solution[0][1]=list[2]; solution[0][2]=list[4]; printsolution(); return; } if ((list[0]+list[3]==list[4]) && (list[1]+list[2]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[3]; solution[1][2]=list[4]; solution[0][0]=list[1]; solution[0][1]=list[2]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[2]==list[4]) && (list[1]+list[3]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[2]; solution[1][2]=list[4]; solution[0][0]=list[1]; solution[0][1]=list[3]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[2]==list[3]) && (list[1]+list[4]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[2]; solution[1][2]=list[3]; solution[0][0]=list[1]; solution[0][1]=list[4]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[1]==list[4]) && (list[2]+list[3]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[1]; solution[1][2]=list[4]; solution[0][0]=list[2]; solution[0][1]=list[3]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[1]==list[3]) && (list[2]+list[4]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[1]; solution[1][2]=list[3]; solution[0][0]=list[2]; solution[0][1]=list[4]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[1]==list[2]) && (list[3]+list[4]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[1]; solution[1][2]=list[2]; solution[0][0]=list[3]; solution[0][1]=list[4]; solution[0][2]=list[5]; printsolution(); return; } return; } k=3*n-1; for(j=3*n-2; (j>0); j--) { for ( ; ; k-- ) { if (list[0]+list[j]==list[k]) { if(!reduce(list, newlist, j, k, n)) // delete triple from list { solution[n-1][0]=list[0]; solution[n-1][1]=list[j]; solution[n-1][2]=list[k]; search(newlist, n-1); } k--; // largest k with list[k]


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.89, eingetragen 2020-04-21

\quoteon(2020-04-20 22:38 - hyperG in Beitrag No. 83) Also habe ich das gleich als erstes meiner vielen Vorschläge getestet: \sourceon cpp if(2*n-2 ==16) sum1 = SumAVX(&newlist[0], 16); else { sum1 = 0; for (i = 0; i < 2 * n - 2; i++) sum1 += newlist[i]; } \sourceoff \quoteoff Also zumindest für größere n könntest du diese Einsparung ja auch einbauen: \sourceon cpp sum1 = 0; i = 0; if(2*n-2 >= 16) { sum1 = SumAVX(&newlist[0], 16); i = 16; } for ( ; i < 2 * n - 2; i++) sum1 += newlist[i]; \sourceoff Das sollte zumindest immer die ersten 16 (sofern so viele vorhanden) Einträge parallel summieren. Da ich keinen entsprechenden Prozessor hier habe, kann ich es nicht ausprobieren. Eine zweite Idee: Spricht etwas dagegen, das newlist-Array vor den Additionen mit Nullen aufzufüllen? Dann könnte man zumindest immer sum2 parallel berechnen. edit: Noch besser: newlist besteht aus fester Länge 48=16*3. (Das reicht für n=17 aus.) Alle nicht benötigten Einträge werden genullt. Dann wird die Summe $S$ aller 48 Elemente parallel berechnet sowie analog parallel die Summe $sum2$ der Elemente newlist[2*n-2+0] bis newlist[2*n-2+15], in denen ausschließlich die Elemente des letzten Drittels des eigentlich zu betrachtenden Intervalls und Nullen stehen. Es wäre dann $sum1=S-sum2$; aber das Abbruch-Kriterium könnte dann einfacher S>2*sum2 lauten. noch'n edit: Die Summe $S$ aller Elemente könnte man aber auch der Rekursion mitgeben, da das nur die vorhergehende Summe - 2*list[k] ist. Es verbliebe nur die Summe sum2 zu berechnen, was man eben ggf. parallelisieren kann.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.90, eingetragen 2020-04-21

Die Idee aus dem letzten edit (Summe aller Elemente rekursiv bestimmen) habe ich fix mal umgesetzt: Hat nochmal ca. 15% Zeitersparnis gebracht, bin jetzt bei knapp über 2,5 Minuten für N=12. \showon Quelltext geänderter Funktionen \sourceon C /* delete list[0], list[j] and list[k] from list[0]...list[3n-1] and check the reduced list Return value: 0, if (sum of the first two thirds entries of the new list) <= (sum of the last third entries of the new list) 1, else -> abort */ int reduce(const int list[3*Nmax], int newlist[3*Nmax], const int j, const int k, const int n, const int sum){ int i, m = 0, sum2 = 0; for(i=1; i 2*sum2) return 1; // -> abort else return 0; } // Recursive search for valid partitions in a list of length 3*n<=18 void search(const int list[3*Nmax], const int n, const sum) { int newlist[3*Nmax]; int j, k; if(n == 2) { if ((list[0]+list[4]==list[5]) && (list[1]+list[2]==list[3])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[4]; solution[1][2]=list[5]; solution[0][0]=list[1]; solution[0][1]=list[2]; solution[0][2]=list[3]; printsolution(); return; } if ((list[0]+list[3]==list[5]) && (list[1]+list[2]==list[4])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[3]; solution[1][2]=list[5]; solution[0][0]=list[1]; solution[0][1]=list[2]; solution[0][2]=list[4]; printsolution(); return; } if ((list[0]+list[3]==list[4]) && (list[1]+list[2]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[3]; solution[1][2]=list[4]; solution[0][0]=list[1]; solution[0][1]=list[2]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[2]==list[4]) && (list[1]+list[3]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[2]; solution[1][2]=list[4]; solution[0][0]=list[1]; solution[0][1]=list[3]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[2]==list[3]) && (list[1]+list[4]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[2]; solution[1][2]=list[3]; solution[0][0]=list[1]; solution[0][1]=list[4]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[1]==list[4]) && (list[2]+list[3]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[1]; solution[1][2]=list[4]; solution[0][0]=list[2]; solution[0][1]=list[3]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[1]==list[3]) && (list[2]+list[4]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[1]; solution[1][2]=list[3]; solution[0][0]=list[2]; solution[0][1]=list[4]; solution[0][2]=list[5]; printsolution(); return; } if ((list[0]+list[1]==list[2]) && (list[3]+list[4]==list[5])) { solutioncounter++; // solution found solution[1][0]=list[0]; // add triplets to solution solution[1][1]=list[1]; solution[1][2]=list[2]; solution[0][0]=list[3]; solution[0][1]=list[4]; solution[0][2]=list[5]; printsolution(); return; } return; } k=3*n-1; for(j=3*n-2; (j>0); j--) { for ( ; ; k-- ) { if (list[0]+list[j]==list[k]) { int s = sum - 2*list[k]; if(!reduce(list, newlist, j, k, n, s)) // delete triple from list { solution[n-1][0]=list[0]; solution[n-1][1]=list[j]; solution[n-1][2]=list[k]; search(newlist, n-1, s); } k--; // largest k with list[k] Nmax || N < 1){ printf("Invalid N = %d\n", N); return 1; } for(hlp=i=0; i<3*N; i++) hlp += i+1; if(hlp % 2){ printf("There is no valid partition of 1...3*N for N = %d\n", N); return 1; } if(ac == 5){ a = atoi(av[2]); b = atoi(av[3]); c = atoi(av[4]); printf("a = %d b = %d c = %d\n", a, b, c); if(a < 1 || a > 3*N){ printf("Invalid value a = %d\n", a); error = 1; } if(b < 1 || b > 3*N){ printf("Invalid value b = %d\n", b); error = 1; } if(c < 1 || c > 3*N){ printf("Invalid value c = %d\n", c); error = 1; } if((a == b) || (a + b != c)){ printf("a and b must be different and must add up to c"); error = 1; } if(error) return 1; if(b < a){ hlp = b; b = a; a = hlp; } printf("Find %d disjoint triplets from 1...%d that contain the triple (%d %d %d)\n", N, 3*N, a, b, c); // create initial list in which the triple (a b c) is missing for(j=0, i=1; i


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.91, eingetragen 2020-04-21

Abschließend... Habe jetzt auch sum2 in die Rekursion gezogen: Laufzeit nun bei 2 Minuten für n=12 auf meinem Netbook, d.h., startend von der Ursprungsversion nen Faktor 2,5 in der Laufzeit gewonnen. Mehr Ideen habe ich nicht, deswegen lasse ich das Ganze jetzt ruhen. Der Vollständigkeit halber noch der Quelltext mit den geänderten Funktionen: \showon \sourceon nameDerSprache // delete list[0], list[j] and list[k] from list[0]...list[3n-1] void reduce(const int list[3*Nmax], int newlist[3*Nmax], const int j, const int k, const int n) { int i, m = 0; for(i=1; i0); j--) { for ( ; ; k-- ) { if (list[0]+list[j]==list[k]) { int s = sum - 2*list[k]; int s2 = sum2; if (k<=2*n-1) { s2 -=list[2*n]; } else if (j<=2*n-1) { s2 -=list[k]; } else { s2 -=list[k]+list[j]-list[2*n-1]; } if(s <= 2*s2) { reduce(list, newlist, j, k, n); // delete triple from list solution[n-1][0]=list[0]; solution[n-1][1]=list[j]; solution[n-1][2]=list[k]; search(newlist, n-1, s, s2); } k--; // largest k with list[k] Nmax || N < 1){ printf("Invalid N = %d\n", N); return 1; } for(hlp=i=0; i<3*N; i++) hlp += i+1; if(hlp % 2){ printf("There is no valid partition of 1...3*N for N = %d\n", N); return 1; } if(ac == 5){ a = atoi(av[2]); b = atoi(av[3]); c = atoi(av[4]); printf("a = %d b = %d c = %d\n", a, b, c); if(a < 1 || a > 3*N){ printf("Invalid value a = %d\n", a); error = 1; } if(b < 1 || b > 3*N){ printf("Invalid value b = %d\n", b); error = 1; } if(c < 1 || c > 3*N){ printf("Invalid value c = %d\n", c); error = 1; } if((a == b) || (a + b != c)){ printf("a and b must be different and must add up to c"); error = 1; } if(error) return 1; if(b < a){ hlp = b; b = a; a = hlp; } printf("Find %d disjoint triplets from 1...%d that contain the triple (%d %d %d)\n", N, 3*N, a, b, c); // create initial list in which the triple (a b c) is missing for(j=0, i=1; i


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8028
Wohnort: Milchstraße
  Beitrag No.92, eingetragen 2020-04-21

Hallo Ixx, das mit der neuen k-Schleife fetzt! Auch deine Idee mit der Summe ist eine schöne Idee, die bei mir einiges gebracht hat. sum2 habe ich aber noch nicht ausprobiert. Übrigens braucht man die j- und k-Schleife nicht rückwärts laufen zu lassen. Vorwärts geht es ebenso und bringt bei mir keine Unterschiede in der Laufzeit. Hier meine Vorwärts-Schleife: \sourceon C for(j=1, k=2; j<3*n-1; j++){ for( ; k<3*n; k++){ // searching for triplets (list[0] list[j] list[k]) if(list[0] + list[j] == list[k]){ // new triple found newsum = sum - 2*list[k]; if(!reduce(list, newlist, j, k, n, newsum)){ // delete triple from list // test of newlist passed addtosolution(list, 0, j, k, n); // add triple to solutions search(newlist, n-1, newsum); // search shortened list } k++; break; // next j } if(list[0] + list[j] < list[k]) // for this (j, k) and greater k break; // no solution is possible -> next j } } \sourceoff Die Spezialbehandlung für n=2 hat bei mir übrigens nichts gebracht. (Ist eigentlich klar, wieso von den acht Fällen höchstens einer auftreten kann? Wurde das hier irgendwo im Thread schon thematisiert?) Darf ich noch fragen, mit welchem Betriebssystem du mit einem Laptop unterwegs bist? (Vielleicht steht das hier auch schon irgendwo.) Das mit den missglückten Einrückungen liegt möglicherweise an den Tabs, die unterschiedlich interpretiert werden.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.93, eingetragen 2020-04-21

\quoteon(2020-04-21 20:46 - StrgAltEntf in


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.94, eingetragen 2020-04-21

Respekt Ixx, die Summe als Übergabeparameter in die Rekursion mit zu übergeben ist besser als jede Optimierung der ganzen Summe! Da muss man sich schon sehr tief in die Materie hineindenken, um das noch zu verstehen. zu "...könnte man zumindest immer sum2 parallel berechnen." Das Problem beim "echten Parallelisieren" ist, dass man den Compiler sehr stark davon überzeugen muss, dass sich wirklich alle Variablen garantiert niemals überlagern. Da das Quell-Array für beide Summen jedoch aus der identischen Deklaration kommt, gewinnt man trotz 100% Auslastung 2er Kerne kaum Zeit (da der Compiler Zwischenstopps einfügt um jeden erdenklichen Crash vorzubeugen) ! Man müsste schon ein temporäres 2. Array vor jeder Parallelisierung füllen, was auch wieder Zeit kostet! Besser wäre, wenn man 2 globale Arrays hätte, wo statt "alle bis auf 3 zu kopieren" besser nur "wenige aus dem vorhandenen Array herausgenommen" werden. So verschachtelt und durch zig Bedingungen zerstückelt der Code momentan ist, sehe ich keine Möglichkeit zur Parallelisierung (weder mit Threads noch per AVX). Das ist aber Gesamt-technisch gesehen nicht schlecht, da StrgAltEntf ja bereits durch Startparameter eine Parallelisierung der exe ermöglicht hat. Solange ich unter 13 Stunden pro Tag bleibe, kann ich somit bis zu 20 exe starten, was effektiver ist, als wenn 1 exe mit 2 Kernen gerade mal 1 Stunde pro Tag gewinnt und ich aber nur 10 exe pro Tag starten kann. Ich bin ja gespannt, wie sich diese große Änderung bei mir auswirkt... [Die Antwort wurde nach Beitrag No.91 begonnen.]


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 7009
Wohnort: Niedersachsen
  Beitrag No.95, eingetragen 2020-04-21

Ich habe mal über zusätzliche Abbruchkriterien nachgedacht. Neben der absoluten Größe der Zahlen spielen auch ihre Reste eine Rolle. Da es kein gültiges Tripel X+Y=Z mit _drei_ ungeraden Zahlen gibt, kann man abbrechen, wenn weniger als ein Drittel der verbleibenden Zahlen gerade ist (*). Die Idee lässt sich aber noch erweitern: Unter den Zahlen 1..51 sind 25 gerade und 26 ungerade Zahlen. In einem gültigen Tripel sind entweder drei gerade Zahlen, oder es sind zwei ungerade und eine gerade Zahl. Es gibt also genau vier Tripel mit lauter geraden Zahlen und 13 Tripel mit je zwei ungeraden und einer geraden Zahl. Wenn man zuerst die vier geraden Tripel auswählt, dann bleiben nur noch ungerade-ungerade-gerade-Tripel übrig. Das müsste den Suchaufwand reduzieren, weil man kürzere Listen (nur die ungeraden oder nur die geraden Zahlen) durchlaufen muss. Das ist von der Programmierung her etwas aufwändiger, sollte die Suche aber um einiges beschleunigen. Als kleine Einsparung kann man sich die oben unter (*) beschriebene Abfrage dann sparen. [Die Antwort wurde nach Beitrag No.92 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.96, eingetragen 2020-04-21

Bei mir ist es zwar nicht Faktor 2,5 geworden, da die AVX-Vorteile nun wegfallen, aber ich konnte mit Variablen-Typ-Optimierung, inline Ptr und Compileroptimierung die 10 s Marke knacken: \sourceon nameDerSprache | exe 13 10 20 30 | exe 12 | exe 13 exe \ CPU; Zeit in s | ? | i7 | i9 | i9 |IxxNB | i9 ------------------------+--------+-------+-------+------+------+-------- Borland CB6 | 35 | | | DreierPartitionen32 | | 20,49 | 17,3 | DreierPartitionen | | 17,42 | 14,5 | | 5 min| 4,88 min Ixx+hyperG | | 16,18 | 13,47 | | Ixx+hyperG+SumAVX | | | 12,7 |22.9 | | IxxRekuSum + hyperG-Opt | | | 9,82 |17.5 |120 s | 3,46 min \sourceoff 1,3717 mal schneller bedeutet beim 17er nicht mehr 13 h sondern 9,48 Stunden! Hallo Kitaktus, gute Idee. Die Abfrage nach Gerade/ungerade kann man mit Bit-UND sehr schnell in c erledigen.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.97, eingetragen 2020-04-22

\quoteon(2020-04-21 21:14 - Kitaktus in Beitrag No. 95) Ich habe mal über zusätzliche Abbruchkriterien nachgedacht. Neben der absoluten Größe der Zahlen spielen auch ihre Reste eine Rolle. Da es kein gültiges Tripel X+Y=Z mit _drei_ ungeraden Zahlen gibt, kann man abbrechen, wenn weniger als ein Drittel der verbleibenden Zahlen gerade ist (*). \quoteoff Das habe ich mal ausprobiert. Leider führt dieses alternative Kriterium zu selten zusätzlich zum bisherhigen zum Abbruch, sodass man nicht viel spart, aber Auswertungsaufwand gewinnt. In Summe führte das bei mir zu einer Verlangsamung der Berechnung. \quoteon Die Idee lässt sich aber noch erweitern: Unter den Zahlen 1..51 sind 25 gerade und 26 ungerade Zahlen. In einem gültigen Tripel sind entweder drei gerade Zahlen, oder es sind zwei ungerade und eine gerade Zahl. Es gibt also genau vier Tripel mit lauter geraden Zahlen und 13 Tripel mit je zwei ungeraden und einer geraden Zahl. Wenn man zuerst die vier geraden Tripel auswählt, dann bleiben nur noch ungerade-ungerade-gerade-Tripel übrig. Das müsste den Suchaufwand reduzieren, weil man kürzere Listen (nur die ungeraden oder nur die geraden Zahlen) durchlaufen muss. \quoteoff Naja, man müsste dann schon ungerade+ungerade=gerade und ungerade+gerade=ungerade getrennt prüfen. Effektiv sollte sich die Anzahl der zu prüfenden Summen nicht reduzieren, aber die Liste, in der man die Summe sucht, von der Länge halbieren. Ob das jedoch einen Zugewinn in der aktuellen Implementation bringt, die aufgrund der Ergebnisse aus den vorherigen for-j-Schleifendurchläufen schnell für den nächsten die Summe in der Liste findet (oder ausschließt, dass diese in der Liste steht), sehe ich gerade eher etwas skeptisch.


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 7009
Wohnort: Niedersachsen
  Beitrag No.98, eingetragen 2020-04-22

Die "schlauen for-j-Schleifendurchläufe" kann man doch immer noch nutzen. Man muss nur eine Fallunterscheidung machen: Ist die 1. Zahl ungerade, dann probiere nacheinander: 2. Zahl aus der Liste der geraden Zahlen -- 3. Zahl aus der Liste der ungeraden Zahlen 2. Zahl aus der Liste der ungeraden Zahlen -- 3. Zahl aus der Liste der geraden Zahlen Ist die 1. Zahl gerade, dann probiere: 2. Zahl aus der Liste der ungeraden Zahlen -- 3. Zahl aus der Liste der ungeraden Zahlen Der vierte Fall 1. Zahl gerade -- 2. Zahl aus der Liste der geraden Zahlen -- 3. Zahl aus der Liste der geraden Zahlen wird nur für die ersten vier Tripel (bei n=16,17) angewendet -- in diesem Fall als einziger -- und wird für alle weiteren Tripel weggelassen. Das die Listen kürzer werden hat sicher einen Effekt, ich würde Einsparung aber besonders an der Stelle erwarten, an der ich den Fall gerade-gerade-gerade gar nicht zulasse, also in einem von neun Fällen die Verzweigung des Suchbaums verhindere(*). Wenn man auf neun Ebenen den Verzweigungsgrad um 1/9 verringert(*), spart das knapp 65% des Aufwands. (*) Je nach Umsetzung wird man auf etwa drei Ebenen den Aufwand um 1/3 verringern, das Einsparungspotenzial ist aber ähnlich. Eine Alternative wäre, _immer_ als erstes eine gerade Zahl g auszuwählen. Dann muss man allerdings zusätzlich den Fall untersuchen, dass g die Summe aus zwei ungeraden Zahlen ist. Intuitiv erscheint mir das aufwendiger.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.99, eingetragen 2020-04-22

Ich wollte nur darauf hinweisen, dass die Verkürzung des Suchintervalls -- für k, also die Summe-- wenig bringt, wenn der Treffer -- nach Konstruktion -- eigentlich immer direkt am Anfang zu erwarten ist. Was etwas ändern kann, ist die Verkürzung des Intervalls für den zweiten Summanden-- also j in obigem Code. Wenn man das über die zwei Listen -- für gerade und für ungerade Folgenglieder getrennt -- organisiert, dann müsste man wohl die Berechnung der Summe der Elemente des letzten Drittels wieder überdenken. Das ist mir nämlich noch nicht klar, wie man das effizient hinbekommt, wenn sich die Elemente über zwei Listen verteilen... Vielleicht hat der Ansatz aber auch Chancen ganz ohne die Summe-Prüfung.


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2352
Wohnort: Thüringen
  Beitrag No.100, eingetragen 2020-04-22

Hallo ! Ich habe mir auch mal einen anderen Ansatz überlegt, weiß aber nicht , ob besser, da ich ihn noch nicht zum laufen bringen konnte. Hier im Ansatz für n=4 [1..12] Wir haben ein 2D-Feld F[] und ein 1D-Feld C[] und noch ein Feld für die Belegung einer Zahl,ob gerade in Verwendung B[12]. Man liest alle Tripelbildungen ein. Bsp. F[1,2]=3,F[1,3]=4,...F[1,11]=12: C[1]=10 1.Schleife, 10 Fälle F[2,3]=5,...F[2,10]=12 C[2]=8,8 Fälle .. F[5,6]=11,F[5,7]=12 C[5]=2 Fälle Es gibt 5 Schleifen, C[?] ist für die Zählvariable die Grenze Bsp. For j=1 TO C[1] usw Jetzt kommt die Abklärung... Wir haben F[1,2]=3 , Setze B[1],B[2],B[3] als "true" 2. Schleife F[2,3]=5,... Da hier B[2] in Benutzung , springe gleich in die 3. Schleife 3. Schleife F[3,4]=7,... Da hier B[3] in Benutzung , springe gleich in die 4. Schleife 4. Schleife F[4,5]=9, B[4],B[5],B[9]=true setzen..alle 3 Zahlen sind frei und werden belegt ..gehe in die 5. Schleife. 5. Schleife F[5,6]=11...da B[5]=true, gehe in die 4. und nehme F[4,6]=10 etc Fazit ist, wenn B[1..12]=true, ist Kombination gefunden. Springe zurück und arbeite hintere Schleifen bis zum Ende usw. Zwischdrin müsste ein Zähler laufen, der bei 12 die Lsg registriert. Sobald Kombination durch, wird zähler wieder verringert und B[?] auch als false gesetzt, da wieder frei geworden.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.101, eingetragen 2020-04-22

Da mich ja die Compiler-Anteile bei identischer CPU interessierten, habe ich mir MingW-w64 (analog zum gcc) besorgt und mit Geschwindigkeitsoptimierungsparameter 2 Vergleichs-EXE (Beiträge 4 & 91) erstellt: \sourceon nameDerSprache Startparameter | exe 13 10 20 30 | exe 12 | exe 13 |16 1 2 3 exe \ CPU; Zeit in s | ? | i7 | i9 | i9 |i7 |Aldi | IxxNB |Aldi | i9 |i9 |Aldi ------------------------+--------+-------+-------+------+----+-----+-------+-----+------------+-----+---- Borland CB6 / MingW-w64 | 35 | 18 | 16 | 29 | 33 | | | | | | DreierPartitionen32 | | 20,49 | 17,3 | | | | | | | | DreierPartitionen | | 17,42 | 14,5 | | | | 5 min| |4,88 min | |71,4 min Ixx+hyperG | | 16,18 | 13,47 | | | 60 s| | | | | Ixx+hyperG+SumAVX | | | 12,7 |22.9 | | | | | | | IxxRekuSum + hyperG-Opt | | 10,6 | 9,82 |17.5 | 19 | | | |3,46 min | | n2 | | 11 | 9,6 |17,3 | 20 | | | 316 |204s=3,4 min|43min| IxxRekuSum per MingWw64 | | 12 | 12 |23 | 23 | | 55 s| | \sourceoff MingWw64 ist etwa 10...12 % langsamer als VC2017 Mit zusätzlicher Ptr- & Var-Optimierung bei VC sogar 18...24 % langsamer. [Die Antwort wurde nach Beitrag No.98 begonnen.]


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.102, eingetragen 2020-04-22

Ich habe mal Kitaktus' Idee in der Form ausprobiert, erst die "alles-gerade"-Tripel zu erzeugen und dann jeweils in den tieferen Rekursionsebenen die Fälle, wo beide Summanden gerade sind, direkt abzubrechen. Ergebnis bei mir: Laufzeitverlängerung um ca. 10%. Offenbar bringt jedenfalls in meinem Ansatz das ständige Parität-Prüfen mehr Nach- als Vorteile... btw: Durch den Hinweis von StrgAltEntf habe ich dann doch mal Optimierungs-Compiler-Flags gesetzt, was mich nun auch für n=12 in 55s mitspielen lässt. Die Sonderbehandlung von n=2 bringt aber noch immer 5s (ohne bin ich bei einer Laufzeit von 1m).


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.103, eingetragen 2020-04-22

Hinweis zur eigenartigen Anzeige des Codes in Beitrag 91: - bei sourceon wurde cpp vergessen - statt 0D 0A enden viele Zeilen mit 0D 0A A0 0D 0A Dieses Sonderzeichen A0=160 ist völlig A-typisch für Editoren der Windows-Welt. Tabulator ist 09 . Wenn ich den langsamen gcc und den Faktor 6 bei den Ergebnissen Vergleiche und bei https://www.cpubenchmark.net/singleThread.html meinen 12 Jahre alten i7 durch diesen Faktor dividiere, könnte die CPU im Lubuntu-Netbook ein Intel Pentium 4 1500 MHz (etwa 20 Jahre) sein, die schon SSE2 Befehle konnte... [Die Antwort wurde nach Beitrag No.101 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.104, eingetragen 2020-04-22

OK, damit verkleinern sich die 120 auf 55 s -> in Tabelle angepasst. ...und die mögliche CPU ein Intel Core2 Duo E4500 2.20GHz.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.105, eingetragen 2020-04-22

\quoteon(2020-04-22 21:41 - hyperG in Beitrag No. 104) OK, damit verkleinern sich die 120 auf 55 s -> in Tabelle angepasst. ...und die mögliche CPU ein Intel Core2 Duo E4500 2.20GHz. \quoteoff Ich habe mal nachgeschaut: Es ist ein Intel Dual-Core N3060, Taktfrequenz habe ich gerade nicht parat -- laut Internet-Angabe "maximal 2.48 GHz".


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.106, eingetragen 2020-04-23

Hallo Ixx, ich habe mir mal Deine 2*8= 16 If-Abfragen im Fall n=2 angesehen: - 16 mal Add - 16 mal Abfrage nach == (Compare) - und noch ein weiteres UND pro IF Das konnte ich auf 2 AVX2 Maschinenbefehle (+ 3 Ladebefehle) reduzieren und über bleibt noch: if(maske & 0xC00U == 0xC00U) { Solu.. print return; } Ergebnis 0,08 s langsamer, da die vorderen If-Abfragen mit return vorzeitig weitere Add + Compare + UND + IF vermeiden. Könnte man nicht auch hier analog zur Sum gewisse Add+Compare-Ergebnisse als Übergabeparameter mit in die Rekursion übernehmen, um sie nicht immer wieder neu zu berechnen? Oder mit n==3 noch eine weitere Rekursion vermeiden (AVX512 kann 32 Add parallel!) ? Grüße


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.107, eingetragen 2020-04-23

Also in unserer Sortierung, sofern man die Tripel nach "aufsteigendem kleinstem Element" sucht, fallen auch noch vier der acht Fälle für n=2 Weg: a) (list[0]+list[4]==list[5]) && (list[1]+list[2]==list[3]), b) (list[0]+list[2]==list[3]) && (list[1]+list[4]==list[5]), c) (list[0]+list[1]==list[3]) && (list[2]+list[4]==list[5]) und d) (list[0]+list[1]==list[2]) && (list[3]+list[4]==list[5]). Das sind genau die Fälle, in denen die beiden größten Elemente im gleichen Tripel vorkommen. Das liegt an unserer Abarbeitungs-Reihenfolge der Tripel, da vor dieser Fallunterscheidung zuvor schon N-2 Tripel ausgewählt wurden, also $list[0] \geq N-1$ ist. Insbesondere ist damit auch $list[1] \geq N$. Weiterhin ist $list[5]\leq 3N$. zu d): Damit ist $list[2]\geq 2N-1$, also $list[3]\geq 2N$ und damit $list[4]\leq 3N-2N


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 7009
Wohnort: Niedersachsen
  Beitrag No.108, eingetragen 2020-04-23

Ich habe die Paritätenprüfung mal in meinem Programm umgesetzt. Als reines Abbruchkriterium bringt es mir ein paar Prozent (ca. 7%). Erst die reinen geraden Tupel auszuwählen und dann den Fall auszuschließen, dass die beideren kleineren Zahlen gerade sind, hat mir nichts gebracht. Zusätzlich die Zahlen in zwei Gruppen aufzuteilen, um dann nur noch in der geraden oder ungeraden Gruppe suchen zu müssen, habe ich nicht probiert. Schade, ich hatte mir mehr erhofft.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.109, eingetragen 2020-04-23

Hm seltsamer Effekt: Dadurch, dass bei n=2 die beiden größten Werte in verschiedenen Tripeln landen müssen, kann man bei der Prüfung vor Aufruf dieser Rekursionsebene echt auf Gleichheit sum1==sum2 bzw. S==2*sum2 (und nicht nur <=) testen, was meine Laufzeit für N=12 von 55s auf 53s drückt. Eigentlich kann man sich dann im Fall n=2 dann aber auch die Prüfung von je einer Gleichheit sparen, da diese dann automatisch erfüllt ist. Jedoch verlängert sich durch das Weglassen dieser überflüssigen zweiten Prüfung die Laufzeit wieder auf 54s...


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.110, eingetragen 2020-04-23

Ja, solche Effekte kenne ich auch: Bei der printf-Ausgabe habe ich ja für die Fehlersuche noch zusätzlich die ersten 3 Zeilen immer ausgegeben: \sourceon cpp if ((solutioncounter <4) || (solutioncounter % boundary[N]) < 1) printsolution(); \sourceoff Obwohl 3 Zeilen mehr printf und pro Solution 2 Befehle mehr (<4 und OR ) ist die gemessene Zeit nicht etwa länger sondern etwa 0,05 s kürzer. Meist liegt es an der Adressenausrichtung der Maschinenbefehle (glatte Vielfache von 64 , was eigentlich der LINKER optimieren sollte). Dein Trick mit S==2*sum2 habe ich mal nicht erst bei n==2 sondern so eingesetzt, dass die Rekursion (innerhalb der Rekursion) nur aufgerufen wird, wenn n>2 || s< 2*s2. Das brachte pro 4 Mio. Solutions etwa 0,1 s. Bei N=13 bin ich bei 206 s.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.111, eingetragen 2020-04-24

Fortsetzung von Beitrag 34 und kleine Optimierung von 2*n (exe 13 in 204 s): \sourceon nameDerSprache 17 1 2 3 10873579079 hyperG in 13,00 h 17 1 3 4 11265391089 hyperG in 13,50 h 17 1 4 5 11726044854 hyperG in 13,75 h 17 1 5 6 12257306077 hyperG in 14,40 h 17 1 6 7 12866587574 hyperG in 15 h; mit n2 12,39 h 17 1 7 8 13549711175 hyperG in 13,12 h mit n2 ###################### 17 1 8 9 14311511163 hyperG in 13,96 h 17 1 9 10 15173542983 hyperG in 14,99 h 17 1 10 11 16110572783 hyperG in 16,24 h 17 1 11 12 17153121784 hyperG in 17,58 h 17 1 12 13 18251666239 hyperG in 18,99 h 17 1 13 14 19392436217 hyperG in 20,9 h 17 1 14 15 20703689337 hyperG in 7,42 h V n3 also 3 mal schneller#### 17 1 15 16 22138841380 hyperG in 10,3 h 17 1 16 17 23591276423 hyperG in 13,395h 17 1 17 18 24772324686 hyperG in 14,367h 17 1 18 19 26177242793 hyperG in 13,19 h 17 1 19 20 27797557916 hyperG in 14,157h 17 1 20 21 29484194970 hyperG in 16,9 h 17 1 21 22 31216487343 hyperG in 16,3 h 17 1 22 23 32977254286 hyperG in 23,2 h (5 h langsamer als erwartet) 17 1 23 24 34817801899 hyperG in 20,3 h 17 1 24 25 36428557022 hyperG in 21 h 17 1 25 26 36090309522 hyperG in 21,01 h (erster fallender Wert) 17 1 26 27 34455133562 hyperG in 21,5 h 17 1 27 28 35829539300 hyperG in 21,9 h 17 1 28 29 37256636943 hyperG in 22 h 17 1 29 30 38823585285 hyperG in 22 h 17 1 30 31 40418176371 hyperG in 21,6 h 17 1 31 32 42089818503 hyperG in 21,24 h 17 1 32 33 43827831321 pzktupel i 34,49h ####################### 17 1 33 34 45635993229 pzktupel i 35,22h 17 1 34 35 47253269348 pzktupel i 30.22h 17 1 35 36 48902206476 pzktupel i 31,05h 17 1 36 37 50579064214 pzktupel i 32,46h 17 1 37 38 52283058915 pzktupel i 34,56h 17 1 38 39 53996324691 pzktupel i 37,00h 17 1 39 40 55671295146 pzktupel i 39,38h 17 1 40 41 57192254943 pzktupel i 41,47h 17 1 41 42 58763734636 pzktupel i 43,49h 17 1 42 43 60183744398 pzktupel i 51,98h 17 1 43 44 61540079868 hyperG in 30,65h (i9) 17 1 44 45 62807759176 pzktupel i 56,20h 17 1 45 46 63955124900 pzktupel i 56,57h 17 1 46 47 64831433030 pzktupel i 59,57h 17 1 47 48 65650341154 pzktupel i 58,61h 17 1 48 49 65991602320 pzktupel i 58,59h 17 1 49 50 65893060966 pzktupel i 52,21h ##################### 17 1 50 51 63694096074 hyperG in 22,87h # Summe: 1836652173363 =A108235[17] ########################## \sourceoff Mal sehen, was die Optimierungen brachten & ob sich noch jemand traut... Ich kann auch gern Win64 EXE bereitstellen mit Befehlssätzen: - SSE (20 Jahre alte CPU) - AVX (16 ...8 Jahre alte CPU) (zur Not auch Win32 ) Ergänzung: Praktisch haben wir 13 Tage daran gerechnet & optimiert. Alles seriell hintereinander mit 1 Thread (1 Kern) hätte der i9 etwa 915 h benötigt. Wenn man die 17...18 exe parallel laufen lässt, kommt man: - von "unten nach oben" mit 3 Blöcken auf etwa 68 h - "von oben nach unten" mit "sofort nächste exe sobald 1 fertig" auf 60 h


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8028
Wohnort: Milchstraße
  Beitrag No.112, eingetragen 2020-04-24

Hi, auch ich habe jetzt mal "17 1 2 3" ausprobiert und komme auf dasselbe Ergebnis wie hyperG, nämlich 10.873.579.079. Von den Zeiten kann ich aber nur träumen. Ich benötige 17,74 Std. Kannst du, hyperG, bitte noch mal sagen, wie ich an die neueste ausführbare Version deines Programms herankomme, dass ich es bei mir ausprobieren kann? @Kitaktus: Deinen Vorschlag mit den geraden/ungeraden Zahlen fand ich sehr reizvoll und habe diesen aufwändig als Programm umgesetzt. Tja, hat leider nichts gebracht. Die Berechnung von "16 1 2 3" verlangsamte sich dadurch von 1,19 Std. auf 1,74 Std.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.113, eingetragen 2020-04-24

Die neuste Version ist noch mal mindestens 1,3 mal schneller: DreierPartRekuSumAVX.zip was die 15 Stunden auf 11,4 h reduzieren könnte...


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8028
Wohnort: Milchstraße
  Beitrag No.114, eingetragen 2020-04-24

\quoteon(2020-04-24 21:52 - hyperG in Beitrag No. 113) Die neuste Version ist noch mal mindestens 1,3 mal schneller: DreierPartRekuSumAVX.zip was die 15 Stunden auf 11,4 h reduzieren könnte... \quoteoff Vielen Dank! Das Programm läuft bei mir. a(13) in 316 Sekunden. Das ist schneller als mit meinem Programm (460 sec) aber langsamer als bei dir (206 sec).


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.115, eingetragen 2020-04-24

Das war schon die 204 s Version. Habe die Tabelle Beitrag 101 aktualisiert.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.116, eingetragen 2020-04-24

Die 16 1 2 3 dauern bei mir 43 min Ergebnistabelle im Beitrag 101 angepasst.


   Profil
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 340
  Beitrag No.117, eingetragen 2020-04-25

Ich bin für N=12 jetzt runter auf 28s (macht ca. 45% Zeitgewinn; N=13 --> 5.18 min), indem ich vor die eigentliche Berechnung für $n\geq 3$ in der search-Funktion folgende Abfragen eingebaut habe: \sourceon C if (list[0]+list[2*n-1]>list[3*n-1]) return; else if (list[0]+list[2*n-1] == list[3*n-1]) { if (sum < 2*sum2) return; reduce(list, newlist, 2*n-1, 3*n-1, n); // delete triple from list solution[n-1][0]=list[0]; solution[n-1][1]=list[2*n-1]; solution[n-1][2]=list[3*n-1]; search(newlist, n-1, sum - 2* list[3*n-1], sum2 - list[3*n-1]); return; } int k_min = 2; int j_max = 3*n-2; if (list[0]+list[2*n]>=list[3*n-1]) { if (list[0]+list[2*n]==list[3*n-1]) { int s = sum-2*list[3*n-1]; int s2= sum2-list[3*n-1]-list[2*n]+list[2*n-1]; if (s<=2*s2) { reduce(list, newlist, 2*n, 3*n-1, n); // delete triple from list solution[n-1][0]=list[0]; solution[n-1][1]=list[2*n]; solution[n-1][2]=list[3*n-1]; search(newlist,n-1, s, s2); } } if (sum < 2*sum2) return; k_min = 2*n; j_max = 2*n-1; } k = 3*n-1; for (j=j_max; j > 0; j--) { for ( ; ; k-- ) { //... } if (klist[3n-1], so gilt für $i\geq 0$ und $2n-1\leq j < k\leq 3n-1$ die Abschätzung list[i]+list[j] >= list[0] + list[2n-1] > list[3n-1] >= list[k], also list[i]+list[j] > list[k], sodass insbesondere list[j] und list[k] nicht gemeinsam in einem Tripel vorkommen können. Anders formuliert: Von den Werten list[j], $2n-1\leq j \leq 3n-1$ müsste jedes in einem eigenen Tripel (und dort als Summe) vorkommen. Nun gibt es aber davon $n+1$ Stück, während nur noch $n$ Tripel zu bilden sind, Widerspruch. Mit der ersten Abfrage werden also eine Reihe unmöglicher Fälle abgefangen. Gilt aber Gleichheit (der else-if-Fall), so gibt es genau eine Möglichkeit, wo von den n+1 Werten list[2n-1] bis list[3n-1] (mindestens) zwei in einem gemeinsamen Tripel auftauchen können, nämlich genau im Tripel list[0]+list[2n-1]=list[3n-1]. Also muss dieses Tripel Teil der Lösung sein, sodass wir nach weiteren für dieses n gar nicht suchen müssen. Weiterhin wissen wir aber nun zusätzlich, dass die n Zahlen list[2n] bis list[3n-1] auf die n verschiedenen Tripel zu verteilen sind und dort jeweils die Summen darstellen. Also wissen wir, dass sum2 als Summe dieser Zahlen (und damit Summe der "Tripel-Summen" [bei a+b=c ist c die "Tripel-Summe"]) genau[!] der Hälfte der Summe aller Zahlen ausmachen muss, sodass wir hier auf Gleichheit testen können und nur fortfahren müssen, wenn sum == 2*sum2 ist. Tritt der Fall list[0]+list[2n-1] >= list[3n-1] nicht ein, aber zumindest list[0]+list[2n]>list[3n-1], so müssen analog nach eben erfolgter Überlegung die $n$ Werte list[2n] bis list[3n-1] auf $n$ verschiedene Tripel verteilt werden und sind dabei dort jeweils die Summen. Wieder wissen wir nun, dass sum2 genau die Summe der "Tripel-Summen", also sum/2 ist, sodass wir auch hier auf Gleichheit prüfen können. Ist diese erfüllt, so müssen wir nun nur noch nach Tripeln list[0]+list[j]=list[k] mit $j\leq2n-1$ und $k\geq 2n$ suchen, sodass wir die for-Schleifen abbrechen können, wenn k unter diesen Wert fällt. Abschließend: Tritt der Fall list[0]+list[2n] = list[3n-1] ein, so kann entweder dieses Tripel ausgesucht werden (was dann zu einer entsprechenden Reduktion und neuem Rekursionsaufruf führt), oder es sind wieder die n Zahlen list[2n] bis list[3n-1] auf die verbleibenden n verschiedenen Tripel zu verteilen, sodass all das greift, was im vorherigen Absatz steht. ediit: Klammer-Fehler (siehe nachfolgender Beitrag) ausgebessert.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1847
  Beitrag No.118, eingetragen 2020-04-25

Wow, bis nach 4:00 Uhr noch gearbeitet... Hört sich zunächst alles super an, aber der Code lief zunächst nicht. Die Klammer nach dem if (list[0]+list[2*n]==list[3*n-1]) konnte ich ja dann korrigieren [ -> { Die 9,5 s nun in 5,2 s WOW!!! Dann noch meine Optimierungen von n2=n+n; n3=3*n; -> 5,0 s!!! Aber jetz kommt's: für größere Zahlen wird es immer schneller -> mehr als Faktor 2 bei exe 13: \sourceon nameDerSprache Startparameter | exe 13 10 20 30 | exe 12 | exe 13 |16 1 2 3 exe \ CPU; Zeit in s | ? | i7 | i9 | i9 |i7 |Aldi | IxxNB |Aldi | i9 |i9 |Aldi ------------------------+--------+-------+-------+------+----+-----+-------+-----+------------+-----+---- Borland CB6 / MingW-w64 | 35 | 18 | 16 | 29 | 33 | | | | | | DreierPartitionen32 | | 20,49 | 17,3 | | | | | | | | DreierPartitionen | | 17,42 | 14,5 | | | | 5 min| |4,88 min | |71,4 min Ixx+hyperG | | 16,18 | 13,47 | | | 60 s| | | | | Ixx+hyperG+SumAVX | | | 12,7 |22.9 | | | | | | | IxxRekuSum + hyperG-Opt | | 10,6 | 9,82 |17.5 | 19 | | | |3,46 min | | n2 | | 11 | 9,6 |17,3 | 20 | | | 316 |204s=3,4 min|43min| IxxRekuSum per MingWw64 | | 12 | 12 |23 | 23 | | 55 s| | | IxxRekuSum + Vorfiltern3| | | 5,0 |8,44 | | | 28 s| |94,8s=1,5min| \sourceoff


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 7009
Wohnort: Niedersachsen
  Beitrag No.119, eingetragen 2020-04-25

Es gibt (insbesondere durch Ixxs Ausführungen ist das nochmal deutlich geworden) Situationen, in denen man schon weiß, dass von den verbleibenden 3k Zahlen die oberen k Zahlen genau die Zahlen sind, die als Summe in den Tripeln auftreten. Wenn dieser Fall einmal eingetreten ist, wird sich das auch nicht mehr ändern, wenn man tiefer in die Rekursion hinabsteigt. Wenn man schon sicher _weiß_, dass die oberen k Zahlen genau der Summe der unteren 2k Zahlen entspricht, dann kann man einige Schritte weglassen. Man muss diese Summen nicht mehr berechnen, man muss keine Fallunterscheidungen nach dieser Summe mehr ausführen und man muss nur noch Konstellationen berücksichtigen, bei denen die beiden Summanden zu den ersten 2k Zahlen gehören und die Summe zu den größten k Zahlen. Die Idee ist, in diesem Fall nur noch eine abgespeckte Variante der Rekursion aufzurufen, die schneller ist, als die "volle" Variante. Vermutlich wird durch die Idee von Ixx schon eine Menge des Verbesserungspotentials gehoben, aber vielleicht lässt sich noch ein bisschen was rausholen.


   Profil
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
-->> Fortsetzung auf der nächsten Seite -->>
Seite 3Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6  

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]