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
Druckversion
Druckversion
Antworten
Antworten
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: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.80, eingetragen 2020-04-20


2020-04-20 19:25 - StrgAltEntf in Beitrag No. 78 schreibt:
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.

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.


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?

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.


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.

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...


Ebenso hat es die Laufzeit nicht messbar verbessert, die Zuweisung der Variablen solution erst nach einem erfolgreichen Test in reduce durchzuführen.

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.


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.

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.


 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.

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. :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
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: 6011
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
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
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6011
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.83, eingetragen 2020-04-20


2020-04-20 20:03 - Ixx in Beitrag No. 80 schreibt:
...
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. :)

Also habe ich das gleich als erstes meiner vielen Vorschläge getestet:
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];	  
}

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.:
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

Bei n=17 reicht es nicht für einen 2. Fall, da (17-1)*2-2 < 32 :-(



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.85, eingetragen 2020-04-20


2020-04-20 21:54 - StrgAltEntf in Beitrag No. 81 schreibt:
...
 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.
...
SumAVX.exe
i9 10567748 in  22.9 s
i7 10567748 in  27.2 s


[Die Antwort wurde nach Beitrag No.83 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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]<list[k], so können wir die Suche für list[0]+list[j+1] nur bei k starten.)

edit: Da es uns um die letzten paar Tripel geht und dort die kleinsten Werte schon relativ groß sind, könnte es vielleicht helfen, dort bei der Suche nach einem k für list[0]+list[j]=list[k] "von hinten", also mit 3n-1 anzufangen zu prüfen. Probiere ich bei Gelegenheit vielleicht mal aus...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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)

Quelltext
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]<list[0]+list[j]
					break; //next j
 
				}
				else if (list[k] < list[0]+list[j])
				{
					// largest k with list[k]<list[0]+list[j]
					break; // next j
				}
			}
		}
    }



Mit der Laufzeit bin ich jetzt auf knapp unter 3 Minuten für n=12 herunter, sodass das noch einmal ca. 25% Zeitersparnis wären. Außerdem sind binsearch und linsearch wieder rausgeflogen, sodass der Code wieder fast die Struktur wie zu Beginn hat. :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.89, eingetragen 2020-04-21


2020-04-20 22:38 - hyperG in Beitrag No. 83 schreibt:
Also habe ich das gleich als erstes meiner vielen Vorschläge getestet:
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];	  
}


Also zumindest für größere n könntest du diese Einsparung ja auch einbauen:
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];	  

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.

Quelltext geänderter Funktionen
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<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=2*n-2; i<3*n-3; i++)
        sum2 += newlist[i];
 
      if(sum > 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]<list[0]+list[j]
					break; //next j
 
				}
				else if (list[k] < list[0]+list[j])
				{
					// largest k with list[k]<list[0]+list[j]
					break; // next j
				}
			}
		}
    }
 
 
    //---------------------------------------------------------------------------
 
// Nur Rekursionsaufruf mit Summe aller Elemente bzw. aller bis auf erstem Tripel ergänzt
 
    int main(int ac, char **av){
      int list[3*Nmax];
      int i, j, a, b, c, error = 0, hlp;
      time_t begin, end, total;
 
      time(&begin);
 
      printf("===================\n");
      printf("|   OEIS A108235  |\n");
      printf("===================\n");
 
      if(ac != 2 && ac !=5){
        printf("Usage:\n");
        printf("    %s N\n", av[0]);
        printf("  or\n");
        printf("    %s N a b c\n", av[0]);
        printf("  (a + b = c)\n");
        return 1;
      }
 
      N = atoi(av[1]);
      int sum = 3*N*(3*N+1)/2;
 
      printf("Compute f(N) for N = %d\n", N);
 
      if(boundary[N] == 1)
        printf("Output every solution\n");
      else
        printf("Output every %d-th solution\n", boundary[N]);
 
      if(N > 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<a; i++)
          list[j++] = i;
        for(i=a+1; i<b; i++)
          list[j++] = i;
        for(i=b+1; i<c; i++)
          list[j++] = i;
        for(i=c+1; i<=3*N; i++)
          list[j++] = i;
 
        solution[N-1][0] = a;  // add triple (a b c) to the solutions
        solution[N-1][1] = b;
        solution[N-1][2] = c;
 
        search(list, N-1, sum-2*c);     // call of the recursive function
      }
      else{
        printf("Find %d disjoint triplets from 1...%d\n", N, 3*N);
 
        for(i=0; i<3*N; i++)   // create initial list
          list[i] = i+1;
 
        search(list, N, sum);       // call of the recursive function
      }
 
      printf("Number of valid partitions = %Ld\n", solutioncounter);
 
      // calculate the time needed
      time(&end);
      total = end - begin;
      if(total < 60)
        printf("Time needed: %d sec\n", total);
      else if(total < 3600)
        printf("Time needed: %.2f min\n", (double)total/60.);
      else
       printf("Time needed: %.2f h\n", (double)total/3600.);
 
      return 0;
    }






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:


    // 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; 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];
    }
 
    //---------------------------------------------------------------------------     
    // Recursive search for valid partitions in a list of length 3*n
    void search(const int list[3*Nmax], const int n, const int sum, const int sum2)
    {
		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];
					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]<list[0]+list[j]
					break; //next j
 
				}
				else if (list[k] < list[0]+list[j])
				{
					// largest k with list[k]<list[0]+list[j]
					break; // next j
				}
			}
		}
    }
 
    //---------------------------------------------------------------------------
 
    int main(int ac, char **av){
      int list[3*Nmax];
      int i, j, a, b, c, error = 0, hlp;
      time_t begin, end, total;
 
      time(&begin);
 
      printf("===================\n");
      printf("|   OEIS A108235  |\n");
      printf("===================\n");
 
      if(ac != 2 && ac !=5){
        printf("Usage:\n");
        printf("    %s N\n", av[0]);
        printf("  or\n");
        printf("    %s N a b c\n", av[0]);
        printf("  (a + b = c)\n");
        return 1;
      }
 
      N = atoi(av[1]);
      int sum = 3*N*(3*N+1)/2;
      int sum2 = N*(2*N+1+3*N)/2;
 
      printf("Compute f(N) for N = %d\n", N);
 
      if(boundary[N] == 1)
        printf("Output every solution\n");
      else
        printf("Output every %d-th solution\n", boundary[N]);
 
      if(N > 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<a; i++)
          list[j++] = i;
        for(i=a+1; i<b; i++)
          list[j++] = i;
        for(i=b+1; i<c; i++)
          list[j++] = i;
        for(i=c+1; i<=3*N; i++)
          list[j++] = i;
 
        solution[N-1][0] = a;  // add triple (a b c) to the solutions
        solution[N-1][1] = b;
        solution[N-1][2] = c;
 
        sum -= 2*c;
        if (c <= 2*N-1)
        {
			sum2 -= 2*N;
		}
		else if (b <= 2*N-1)
		{
			sum2 -= c;
		}
		else if (a <= 2*N-2)	
		{
			sum2 -= c+b-(2*N-1);
		}
		else
		{
			sum2 -= c+b+a-(2*N-1)-(2*N-2);
		}
 
        search(list, N-1, sum, sum2);     // call of the recursive function
      }
      else{
        printf("Find %d disjoint triplets from 1...%d\n", N, 3*N);
 
        for(i=0; i<3*N; i++)   // create initial list
          list[i] = i+1;
 
        search(list, N, sum, sum2);       // call of the recursive function
      }
 
      printf("Number of valid partitions = %Ld\n", solutioncounter);
 
      // calculate the time needed
      time(&end);
      total = end - begin;
      if(total < 60)
        printf("Time needed: %d sec\n", total);
      else if(total < 3600)
        printf("Time needed: %.2f min\n", (double)total/60.);
      else
       printf("Time needed: %.2f h\n", (double)total/3600.);
 
      return 0;
    }
 

btw: Ich habe keine Ahnung, warum hier die Einrückungen so schräg dargestellt werden...




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6011
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
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
    }
  }

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.93, eingetragen 2020-04-21


(2020-04-21 20:46 - StrgAltEntf in <a
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?)

Ich habe es am Ende nicht noch einmal ausprobiert; in einem Zwischenstand brachte es jedenfalls 5%; kann aber jetzt durch andere Dinge wieder aufgefangen worden sein.

Ich habe mir einfach die $\binom{8}{2}$ Gleichungssysteme aus je vier Gleichungen von zwei gleichzeitig eintretenden Fällen angeschaut. Jeweils folgt die Identität von (mindestens) zwei verschiedenen Variablen.


Darf ich noch fragen, mit welchem Betriebssystem du mit einem Laptop unterwegs bist?

Auf dem Netbook läuft ein Lubuntu, damit es überhaupt noch betrieben werden kann. Insofern wird mit einem gcc compiliert, aber nicht mit allen Optimierungs-Compiler-Flags, da das eh nicht viel bringt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6421
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:

                        |  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

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.97, eingetragen 2020-04-22


2020-04-21 21:14 - Kitaktus in Beitrag No. 95 schreibt:
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 (*).

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.


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.

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6421
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1458
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.  






-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:

         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|     |

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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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
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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.105, eingetragen 2020-04-22


2020-04-22 21:41 - hyperG in Beitrag No. 104 schreibt:
OK, damit verkleinern sich die 120 auf 55 s -> in Tabelle angepasst.
...und die mögliche CPU ein Intel Core2 Duo E4500 2.20GHz.

Ich habe mal nachgeschaut: Es ist ein Intel Dual-Core N3060, Taktfrequenz habe ich gerade nicht parat -- laut Internet-Angabe "maximal 2.48 GHz".



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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<list[3]$, Widerspruch.

zu c): Damit ist $list[3]\geq 2N-1$, also $list[4]\geq 2N$ und damit $N+1 \leq list[2]\leq 3N-2N=N$, Widerspruch.

zu b): Damit ist wegen $list[2]\geq N+1$ auch $list[3]\geq 2N$ und $2N+1\leq list[4] \leq 3N-N=2N$, Widerspruch.

zu a): Damit ist wegen $list[2]\geq N+1$, also $list[3]\geq N+(N+1)=2N+1$, und $list[4]\leq 3N-(N-1)=2N+1$ aber $2N+1\leq list[3]\leq 2N$, Widerspruch.


Das Einsparen dieser vier überflüssigen Fälle dürfte den Code minimal schneller, aber zumindest etwas kürzer machen. :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6421
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
cpp
if ((solutioncounter <4) || (solutioncounter % boundary[N]) < 1) printsolution();

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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.111, eingetragen 2020-04-24


Fortsetzung von Beitrag 34 und kleine Optimierung von 2*n (exe 13 in 204 s):

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] ##########################

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6011
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6011
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.114, eingetragen 2020-04-24


2020-04-24 21:52 - hyperG in Beitrag No. 113 schreibt:
Die neuste Version ist noch mal mindestens 1,3 mal schneller:
DreierPartRekuSumAVX.zip
was die 15 Stunden auf 11,4 h reduzieren könnte...

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).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.115, eingetragen 2020-04-24


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.116, eingetragen 2020-04-24


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
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 (k<k_min)
        return;
} 

Das hat folgenden Hintergrund: Ist list[0]+list[2n-1]>list[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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.02.2017
Mitteilungen: 1116
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:

         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|



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6421
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
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  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2020 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]