Liste mit Zeigern

volkard

mrmo schrieb:

Von welchem vector redest du :D?

std::vector
Kommt im Buch noch. (Hoffentlich!!)
Wenn nicht, verrate uns das Buch, das käme dann bestimmt auf die Spott-Liste.

eben den Vorteil, dass ich keine Multiplikation habe, sondern einfach direkt zum nächsten Zeiger springe. In meinen Augen ist das effizienter

Ja, aber es gibt auf PCs Prozessorbefehle, die den Indexzugriff inklusive Multiplikation ohne Zeitverlust für die Multiplikation schaffen.

Und selbst wenn es den nicht gäbe, würde der schlaue Compiler deine Schleife umbasteln in eine, die statt den Index in einersprüngen laufen zu lassen und bei jedem Zugriff *4 rechnet, dann würde er den Index gleich in Vierersprüngen laufen lassen.

Wobei eine Multiplikation mit 4 auch nicht so teuer ist, es ist nur ein <<2, ein Nach-Links-Schieben aller Bits um 2 Stellen, das kann er sauschnell.

volkard

mrmo schrieb:

braucht für die Primzahlen von 2 bis 200000 fast 4:30, wobei meine Implementierung mit Arrays dafür keine Sekunde benötigt. Hab ich da irgendwo einen Fehler drin oder ist das tatsächlich so langsam?

Ich teste mal mit identischem Code für Liste und Array (also für std::list und std::vector).

Zuerst die Liste:

#include <iostream>
#include <list>

using namespace std;

int main(){
    int const max=1000000;
    int c=0;
    list<int> primzahlen;
    primzahlen.push_back(2);
//    cout<<2<<'\n';
    ++c;
    for(int n=2;n!=max;++n){
        for(list<int>::iterator i=primzahlen.begin(),e=primzahlen.end();i!=e;++i){
            if(n%*i==0){
                goto warKeinePrimzahl;
            }
        }
//        cout<<n<<'\n';
        ++c;
        primzahlen.push_back(n);
        warKeinePrimzahl:;
    }
    cout<<c<<" Stück\n";
}

Zwischenstand: Gähn.

90,281 Sekunden.

Jetzt mit dem Array:
78,983 Sekunden.

Also kaum Unterschied. Das liegt daran, daß fast die gesamte Rechenzeit für unglaublich viele Divisionen draufgegangen ist.
Aber ich bin ja auch doof, habe den sqrt-Trick vergessen.
Ich mach mal nicht teiler<=sqrt(n), sondern teiler*teiler<=n, kommt ja aufs Gleiche Raus.

for(vector<int>::iterator i=primzahlen.begin(),e=primzahlen.end();i!=e && *i**i<=n;++i){

Beide zu schnell zu Messen.

int const max=10000000;

Liste: 8.484 Sekunden
Array: 8.094 Sekunden

Kaum Unterschied.

Das liegt daran, daß die teuren Divisionen fast die ganze Rechenzeit verbraten.
Immerhin geschehen 291144936 Divisionen.

Mal nur zum Jux vector gegen list vergleichen bei einem anderen Programm.

#include <iostream>
#include <list>

using namespace std;

int main(){
    int const max=100000000;
    list<int> zahlen;
    for(int i=0;i<max;++i)
        zahlen.push_back(i);

    long long summe=0;
    for(list<int>::iterator i=zahlen.begin(),e=zahlen.end();i!=e;++i){
        summe+=*i;
    }
    cout<<"Summe: "<<summe<<'\n';
}

Liste: 5,797 Sekunden
Array: 0.281 Sekunden

volkard

Warum schreibst Du eigentlich

if (0 == prim % (laeufer->data))

statt

if (prim % (laeufer->data) == 0)

?

mrmo

Volkard,
dann werde ich wohl noch etwas weiterlesen müssen bis zu vector bisher habe ich ihn noch nicht entdeckt, bin aber auch erst auf Seite 150.
Dass mein Compiler soo schlau ist, dass er das in vierersprüngen durchgeht, wusste ich gar nicht.

Und ob ich nun (0 == xyz) oder (xyz == 0) schreibe ist ja egal. Zuerst die Zahl zu schreiben habe ich jedoch aus meinem schlauen Buch. In diesem Fall trifft das ganze nicht zu, aber falls mal mal ausversehen (bei mir als Umsteiger von Pascal/Delphi gar nicht mal so unwahrscheinlich) als Vergleichsoberator nur ein Gleichzeichen nimmt weist man das ganze ja unbeabsichtigt zu. Wenn ich das nun aber 0 = xyz vergleiche schmiert das ding mit nem Compilerfehler ab.
Danke für deinen Speedtest, wie misst man sowas so genau?

volkard

mrmo schrieb:

Zuerst die Zahl zu schreiben habe ich jedoch aus meinem schlauen Buch.

Ja, das hatte ich befürchtet. Du darfst das Buch beruhigt wegwerfen.

mrmo schrieb:

Danke für deinen Speedtest, wie misst man sowas so genau?

Code::Blocks zeigt die Zeit automatisch an.

mrmo

...und stattdessen welches Buch nutzen?

volkard

mrmo schrieb:

...und stattdessen welches Buch nutzen?

Die meisten Empfehlungen bekommen regelmäßig der C++-Primer, Thinking in C++ und der Breymann.

Nexus

mrmo schrieb:

Und ob ich nun (0 == xyz) oder (xyz == 0) schreibe ist ja egal. Zuerst die Zahl zu schreiben habe ich jedoch aus meinem schlauen Buch. In diesem Fall trifft das ganze nicht zu, aber falls mal mal ausversehen (bei mir als Umsteiger von Pascal/Delphi gar nicht mal so unwahrscheinlich) als Vergleichsoberator nur ein Gleichzeichen nimmt weist man das ganze ja unbeabsichtigt zu. Wenn ich das nun aber 0 = xyz vergleiche schmiert das ding mit nem Compilerfehler ab.

Nexus (von <a href= schrieb:

hier)">

minastaros schrieb:
Für das Problem mit dem versehentlichen
if( a = 1 )
hab ich mir
if( 1 == a )
angewöhnt, dann meckert der Compiler, wenn man = schreibt...
Hihi, das hört man immer wieder
Was ich davon halte:

Es ist weniger übersichtlich und logisch, wenn die zu prüfende Variable am Schluss steht. Gerade wenn der Ausdruck komplizierter ist als ein Literal.

Man kann das nicht konsistent durchziehen. Was machst du bei a == b ?

Man wiegt sich in falscher Sicherheit. Zum Beispiel kann if (Function() = b) ohne Probleme kompilieren, wenn ein nicht-skalarer RValue zurückgegeben wird.

Dieser typische Anfängerfehler kommt so selten vor, dass es sich nicht lohnt, den Code hässlich zu machen.

Wie von volkard erwähnt helfen einem gewisse Compiler sogar mit einer Warnung.

mrmo

Danke, ich werde mich mal drum kümmern

volkard

Nexus schrieb:

[list][*]Es ist weniger übersichtlich und logisch, wenn die zu prüfende Variable am Schluss steht. Gerade wenn der Ausdruck komplizierter ist als ein Literal.

Oder in der umgekehrten Schreibweise, also mit dem betrachteten Objekt hinten:

Ugly schrieb:

[list][*]Übersichtlich und logisch ist es weniger, wenn am Schluß die zu prüfende Variable steht. Gerade wenn ein Literal unkomplizierter ist als der Ausdruck.