Effektivster Weg, unsigned int in string umzuwandeln

[Gilder]

Hallo, ich schreibe gerade eine Anwendung, in der ich ein unsigned int in einen string umwandeln muss. Normalerweise mache ich das immer so:

std::stringstream Str;
Str<<MeineZahl;
Str>>Mein_std_string;

Das ist zuverlässig, bietet manipulatoren und ist sicher. Allerdings brauche ich jetzt eine Funktion, die diese umwandlung so schnell wie möglich macht. Dabei ist es mir egal, ob die Zahl als std::string oder C-String vorliegt (was halt schneller ist). Zuerst dachte ich an atoi, allerdings weis ich nicht, wie diese Funktion intern funktioniert.
Dann wollte ich mir das selber schreiben:

unsigned int zahl;
std::string str(10, '0');
str[0]=static_cast<char>(zahl/1000000000+'0');
str[1]=static_cast<char>(zahl/100000000+48);
str[2]=static_cast<char>(zahl/10000000+48);
//usw

Allerdings weis ich nicht, ob die ganzen Divisionen bei der Performance stören.
Welche Methode würdet ihr wählen? Gibt es eine "Standard Vorgehensweise" für die performante Umwandlung von Zahlen in strings? Denn irgendwie muss der Computer aus den Bitmustern ja auch lesbare ASCII Zeichen machen.

Schonmal Danke im Voraus!

[Gilder]

//EDIT:
Ersetze atoi im Text oben mit itoa

[volkard]

Gilder schrieb:

Allerdings weis ich nicht, ob die ganzen Divisionen bei der Performance stören.

Natürlich stören sie.
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF
Punkt 8.7

[unskilled]

so:

std::stringstream ss;
ss << number;
ss >> string;

ich bin mir zwar nicht sicher, wie man es am besten machen kann, aber ich denke fast, dass es nen weg mit weniger divisionen gibt^^ vll mit irgendwelchem bit-gefrickel, aber kann mir nur schwer vorstellen, dass stringstream so extrem viel langsamer sein soll, wie wenn mans selbst machen wöllte...

bb

[volkard]

unskilled schrieb:

ich bin mir zwar nicht sicher, wie man es am besten machen kann, aber ich denke fast, dass es nen weg mit weniger divisionen gibt^^ vll mit irgendwelchem bit-gefrickel, aber kann mir nur schwer vorstellen, dass stringstream so extrem viel langsamer sein soll, wie wenn mans selbst machen wöllte...

Kann ich mir aber schon vorstellen. Also ich könnte mir vorstellen, daß dauernd die aktuellen loales befragt werden, daß streamflags wie width und fill befragt werden, halt erstmal möglichst viel zeugs, das die sache flexibler und langsamer macht. und der fetteste brocken ist vermutlich der auf dem freispeicher angelegte puffer des stringstreams. klingt nach 100 takten grundgebühr und um 5% höhere ziffernkosten, als man per hand hinkriegt.

aber fast immer ist es völlig egal, weil die zahl dann auf den bildschirm zu bringen nochmal das zehntausendfache kostet.

[Gilder]

Wäre sprintf(str,"%u",value) für euch eine Alternative? Würde das besser abschneiden als über stringstreams?
Und wie soll bitte das "Bitgefrickel" aussehen?

[SeppJ]

Gilder schrieb:

Und wie soll bitte das "Bitgefrickel" aussehen?

Das was volkard zuerst geposted hat. Wobei das soooo frickelig gar nicht ist, wenn man sich mal die Zeit nimmt, den Algorithmus nachzuvollziehen.

[unskilled]

volkard schrieb:

und der fetteste brocken ist vermutlich der auf dem freispeicher angelegte puffer des stringstreams. klingt nach 100 takten grundgebühr und um 5% höhere ziffernkosten, als man per hand hinkriegt.

konnte man den nicht noch irgendwie manuell festlegen?!
sollten ja 11 stellen reichen...

die sache mit den flags ist wohl aber nicht von der hand zu weisen^^

bb

[Gilder]

Assemblercode verstehe ich nicht. Da muss ich wohl jemanden finden, der mir das in C++ "übersetzt"

[volkard]

Gilder schrieb:

Wäre sprintf(str,"%u",value) für euch eine Alternative? Würde das besser abschneiden als über stringstreams?

Das parsen des format-strings dauert auch.

Gilder schrieb:

Und wie soll bitte das "Bitgefrickel" aussehen?

Normalerweise im Kern nur

do{
   *writepos=x%10;
   ++writepos;
}while(x/=10);
//umdrehen
//zurückgeben

Und dann hat man die Wahl, ob man eine static array nimmt für die Rückgabe, was den Vorteil hat, daß man rückwärts schreiben kann, ob man den String danach umdreht oder ob man per Rekursion rückwärts schreibt. Und Ob man versucht Tabellenguckerchen zu machen umd Divisionen zu sparen. Und ob man gleich asm leut Buch benutzt.

Ich benutze nur Rekursion zum Umdrehen und keine weiteren Tricks, ist mir schnell genug so im Moment. Ich hab's aber nicht direkt der Geschwindigkeit wegen gemacht, sondern eher, ums gemacht zu haben.

ostream& operator<<(ostream& out,unsigned int x){
   if(n>=10)
      out<<n/10;
   return out<<char('0'+n%10);
}

[unskilled]

Gilder schrieb:

Assemblercode verstehe ich nicht. Da muss ich wohl jemanden finden, der mir das in C++ "übersetzt"

__declspec(naked) void __stdcall uint_to_ascii_lz(char *sptr, unsigned int x)
{
  __asm {
    push edi ; Save as per calling conventions.
    push esi ; Save as per calling conventions.
    push ebx ; Save as per calling conventions.
    mov eax, [esp+20] ; x
    mov edi, [esp+16] ; sptr
    mov esi, eax ; x
    mov edx, 0xA7C5AC47 ; Divide x by
    mul edx ; 10,000 using
    add eax, 0xA7C5AC47 ; multiplication
    adc edx, 0 ; with reciprocal.
    shr edx, 16 ; y1 = x / 1e5
    mov ecx, edx ; y1
    imul edx, 100000 ; (x / 1e5) * 1e5
    sub esi, edx ; y2 = x % 1e5
    mov eax, 0xD1B71759 ; 2^15 / 1e4 * 2^30
    mul ecx ; Divide y1 by 1e4,
    shr eax, 30 ; converting it into
    lea ebx, [eax+edx*4+1] ; 17.15 fixed-point format
    mov ecx, ebx ; such that 1.0 = 2^15.
    mov eax, 0xD1B71759 ; 2^15 / 1e4 * 2^30
    mul esi ; Divide y2 by 1e4,
    shr eax, 30 ; converting it into
    lea esi, [eax+edx*4+1] ; 17.15 fixed-point format
    mov edx, esi ; such that 1.0 = 2^15.
    shr ecx, 15 ; 1st digit
    and ebx, 0x00007fff ; Fraction part
    or ecx, '0' ; Convert 1st digit to ASCII.
    mov [edi+0], cl ; Store 1st digit in memory.
    lea ecx, [ebx+ebx*4] ; 5 * fraction, new digit ECX[31-14]
    lea ebx, [ebx+ebx*4] ; 5 * fraction, new fraction EBX[13-0]
    shr edx, 15 ; 6th digit
    and esi, 0x00007fff ; Fraction part
    or edx, '0' ; Convert 6th digit to ASCII.
    mov [edi+5], dl ; Store 6th digit in memory.
    lea edx, [esi+esi*4] ; 5 * fraction, new digit EDX[31-14]
    lea esi, [esi+esi*4] ; 5 * fraction, new fraction ESI[13-0]
    shr ecx, 14 ; 2nd digit
    and ebx, 0x00003fff ; Fraction part
    or ecx, '0' ; Convert 2nd digit to ASCII.
    mov [edi+1], cl ; Store 2nd digit in memory.
    lea ecx, [ebx+ebx*4] ; 5 *f raction, new digit ECX[31-13]
    lea ebx, [ebx+ebx*4] ; 5 * fraction, new fraction EBX[12-0]
    shr edx, 14 ; 7th digit
    and esi, 0x00003fff ; Fraction part
    or edx, '0' ; Convert 7th digit to ASCII.
    mov [edi+6], dl ; Store 7th digit in memory.
    lea edx, [esi+esi*4] ; 5 * fraction, new digit EDX[31-13]
    lea esi, [esi+esi*4] ; 5 * fraction, new fraction ESI[12-0]
    shr ecx, 13 ; 3rd digit
    and ebx, 0x00001fff ; Fraction part
    or ecx, '0' ; Convert 3rd digit to ASCII.
    mov [edi+2], cl ; Store 3rd digit in memory.
    lea ecx, [ebx+ebx*4] ; 5 * fraction, new digit ECX[31-12]
    lea ebx, [ebx+ebx*4] ; 5 * fraction, new fraction EBX[11-0]
    shr edx, 13 ; 8th digit
    and esi, 0x00001fff ; Fraction part
    or edx, '0' ; Convert 8th digit to ASCII.
    mov [edi+7], dl ; Store 8th digit in memory.
    lea edx, [esi+esi*4] ; 5 * fraction, new digit EDX[31-12]
    lea esi, [esi+esi*4] ; 5 * fraction, new fraction ESI[11-0]
    shr ecx, 12 ; 4th digit
    and ebx, 0x00000fff ; Fraction part
    or ecx, '0' ; Convert 4th digit to ASCII.
    mov [edi+3], cl ; Store 4th digit in memory.
    lea ecx, [ebx+ebx*4] ; 5 * fraction, new digit ECX[31-11]
    shr edx, 12 ; 9th digit
    and esi, 0x00000fff ; Fraction part
    or edx, '0' ; Convert 9th digit to ASCII.
    mov [edi+8], dl ; Store 9th digit in memory.
    lea edx, [esi+esi*4] ; 5 * fraction, new digit EDX[31-11]
    shr ecx, 11 ; 5th digit
    or ecx, '0' ; Convert 5th digit to ASCII.
    mov [edi+4], cl ; Store 5th digit in memory.
    shr edx, 11 ; 10th digit
    or edx, '0' ; Convert 10th digit to ASCII.
    mov [edi+9], dx ; Store 10th digit and end marker in memory.
    pop ebx ; Restore register as per calling convention.
    pop esi ; Restore register as per calling convention.
    pop edi ; Restore register as per calling convention.
    ret 8 ; Pop two DWORD arguments and return.
  }
}

was verstehst du daran nicht?
das rechts neben dem semikolon ist btw kein asm

bb

[Nexus]

volkard schrieb:

Und Ob man versucht Tabellenguckerchen zu machen umd Divisionen zu sparen.

Wenn man div() benutzt, sind die Chancen eventuell höher, dass Division und Modulo gleichzeitig berechnet werden können:
http://www.cplusplus.com/reference/clibrary/cstdlib/div/

[SeppJ]

Nexus schrieb:

volkard schrieb:

Und Ob man versucht Tabellenguckerchen zu machen umd Divisionen zu sparen.

Wenn man div() benutzt, sind die Chancen eventuell höher, dass Division und Modulo gleichzeitig berechnet werden können:
http://www.cplusplus.com/reference/clibrary/cstdlib/div/

Cool, das kannte ich ja noch gar nicht. Ich sollte mir mal die C Bibliothek genauer angucken, vielleicht gibt es dort ja noch mehr solche Schätze.

[unskilled]

Die allerschnellste Methode ist vermutlich ca. 2^32 Zeilen lang, kostet fast gar nichts, aber der quelltext ist grob überschlagen 80GB groß

bb

[volkard]

Nexus schrieb:

volkard schrieb:

Und Ob man versucht Tabellenguckerchen zu machen umd Divisionen zu sparen.

Wenn man div() benutzt, sind die Chancen eventuell höher, dass Division und Modulo gleichzeitig berechnet werden können:
http://www.cplusplus.com/reference/clibrary/cstdlib/div/

Der Compiler faßt in der Nähe liegende % und / auch selber zusammen, wenn das geht. Kein Bedarf. Außerdem macht er gar kein DIV, sondern erledigt das per Multiplikation, da der Teiler compilezeitkonstant ist.

[SeppJ]

unskilled schrieb:

Die allerschnellste Methode ist vermutlich ca. 2^32 Zeilen lang, kostet fast gar nichts, aber der quelltext ist grob überschlagen 80GB groß

Das ist gar nicht mal so doof. Wenn man das nur für Zahlen bis um die 1000 braucht, dann ist ein switch (den man mittels Präprozessor erstellen lässt) extrem effizient. Gibt's eigentlich ein Maximum an möglichen switch cases?

[unskilled]

SeppJ schrieb:

unskilled schrieb:

Die allerschnellste Methode ist vermutlich ca. 2^32 Zeilen lang, kostet fast gar nichts, aber der quelltext ist grob überschlagen 80GB groß

Das ist gar nicht mal so doof. Wenn man das nur für Zahlen bis um die 1000 braucht, dann ist ein switch (den man mittels Präprozessor erstellen lässt) extrem effizient. Gibt's eigentlich ein Maximum an möglichen switch cases?

weiß ich nicht - ich habs gerad mit unsigned short versucht - mein compiler hat jz scho 7 Minuten CPU-Zeit verbraucht und noch hat sich nichts getan, außer das er ca. 32mb ram belegt hat...^^
hab dir auch mal mit geschrieben, wie ich die datei erzeugt hab - damit du nicht so viel tippen musst ;o)

bb

#include <fstream>
#include <iostream>
#include <limits>

void create()
{
	std::ofstream str("Q:/convert.h");
	str << "const char* ToString(unsigned short tmp)" << std::endl
		<< '{' << std::endl
		<< "\tswitch(tmp)" << std::endl
		<< "\t{" << std::endl;

	for(unsigned short i(1); i != 0; ++i)
	{
		str << "\t\tcase " << i << ": return \"" << i << "\";" << std::endl;
		if(i%1000 == 0)
			std::cout << i << " / " << std::numeric_limits<unsigned short>::max() << std::endl;
	}

	str << "default: return \"0\";" << std::endl
		<< "\t}" << std::endl
		<< '}' << std::endl
		<< std::endl;
}

#include "Q:/convert.h"

int main()
{
//	create();

	const char* tmp = ToString(5432);
	std::cout << tmp << std::endl;

	system("PAUSE");
}

[unskilled]

MSVC schrieb:

1>Linking...
1>Generating code
1>fatal error C1510: Cannot load language resource clui.dll.
1>Project : error PRJ0002 : Error result 1 returned from 'c:\Program Files\Microsoft Visual Studio 9.0\VC\bin\link.exe'.

nachdem mein laptop zwischenzeitlic gar nicht mehr reagiert hat... xD
vll kanns ja der gcc!?
hab iwie das gefühl, dass der versuch bleibende schäden hinterlassen hat - fühlt sich alles gerad so extrem langsam an

bb

[otto8]

#include <cstring>

int main()
{
    unsigned int a = 551, b = 551;
    char string1[11] = {0,}; 
    // C
    int i = 9;
    do 
    {
        string1[i]= a%10+'0';
        a /= 10;
        i--;
    }while(a);
    strcpy(string1, &string1[i+1]);

    char string2[11] = {0,};
    // Assembler
    __asm
    {
        mov  eax, b
        mov  ebx, 10
        sub  ecx, ecx
rechnen:
        xor  edx, edx
        div  ebx
        push edx
        inc  ecx
        or   eax, eax
        jne  rechnen
um:     pop  edx
        add  dl, '0'
        mov  string2[eax], dl
        inc  eax
        dec  ecx
        jne  um
    }

    return 0;
}

[SeppJ]

Hier ein Beispiel für die ultimativ schnelle Lösung. Wobei ich die Geschwindigkeit nicht verglichen habe, aber es "sollte" schneller sein als alles andere. Das Kompilat ist bei mir stolze 38 kb groß.

#include <string>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/preprocessor/stringize.hpp>

std::string char2string(unsigned char i)
{
  switch(i){
#define MY_SWITCHER(ret,n,dummy) case n : return BOOST_PP_STRINGIZE(n);
    BOOST_PP_REPEAT(256, MY_SWITCHER,)
#undef MY_SWITCHER
  }
}

Das Limit für BOOST_PP_REPEAT ist derzeit 256, weswegen ich als integralen Datentyp char gewählt habe. Es ist aber natürlich möglich durch automatisch erstellten Code das Makro auf größere Wertbereiche zu erweitern.

[unskilled]

SeppJ schrieb:

Das Limit für BOOST_PP_REPEAT ist derzeit 256, weswegen ich als integralen Datentyp char gewählt habe. Es ist aber natürlich möglich durch automatisch erstellten Code das Makro auf größere Wertbereiche zu erweitern.

aber auf wie viel größere wertebereiche weist du auch nicht!?

bb