3. Liste mit Zeigern

Liste mit Zeigern

  • E

    Dobi schrieb:

    seine Werke für mich als Spaß-Lektüre

    Und als Brandverstärker oder Klopapier.

    0
  • V

    Nun habe ich in einem Buch gelesen, eine dynamisch verkettete Liste würde schneller laufen.

    Das ist im Allgemeinen falsch.
    Wobei das Reservieren mit dem Maximalwert gar nicht soo wichtig ist.
    So teuer ist das Umkopieren nämlich nicht und der vector gewinnt trotzdem haushoch gegen die normale verkettet Liste.
    Nehmen wir mal einen vector, der von selbst mit reserve(1) anfängt und immer bei Größenüberschreitung sich verdoppelt. Und nehmen wir 1000000 Primzahlen.
    Dann muß der vector verdoppeln zu 2,4,8,16,...,1048576.
    Und er kopiert dabei 1+2+4+8+...+524288=1048575 Elemente.
    Und ruft dabei 19 mal new+delete auf.
    Pro Einfügung eines int bezahlen wir also höchstens einmal Kopieren eines int und ungefähr nullmal new/delete. Und das Kopieren ist inmitten einer Kopierschleife, das ist schnell.
    Bei der Liste bezahlen wir pro Einfühung ein new. 😮
    Da ein new mit Sicherheit teuer ist als einnmal einen int zu kopieren (soviel kostet ja schon allein der Funktionsaufruf, ohne, daß die Funktion was tut), ist der vector schneller, was das Einfügen angeht.

    Darüberhinaus wird hier der Container jedesmal von vorn nach hinten lesend durchlaufen. Da liegen im vector die Daten cachefreundlicher, er wird auch schneller ausgelesen.

    Und er braucht weniger Speicher, auf win32 bekommt man normalerweise mindestens 32Byte allokiert, also 7-facher Overhead. Da ist auch 7-mal schneller der primary cache am Ende.

    als ein Array und ganz nebenbei genau so viel Speicherplatz brauchen, wie erforderlich ist.

    Nicht ganz wahr. Sie braucht genausoviel Speicher wie erforderlich, aber pro Element hat sie einen gewissen Overhead, hier 28 Bytes.
    Der vector frißt bis zu doppelt so viel Speicher wie benötigt, nämlich wenn er gerade gewachsen ist. Sind die Datenelemente groß und/oder sehr teuer zu kopieren, spricht es eher für die Liste. Aber int spricht stark für vector.

    Normalerweise verzichte ich bei so unscharfen Abschätzungen wie reserve(max) lieber darauf. Bis 1000000 gibt es nur 78498 Primzahlen. Da mag ich nicht.
    Ok, hier kann man zufällig mit reserve(max/log(max)*1.1056)[1] sicher abschätzen, also warum nicht?)

    [1] http://de.wikipedia.org/wiki/Primzahlsatz#Geschichte

    0
  • V

    Dobi schrieb:

    314159265358979 schrieb:

    Lass mich raten, der Auto deines Buches hat die Initialen J.W. ?

    Das ist einfach reiner Schwachsinn, beide Behauptungen, dass
    1.) Eine verkettete Liste genau so viel Speicher braucht wie ein Array
    und
    2.) Eine verkettete Liste schneller wäre.

    Lol, schreibt der erwähnte Autor tatsächlich solche Sachen?

    Noch ist das nur eine böse Unterstellung, solange mrmo noch nicht gesagt hat, in welchem Buch das stand.

    edit: mrmo statt Dobi

    0
  • D

    Meinst du 314159265358979, mich oder mrmo?

    Edit: Vermutlich mrmo. 🙂

    0
  • M

    Tut mir leid,
    das habe ich nicht in Herrn Wolfs Buch gelesen (ich gehe mal davon aus dass ihr von ihm sprecht), sondern in einem Buch des gleichen Verlags mit dem Autor A.W.

    Aber nun zurück zum Thema:
    Ich der Aussage erstmal aus zwei Gründen glauben geschenkt. Ich weiß nämlich zu beginn nicht, wie viele Primzahlen sich in dem Bereich zwischen 1 und der vom Nutzer gewählten Zahl befinden. Tatsächlich kann ich die Anzahl auch nicht genau berechnen http://de.wikipedia.org/wiki/Primzahlsatz.
    Natürlich könnte ich das über eine der Formeln im Wiki-Artikel annähern, aber ich will das ganze (auch wenn es im Prinzip egal ist) optimal basteln 😉
    Ich weiß ehrlich gesagt gar nicht wie das mit dynamischen Arrays ist - aber das Array in einer Forschleife jedes mal um eins zu vergrößern ist dann wohl die absolut ineffizienteste Methode.

    Zum Code: Caligulaminus, du beschreibst was das Problem ist. Ich dachte eigentlich, dass der Zeiger, wie jede andere Variable auch, auch außerhalb dieser If-Abfrage bestehen bleibt. Wie sorge ich dafür dass er das tut?

    Volkard, Ich habe nicht ganz verstanden was du mir sagen willst. Von welchem vector redest du :D?
    In dem Buch war das ganze so erklärt, dass bei einem Array immer folgendes getan wird, wenn ich einen weiteren Wert ans Ende schreibe:
    1. Anfangsadresse des Arrays wird ausgelesen
    2. größe der Arrayelemente wird mit dem Platz an dem ich schrieben will multipliziert
    3. dorthin wird geschrieben / gelesen

    bei einer verketteten Liste habe ich eben dne Vorteil, dass ich keine Multiplikation habe, sondern einfach direkt zum nächsten Zeiger springe. In meinen Augen ist das effizienter 😃

    Wobei mir gerade bei genauerem Nachdenken einfällt, dass ja im Array kein Zeiger auf das nächste Element existiert (weil die Größe eines Elements ja immer fix und somit berechenbar ist), während ich ja bei der Liste n*(die größe eines Zeigers) hab. Dass das auch eine gewisse Platzverschwendung ist sehe ich ein.

    Ich werde also wohl doch, wie volkard geschrieben hat, über den Primzahlsatz die Größe des Arrays ungefähr ermitteln, und das dementsprechend einstellen.

    Und alle die sich jetzt wundern, dass ich mir wiederspreche: Mir ist das eben alles klar geworden 💡
    Dankeschön 😉

    0
  • C

    mrmo schrieb:

    Zum Code: Caligulaminus, du beschreibst was das Problem ist. Ich dachte eigentlich, dass der Zeiger, wie jede andere Variable auch, auch außerhalb dieser If-Abfrage bestehen bleibt. Wie sorge ich dafür dass er das tut?

    Du hast zwei Variablen mit dem selben Namen angelegt. Die erste ist global und behält ihren Wert bis zum Ende des Programms (oder bis du ihr etwas anderes zuweist), die zweite ist lokal und gilt nur bis zum Ende des {...}-Blocks, in dem sie definiert ist.

    Volkard, Ich habe nicht ganz verstanden was du mir sagen willst. Von welchem vector redest du :D?
    In dem Buch war das ganze so erklärt, dass bei einem Array immer folgendes getan wird, wenn ich einen weiteren Wert ans Ende schreibe:
    1. Anfangsadresse des Arrays wird ausgelesen
    2. größe der Arrayelemente wird mit dem Platz an dem ich schrieben will multipliziert
    3. dorthin wird geschrieben / gelesen

    bei einer verketteten Liste habe ich eben dne Vorteil, dass ich keine Multiplikation habe, sondern einfach direkt zum nächsten Zeiger springe. In meinen Augen ist das effizienter 😃

    Die Multiplikation geht aber wesentlich schneller als sich entlang der Kettenglieder zur richtigen Position durchzuhangeln.

    Und außerdem ist es im Zweifelsfall günstiger, sich auf vorgefertigte und ausgiebig getestete Datenstrukturen zu verlassen als sowas selber zu schreiben. Die Standard-Bibliothek bietet dafür u.a. vector<> (mit Array-ähnlicher Semantik) oder list<> (eine doppelt verkettete Liste). Die haben darüber hinaus den Vorteil, daß du nicht vorher wissen mußt, wieviel Platz du eigentlich benötigen wirst - die wachsen mit, wenn es nötig wird.

    0
  • M

    Oh ja, das hätte mir aber auch auffallen können dass das ne redeklaration ist 😕
    Ich hab das eben blind aus dem Buch übernommen 😉

    Ich würde mich nicht an den Kettengliedern entlanghangeln. Ich muss ja, wenn ich überprüfe ob ich eine Primzahl habe, durch jedes Element der Liste teilen. Und ob ich da nun 10000 Multiplikationen habe, oder mich von einem Element zum nächsten hangele (wobei ich ja sowieso den Inhalt jedes Elements brauche), dachte ich dass ich so besser zum Ziel käme.
    Ganz ausgereift ist der Code sowieso noch nicht, natürlich bräuchte man noch einen Zeiger, der dauerhaft auf das letzte Element zeigt.
    Mal sehen wann ich das ganze umstelle 😉

    /edit:
    So, das ganze hab ich jetzt zum laufen gekriegt. Mit Zeigern ist das Ding deutlich langsamer als mit einem Array...

    /* 
 * File:   main.cpp
 * Author: moritz
 *
 * Created on 16. April 2011, 17:01
 */

#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;

struct tPrimkette
{
    int data;
    tPrimkette *next;
};
tPrimkette *Anker = 0;
tPrimkette *aktuell = 0;
tPrimkette *laeufer = 0;

int main() {
    const int min = 2; //bei kleineren Zahlen: Fehlverhalten
    int max;
    cout << "Berechnen bis ";
    cin >> max;
    //max=2000000;
    int pzahlen[max];
    int prim, akt, zaehler;
    bool istprim;
    pzahlen[0]=2;
    akt = 1;
    tPrimkette *Anker = new tPrimkette;
    Anker->data = 2;
    aktuell = Anker;  
    for (prim=min; prim <= max; prim ++)
    {
        istprim = true;
        //Pruefung optimiert
        //und nun durch Zeiger erneut gepimpt
        laeufer = Anker;
        for (zaehler = 0; istprim && (laeufer->data) <= sqrt(prim) && zaehler < akt; zaehler ++)
        {
            //Teilbar durch eine bereits gefundene Primzahl?
            if (0 == prim % (laeufer->data))
            {
                istprim = false;
            }
        }
        if (istprim)
        {
            cout << prim << endl;
            aktuell = aktuell->next;
            aktuell = new tPrimkette;
            aktuell->data = prim;
            akt++;
        }
        laeufer = laeufer->next;
    }
    cout << "Das Maximum war " << max << endl;

    return 0;
}

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

    0
  • V

    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.

    0
  • V

    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

    0
  • V

    Warum schreibst Du eigentlich

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

    statt

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

    ?

    0
  • M

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

    0
  • V

    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.

    0
  • M

    ...und stattdessen welches Buch nutzen?

    0
  • V

    mrmo schrieb:

    ...und stattdessen welches Buch nutzen?

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

    0
  • N

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

    Danke, ich werde mich mal drum kümmern 😉

    0
  • V

    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.

    0
Anmelden zum Antworten