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

n3on

char* strings sind schneller, aber bieten mehr Freiraum für Fehler.

Die Frage ist nur wie wichtig dir die Geschwindigkeit ist.

Skym0sh0

pass mit char pointern gut auf und programmier sauber dann ist es schneller als std::string

aber das machen halt nicht viele...

std::vector<char>

AceKiller73

@ volkard

Was sind denn Indexketten?

MFG
Ace

volkard

damit meine ich, daß du nicht als permutation permstring="baum hase ast" machst, sondern nur perm[]={17,2,45}, und erst bei der ausgabe statt cout<<langerString jetzt cout<<wortliste[perm[0]]<<' '<<wortliste[perm[1]]<<' '<<wortliste[perm[2]] machst.
wenn du mit den permutationen nämlich noch was machen willst, wie buchstaben zählen und nur gewisse permutationen dann rauslassen, zum beispiel bei nem anagrammgenerator, dann sparst du die die gesamte stringkopiererei und kannst hundertmal schneller sein.

AceKiller73

Das ganze sollte in eine Datei geschrieben werden.

Dann muss aber mehrmals fstream << ... aufgerufen werden. fstream << ... << ... geht nicht, weil dynamisch festgelegt wird, wie viele wörter kombiniert werden.

Ist es dann trozdem noch schneller als alles in einen String zu kopieren und nur einmal zu schreiben?

MFG
Ace

Shade Of Mine

Warum solltes es relevant sein wie oft du den operator<< aufrufst?
Das was die Zeit kostet ist das reinschreiben in die Datei und egal welche Variante du nimmst, es sind immer gleichviel Byte...

unskilled

naja - wenn die länge zur compilezeit bekannt ist würde ich wohl auch char[] nehmen - wenn nicht würde ich allerdings auf char* verzichten und direkt std::string wählen (da das eigtl Problem nun mal bleibt, die permutationen auszurechnen)

was nützt es dir mal 100 takte einzusparen wenn allein next_permutation 50000 braucht?
vll ist dein fertiges programm ein paar byte kleiner - aber ich vermute mal, dass es eh <4KB ist von daher ist das eh egal ^^
also wird es nur unübersichtlicher und anfälliger für fehler

bb

Shade Of Mine

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.

unskilled

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

volkard

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?

unskilled

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

hustbaer

@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

AceKiller73

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

Shade Of Mine

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...

unskilled

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

Nexus

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...

volkard

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.

volkard

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.

Shade Of Mine

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.