3. [GELÖST] char* oder String - Was ist schneller

[GELÖST] char* oder String - Was ist schneller

  • S

    unskilled schrieb:

    was nützt es dir mal 100 takte einzusparen wenn allein next_permutation 50000 braucht?

    Die Allokationen fuer neue Strings und natuerlich der Speicherbereich der dann ploetzlich mehr gebraucht wird (was zu mehr page faults fuehrt) ist nicht gerade trivial.

    du wirst also mit volkards variante einen deutlichen unterschied in der performance sehen.

    0
  • U

    Shade Of Mine schrieb:

    unskilled schrieb:

    was nützt es dir mal 100 takte einzusparen wenn allein next_permutation 50000 braucht?

    Die Allokationen fuer neue Strings und natuerlich der Speicherbereich der dann ploetzlich mehr gebraucht wird (was zu mehr page faults fuehrt) ist nicht gerade trivial.

    du wirst also mit volkards variante einen deutlichen unterschied in der performance sehen.

    wieso soll der speicherverbrauch ansteigen, wenn man etwas nur _anders_ speichert?

    wieso bringst du die allokation neuer strings mit ein? imho hat sich das so angehört, als ob es nur einen gäbe?!

    bb

    0
  • V

    unskilled schrieb:

    wieso bringst du die allokation neuer strings mit ein? imho hat sich das so angehört, als ob es nur einen gäbe?!

    und viele viele temporäre.
    wieviele strings werden konstruiert bei string e=a+b+c+d?

    0
  • U

    volkard schrieb:

    unskilled schrieb:

    wieso bringst du die allokation neuer strings mit ein? imho hat sich das so angehört, als ob es nur einen gäbe?!

    und viele viele temporäre.
    wieviele strings werden konstruiert bei string e=a+b+c+d?

    Wer sagt denn, dass so etwas im quellcode vorkommen würde? oO

    bb

    0

  • @AceKiller73:
    Speicher die Wörter ruhig als std::string, die werden ja nur 1x erzeugt, und dann immer bloss gelesen, d.h. hier kannst du ruhig std::string verwenden.

    Dann lass dir die Permutationen als Liste von Indices erzeugen, also (1,2,3) (1,3,2) (2,1,3) ...

    Dann schreib die Strings einfach anhand der Liste von Indices in den File-Stream, einen nach dem anderen. Hübsch mit Leerzeichen dazwischen oder wie auch immer du es haben willst.

    Die C++ Stream-Klassen puffern intern schon, d.h. der File-Stream schreibt eh nicht jedes Wort einzeln in die Datei, sondern der puffert erstmal ein paar tausend Byte, und schreibt die dann aufeinmal raus. Das sollte reichen um knapp an die maximale Geschwindigkeit der Festplatte zu kommen.

    Falls nicht kannst du natürlich selbst nochmal einen Puffer implementieren, z.B. einfach mit einem std::vector<char>.

    EDIT: wenn ich mir das so ansehe ist das ziemlich dasselbe was volkard schon geschrieben hat. Hihi, naja, auch gut 🙂

    0
  • A

    Erstmal danke an euch alle.

    Ich werde es jetzt mit Indizes machen. So hatte ich auch die Permutation gerell implementiert. Ich verwende auf keinen Fall next_permutation.

    Mir war nicht klar, wie C++ mit Dateien arbeitet. Dachte es könnte bei vielen Aufrufen Geschwindigkeitsverlust geben.

    Nochmal danke.

    MFG
    Ace

    0
  • S

    unskilled schrieb:

    Wer sagt denn, dass so etwas im quellcode vorkommen würde? oO

    Wenn du effektiv mit std::string arbeiten willst hast du entweder verrenkungen im code oder temporaere objekte. ist einfach so.

    und wenn du die permutationen speichern willst, dann hast du natuerlich pro permutation einen gewissen speicher verbrauch: du musst die worte ja abspeichern.

    deshalb die idee nur indizes zu speichern oder aber nocopy strings. dadurch hast du natuerlich nur einen bruchteil des speicher verbrauchs...

    0
  • U

    wieviele strings werden konstruiert bei string e=a+b+c+d?

    Und wie viele char* werden konstruiert, wenn man so etwas schreiben würde? Oh - das geht ja gar nicht... ;P

    std::string e;
e.reserve(a.length() + b.length() + c.length() + d.length());
e = a;
e += b;
e += c;
e += d;

    effektiver bekommst du es wohl mit char`s auch nicht hin?!

    bb

    0
  • N

    volkard schrieb:

    wieviele strings werden konstruiert bei string e=a+b+c+d?

    Das Problem sollte im neuen Standard durch RValue-Referenzen auch eingedämmt werden...

    0
  • V

    unskilled schrieb:

    std::string e;
e.reserve(a.length() + b.length() + c.length() + d.length());
e = a;
e += b;
e += c;
e += d;

    effektiver bekommst du es wohl mit char`s auch nicht hin?!

    das ist richtig. und sogar noch mehr: mit char* würde man wohl normalerweise strcat nehmen und mußte schon sehr fleißig (und vielleicht mutig) sein, deine schnelle version nachzubauen.

    ich würde die wörter vermutlich sogar in einem vector<string> halten und die permutationen rekursiv erzeugen und gleich ausgeben mit dreimal swap pro permutation.

    0
  • V

    Nexus schrieb:

    volkard schrieb:

    wieviele strings werden konstruiert bei string e=a+b+c+d?

    Das Problem sollte im neuen Standard durch RValue-Referenzen auch eingedämmt werden...

    ja. nur das anfängliche allokieren genau der richtigen speichermenge geht noch nicht einfach. mit expression templates würde aber auch das gehen.

    0
  • S

    unskilled schrieb:

    effektiver bekommst du es wohl mit char`s auch nicht hin?!

    Wer will char* verwenden?

    Ein simpler Ansatz waere zB:

    std::vector<std::vector<nocopystr> > permutations;
std::vector<nocopystring> current;
//current fuellen
do {
  permutations.push_back(current);
} while(next_permutation(current.begin(), current.end());

    Sofern man die Permutationen speichern will bietet sich nun eben nocopy string oder nur die indizes an. std::string waere hier die falsche variante.

    natuerlich kann man auch std::string verwenden wenn man es wie volkard macht und die permutationen nicht speichert.

    was ich eigentlich sagen will ist, dass nocopy strings ein tool sind das man kennen sollte. ob es hier und jetzt sinn macht, will ich nicht naeher diskutieren - es faellt mir nur auf dass c++ sehr viele tools anbietet die aber nicht bei boost oder in der stl zu finden sind und sie deshalb fast niemand kennt.

    ich will hiermit eigentlich nur anregen ab und zu mal an nocopy strings zu denken wenn man mit string kopiererei zu tun - denn sie sind ein wunderbares tool.

    0

  • Was ist jetzt bitte ein "nocopystring"?

    0
  • S

    hustbaer schrieb:

    Was ist jetzt bitte ein "nocopystring"?

    Ein string der nicht kopiert sondern sich nur merkt worauf er zeigt. idealerweise über einen first und last zeiger implementiert.

    nocopystring(char* p)
: first(p), last(p+traits::length(p)) {
}

    Wobei du dir bei konstanten strings ja das length() sparen kannst...

    Du hast 0 allokationen und dennoch den komfort von std::string. du musst aber natürlich garantieren dass der speicher die ganze zeit über gültig ist.

    ist zB beim parsen von dateien sehr effizient weil du die datei soweiso in den speicher mappst und du dann ohne string kopieren auskommst...

    0

  • OK, danke 🙂

    Ich hab' bloss gefragt weil deine Aussage "Wer will char* verwenden?" für mich irgendwie danach geklungen hat, als meintest du was anderes.

    0
  • S

    hustbaer schrieb:

    OK, danke 🙂

    Ich hab' bloss gefragt weil deine Aussage "Wer will char* verwenden?" für mich irgendwie danach geklungen hat, als meintest du was anderes.

    Naja der Punkt ist, dass du mit so einer Klasse rohe char* ja auch nie wieder anfassen musst...

    0
Anmelden zum Antworten