Container verschnellern....



  • Die größte Optimierungsmöglichkeit liegt wohl im Algorithmus selber. Bin jetzt kein Mathematiker, aber es gibt wohl sehr viel schnellere Möglichkeiten als alle Zahlen durch zu probieren.



  • brak schrieb:

    hustbaer schrieb:

    brak schrieb:

    Ich habe meinen Container mit push_back gefüllt. Das soll viel Zeit beanspruchen, weil der Computer alles neu adressieren muß.

    Es "soll". Aha.
    Wo haste denn diese Information her?

    Von Dirk Louis C++ s. S. 251 "wegen des ständigen Speichervergrößernd im Hintergrund etwas ineffektiv"

    Sagt mir nix der Kerl. Aber die Aussage ist so nicht korrekt.

    Vektoren vergrößern sich, wenn sie voll werden automatisch. Ja das stimmt. Und alle Werte dann rüberkopiert (oder gemovt, kA). Und ja,d as ist in dem Moment auch ineffektiv.

    Aber sie vergrößern sich nicht um ein Element oder um 10. Normalerweise vergrößern sie sich um einen gewissen Faktor, wachsen also exponentiell. Damit wird das neu allokieren und kopieren immer weniger je mehr Elemente du einfügst.
    man spricht dabei auch von amortisierter Laufzeit, in dem Fall ist der Average-Case nämlich konstant.

    Und wenn du weist, dass du n Elemente auf ejdenfall haben wirst, dann reservier dir vorher genug Speicher. (logischerweise mit reserve)
    Der Vektor ist dann von dem Aufruf an groß genug und muss sich nicht selbst mehr vergrößern. => keienrlei Overhead durch reallokieren und moven mehr!



  • TNA schrieb:

    Die größte Optimierungsmöglichkeit liegt wohl im Algorithmus selber. Bin jetzt kein Mathematiker, aber es gibt wohl sehr viel schnellere Möglichkeiten als alle Zahlen durch zu probieren.

    Mal zwei Vermutungen aus dem Ärmel (ohne Beweis):

    1. Doppelt so schnell wird es schonmal, wenn man nur bis zur Hälfte zählt. Größere Teiler wird es wohl kaum geben.

    2. Noch besser: Wenn man sowohl i als auch gleich das sich ergebende ganzzahlige quot in einem set (statt vector ) sammelt und nur so weit geht, bis i >= quot (d.h.: Wurzel), sollte man eigentlich alle Teiler zusammenkriegen.

    ^[Edit: 50% ist nicht doppelt so schnell...]^


  • Mod

    2. Noch besser: Wenn man sowohl i als auch gleich das sich ergebende ganzzahlige quot in einem set (statt vector) sammelt und nur so weit geht, bis i >= quot (d.h.: Wurzel), sollte man eigentlich alle Teiler zusammenkriegen.

    Das ist korrekt.
    Teiler sind symmetrisch. Für größere Zahlen ist es *sehr* lohnenswert, die Ganzzahlige Wurzel zu berechnen und nur bis zu ihr zu zählen. Denn das Wurzel/Radikant Verhältnis wird schließlich immer kleiner.

    Man summiert dann auf, in dem man den Teiler plus das Gegenstück des Teilers (N/Teiler) addiert. Wenn die Quadratwurzel ganzzahlig ist, addiert man sie auch noch.

    Edit: Ich hatte die acc_divisor -Funktion noch, habe sie gelöscht (brauchte sie nicht mehr). Naja, ist ja auch eigentlich trivial.

    und wechle mal nach uint64_t

    uint_fast64_t ?



  • brak schrieb:

    hustbaer schrieb:

    Wie volkard schon geschrieben hat: push_back ist sicher nicht das Problem.

    brak schrieb:

    Jetzt merkt man es noch nicht, aber wenn ich z. b. den Bereich zwischen 10 und 20 Mio. durchsuchen will, wird dies 100% bemerkbar sein.

    Oh du Experte 🙄

    Hatte schon mal ein ähnliches Macro, welches ich bis 10 Mio laufen lies, was über 24 Stunden den Comp beanspruchten, nur um ca 150 Zahlern zu suchen. Sowas will ich mir nicht noch mal leisten, einen Tag ohne Computer, nur weil er so langsam rechnet ....

    Du glaubst also dass das Einfügen von 150 Zahlen 24 Stunden dauert?
    Hm.



  • Arcoth schrieb:

    und wechle mal nach uint64_t

    uint_fast64_t ?

    Dir ist klar dass das keinen Unterschied macht, und du nur mal wieder sinnlos "schlau" bist hier, ja?


  • Mod

    hustbaer schrieb:

    Dir ist klar dass das keinen Unterschied macht, und du nur mal wieder sinnlos "schlau" bist hier, ja?

    Das 🤡 musst du dir dazu denken. Ein Scherzchen ist mir doch gegönnt.



  • Arcoth schrieb:

    Für größere Zahlen ist es *sehr* lohnenswert, die Ganzzahlige Wurzel zu berechnen und nur bis zu ihr zu zählen. Denn das Wurzel/Radikant Verhältnis wird schließlich immer kleiner.

    Sehr gut: Wurzel einmal berechnet, spart vielmaliges if .

    Arcoth schrieb:

    Man summiert dann auf, in dem man den Teiler plus das Gegenstück des Teilers (N/Teiler) addiert.

    Die Frage ist: Wenn n eine Quadratzahl ist, wird dann der Wurzel-Teiler einmal oder zweimal gezählt? Wenn einmal, vermeidet std::accumulate Komplikationen. Und trennt die Berechnung der Teiler von der Berechnung der Summe. Find ich elegant.



  • Nein, das 🤡 musst du schon dazuschreiben.
    Du schreibst oft Genug Mist den du ernst meinst.
    Ich kann nich hellsehen.



  • TNA schrieb:

    Die größte Optimierungsmöglichkeit liegt wohl im Algorithmus selber. Bin jetzt kein Mathematiker, aber es gibt wohl sehr viel schnellere Möglichkeiten als alle Zahlen durch zu probieren.

    passt.

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    struct Primfaktorpotenz{
    	uint64_t primteiler;
    	int exponent;
    };
    
    void enumeriereTeilerverbandUndSummiere(
    	vector<Primfaktorpotenz>::iterator begin,
    	vector<Primfaktorpotenz>::iterator end,
    	uint64_t basis,
    	uint64_t* pSumme
    	){
    	if(begin==end){
    		cout<<basis<<'\n';
    		*pSumme+=basis;
    		return;
    	}
    	uint64_t aufzahl=1;
    	for(int i=0;i<=begin->exponent;++i){
    		enumeriereTeilerverbandUndSummiere(begin+1,end,aufzahl*basis,pSumme);
    		aufzahl*=begin->primteiler;
    	}
    };
    
    int main ()
    {
        uint64_t n=5896847556;
    //    uint64_t n=100;
    
    	cout<<"n = ";
        vector<Primfaktorpotenz> primfaktorenpotenzen;
        for(uint64_t teiler=2;teiler*teiler<=n;++teiler){
    		if(n%teiler==0){
    			int exponent=0;
    			do{
    				n/=teiler;
    				++exponent;
    			}while(n%teiler==0);
    			primfaktorenpotenzen.push_back(Primfaktorpotenz{teiler,exponent});
    		}
        }
        if(n!=1){
    		primfaktorenpotenzen.push_back(Primfaktorpotenz{n,1});
        }
        for(auto pfp:primfaktorenpotenzen)
    		cout<<pfp.primteiler<<"^"<<pfp.exponent<<' ';
    	cout<<'\n';
    
    	uint64_t summe=0;
    	enumeriereTeilerverbandUndSummiere(primfaktorenpotenzen.begin(),primfaktorenpotenzen.end(),1,&summe);
    	cout<<"Teilersumme: "<<summe<<'\n';
    }
    

    Laufzeit 0.002s.

    Altes Vergleichsprogramm hatte Laufzeit 81.337s.

    Nächste Optimierungen sind:

    - Teiler 2, 3 und 5 hardcoden (oder %30 mit nur einer Division und Tabellennachgucker(passt sogar in einen int)) und ab dann bei der Teilersuche nur die 8 möglichen Teilerklassen modulo 30 zu probieren.

    - eine schnelle istPrimzahl(n) vor der Teilersuch anzuwerfen. Wenn die kleinen Teiler abgefischt sind, ist es schon verdammt oft eine Primzahl. Primalität feststellen geht VIEL schneller als Teilerfinden.

    - Dicke Zahlen mit Pollard's-Rho spalten.


  • Mod

    Arcoth schrieb:

    Man summiert dann auf, in dem man den Teiler plus das Gegenstück des Teilers (N/Teiler) addiert.

    Die Frage ist: Wenn n eine Quadratzahl ist, wird dann der Wurzel-Teiler einmal oder zweimal gezählt?

    Natürlich nur einmal, wieso um Himmels Willen sollte man ihn zweimal zählen 😕

    for(uint64_t teiler=2;teiler*teiler<=n;++teiler)
    

    Wieso das Produkt in jedem Schleifendurchlauf berechnen? Wenn man schon diesen Weg einschlägt, kann man gleich die Regel anwenden, nach der Quadrate steigen, und wenigstens das Produkt durch eine Addition ersetzen. Am besten wäre allerdings isqrt .



  • Arcoth schrieb:

    Natürlich nur einmal, wieso um Himmels Willen sollte man ihn zweimal zählen 😕

    Weil ich zu sehr in meinem "Kopfprogramm" gedacht habe: Jeweils Teiler und Komplementär gleichzeitig abspeichern bzw. aufsummieren. Bei Quadratzahlen hätte man sowohl für Teiler als auch den quot die gleiche Zahl, was man beim on-the-fly-Aufsummieren dann abfangen müsste, um sie nur einmal zu zählen. Klar eigentlich, dass man sie bei einer Teilersumme nur einmal braucht. Nix für ungut.



  • Arcoth schrieb:

    for(uint64_t teiler=2;teiler*teiler<=n;++teiler)
    

    Wieso das Produkt in jedem Schleifendurchlauf berechnen? Wenn man schon diesen Weg einschlägt, kann man gleich die Regel anwenden, nach der Quadrate steigen, und wenigstens das Produkt durch eine Addition ersetzen. Am besten wäre allerdings isqrt .

    Kein Problem. Bleibt aber bei O(n). Hab hier nur auf auf die Primfaktorenzerleging und das Aufspannen des Teilerverbands wert gelegt, das bringt erstmal am meisten bei wenig Mathe-Aufwand.

    isqrt64 hätte ich erstmal anbieten müssen, ist ein eigenes thema. uint64_t ist größer als double. ::sqrt(double) reicht nicht. Eigenen Thread wert, wie ich sehe, haben wir hier noch keine gute Lösung.

    die binomische formel wollte ich nicht noch reinmüllen, zumal bei modernen prozessoren, die nur 6 Takte pro multiplikation brauchen, der trick auch arg wenig dazu bringt.


  • Mod

    Arcoth schrieb:

    Arcoth schrieb:

    Man summiert dann auf, in dem man den Teiler plus das Gegenstück des Teilers (N/Teiler) addiert.

    Die Frage ist: Wenn n eine Quadratzahl ist, wird dann der Wurzel-Teiler einmal oder zweimal gezählt?

    Natürlich nur einmal, wieso um Himmels Willen sollte man ihn zweimal zählen 😕

    for(uint64_t teiler=2;teiler*teiler<=n;++teiler)
    

    Wieso das Produkt in jedem Schleifendurchlauf berechnen? Wenn man schon diesen Weg einschlägt, kann man gleich die Regel anwenden, nach der Quadrate steigen, und wenigstens das Produkt durch eine Addition ersetzen. Am besten wäre allerdings isqrt .

    Man kann auch das Divisionsergebnis des letzten Modulo heranziehen.



  • Das Problem ist, Ich bat darum, nicht das Problem an sich zu lösen, das will ich machen, sondern mir nur an bestimmten Stellen Tips zu geben, die ich dann selber umsetzen kann. Mein Programm läuft jetzt auch, bestimmt nicht so schnell und elegant wie Euers und auch nicht zu so hohen Zahlen.....

    Trotzdem vielen Dank



  • Von Dirk Louis C++ s. S. 251 "wegen des ständigen Speichervergrößernd im Hintergrund etwas ineffektiv"

    'Staendig' ist falsch.

    sondern mir nur an bestimmten Stellen Tips zu geben

    1.) Mit dem Programm nicht alle Zahlen bis n testen sindern nur bis sqrt(n).
    2.) Laufzeit vorher abschaetzen, d.h. wenn Zahlen bis 10000 Zeit x kosten, wieviel kosten dann Zahlen bis 1000000.
    3.) Primzahlsieb mit prime-wheel benutzen (advanced).
    4.) Geeignete Datenstruktur benutzen die effizienter als std::vector ist, beispielsweise ein Bitset.

    Alle Faktoren finden ist aehnlich zu alle Primzahlen finden. Dort findest du weitere Anregungen.



  • brak schrieb:

    Das Problem ist, Ich bat darum, nicht das Problem an sich zu lösen, das will ich machen, sondern mir nur an bestimmten Stellen Tips zu geben, die ich dann selber umsetzen kann. Mein Programm läuft jetzt auch, bestimmt nicht so schnell und elegant wie Euers und auch nicht zu so hohen Zahlen.....

    Das fertige Programm musste sein, um Dir vorzumachen, wie unglaublich viel es bringt, sich über den Algo Gedanken zu machen und wie unglaublich wenig dagegen Mikro-Optimierungen bringen.
    Oh, es hat noch viel Optimierungspotenzial, er schreit ein wenig nach Mikrooptimierung. Ist aber noch viel zu früh…



  • knivil schrieb:

    4.) Geeignete Datenstruktur benutzen die effizienter als std::vector ist, beispielsweise ein Bitset.
    Alle Faktoren finden ist aehnlich zu alle Primzahlen finden. Dort findest du weitere Anregungen.

    stumpf ist Trumpf. Rot13, weil ich keinen Code mehr Zeigen darf.

    #vapyhqr <vbfgernz>
    #vapyhqr <irpgbe>
    
    vag znva(){
    	hvag32_g pbafg znk=10000000;
    	fgq::irpgbe<hvag32_g> grvyre(znk);
    	sbe(hvag32_g mnuy=1;mnuy<znk;++mnuy)
    		sbe(hvag32_g ivry=mnuy;ivry<znk;ivry+=mnuy)
    			grvyre[ivry]+=mnuy;
    	sbe(hvag32_g mnuy=1;mnuy<znk;++mnuy)
    		vs(grvyre[mnuy]==2*mnuy)
    			fgq::pbhg<<"Qvr Mnuy "<<mnuy<<" vfg cresrxg.\a";
    }
    


  • brak schrieb:

    Das Problem ist, *snip*

    Das Problem ist, dass du behauptet hast dass ein ganz bestimmter Befehl ( push_back ) das Bottleneck wäre, und dann nur nach Lösungen für dieses, nicht existente, " push_back -Problem" gefragt hast.
    Das erzeugt bei einigen Leuten (z.B. mir ;)) ein wenig Unwillen/Mismut.

    Du du aber anscheinend gar nicht so stur bist wie dich das hat erscheinen lassen, ein freundlich gemeinter Hinweis (und das ist ausnahmsweise mal kein Zynismus von mir, ich meine das echt nicht böse): wenn du dir wo nicht sicher bist, wie z.B. bei der push_back -Sache, dann lass dir das erstmal vom Forum bestätigen. Ala "ich will das optimieren und ich glaube die Problemstelle ist X - stimmt das soweit?".
    Und wenn du nicht nur eine bestimmte Problemstelle entfernen willst, sondern allgemein nach Möglichkeiten suchst was zu verbessern/verschnellern, dann darfst du das auch gerne dazuschreiben 😉

    Zu breit/allgemein formulierte Fragen werden auch nicht gerne beantwortet. Dein Beispielcode war aber ausreichend klein und ausreichend spezifisch dass man da ohne weiteres "was kann man da noch verbessern" fragen kann. Ohne dass die Frage dadurch zu breit/unspezifisch wird.

    ----

    So. Mathemässig kann ich dir nicht weiterhelfen, da haben andere hier viel viel viel mehr drauf als ich. Und da hast du ja auch schon einige gute Tips bekommen.



  • stumpf ist Trumpf. Rot13, weil ich keinen Code mehr Zeigen darf.

    Bei Primzahlproblemen ist meine persoenliche Messlatte 10^10, erst dann wird es interessant. Deine Loesung kommt mit 10^9 nicht mehr klar, auch 10^8 kann bei Rechnern mit wenig Speicher problematisch sein. Wie nah aber vollkommene Zahlen jetzt dem Primzahlproblem sind, weiss ich nicht.


Anmelden zum Antworten