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 2   [1 2 3 4 5 6]   6 Seiten
Autor
Kein bestimmter Bereich * Das kaputte (¼) Osterei
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8028
Wohnort: Milchstraße
  Beitrag No.40, eingetragen 2020-04-18

\quoteon(2020-04-18 00:38 - hyperG in Beitrag No. 37) Die 17er sind doch sehr viel größer: \quoteoff Interessant. Da habe ich mich noch nicht dran gewagt. Hältst du es für realistisch, das auch für große Werte zuende zu rechnen, also bis zu (1 50 51)?


   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.41, eingetragen 2020-04-18

So, ich habe jetzt für den Matheplanet einen Artikel in englischer Sprache verfasst. Matroid hat ihn bereits freigegeben. Kommentare sind willkommen, auch zum Sprachlichen. Jetzt muss ich nur noch jemanden von OEIS hierher locken 😃


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

\quoteon(2020-04-18 18:47 - StrgAltEntf in Beitrag No. 40) \quoteon(2020-04-18 00:38 - hyperG in Beitrag No. 37) Die 17er sind doch sehr viel größer: \quoteoff Interessant. Da habe ich mich noch nicht dran gewagt. Hältst du es für realistisch, das auch für große Werte zuende zu rechnen, also bis zu (1 51 52)? \quoteoff Also eher (1 50 51),oder ? Für die 17 braucht man eben ~10fache Zeit und 1.5 Bio in der Gesamtanzahl. Ein Monat dürfte reichen. Gruß


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

Hallo pzktupel, \quoteon(2020-04-18 19:41 - pzktupel in Beitrag No. 42) Also eher (1 50 51),oder ? Für die 17 braucht man eben ~10fache Zeit und 1.5 Bio in der Gesamtanzahl. Ein Monat dürfte reichen. \quoteoff Wie kommst du auf den Faktor 10? Hast du bereits irgendwelche Rechnungen durchgeführt? Und: Klar, sollte (1 50 51) heißen. Habe es oben verbessert.


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

Ich kann Euch ja meine exe zum Download anbieten -> die war mindestens doppelt so schnell (5,8 statt 12 h). Die 13 h für die ersten 3 Werte sind für mich Maximum, da ich nachts ausschalten muss. Optimierungsmöglichkeiten: a) Für Vielfache von 16 habe ich auch eine schnellere Addition mit SSE/AVX, aber diese Sonderfälle sind zu selten. (da würde eine Abfrage nach n % 16 die gewonnene Zeit wieder auffressen) Was aber geht, ist die Aufsplittung einer for-Schleife -for(j=1...15) - schneller Sonderfall mit 16 additionen - for(j=17...31) - schneller Sonderfall b) Kann man die erste for Schleife for(j=1; j<3*n; j++) der Rekursions-Funktion search() nicht nach AUßen holen? Dann kann ich entweder mehrere Task ansetzen, oder über einen weiteren Übergabeparameter startet man einfach mehrere EXE. c) weg von der Rekursion. Die sind zwar schön anzuschauen, aber bremsen die Effektivgeschwindigkeit Hier schon mal der Anfang der Tabelle \sourceon 17 er Partitionen 17 1 2 3 10873579079 hyperG 13 h 17 1 3 4 11265391089 hyperG 13,46 h 17 1 4 5 11726044854 hyperG 13,75 h 17 1 5 6 in Arbeit hyperG 17 1 6 7 in Arbeit hyperG ... \sourceoff [Die Antwort wurde nach Beitrag No.42 begonnen.]


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

Faktor 10 kommt hin: ich brauche 1,714 h pro 1 Mrd. Der 1. 16er hatte etwa 1, 5 h der 1. 17er hatte etwa 13 h also fast das 10fache und es kommen ja noch am Ende 3 mehr hinzu.


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

\quoteon(2020-04-18 20:44 - hyperG in Beitrag No. 44) Ich kann Euch ja meine exe zum Download anbieten -> die war mindestens doppelt so schnell (5,8 statt 12 h). \quoteoff Faktor 0,5 ist ja mal eine Ansage. Würdest du auch deinen Quellcode bekanntgeben?


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

@StrgAltEntf Das resultiert aus den bisherigen Ergebnissen. ...und hyperG ermittelte ja auch den Anfang mit etwa Faktor 10 in der Anzahl. Anmerkung: Die nächste Stufe mit n=20 würde ich nicht empfehlen, da die Summe sich auf >1 Billiarde (10^15) beläuft. Vielleicht lässt sich eine Summe aus einer Summation von geschickten Biominialkoeffizieten schneller berechnen.


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

\quoteon(2020-04-18 21:52 - pzktupel in Beitrag No. 47) Anmerkung: Die nächste Stufe mit n=20 würde ich nicht empfehlen, da die Summe sich auf >1 Billiarde (10^15) beläuft. Vielleicht lässt sich eine Summe aus einer Summation von geschickten Biominialkoeffizieten schneller berechnen. \quoteoff Die 20 würde ich auch erst einmal zurückstellen 🙃 Dass sich hier eine Formel (mit Binomialkoeffizieten oder wie auch immer) herleiten lässt, glaube ich eher weniger.


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

Man könnte mal testen, ab wann eigentlich der Summen-Test anschlägt und zeigt, dass es mit dieser bisherigen Auswahl keine Lösung gibt. Vermutlich wird das erst in einer gewissen Tiefe der Fall sein, sodass man davor auf diesen verzichten kann. Wahrscheinlich wird aber die meiste Rechenarbeit in noch tieferen Ebenen stattfinden. Die Frage ist, ob man hier optimieren kann. Bei der Suche nach einem neuen Tripel fällt mir auf, dass du linear für list[0]+list[j] suchst, ob dies in der liste enthalten ist (und wenn ja, wie dessen Index k lautet). Binäre Suche könnte hier schneller sein. Ne Kleinigkeit wäre, dass man das neue Tripel erst dann zur Lösung solution hinzufügt, wenn nicht die reduzierte Liste zum Widerspruch geführt hat. Dies nur als kleine Stellen, die mir beim Lesen des Codes aus #4 aufgefallen sind. Substantielle Verbesserungen (wenn überhaupt) wird das zwar nicht bringen, da der Hauptteil der Rechenarbeit bei wohl eher vergleichsweise kleinen Arrays stattfinden wird, aber ich wollte es mal geschrieben haben.


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

\quoteon(2020-04-18 21:41 - StrgAltEntf in Beitrag No. 46) ... Faktor 0,5 ist ja mal eine Ansage. Würdest du auch deinen Quellcode bekanntgeben? \quoteoff Etwa doppelt so schnell kommt aus 2 Quellen: - gonz hatte etwa 12 h gebraucht, wo ich 5,8 h brauchte - DreierPartitionenFast16Bit.exe 13 10 20 30 bei Dir Beitrag 12 35 Sek (handgestoppt) entsprach mein i7 unoptimiert 21 s; i9 CPU 19 s Code-Änderung nur die 2 bereits genannten: a) in Beitrag 17 Variablen-Typ von 32 auf 16 Bit (8 Bit wird dann wieder lagsamer) nur 1...5% -> da Dein %d funktioniert, hat Dein Compiler vermutlich eine 16 Bit variable daraus gemacht b) Funktion reduce aufgelöst -> bekommt man vermutlich mit einem "inline" vor der Zeile genau so hin (spart Stack Arbeit 1...5%) nun partitions = 3987507 in 14.717 s Der größte Teil kommt vom Compiler + CPU, der zusätzlich auf AVX Optimierung eingestellt ist (können alte Compiler & CPUs nicht): https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_AVX.PNG Auch die Ausrichtung auf Adressenvielfache spielt eine große Rolle. Das reicht aber noch lange nicht, wenn selbst der kleinste 17er mit meiner schnellsten Kombination noch über 13 h dauert. Ich schaue mir noch an: - die äußere for-Schleife (entweder mehrere Threads oder über exe Übergabe-Parameter) - am besten weg von der Rekursion (die sind immer langsam) - klar wäre explizite Summenformel noch besser Morgen mehr


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

Nen paar wenige Prozent Laufzeit habe ich dadurch rauskitzeln können, dass ich die letzten 6 Elemente explizit betrachtet habe und dementsprechend der Rekursionsabbruch bei n=2 erfolgt. Zusammen mit der binären Suche für list[0]+list[j] bei der Tripel-Suche kam ich in meinen Tests auf ca. 20% Zeitersparnis. Der entsprechende Code-Schnipsel sieht wenig hübsch wie folgt aus: \showon Der Quelltext \sourceon C //--------------------------------------------------------------------------- int binsearch(int list[3*Nmax], int val, int low, int high) { int l=low; int h=high; while (l


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

Mit dieser EXE hier können wir ja mal vergleichen. \sourceon DreierPartitionen.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 \sourceoff Die DLL habe ich in die ZIP mit hineingepackt, falls jemand die Runtime nicht installiert hat. Die exe ist Win 64 Bit mit AVX Befehlen (führt bei CPU ohne AVX-Befehlssatz garantiert zum Absturz; ist aber seit 12 Jahren Standard). Eine Erkennung, ob CPU AVX hat, könnte ich noch einbauen, wenn jemand Angst oder sehr großes Interesse hat... Die BAT garantiert, dass wir alle den selben Test starten.


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

Achtung! Da der Code von Ixx schon bei n==2 endet, fehlen die letzten 2, was der builtintest auch anzeigt, wenn man ihn aktiviert: \sourceon nameDerSprache if(builtintest()){ // for paranoids ... may be omitted printsolution(); printf("Fatal error in program!\n"); std::cin.get(); exit(0); } No. 0 (10 20 30) (1 2 3) (4 9 13) (5 24 29) (6 25 31) (7 26 33) (8 27 35) (11 28 39) (12 22 34) (14 18 32) (15 21 36) (0 0 0) (0 0 0) Fatal error in program! \sourceoff Korrektur: da dieser Fall am Ende nie gezählt wird, ist builtintest hier nie zu aktivieren.


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

Man müsste diese Überprüfung halt in jeden Fall packen, wenn eine Lösung gefunden wurde. Es werden da ja die letzten zwei Tripel in die solution eingetragen.


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

Ja stimmt, dieser letzte Fall ist ja ein "nicht passender", der ja auch nicht gezählt wird. -> kann man doch gelten lassen. hier die GLIxxAVX.zip Mit der Parallelen j Laufvariable hat es nicht funktioniert, da durch die Rekursion leider doch ein serielles "hintereinander Abarbeiten" der Felder davor nötig ist :-( AVX greift auch nicht richtig, da immer nur winzig kleine Arrays bearbeitet werden. Ich brauche aber Vielfache von 16.


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

Hier der zusammengeführte Code von Ixx & mir: ##### 2 Änderungen am 20.04.2020: ############## - memset für definierte list gleich nach Deklaration - for-j-Schleife 1 weniger #################################################### \showon \sourceon cpp #include //nur wenn man AVX Befehle explizit verwendet #define __IS16BitVAR #if defined (__IS16BitVAR) #define OptimalTyp __int16 #else #define OptimalTyp unsigned char #endif Änderung 1: nur in der main gleich nach Deklaration: memset(&list[0], 0, sizeof(OptimalTyp)*Nmax * 3); inline OptimalTyp binsearch(OptimalTyp *list, OptimalTyp val, OptimalTyp low, OptimalTyp high) // list[3 * Nmax] { OptimalTyp m,l = low, h = high; while (l < h - 1) { m = (l + h) >> 1;// / 2 if (val == list[m]) return m; else if (val < list[m]) h = m; else l = m + 1; } if (val == list[l]) return l; else return 0; } void search(OptimalTyp *list, OptimalTyp n) // list[3*Nmax] { OptimalTyp newlist[3*Nmax]; OptimalTyp j, k , m, i; uint32_t sum1, sum2;//__int16 if (n == 2) { if ((list[0] + list[1] == list[2]) && (list[3] + list[4] == list[5])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[1]; // ... to print it out later solution[1][2] = list[2]; // ... (may be omitted) solution[0][0] = list[3]; solution[0][1] = list[4]; // ... to print it out later solution[0][2] = list[5]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[1] == list[3]) && (list[2] + list[4] == list[5])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[1]; // ... to print it out later solution[1][2] = list[3]; // ... (may be omitted) solution[0][0] = list[2]; solution[0][1] = list[4]; // ... to print it out later solution[0][2] = list[5]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[1] == list[4]) && (list[2] + list[3] == list[5])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[1]; // ... to print it out later solution[1][2] = list[4]; // ... (may be omitted) solution[0][0] = list[2]; solution[0][1] = list[3]; // ... to print it out later solution[0][2] = list[5]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[2] == list[3]) && (list[1] + list[4] == list[5])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[2]; // ... to print it out later solution[1][2] = list[3]; // ... (may be omitted) solution[0][0] = list[1]; solution[0][1] = list[4]; // ... to print it out later solution[0][2] = list[5]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[2] == list[4]) && (list[1] + list[3] == list[5])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[2]; // ... to print it out later solution[1][2] = list[4]; // ... (may be omitted) solution[0][0] = list[1]; solution[0][1] = list[3]; // ... to print it out later solution[0][2] = list[5]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[3] == list[4]) && (list[1] + list[2] == list[5])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[3]; // ... to print it out later solution[1][2] = list[4]; // ... (may be omitted) solution[0][0] = list[1]; solution[0][1] = list[2]; // ... to print it out later solution[0][2] = list[5]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[3] == list[5]) && (list[1] + list[2] == list[4])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[3]; // ... to print it out later solution[1][2] = list[5]; // ... (may be omitted) solution[0][0] = list[1]; solution[0][1] = list[2]; // ... to print it out later solution[0][2] = list[4]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } if ((list[0] + list[4] == list[5]) && (list[1] + list[2] == list[3])) { solutioncounter++; // BINGO! Valid partition found solution[1][0] = list[0]; // add triple to solutions solution[1][1] = list[4]; // ... to print it out later solution[1][2] = list[5]; // ... (may be omitted) solution[0][0] = list[1]; solution[0][1] = list[2]; // ... to print it out later solution[0][2] = list[3]; // ... (may be omitted) if ((solutioncounter % boundary[N]) < 1) printsolution(); // may be omitted return; } //if(builtintest()) hier nicht! return; } for (j = 1; j < 3*n-1; j++) //2. Änderung: statt 3 * n nur 3 * n-1 { k = binsearch(list, list[0] + list[j], j + 1, 3 * n); // searching for triplets (list[0] list[j] list[k]) if (k != 0) { // new triple found solution[n - 1][0] = list[0]; // add triple to solutions solution[n - 1][1] = list[j]; // ... to print it out later solution[n - 1][2] = list[k]; // ... (may be omitted) // if (reduce(list, newlist, j, k, n)) continue; sum1 = 0; sum2 = 0; m = 0; for (i = 1; i < j; i++) newlist[m++] = list[i]; for (i = j + 1; i < k; i++) newlist[m++] = list[i]; for (i = k + 1; i < 3 * n; i++) newlist[m++] = list[i]; for (i = 0; i < 2 * n - 2; i++) sum1 += newlist[i];// for (i = 2 * n - 2; i < 3 * n - 3; i++) sum2 += newlist[i]; if (sum1 > sum2) continue; search(newlist, n - 1); // search shortened list //break; } } } \sourceoff \showoff Tests mit 8Bit Variablen (unsigned char) erforderten bei der Anzeige eine while-Schleife & brachten etwas langsameren Code. Da aber 16er-Byte-Blöcke mit SSE2/AVX schneller werden könnten, habe ich es zunächst so belassen. Eure Zeiten würden mich schon interessieren.


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

Da A108235(13)=103372655= A002849(39)= 103372655 habe ich mal den dortigen Pari-Code mit unserer schnellsten exe ( je als 1 Thread also nichts parallel) verglichen. \sourceon Pari/GP nxyz(v, t)=local(n, r, x2); r=0; if(t==0, return(1)); for(i3=3*t, #v, n=v[i3]; for(i1=1, i3-2, x2=n-v[i1]; if(x2<=v[i1], break); for(i2=i1+1, i3-1, if(v[i2]>=x2, if(v[i2]==x2, r+=nxyz(vector(i3-3, k, v[if(k


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

Beim Vergleich mit dem 12er A108235(12)=A002849(36)=10567748 kam bei der letzten Optimierung jedoch ein anderes Ergebnis: \sourceon nameDerSprache DreierPartIxxAVX.exe 12 No. 10400000 (1 35 36) (2 27 29) (3 22 25) (4 24 28) (5 15 20) (6 8 14) (7 26 33) (9 23 32) (10 11 21) (12 19 31) (13 17 30) (16 18 34) No. 10500000 (1 35 36) (2 30 32) (3 24 27) (4 13 17) (5 23 28) (6 16 22) (7 18 25) (8 26 34) (9 10 19) (11 20 31) (12 21 33) (14 15 29) Number of valid partitions = 10569630 in 29.168 s Wiederholung: DreierPartIxxAVX.exe 12 No. 10400000 (1 35 36) (2 27 29) (3 23 26) (4 17 21) (5 28 33) (6 8 14) (7 24 31) (9 13 22) (10 15 25) (11 19 30) (12 20 32) (16 18 34) No. 10500000 (1 35 36) (2 30 32) (3 24 27) (4 25 29) (5 23 28) (6 12 18) (7 15 22) (8 9 17) (10 16 26) (11 20 31) (13 21 34) (14 19 33) Number of valid partitions = 10567748 in 29.095 s DreierPartitionen.exe 12 No. 10400000 (1 35 36) (2 27 29) (3 23 26) (4 17 21) (5 28 33) (6 8 14) (7 24 31) (9 13 22) (10 15 25) (11 19 30) (12 20 32) (16 18 34) No. 10500000 (1 35 36) (2 30 32) (3 24 27) (4 25 29) (5 23 28) (6 12 18) (7 15 22) (8 9 17) (10 16 26) (11 20 31) (13 21 34) (14 19 33) Number of valid partitions = 10567748 in 31.821 s \sourceoff Das sieht nach fehlender Initialisierung einer Variablen aus, wenn trotz immer gleicher Parameter nicht immer das selbe Ergebnis herauskommt... (Pari 25 min; i9 24 s)


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

Hier zur Fehlersuche die Ergebnisse der 12er nach der letzten Optimierung. Die ersten 3 Zeilen habe ich nun immer mit ausgegeben Referenz für OK-Fall: https://www.lamprechts.de/exe/12erOK_Fall_748.txt Und hier die Fehler, die beim i7 etwa jeden 20. Fall auftreten: https://www.lamprechts.de/exe/Falscher12erErsten3_177.txt https://www.lamprechts.de/exe/Falscher12erErsten3_821.txt https://www.lamprechts.de/exe/Falscher12erErsten3_630.txt


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

Ich sehe kein Problem im angegebenen Code; bei mir trat bisher auch keine solche Abweichung auf, wobei ich auch nicht exzessiv getestet habe.


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

Komisch, dass die Fehler nur beim i7 unter Win7 auftraten. Dieser hat weniger RAM und da könnten häufiger RAM-Bereiche ungleich Byte 00 vorliegen. Ich werde mal die Überprüfung der Zeilen per builtintest für jeden Fall aktivieren, der gezählt wird.


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

Beim i7: \sourceon nameDerSprache No. 10129302 (1 35 36) (2 14 16) (3 32 35) (4 30 34) (5 18 23) (6 19 25) (7 22 29) (8 20 28) (9 17 26) (10 21 31) (11 13 24) (12 15 27) Falsche Summe bei 10129302! \sourceoff 33 fehlt & 35 doppelt! Durch die verkürzte Abfrage der letzten beiden n-Fälle if ((list[0] + list[4] == list[5]) && (list[1] + list[2] == list[3])) ... stimmen zwar die Summen, aber doppelte Glieder werden nicht abgefangen...


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

Da in der von dir angegebenen Partition die doppelte 35 schon im ersten Tripel enthalten ist, was also für n=12 direkt am Anfang ermittelt wird, muss dort bei der Löschung was schiefgelaufen sein.


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

Ah, ich hab's: Das Problem liegt in der Schleife in der search-Funktion: Dort sollte j nur bis 3n-2 laufen, da das größte Element list[3n-1] keiner der Summanden sein kann. (Das Problem dürfte entstanden sein, weil dadurch nicht gesichert war, dass binaryserach nur mit Suchintervallgrenzen low


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

Zwar stimmte es, dass die j-Schleife nur bis 3n-2 (also j < 3*n-1 ) aber es gibt unter Win7 immer noch Fehler \sourceon nameDerSprache No. 81326 (1 2 3) (4 34 38) (5 17 22) (6 20 26) (7 21 28) (8 23 31) (9 24 33) (10 25 35) (11 16 27) (12 18 30) (13 19 32) (14 15 29) Falsche Summe bei 81326! 36 fehlt aber 38 zu viel \sourceoff Die 38 kann doch nur aus einem nicht eindeutig initialisierten Array kommen...


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

Offenbar greift binsearch immer noch ggf. über den eigentlichen Zugriffsbereich hinaus: Eigentlich sucht binsearch im Intervall [low; high[ , aber ist l=3n-2 und h=3n, so ist m=3n-1. Ist nun val>list[m], wird l=m+1=3n gesetzt und in der abschließenden Prüfung an dieser Stelle der passende Wert, wird der Index 3n zurückgegeben, der außerhalb des eigentlich zu betrachtenden Bereichs liegt. Ein schneller Hack wäre, dass man das Nichtfinden generell nicht mit dem Rückgabewert 0, sondern mit dem Wert high=3n belegt, und dann in der search-Funktion nicht auf "k!=0", sondern auf k"!=3n" prüft. Schneller (bezügl. der Laufzeit) könnte in der j-For-Schleife der search-Funktion die zusätzliche Prüfung list[0]+list[j]<=list[3n-1] sein; habe ich aber nicht ausprobiert. Und ja, der Fehler tritt bei mir wohl deshalb nicht auf, weil die Arrays alle automatisch 0-initiallisiert sind, während die von dir verwendeten Pointer natürlich nicht notwendigerweise auf leeren Speicher zeigen. In der search-Funktion werden ja nur so viele Werte gesetzt, wie noch im Aufruf der nächsten Iterationstiefe verwendet werden, sodass ein Griff über die Intervallgrenzen hinaus auf beliebige Werte zeigen können.


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

\quoteon(2020-04-20 16:55 - Ixx in Beitrag No. 66) Offenbar greift binsearch immer noch ggf. über den eigentlichen Zugriffsbereich hinaus: Eigentlich sucht binsearch im Intervall [low; high[ , aber ist l=3n-2 und h=3n, so ist m=3n-1. Ist nun val>list[m], wird l=m+1=3n gesetzt und in der abschließenden Prüfung an dieser Stelle der passende Wert, wird der Index 3n zurückgegeben, der außerhalb des eigentlich zu betrachtenden Bereichs liegt. Ein schneller Hack wäre, dass man das Nichtfinden generell nicht mit dem Rückgabewert 0, sondern mit dem Wert high=3n belegt, und dann in der search-Funktion nicht auf "k!=0", sondern auf k"!=3n" prüft. \quoteoff Hm, ich weiß ja nicht, ob man ein Fehlverhalten von dubiosem* Code durch ein Workaround begegnen sollte. Darf ich fragen, wie viel Ersparnis binsearch gegenüber der linearen Suche überhaupt gebracht hat? * Verzeiht, wenn ich es so nenne, aber anscheinend ist die Funktionsweise der Funktion binsearch hier nicht vollkommen klar.


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

Es ist normale binäre Suche. Natürlich ist jedem selbst überlassen, das auch ordentlicher umzusetzen als ich es getan habe. Wobei ich schon meine, dass ein O(log n)) deutlich O(n) schlägt...


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

So, jetzt geht's. Es lag wie vermutet an der fehlenden Initialisierung des Arrays. \sourceon cpp memset(&list[0], 0, sizeof(OptimalTyp)*Nmax * 3); \sourceoff Damit sind die Ausgangsbedingungen immer gleich! Zusammen mit den Änderungen der for-j-Schleife ändere ich noch den Code und in den nächsten 10 min die letzte & schnellste zip. Eure Zeiten interessieren mich noch immer... [Die Antwort wurde nach Beitrag No.66 begonnen.]


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

Leider verstehe ich den Code nur zum Bruchteil. Macht es Sinn, ein n-dimensionales Feld zusätzlich zu schalten, wo eine Verwendete Zahl in diesem Feld auf 1 gesetzt wird, andernfalls wieder auf 0 ? Wird in einem Tripel die 3. Zahl aus der Summe der ersten beiden automatisch generiert,ohne Schleife ? Könnte man eine Prüfsumme S mit einbinden S=(p^2+p)/2, p hier alle Zahlen 1-3n Gruß P.S. Erbitte Nachsicht, falls bereits vorhanden. [Die Antwort wurde nach Beitrag No.68 begonnen.]


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

\quoteon(2020-04-20 18:02 - StrgAltEntf in Beitrag No. 67) ... wie viel Ersparnis binsearch gegenüber der linearen Suche überhaupt gebracht hat? ... \quoteoff Ich halte die Tabelle Beitrag 52 aktuell: etwa 1 s pro 4 Mio. Datensätze (Zeilen). [Die Antwort wurde nach Beitrag No.69 begonnen.]


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

... was nicht heißen soll, dass die obige Implementation der binären Suche die beste ist. Die sollte schon sicher nicht über den zu betrachtenden Bereich hinausreichen. Insofern bitte gerne sauberer programmieren, als ich das vor ein paar Tagen mitten in der Nacht gemacht habe! :)


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

\quoteon(2020-04-20 18:23 - pzktupel in Beitrag No. 70) Leider verstehe ich den Code nur zum Bruchteil. Macht es Sinn, ein n-dimensionales Feld zusätzlich zu schalten, wo eine Verwendete Zahl in diesem Feld auf 1 gesetzt wird, andernfalls wieder auf 0 ? Wird in einem Tripel die 3. Zahl aus der Summe der ersten beiden automatisch generiert,ohne Schleife ? Könnte man eine Prüfsumme S mit einbinden S=(p^2+p)/2, p hier alle Zahlen 1-3n Gruß P.S. Erbitte Nachsicht, falls bereits vorhanden. [Die Antwort wurde nach Beitrag No.68 begonnen.] \quoteoff - 17-Dimensionale Felder würden extrem Zeit fressen - mit den beiden for Schleifen (oder binsearch) wird schon sicher gestellt, dass die 2. Laufvariable immer mindestens 1 größer ist - extra Prüfsumme pro Datensatz per builtintest frisst etwa 1s pro 20 Mio. Datensätze [Die Antwort wurde nach Beitrag No.71 begonnen.]


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

Oh, da habe ich Quatsch erzählt...meinte ein Feld der Größe n (3n) nicht dimensional. Also , das jede Zahl die gerade verwendet wird, durch die Belegung im Feld nicht extra gesucht werden brauch. (1,2,3).... Feld[1]=true,Feld[2]=true,Feld[3]=true Feld[4...3n]=false der Art.


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

\quoteon(2020-04-20 18:41 - Ixx in Beitrag No. 72) ... sollte schon sicher nicht über den zu betrachtenden Bereich hinausreichen. Insofern bitte gerne sauberer programmieren, als ich das vor ein paar Tagen mitten in der Nacht gemacht habe! :) \quoteoff Die for-j-Schleife wurde schon korrigiert (Beitrag 65 + 69 + verlinkte ZIP in Beitrag 55). Eine weitere Verkürzung von binsearch(list, list[0] + list[j], j + 1, 3*n); nach binsearch(list, list[0] + list[j], j + 1, 3*n-1); (die auch StrgAltEntf schon anfragte) ist zu viel & erzeugt Fehler. Ich merke schon, dass Ihr die beiden exe nicht testen wollt... Das wäre doch auch ein schöner Vergleich der Compiler... [Die Antwort wurde nach Beitrag No.73 begonnen.]


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

Was richtig effektiv wäre, ist https://en.wikipedia.org/wiki/Dancing_Links so wie es z.B. per Sage so aussieht: \sourceon Sage A = lambda n:sum(1 for t in DLXCPP([(a-1, b-1, a+b-1) for a in (1..3*n) for b in (1..min(3*n-a, a-1))])) \sourceoff Aber es gibt so viele Seiten zu DLXCPP oder https://www.npmjs.com/package/dlxlib und jeder verwendet andere Parameter...


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

Über Dancing Links habe ich auch nachgedacht, denke aber nicht, dass das hier viel bringt. Das Verfahren funktioniert ja dann gut, wenn es viel ums Raus- und Rein von verschiedenen Elementen in doppelt verketteten Listen geht. Unsere Daten liegen in Arrays vor, und ich denke, der Overhead der Implementierung einer doppelt verketteten Liste dürfte hier nicht schneller sein.


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

Zunächst einmal freut es mich, wenn ihr das Programm optimiert! \quoteon(2020-04-20 18:05 - Ixx in Beitrag No. 68) Wobei ich schon meine, dass ein O(log n)) deutlich O(n) schlägt... \quoteoff Wenn der Algorithmus den Wert a(n) in einer Zeit von O(log(n)) anstatt O(n) berechnen würde, würde ich dir sofort zustimmen. 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. 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? 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. Ebenso hat es die Laufzeit nicht messbar verbessert, die Zuweisung der Variablen solution erst nach einem erfolgreichen Test in reduce durchzuführen. 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. 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. Grüße StrgAltEntf [Die Antwort wurde nach Beitrag No.73 begonnen.]


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

Momentan bin ich bei weiteren 2 (noch nicht veröffentlichten) 17er um die 14 Stunden mit der schnellsten EXE. Ob ich allein die 17er weitermache, hängt von der Motivation ab, die momentan nicht sehr hoch ist. Bekommt man nicht doch bei der Summation den 16er Byte-Block hin? Ich probier das mal mit: if (Größe % 16) AVX else for(, Größe) sum1=... endif [Die Antwort wurde nach Beitrag No.77 begonnen.]


   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 2Gehe 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]