Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (WinAPI, Konsole) » Optimierung einer Funktion um Primzahlen zu filtern
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: [ 1 ] > 2 < [ 3 ]
010
07.01.2007, 12:57 Uhr
~Starsurfer
Gast


@Suba Esel

es is mir nur wichtig wie lang der Algo braucht um die Primzahlen zu filtern, wie viel Zeit der fürs Anzeigen/Speichern braucht ist vollkommen egal...


Zitat:

Das Programm braucht auf meinem AMD Athlon 3500+ (2,2 GHz):
~37 Sekunden, wenn ich es so lasse (ist dann aber sinnlos )
~ 40 Sekunden, wenn ich in die Datei schreibe
~ 60 Sekunden, wenn ich die Zahlen ausgebe
~ 67 Sekunden, wenn ich in die Datei speichere und die Zahlen ausgebe

für wie viele Primzahlen?

Tipps für dein Programm:
-functionsaufrufe sind lahm wie sau, weglassen oder inline(?)
-i <= sqrt(n) sqrt is dermaßen langsam , nehm lieber i*i<n

ach ja: time(0) ist viel zu ungenau, ich brauch ms ...


so hab auch ne neue Version, die kommt noch im laufe des Tages...

Starsurfer
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
011
07.01.2007, 13:02 Uhr
Suba Esel



 500000 Primzahlen
Funktionen nehm ich raus, mal sehn ob das was bringt
Was ist inline?
Das mit dem sqrt ist ne gute Idee, nach etwas Überlegen ist mir klar geworden, dass das sogar funktioniert^^
Time(0) ist vielleicht ungenau, aber dafür schneller
--
Simon
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
012
07.01.2007, 13:07 Uhr
~Starsurfer
Gast



Zitat:

Was ist inline?

inline schreibst du vor ne Funktion davor und sagst damit dem Compiler das er Funktionsaufrufe der Funktion ersetzt in dem er einfach dem Code der Funktion an die Stelle der Aufrufe setzt.
Damit muss er nicht immer ein Funktionsaufruf erzeugen sondern muss nur Zeile für Zeile durchgehen....
ok, bissel schwammig erklärt, aber so grob triffts das ^_^


Zitat:

Time(0) ist vielleicht ungenau, aber dafür schneller

Diese Funktion wird aber nur 2 mal aufgerufen... also ist der Nutzen nur extrem minimal


Starsurfer
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
013
07.01.2007, 13:18 Uhr
Suba Esel



 Das mit dem inline bringt mir bei 500000 Zahlen ganze 2 Sekunden^^
Und das mit dem sqrt(n) noch mal 2
--
Simon
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
014
07.01.2007, 13:21 Uhr
Suba Esel



 Ups nee, sorry, hab falsch gerechnet, ich hatte noch ne Ausgabe mit drin
Bin jetzt bei 16 Sekunden statt 40 (mit speichern)
--
Simon
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
015
07.01.2007, 13:30 Uhr
~Starsurfer
Gast


so neue Version basiert aber auf einem anderen Funktionsprinzip als meine bisherigen Programme...

Es wird nicht gefragt wie viele Primzahlen man haben will sondern bis zu welcher Zahl man nach Primzahlen suchen soll...

Werte(umgerechnet um mit den anderen zu vergleichen):
0..7368787-> entspricht 500000 Primzahlen -> ~0.455s
0..15485863-> entspricht 1000000 Primzahlen -> ~0.948s
0..179424673-> entspricht 10000000 Primzahlen -> ~11.760s

Vorteil des akt Programms: Rechenaufwand erhöht sich nicht expotenzial
Nachteil des akt Programms: derber RAM Verbrauch...
aber es gibt noch einiges zu optimieren *g*


C++:
//---------------------------------------------------------------------------
#include <iostream>
#include <windows>
#pragma hdrstop
using namespace std;
//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
        unsigned int ges_anzahl,n;
        bool *prim_liste;
        LONGLONG frequenz, end_zeit, start_zeit;
        double TimeScale;
        cout << "Bis zu welcher Zahl soll gefiltert werden?\n";
        cin >> ges_anzahl;
        // dyn array mittels new erzeugen ist nicht schneller
        if((prim_liste=(bool *) malloc(sizeof(bool)*(++ges_anzahl+1)))==NULL)//dyn array erzeugen
        {
                cout << "Nicht genug Speicher fuer Array\n\n";
                system("Pause");
                return 0;
        }

        QueryPerformanceFrequency((LARGE_INTEGER*) &frequenz); //system freq ermitteln
        QueryPerformanceCounter((LARGE_INTEGER*) &start_zeit); //anfangszeit ermitteln
        TimeScale = 1.0/frequenz;

        for(bool *i=prim_liste;i<&prim_liste[ges_anzahl];i++){*i=true;}

        prim_liste[0]=false;
        prim_liste[1]=false;

        for(unsigned int i=1;i*i<ges_anzahl;i++)
        {
                if(prim_liste[i]==true)
                {
                        n=2;
                        while(n*i<=ges_anzahl)
                        {
                                prim_liste[i*n]=false;
                                n++;
                        }

                }
        }

        QueryPerformanceCounter( (LARGE_INTEGER*) &end_zeit);

        n=0;
        for(unsigned int i=0;i<ges_anzahl;i++)
        {
                if(prim_liste[i]==true)
                {
                        n++;
                       // cout<<i<<'\n';
                }

        }
        cout << "Anzahl: " << n << '\n';
        cout << "Zeit  : " << (end_zeit - start_zeit) * TimeScale << " s\n\n";
        free(prim_liste);
        system("Pause");
        return 0;
}
//---------------------------------------------------------------------------



Starsurfer
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
016
07.01.2007, 13:36 Uhr
~Starsurfer
Gast


mmmh sieht irgendwie so ähnlich aus wie Uwe sein´s
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
017
07.01.2007, 13:45 Uhr
Suba Esel



 Frage:

Was hast du außer dem Prozessor für n PC? Mein Athlon 3500+ schafft 500000 Primzahlen in 0,39 Sekunden....

Und derber RAM - Verbrauch kannste laut sagen^^
--
Simon
Dieser Post wurde am 07.01.2007 um 13:47 Uhr von Suba Esel editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
018
07.01.2007, 13:49 Uhr
~Starsurfer
Gast


Das issn Notebook:

HP Pavilion
Intel Core Duo 2*1,66GHz
1026MB RAM
80GB HDD //wobei das
Geforce 7400 //hier ja kaum Einfluss hat


poste mal bitte dein aktuellen code, ich will den mal auf meiner Kiste testen.

Starsurfer
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
019
07.01.2007, 14:18 Uhr
Suba Esel



 Mmh, ich denke mal, dass du langsameren RAM hast.
Mein Prozessor ist nämlich langsamer.

Ist ein Missverständnis: ich hab deinen benutzt

Ich hab aber gestern so etwas ähnliches geschrieben:


C++:
#include <iostream>
#include <fstream>
using namespace std;

inline bool isprime(int n)
{
    if (n<2||n%2==0&&n!=2) return false;
    if (n==2) return true;

    for (int i = 3; i*i < n; i += 2)
    {
        if(n % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    unsigned long long int von;
    cout << "Von welcher Zahl aus sollen alle Primzahlen gefiltert werden?" << endl;
    cin >> von;
    unsigned long long int bis;
    cout << "Bis zu welcher Zahl sollen alle Primzahlen gefiltert werden?" << endl;
    cin >> bis;
    cout << endl;
    cin.sync();
    int startzeit = time(0);
    ofstream out("Primzahlen.txt");
    out << "Primzahlen von " << von << " bis " << bis << "\n\n";
    int anzahl = 1;
    int alt = 0;

    for (; von <= bis; ++von)
    {
        if (isprime(von))
        {
            if (alt != von * 100 / bis)
            {
                cout <<  von * 100 / bis << " %" << endl;
                alt = von*100 / bis;
            }
            out <<  anzahl << ": " << von << "\n";
            ++ anzahl;
        }
    }
    int endzeit = time(0);
    cout << "Dauer: " << endzeit - startzeit << " Sekunden \nGefunden: " << anzahl;
    out << "Dauer: " << endzeit - startzeit << " Sekunden \nGefunden: " << anzahl;
    out.close();
    cin.get();
}


Sind noch ein paar Bugs drin, zum Beispiel die Prozentangabe, wenn man nicht bei 0 startet, aber das versuche ich noch zu beheben^^
--
Simon
Dieser Post wurde am 07.01.2007 um 14:27 Uhr von Suba Esel editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: [ 1 ] > 2 < [ 3 ]     [ C / C++ (WinAPI, Konsole) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: