3. Container verschnellern....

Container verschnellern....

  • B

    Habe untenstehendes Tool geschrieben. Es sucht die Teiler einer Zahl, speichert sie in einem Container, und berechnet die Teilersumme.

    Ich habe folgendes Problem. Mit Umschreiben möchte ich von gegebenen Bereichen alle Teiler der Zahlen raussuchen lassen, zählen, wie oft bestimmte Zahlen TeilerSummen sind, und dies Ausdrucken.

    Ich habe meinen Container mit push_back gefüllt. Das soll viel Zeit beanspruchen, weil der Computer alles neu adressieren muß. Wie kann man das so machen, daß der Befehl nicht soviel Zeit braucht. 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. Ich möchte das alles über for-Schleifen realisieren.

    Da ich Programmieren mir selber beibringe, wollte ich auch noch fragen, was es sonst noch so an meinem Script auszusetzen gibt?

    Vielen Dank

    #include <iostream>
#include <vector>

using namespace std;

int quot;
long long Testzahl;
int Zehler=0;
int TS=0;
vector<int>Teiler(0);

int main ()
{
cout<< "Geben Sie die zu testende Zahl ein: ";
cin>>Testzahl;
cout<<"\n\nMacro Zahltester findet:\n";

for(int i=1;i<=Testzahl;i=i+1)
	{
	quot=Testzahl/i;
		if(0==Testzahl%i)
		{
		Zehler=Zehler+1;
            Teiler.push_back(quot);
		cout<<" "<<quot <<" ist der "<<Zehler<<". Teiler der Zahl "<<Testzahl<<".  \n";
		TS=TS+quot;
		}
	}
    cout<<"Die Zahl "<<Testzahl<<" 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 "<<Testzahl<<".\n";
    return (0);
}
    0
  • V

    brak schrieb:

    Da ich Programmieren mir selber beibringe, wollte ich auch noch fragen, was es sonst noch so an meinem Script auszusetzen gibt?

    Bitte alle Variablen lokal machen.

    und wechle mal nach uint64_t

    Ich baue jetzt auch mnal eine...

    push_back ist SICHER nicht das Problem.

    0
  • T

    brak schrieb:

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

    Ja der Vector wird zwischendurch eventuell mehrmal wachsen müssen, dabei neuen Speicher allokieren und die Elemente umkopieren. Da du schon vor der schleife weißt, wie oft du push_back aufrufen wirst, kannst du dem vector "helfen" indem du direkt mit vector::reserve() die erforderliche Menge an speicher reservierst.

    Edit: Stimmt nicht ganz wie ich gerade sehe. wegen der if Abfrage könntest du hier nur eine obere grenze festlegen.

    0
  • T

    Die Variable Zehler ist übrigens überflüssig, da der vekcor weiß, wie viele Elemente er hat.

    0

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

    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 🙄

    0
  • V

    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.

    0

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

    0
  • B

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

    0
  • B

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

    0
  • T

    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.

    0
  • S

    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!

    0
  • M

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

    0
  • 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 ?

    0

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

    0

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

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

    0
  • M

    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.

    0

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

    0
  • V

    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.

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

    0
Anmelden zum Antworten