Container verschnellern....



  • Hab mal ein Vegleichsprogramm gemacht:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int main ()
    {
        uint64_t n=5896847556;
    
    	vector<uint32_t> Teiler;
    	int Zehler;
    	uint64_t TS=0;
        for(uint64_t i=1; i<=n; i=i+1)
        {
            uint64_t quot=n/i;
            if(0==n%i)
            {
                Zehler=Zehler+1;
                Teiler.push_back(quot);
                cout<<" "<<quot <<" ist der "<<Zehler<<". Teiler der Zahl "<<n<<".  \n";
                TS=TS+quot;
            }
        }
        cout<<"Die Zahl "<<n<<" hat "<<Zehler<<" Teiler. \n";
        //cout<<"Die TS ist: "<<TS<<" = ";
        for(auto it=Teiler.begin(); it!=Teiler.end(); it++)
        {
            cout<<*it;
            if( it!=Teiler.end()-1 )
                cout<<" + ";
        }
        cout<<" = "<<TS<<" ist die Teilersumme der Zahl "<<n<<".\n";
        return (0);
    }
    

    Das werde ich jetzt optimieren.



  • Die einfachste "Optimierung" für einen Geschwindigkeits-Vergleich wäre das push_back ganz rauszunehmen. Wenns damit nicht signifikant schneller ist als ohne "Optimierung", dann ist der Beweis der Sinnlosigkeit schon erbracht.



  • uint64 geht das überhaupt auf OS10.5.8. Ich hab doch einen 32 Bit Bus,oder?



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

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



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


Anmelden zum Antworten