ein paar Designfragen

freakC++

Hallo zusammen,

ich habe einen kaskadierenden Algorithmus implementiert und möchte diesen nun ein wenig optimieren und dabei vor allem den Code verschönern. Dazu habe ich die folgenden Fragen.

1.) Der Algorithmus ist von einer großen Schleife umgeben. Mit jedem Schleifendurchlauf fällt unten ein "int" raus. Bis jetzt schiebe ich dieses in einen stringstream und formatiere diesen später entsprechend. Aus einem anderen Thread habe ich jedoch erfahren, dass dies wohl ziemlich langsam ist.

Daher möchte ich die "herausfallenden" int's zuerst in einer entsprechenden Struktur abspeichern. Klar, es bietet sich vector<int> an. Damit würde es tatsächlich gehen, doch habe ich versucht ohne die STL zu arbeiten (zur Übung).

Ich weiß aber nicht, wie groß ein etwaiges Array sein wird, sodass ich solch eins auch nicht zur Laufzeit erstellen kann. Ich kann die Größe nur auf eine Zweierpotenz abschätzen, doch da würde ich einfach zu viele Bytes wegschmeißen.

Wie würdet ihr soetwas implementieren ohne STL beziehungsweise wie hätte das in alten C Zeiten funktioniert. Ich hoffe nicht, dass irgendeine KLasse geschrieben wurde, die Arrays automatisch durch ewige Kopiervoränge vergrößert, indem es neue erstellt und das alte reinkopiert.

2.) Ich habe nun meine Datenstruktur mit meinen ints und möchte diese nun so formatieren, dass zum Schluss ein string herauskommen.

Warum ist string.push_back so viel schneller als ein stringstream? Warum sollte ich dann überhaupt stingstreams verwenden. Bis jetzt finde ich dies sehr angenehmen, weil ein solcher ja alles frisst, für den der << - Operator definiert ist.

Vielen Dank
LG, freakC++

Eisflamme

Hi,

Der Algorithmus ist von einer großen Schleife umgeben.

Innere Schleifen kannst Du in Funktionen auslagern, das stört die Performance normalerweise nicht und erhöht die Übersichtlichkeit oft beträchtlich.

Mit jedem Schleifendurchlauf fällt unten ein "int" raus. Bis jetzt schiebe ich dieses in einen stringstream

Keine Ahnung, woraus der int fällt und wieso Du den in einen stringstream schiebst.

Damit würde es tatsächlich gehen, doch habe ich versucht ohne die STL zu arbeiten (zur Übung).

Willst Du üben oder guten Code erstellen? Auf die STL zu verzichten ist eine ziemlich unbrauchbare Übung, weil Du Dir schlechten Stil angewöhnst.

Ich kann die Größe nur auf eine Zweierpotenz abschätzen, doch da würde ich einfach zu viele Bytes wegschmeißen.

vector::resize oder reserve.

Wie würdet ihr soetwas implementieren ohne STL beziehungsweise wie hätte das in alten C Zeiten funktioniert.

Ja weißte, dann frag doch einfach im C-Forum nach. Wenn es das optimalste gewesen wäre, hätte man sich vermutlich einen eigenen dynamischen Container generiert. Vermutlich das Anlegen eines großen Speicherbereichs und ein einfaches Mitzählen eines Counters. Wäre der Speicher zu groß, dann eben blockweise Vergrößerung.

Warum sollte ich dann überhaupt stingstreams verwenden.

Keine Ahnung, Du sagst ja nicht, was Du machen willst. Eigentlich haben vector<int> und stringstream andere Anwendungsfälle. Der stringstream muss jeden int parsen und als String darstellen. vector<int> konvertiert nichts, ist doch klar, dass er dann schneller ist.

Beste Grüße

Ethon

Ich weiß aber nicht, wie groß ein etwaiges Array sein wird, sodass ich solch eins auch nicht zur Laufzeit erstellen kann. Ich kann die Größe nur auf eine Zweierpotenz abschätzen, doch da würde ich einfach zu viele Bytes wegschmeißen.

Im Prinzip kannst du beliebig viel Speicher anfordern da dein Betriebssystem den virtuellen Speicher erst "echten" (=physikalischen) Speicher verpasst sobald er verwendet wird. Also trau es dir ruhig. Du verscchwendest im Worst Case Speiccherseitengröße - 1 Bytes, meistens 4095. Das ist wirklich nicht viel.

Problematisch kann es höchstens bei 32bit System werden da dort auch der virtuelle Speicher recht limitiert ist.

freakC++

Eisflamme schrieb:

Keine Ahnung, woraus der int fällt und wieso Du den in einen stringstream schiebst.

Ich habe das Horner-Schema zum Wechseln der Zahlenbasis implementiert. Pro Iterationschritt wird eine Ziffer berechnet und "fällt" quais unten aus der Schleife raus --> bildhaft gesprochen

Eisflamme schrieb:

Ja weißte, dann frag doch einfach im C-Forum nach.

Werde ich machen!

Eisflamme schrieb:

Der stringstream muss jeden int parsen und als String darstellen.

Warum muss ein int geparst werden? Unter Parsen stelle ich mir eine Art Syntaxprüfrung vor. Hat ein int eine Syntax?

Ethon schrieb:

Problematisch kann es höchstens bei 32bit System werden da dort auch der virtuelle Speicher recht limitiert ist.

Jo, es soll aber auch auf 32 Bit Systemen laufen Der Tipp ist aber gut. Danke

Verstehe ich euch richtig, dass ihr zum Erstellen eines Strings nicht stringstream verwenden würdet, wenn der Strinhalts die einzelnen Elemente eines std::vector<int> sind?

Vielen Dank
LG, freakC++

knivil

kaskadierenden Algorithmus ... fällt unten ein "int" raus ... bildhaft gesprochen

Damit kann man echt viel anfangen. Dazu kann ich nur sagen: Nimm blau, dann wirds schoener.

Verstehe ich euch richtig, dass ihr zum Erstellen eines Strings nicht stringstream verwenden würdet, wenn der Strinhalts die einzelnen Elemente eines std::vector<int> sind

Ich verwende std::to_string. Ansonsten: Was soll string.push_back fuer ints sein?

freakC++

knivil schrieb:

Nimm blau, dann wirds schoener.

OK :D. Danke. Das leuchtet auch ein, weil Cola ja besser als aus dem Glas schmeckt!

knivil schrieb:

Ich verwende std::to_string.

und warum muss hier nicht geparst werden? Warum ist es also so viel schneller als die Zahlen in einen stringstream zu schieben?

Danke

knivil

Warum ist string.push_back so viel schneller als ein stringstream?

Welchen Datentyp hat in dieser Aussage das Objekt string ?

und warum muss hier nicht geparst werden?

Wo schreibe ich das?

freakC++

knivil schrieb:

Warum ist string.push_back so viel schneller als ein stringstream?

Welchen Datentyp hat in dieser Aussage das Objekt string ?

?
string

knivil schrieb:

Wo schreibe ich das?

nirgendswo. Aber das schließe ich daraus. Anscheinend ist stringstream ja so langsam, weil die Zahlen zuvor geparst werden. Wenn std::to_string so viel schneller ist, schließe ich daraus, dass hier nicht gepart wird (jaja, sehr gewagt^^). Wo liegt dann der Performancegewinn?

knivil

Wenn std::to_string so viel schneller ist

Wo schreibe ich das? Ich habe keinen Performancevergleich getaetigt.

Aber das schließe ich daraus.

Du gehst von Annahmen aus, die so nicht gegeben sind. Liesst Dinge, die so nicht da sind. Was du schliesst, entbehrt jeder Logik. Hoere auf damit!

?
string

Nun, ich kenne kein string::push_back(int). Diese Methode nimmt fuer gewoehnlich ein char als Parameter.

freakC++

Anscheinend hast Du meinen Punkt nicht verstanden. Mir geht es hier um eine effizientere Lösung für stringstream << int. In einem anderen Thread habe ich erfahren, dass dies nämlich so wegen eines Parsingvorgangs nicht sehr schnell ist.

Wie würdest Du möglichst schnell integer an einen String anfügen?

Du hast von std::to_string gesprochen. Also gehen ich davon aus, dass dies wohl recht flott geht. Mich interessiert warum. Falls dies ebenfalls langsam ist: Warum benutzt Du es?

Vielen Dank
LG, freakC++

knivil

Warum ist string.push_back so viel schneller als ein stringstream? Mir geht es hier um eine effizientere Lösung für stringstream << int.

Deine falsche Vorstellung von Geschwindigkeit ruehrt vielleicht daher, dass du string::push_back falsch benutzt hast. Bitte korrigiere diese Vorstellung oder begruende mit aussagekraeftigen Zahlen oder Verweisen.

Wie würdest Du möglichst schnell integer an einen String anfügen?

mein_string += std::to_string(mein_int);

freakC++

knivil schrieb:

schreibe ich das? Ich habe keinen Performancevergleich getaetigt.

Ich aber!

knivil schrieb:

Was du schliesst, entbehrt jeder Logik. Hoere auf damit!

is ja gut...dafür hättest Du deinen Beitrag nicht änder müssen. char puhh[8] = {67,72,73,76,76,77,65,76};

Nathan

freakC++ schrieb:

Anscheinend hast Du meinen Punkt nicht verstanden. Mir geht es hier um eine effizientere Lösung für stringstream << int. In einem anderen Thread habe ich erfahren, dass dies nämlich so wegen eines Parsingvorgangs nicht sehr schnell ist.

Jein. std::stringstream ist lahm, weil im Hintergrund wegen Formatierung und Fehlerprüfung und generellem Overhead da total viel passiert.

Du hast von std::to_string gesprochen. Also gehen ich davon aus, dass dies wohl recht flott geht. Mich interessiert warum. Falls dies ebenfalls langsam ist: Warum benutzt Du es?

Weil std::to_string() sich den ganzen Stress mit Formatierung spaart, das Ergebnis nicht buffert und geringen Overhead hat.

freakC++

knivil schrieb:

mein_string += std::to_string(mein_int);

Gut. Danke! Mich interessiert, warum dies schnell ist. Dies ist ja deine Antwort auf meine Frage, wie "Du möglichst schnell integer an einen String anfügen" würdest. Ist dies schneller als stringstream << int? Wenn ja, warum?

knivil schrieb:

vielleicht daher, dass du string::push_back falsch benutzt hast.

Ich benutze diese Methode gar nicht, sondern habe ich aus einem anderen Thread. Bis jetzt geht es bei mir nur um die Nutzung von stringstream und eventuell um deine Art.

Danke dir

knivil

Ich aber!

Dann stelle dein Testprogramm und deren Ergebnisse zur Diskussion. Wenn dein Programm string::push_back verwendet ... gute Nacht.

diese Methode gar nicht, sondern habe ich aus einem anderen Thread

Dann sag doch mal mit was du verglichen hast.

Ethon

Wenn das schnell sein muss: Selber basteln! stringstreams haben viel overhead und auch to_string legt eine unnötige Kopie an.

void append(std::string& s, int value, int radix=10)
{
    if(value < 0)
    {
        s.push_back('-');
        value = -value;
    }

    assert(radix > 1 && radix < 17);
    char const* chars = "0123456789abcdef";

    char buffer[sizeof(int) * CHAR_BIT];
    char* iter = buffer;
    while(value >= radix)
    {
        *iter = chars[value % radix];
        value /= radix;
        ++iter;
    }
    *iter = chars[value];

    s.append(std::reverse_iterator<char*>(iter + 1), std::reverse_iterator<char*>(buffer));
}

Ziemlich optimal so.

knivil

char buffer[sizeof(int) * CHAR_BIT];

Sehr kryptische Groessenangabe. Warum genau so, wenn fuer 32 Bit, Stellen ausreichen 11 Stellen ausreichen und fuer 64 Bit eben 21 Stellen genuegen? Klar, wenns binar sein soll, aber das ist nicht die Anforderung. Deswegen bezweifle ich, dass es ziemlich optimal ist, weil eben generalisiert wurde.

Schaut man sich andere Implementierungen so fuellen sie den Buffer gleich von hinten und kopieren mit memcpy und Co.

freakC++

Der Code gefällt mir. Man könnte es noch effizienter machen, wenn man das ganze über eine Loopup-Tabelle regelt:

char const* chars[90] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};

LG, freakC++

freakC++ schrieb:

Der Code gefällt mir. Man könnte es noch effizienter machen, wenn man das ganze über eine Loopup-Tabelle regelt:

1. Low-Level-Code != effizient
2. "gefallen" ist subjektiv, Performance muss man messen!
3. Jedes vnprintf ist schneller als das Gehacke von Ethon.
4. Dein Vorschlag ist Quatsch.

Ethon

knivil schrieb:

char buffer[sizeof(int) * CHAR_BIT];

Sehr kryptische Groessenangabe. Warum genau so, wenn fuer 32 Bit, Stellen ausreichen 11 Stellen ausreichen und fuer 64 Bit eben 21 Stellen genuegen? Klar, wenns binar sein soll, aber das ist nicht die Anforderung. Deswegen bezweifle ich, dass es ziemlich optimal ist, weil eben generalisiert wurde.

Schaut man sich andere Implementierungen so fuellen sie den Buffer gleich von hinten und kopieren mit memcpy und Co.

Stackspeicher zu verschwenden ist doch ziemlich egal.
In welche Richtung man den Buffer befüllt ist auch egal.
Und memcpy bringt bei solchen kleinen Eingabemengen wohl reichlich wenig, mit Pech wird's sogar langsamer.

Ich würde am ehesten kritisieren dass nicht direkt in den String geschrieben wird. Müsste man eben den String zuerst vergrößern. Bezweifle aber dass sich das lohnt.