3. map am ende löschen?

map am ende löschen?

  • H

    sicher? immer? also ich kenne fälle, wo die map schneller als die hashtable ist.

    Jetzt bin ich gespannt.
    Man kann doch problemlos Hashs bauen, die bei mehrfachen berechnen der selben stelle eine Liste verwenden und dort sortiert einfügen. Somit kann man beim Suchen einen logarythmischen Worst Case erziehlen.
    Darum kann es also schonmal nciht gehen. Zeig bzw. erklär mal wo deine Map schneller ist.

    0
  • V

    Helium schrieb:

    sicher? immer? also ich kenne fälle, wo die map schneller als die hashtable ist.

    Jetzt bin ich gespannt.
    Man kann doch problemlos Hashs bauen, die bei mehrfachen berechnen der selben stelle eine Liste verwenden und dort sortiert einfügen. Somit kann man beim Suchen einen logarythmischen Worst Case erziehlen.
    Darum kann es also schonmal nciht gehen. Zeig bzw. erklär mal wo deine Map schneller ist.

    na, das hashen selbst kostet doch.
    nehmen wir als hashfunktion mal

    unsigned int hash::hashstr(String &x)
{
	return hashstr(x.c_str());
}

unsigned int hash::hashstr(const char* x)
{
  unsigned int h = 0;
  unsigned int g;

  while (*x != 0)
  {
    h = (h << 4) + *x++;
    if ((g = h & 0xf0000000) != 0)
      h = (h ^ (g >> 24)) ^ g;
  }
  return h;
}

    und die wahl ist nicht sehr unwahrscheinlich.
    und leider habe ich lauter sehr, sehr, sehr lange strings zu verwalten. sagen wir mal in ner BWT. und beim vergleich mit strcpy fliegt gewöhnlich nach dem ersten zeichen schon ein ergebnis. mit geriner wahrscheinlichkeit muß man auch das zweite angucken, und mit saugeriger wahrscheinlichkeit sogar noch das dritte...
    da kann es locker mal sein, daß ein paar stringvergleiche (für ne million srtings nur 20 strück) für den baum billiger sind, als nen megabytestring durchzuhashen.

    0
  • H

    ok, verstanden. Danke.

    0
  • ?

    habs ebenfalls verstanden, danke 👍

    0
  • O

    volkard schrieb:

    wegen performance. du haust einfach mal so ro zeiger noch 4 bytes für den refcounter dazu. dabei reichen 0 bytes vollkommen aus. ist sich kleiner und schneller (weil gar nix immer und immer wieder auf 0 getestet werden muss.)

    Und du hast noch gar nicht auf die zusätzliche Allokation hingewiesen, die shared_ptr AFAIK immer noch macht. Aber nur weil man in C++ an den entscheidenden Stellen schnell sein kann, schadet der Luxus von shared_ptrs in anderen Teilen des Programms doch nicht... 😕 Ich oute mich jedenfalls als so Boost-süchtig, dass mir die shared_ptr-Lösung gedanklich auch einfacher zu verarbeiten vorkommt als die, wo ich an deletes denken muss.

    0
  • H

    Frage: Es geht doch um Performance. Wenn mir auffällt, dass sich die langen Texte in der Regel bereits durch die ersten paar Zeichen unterscheiden, warum baue ich mir keinen Hasher, der nur eben diese Zeichen beachtet? Da ich bei einem Baum doch einige Vergleiche benötige werde ich den Baum IMO schnell wieder überholen.

    Gut, ich hatte noch nie lange Texte als Index und habe mir deswegen tatsächlich noch nie Gedanken darüber gemacht.

    0
  • V

    Helium schrieb:

    Frage: Es geht doch um Performance. Wenn mir auffällt, dass sich die langen Texte in der Regel bereits durch die ersten paar Zeichen unterscheiden, warum baue ich mir keinen Hasher, der nur eben diese Zeichen beachtet?

    solange man nicht auf die idee kommt, sich auf die ersten 8 zeichen zu beschränken und hinter der hashtable nur ne verkettete liste zu haben, gehts. deine idee mit bäumen hinter der table macht vieles möglich.

    Da ich bei einem Baum doch einige Vergleiche benötige werde ich den Baum IMO schnell wieder überholen.

    jo. sagen wie mal, man beachtet nur das erste zeichen!
    statt

    map<string,Foo> dictionary;

    und

    void insert(string key,Foo value){
   dictionary[key]=value;
}

    schreibt man einfach

    map<string,Foo> dictionary[256];

    und

    void insert(string key,Foo value){
   dictionary[u8(key[0])][key]=value;
}

    spart mit einem tabellengucker (mal gleichverteilng der schlüssel angenommen) gleich 8 verzweigungen. die tabelle kann natürlich auch größer sein, also zwei buchstaben angucken. oder sogar mehrere (wenige) buchstaben angucken und hashen.
    ich setze gerne mit so einfachen tabellenguckern zuvor die suchtiefe runter. das erlaubt dann oft sogar, mal unewöhliche strukturen wie move-to-front-lists zu nehmen oder was ich auch sehr mag, sind hashtables, die fixed sized sind und im falle der kollisiion einfach den alten wert überschreiben. also caches. die kann man fein vor teure rechnungen hängen.

    0
  • V

    operator void schrieb:

    Aber nur weil man in C++ an den entscheidenden Stellen schnell sein kann, schadet der Luxus von shared_ptrs in anderen Teilen des Programms doch nicht... 😕 Ich oute mich jedenfalls als so Boost-süchtig, dass mir die shared_ptr-Lösung gedanklich auch einfacher zu verarbeiten vorkommt als die, wo ich an deletes denken muss.

    haste dir schonmal gedanken gemacht, wie du die kraft von c++ noch viel voller ausschöpfen kannst? indem du java benutzt.
    dort gibt es nen geilen garbage collector und schnell ist die sace auch. und du brauchst vor zeiger kein sternchen mehr zu malen. es gibt auch templates und sicher ist es und überhaupt.
    welchen sinn hat es, sich eingehend mit c++ zu beschäftigen? sauberer java-code, und man sagte mir, es gäbe ihn, ist auch recht schnell. das wäre doch besser, als in c++ hie und da mit shared_ptr rumzumachen und dann vergißt man es doch wanders und alles schmiert wiedermal ab.

    in c++ muß man nicht umständlich ans delete denken. in c++ denkt man IMMER ans delete. ganz einfach ist das. zu jedem new gehöer ein delete. immer. immer. immer. wenn du das aufweichst mit der verwendung von shared_ptr an den nutzlosesten stellen, dann wirste nie mehr klar im kopp, wo du vielleicht doch mal eins brauchst und dein c++-code wird genauso unsicher, wie anno dazumal der c-code war. siehe absturzanzahl von win311 und zugehörigen applikationen. du mußt dich entscheiden: entweder mach den schritt ganz und geh zu java oder bleib hier aber versaue die nichts.

    zu viele designentscheidungen von c++ ehen deutlich nicht in richtung letzem komfort, um dann so zu tun, als sei es doch so. das wird inkonsistent und grausam. benutze c++ für die probleme, wo die ein wenig öl an den fingern nicht weh tut. benutze c++, wenn du peak performance suchst, aber auch was dafür zahlen magst. ich löse die hälfte meiner (programmier-)probleme in perl, vb und php. insbesondere vb nimmt bei mir an bedeutung zu und wird evtl demnächst von c# abgelöst.

    bald isses soweit, daß boost-sucht als krankheit eingestuft werden muß. ich sehe immer mehr boost-mißbrauch. und jedesmal ohne das geringste schlechte gewissen beim kranken.

    0
  • ?

    Wie kriegt man eigentlich ein erase bei nem Container mit um sein delete aufzurufen?

    Wenn man einen Container hat der Zeiger aufnimmt, ihn am Anfang füllt und am Ende wieder alles freigibt - kein Problem. Aber was ist, wenn man irgendwann einen Zeiger mit erase auf dem Container entfernt? Dann kann der doch nicht mehr freigegeben werden, oder?!

    0
  • H

    Dann machs vorher.

    0
  • V

    Helium schrieb:

    Dann machs vorher.

    genau.
    und der container hat doch eh nen wrapper drum, um anwendungsnamen wie Personalliste auf std-namen wie str::map<int,Person*> zu mappen.
    der kann das fein machen.

    void Personal::toeten(int id){
   delete leute[id];
   leute.erase(id);
}
    0
  • O

    volkard schrieb:

    haste dir schonmal gedanken gemacht, wie du die kraft von c++ noch viel voller ausschöpfen kannst? indem du java benutzt.

    Ich finde Java als Sprache einfach impotent - da verwende ich noch lieber den nicht optimierenden Standard-VC (oder vielleicht Ruby). Ist es denn so exotisch, dass man C++ als schöne und mächtige Sprache, nicht nur als Assembler mit templates ansieht?

    in c++ muß man nicht umständlich ans delete denken. in c++ denkt man IMMER ans delete. ganz einfach ist das. zu jedem new gehöer ein delete. immer. immer. immer.

    Ich fahre mit der Regel "es gibt kein ungewrapptes delete. Nie." auch ganz gut und kann mich spontan an keine Bugs erinnern, die ich auf der Ebene gehabt habe. Vielleicht brauche ich ja noch ein paar Monate mehr ohne delete, damit ich vergesse, wo Löschungen statt finden... 🙂

    0
  • V

    operator void schrieb:

    Ich fahre mit der Regel "es gibt kein ungewrapptes delete. Nie."

    halte ich für übertrieben. denn so oft muß man new/delete nu wirklich nicht anfassen. aber wenn du immer smart pointers benutzt, schmeißt du unnötig viel performance weg. ich hab glaub ich schon gepostet, wo man normalerweise die deletes hinversteckt. und das geht ganz ohne smart-pointers. und es geht ganz harmonisch, weil c++ nicht als besserer makroassembler benutzt wurde.
    share_ptr sind wirklich selten vonnöten. ganz selten. ungeheuter selten, um es auf den punkt zu bringen.
    es ist kein witz, daß ich dir empfehle, java zu benutzen. offensichtlich liegt dir c++ nicht. du wirst nur ärger bekommen, wenn du die sprache vergewaltigst. du mußt rausfinden, wie man in der zielsprache am besten programmiert. nicht völlig losgelöst rausfinden, wie man gut programmiert und dann hoffen, daß es kein schuß ins knie wird.

    0
  • V

    operator void schrieb:

    Vielleicht brauche ich ja noch ein paar Monate mehr ohne delete, damit ich vergesse, wo Löschungen statt finden... 🙂

    ist das dein wunsch? ich kenne die lösung...
    du kannst sogar vergessen, wann die löschungen stattfinden.

    0
  • O

    Nö. Ich verwende Smart-Pointer nur, weil ich weiß, was sie wann tun. Das ist aber nicht weiter schwer festzustellen. Ich kenne jedenfalls keinen verbreiteten, der nicht leicht vorhersehbar wäre.

    volkard schrieb:

    halte ich für übertrieben. denn so oft muß man new/delete nu wirklich nicht anfassen. aber wenn du immer smart pointers benutzt, schmeißt du unnötig viel performance weg.

    Ich sagte nicht, dass ich immer shared_ptr verwende. Wo schmeißt ein scoped_ptr Performance weg?
    shared_ptrs brauche ich in der Tat seltener. Und wenn ich sie brauche, dann aber auch oft an Stellen, an denen ein GC nicht helfen würde, sondern ich den Inhalt eines vectors von shared_ptrs z.B. wirklich sicher tot haben will, wenn der vector auch tot geht. Und nie an Stellen, an denen sie der Performance schaden. Mir fällt jedenfalls keine ein.

    Ich fühle mich in C++ eigentlich auch nicht verkehrt. Wenn man sein delete nicht selbst schreibt, sind auf einmal z.B. auch Exceptions kein Problem mehr, sondern funktionieren einfach genau richtig. Aber naja, dass ich nach dem Projekt hier auch mal andere Sprachen ansehen werde, wird dich sicher beruhigen.

    0
  • H

    operator void schrieb:

    Ich fühle mich in C++ eigentlich auch nicht verkehrt.

    Geht mir genauso und ich verwende auch Smart-Ptr und andere RAII-Klassen (und boost und andere Sachen die das Leben leichter, aber nicht zwangsweise langsamer machen).
    Und wenn ich mir den Kopf über Performance zerbreche, versuche ich auch ganz gerne so Evergreens wie die 80-20-Regel zu beachten...

    Hm, allerdings werde ich mir auch nicht von Volkard das C++ Programmierern ausreden lassen 😉

    0
  • V

    operator void schrieb:

    Ich sagte nicht, dass ich immer shared_ptr verwende. Wo schmeißt ein scoped_ptr Performance weg?

    kann sein, daß er keine wegschmeißt. jo, mit der schnittstelle ist man nicht gezwungen, was teures zu machen. also falls man echt pimpl machen muss, sollte man wohl auch scoped_ptr nehmen.
    bin gerade am überlegen, wann ich zum letzten, mal pimpl machen musste. öhm. hab's vergessen.
    wann sollte ich pimple benutzen? warum tut ihr das alle? bloß um die compilezeit zu senken?

    ich hab resentiments gegen smart pointers, weil ich keine gute verwendung sehe. außer mal in kranken ausnahmen, sagen wir mal nicht häufiger als einmal im jahr. und das liegt nicht daran, daß ich smart pointers nicht kennen würde.

    shared_ptrs brauche ich in der Tat seltener. Und wenn ich sie brauche, dann aber auch oft an Stellen, an denen ein GC nicht helfen würde, sondern ich den Inhalt eines vectors von shared_ptrs z.B. wirklich sicher tot haben will, wenn der vector auch tot geht. Und nie an Stellen, an denen sie der Performance schaden.

    jup. refcounting pointers hab ich bisher nur in multithreaded umgebenungen gebraucht, wenn die threads sich die objekte gegenseitig schicken, nur um selber möglichst wenig tun zu müssen. da kann ich nie genau wissen, wie viele threads das objekt gerade kennen.
    es könnte aber sein, daß ich demnächst total viel refcounting mache, umd total viel speed zu kriegen.

    Ich fühle mich in C++ eigentlich auch nicht verkehrt. Wenn man sein delete nicht selbst schreibt, sind auf einmal z.B. auch Exceptions kein Problem mehr, sondern funktionieren einfach genau richtig.

    ich hab auch nie rohe zeiger in der hand. und ich muss nie was catchen, nur um was freizugeben.

    Aber naja, dass ich nach dem Projekt hier auch mal andere Sprachen ansehen werde, wird dich sicher beruhigen.

    och, ist eigentlich egal. java kommt ja im managed käppchen ja auch zu jedem c++-programmierer.

    0
  • H

    volkard schrieb:

    bin gerade am überlegen, wann ich zum letzten, mal pimpl machen musste. öhm. hab's vergessen.
    wann sollte ich pimple benutzen? warum tut ihr das alle? bloß um die compilezeit zu senken?

    Spontan fallen mir drei Gründe ein
    1. Um Transaktionen leichter implementieren zu können
    2. Dazu passend: Um einen exception-sicheren op= für beliebige Klassen implementieren zu können (-> über ein nonthrowing Swap) -> Siehe: "More Exceptional C++" - Item 22
    3. Für Implicit-Sharing (-> siehe Qt)

    Die Compilezeit-Geschichte hat mir bei meinem letzten größeren Projekt aber auch einige Stunden Wartezeit erspart (gcc 3.2 auf einem 200 Mhz Pentium II 128 MB. Das dauert...)

    0
  • O

    volkard schrieb:

    kann sein, daß er keine wegschmeißt. jo, mit der schnittstelle ist man nicht gezwungen, was teures zu machen. also falls man echt pimpl machen muss, sollte man wohl auch scoped_ptr nehmen.

    Tu ich. Und auch für Klassenelemente oft aus diversen Gründen (0/1-Komposition ist der Einleuchtendste).

    bin gerade am überlegen, wann ich zum letzten, mal pimpl machen musste. öhm. hab's vergessen.
    wann sollte ich pimple benutzen? warum tut ihr das alle? bloß um die compilezeit zu senken?

    Jup, das ist definitiv der Hauptgrund. Aber ich finde es auch nicht weiter schlimm/umständlich, zu pimplen - man schreibt das Interface in den Header und arbeitet danach nur an der .cpp. Meistens hab ich das Header-Tab gar nicht offen, wenn ich die Klasse implementiere.
    Das Effizienz-Gegenargument bleibt natürlich bestehen, aber ich nehme für die Mehrproduktivität durch kurze Compilezeiten gerne den Overhead in Kauf. (Geht ja wieder nur um bestimmte Klassen. Wo Effizienz spürbar zählt, orientiere ich mich natürlich auch stärker nach ihr.)

    ich hab resentiments gegen smart pointers, weil ich keine gute verwendung sehe. außer mal in kranken ausnahmen, sagen wir mal nicht häufiger als einmal im jahr. und das liegt nicht daran, daß ich smart pointers nicht kennen würde.

    Wenn du weder smart pointers noch delete häufig brauchst, wüsste ich gerne mal, was dann. Es ist nicht so, als ob ich versuchen würde, möglichst viel new einzusetzen 🙂

    ich hab auch nie rohe zeiger in der hand. und ich muss nie was catchen, nur um was freizugeben.

    Naja, nehmen wir ein einfaches:

    void Personal::ersetzeAngestellten(int id, string infodateiname)
{
    delete map[id];
    map[id] = new Angestellter(infodateiname);
    // Hups, Datei gibts nicht. Exception fliegt, ~Personal löscht nen den alten
    // Eintrag nochmal und das Programm wird mit einer schicken Zugriffsverletzung
    // abgeschosen.
}

    Ist in dem (konstruierten, um am Beispiel zu bleiben) Fall vielleicht eh egal, aber zumindest würde ich mir beim Coden öfter Gedanken machen: Was wäre _wenn_? Mit shared_ptr wäre das

    map[id].reset(new Angestellter(infodateiname));

    Und fertig. Ich kenne Leute, die Exceptions in Konstruktoren aus solchen Gründen verteufeln und lieber nochmal .Create() aufrufen. Ist das im Sinne von C++?

    0
  • V

    operator void schrieb:

    Tu ich. Und auch für Klassenelemente oft aus diversen Gründen (0/1-Komposition ist der Einleuchtendste).

    damit ich mir das besser vorstellen kann, bei welcher klasse zuletzt?

    void Personal::ersetzeAngestellten(int id, string infodateiname)
{
    delete map[id];
    map[id] = new Angestellter(infodateiname);
    // Hups, Datei gibts nicht. Exception fliegt, ~Personal löscht nen den alten
    // Eintrag nochmal und das Programm wird mit einer schicken Zugriffsverletzung
    // abgeschosen.
}

    komisch. mache ich mir nie gedanken um exception sicherheit? irgendwie sehe ich zwar das problem, aber es ist nicht normal für mich.

    void Personal::ersetzeAngestellten(int id, Angestellter* angestellter)//nothrow
{
    delete map[id];
    map[id] = angestellter;
}

    und wenn gründe dafür sprechen, dem user ne andere schnittstelle zu geben, meinetwegen auch

    void Personal::ersetzeAngestellten(int id, string infodateiname)
{
    erstezeAngestellten(id, new Angestellter(infodateiname));
}

    Ist in dem (konstruierten, um am Beispiel zu bleiben) Fall vielleicht eh egal, aber zumindest würde ich mir beim Coden öfter Gedanken machen: Was wäre _wenn_? Mit shared_ptr wäre das

    map[id].reset(new Angestellter(infodateiname));

    ok, klarere punkt für "sich gedanken soll man machen" aber nicht zwingend für shared_ptr.

    Ich kenne Leute, die Exceptions in Konstruktoren aus solchen Gründen verteufeln und lieber nochmal .Create() aufrufen. Ist das im Sinne von C++?

    ganz sicher nicht. Create verschiebt das problem nur, hab ich das gefühl.

    0
Anmelden zum Antworten