int in String umwandeln....

template

Hi,

ich such nach einer schnellen Lösung einen Int in einen String auf Basis eines beliebigen Zahlensystems umwandlen zu lassen. Ich hab auch mal was gecoded (ist jetzt nicht der originalcode, sondern freihand also fehler vorbehalten;))

void UIntToString(unsigned int value, unsigned char system, char* poutput, size_t outputbufsize)
{
  int part;
  char pbuffer[UINTTOSTRING_BUFSIZE]; // Stack allokierung, sollte ja eigentlich kein Performance Problem sein.
  char* ppointer = pbuffer + UINTTOSTRING_BUFSIZE - 1;
  *ppointer = '\0';
  do {
    ppointer--;
    part = value % system; // Rest wohl schon;)
    if (part>9) *ppointer = part - 10 + 'A';
    else *ppointer = part + '0';
    value/= system; // und das hier gefällt mir nun wirklich überhaupt nicht...
  } while (value);

  strlcpy(ppointer, poutput, outputbufsize); // und das frisst erstmal Zeit :(
}

Nun, man könnte ja z.B. noch eine Fallunterscheidung für alle potenzen von 2 machen und dann mit & statt % und mit << statt / arbeiten. Das dürfte die Sache für diese Systeme ja nochmal erheblich beschleunigen. Natürlich wäre es auch sehr hilfreich, wenn man auf einfachem Wege die Stellenanzahl des Ergebnisses ermitteln könnte, so könnte man sich den temporären Puffer und vor allem den strlcpy sparen.

Ich hab mir jetzt deins nicht so genau angeschaut, aber das sollte übersichtlicher sein:

// z.B. in hexzahl
while (n) { 
			h = n % 16; //modulo Rest

			if ( h >= 10 && h <= 15) //Buchstabe a-f nehmen
			s[i++] = 'a' + (h-10);

			else if (h >= 0 && h <= 9) 
			s[i++] = h +'0';  // hier kannst du auch einen 
                                                  // Zeiger nehmen

			n /= 16; .
		}            
                 s[i] = '\0';
                 reverse (s);

Gruß esac

ZuK

template schrieb:

Natürlich wäre es auch sehr hilfreich, wenn man auf einfachem Wege die Stellenanzahl des Ergebnisses ermitteln könnte, so könnte man sich den temporären Puffer und vor allem den strlcpy sparen.

Solange system nicht negativ und > 0 ist ist die Stellenanzahl des Ergebnisses in deinem Fall (für unsigned int ) immer
( value / system ) + 1
Kurt

template

Danke für die schnellen Antworten.

@zuk: ja das dachte ich auch erst, aber 99 im 10er hat 2 stellen. 99 / 10 + 1 = 10

ZuK

Jo da hast recht: so solls aber gehen;

int len = 1;
while ( value > system )
  value /= system; len++;
}

Kurt

template

da hast du natürlich vollkommen recht, aber wenn ich das tue habe ich wieder massenhaft divisionen und ich bin mir nicht wirklich sicher ob mir das im Vergleich zu Stringkopie wirklich allzuviel Zeit spart.

ZuK

Mein code stimmt sowieso nicht.
So gehts aber schnell ist's nicht.

int len = 1;
while ( value >= system )
  value /= system; len++;
}

Kurt

template

Danke für den vorschlag. Leider scheint es von der Perfomance her ein Nachteil zu sein. Ich habs gerade mal ausprobiert:

Testrechner 3Ghz, MSVC 2003

1000 Durchläufe 0xF3BBCA95 ins 10er System

itoa -> ca. 300 µs
variante mit puffer -> ca. 330 µs
variante mit längenberechnung -> ca. 540 µs

ist ja der hammer, wie teuer diese blöden divisionen sind....

Wenn es nur um Geschwindigkeit geht, dann kannst du ja gleich bei itoa bleiben, dann ist die Frage ja aufgrund deiner Messergebnisse überflüssig.

Vielleicht eher im assembler-Forum nachfragen.

ZuK

Kannst es noch mit multiplikationen ausprobieren.

int len = 1, b=system;
while ( num >= b ) {
   b *= base; len++;
}

Ist ca 6x schneller.
Kurt

supertux

wie wäre es mit man: sprintf(3)?

ZuK

supertux schrieb:

wie wäre es mit man: sprintf(3)?

Wie geht das zb mit basis 12 ?
Kurt

template

Ja, die multiplikation ist wirklich ein gutes stück schneller aber leider immer noch um einiges langsamer als die kopier variante. es ergeben sich auch ein paar Probleme bei der Multiplikationsvariante...

printf ist ja allgemein mehr für flexibilität konstruiert als für performance. ich wüsste ehrlich gesagt auch nicht, wie ich damit ein beliebiges Zahlensystem als Basis verwenden lasse.

Ich hab jetzt nochmal ne Variante mit optimierung für die Dualexponential Systeme. Bei diesen wandlungen mache ich die MS implementation von itoa ziemlich nass;)

#define UINTTOSTRING_BUFSIZE				128

#define UINTTOSTRING_ERROR_BUFFERTOSMALL	-1
#define UINTTOSTRING_ERROR_SYSTEMOUTOFRANGE	-2

#define UINTTOSTRING_USEFASTMODE

const int UINTTOSTRING_DATATABLE[38][2] = {
	0, 0x00000000, 0, 0x00000000, 1, 0x00000001, 0, 0x00000000,
	2, 0x00000003, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000,
	3, 0x00000007, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 
	0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000,
	4, 0x0000000F, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 
	0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 
	0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000,
	0, 0x00000000, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000,
	5, 0x0000001F, 0, 0x00000000, 0, 0x00000000, 0, 0x00000000,
	0, 0x00000000, 0, 0x00000000
};

int UIntToString(unsigned int value, unsigned char system, char* poutput, size_t outputbufsize)
{
  int stringsize;
  int part;
  char pbuffer[UINTTOSTRING_BUFSIZE];
  char* ppointer = pbuffer + UINTTOSTRING_BUFSIZE - 1;

  *ppointer = '\0';

  if (system<2 || system>37) return UINTTOSTRING_ERROR_SYSTEMOUTOFRANGE;

#ifdef UINTTOSTRING_USEFASTMODE
  if (UINTTOSTRING_DATATABLE[system][0])
  {
    unsigned int bitcount = UINTTOSTRING_DATATABLE[system][0];
	unsigned int bitmask = UINTTOSTRING_DATATABLE[system][1];

	do {
		ppointer--;
		part = value & bitmask;
		if (part>9) *ppointer = part - 10 + 'A';
		else *ppointer = part + '0';
		value>>= bitcount;
	} while (value);
  }
  else
#endif
  {
	do {
		ppointer--;
		part = value % system;
		if (part>9) *ppointer = part - 10 + 'A';
		else *ppointer = part + '0';
		value/= system;
	} while (value);
  }

  stringsize = pbuffer + UINTTOSTRING_BUFSIZE - ppointer;
  if (outputbufsize < stringsize) return UINTTOSTRING_ERROR_BUFFERTOSMALL;

  strcpy(poutput, ppointer);
  return stringsize-1;
}

braucht für die Zahl 0xF3BBCA95 bei 1000 durchläufen:
itoa -> ca. 270µs
optimierte variante -> ca. 70µs

Allerdings scheint der Overhead bei mir größer zu sein. Bei kleineren Wandlungen schrumpft der Vorsprung (50/30 bei nur einer Stelle...)

Ich glaub ich hab da eh schon viel zu viel Zeit rein investiert. Manchmal verbeis ich mich etwas mit dieser blöden optimiererei...

ZuK

Wahrscheinlich würde es noch ganzes Stück schneller wenn du folgendes machst

const char * parttable = "0123456789ABCDEF";
    do {
        ppointer--;
        *ppointer = parttable[value % system];
        value/= system;
    } while (value);

Kurt

template

He, die Idee war nicht schlecht. Damit komme ich nun auch bei der langsamen Variante mit itoa schon fasst auf Augenhöhe;)

Ich hab auch nochmal geschaut, wieviel ich mir maximal sparen könnte, wenn ich den Puffer weg lasse. Das würde beim oben genannten Benchmark nur nochmal 20µs sparen (gut, bei der schnellen Variante wäre das doch schon ein netter Anteil.

life

ZuK schrieb:

Solange system nicht negativ und > 0 ist ist die Stellenanzahl des Ergebnisses in deinem Fall (für unsigned int ) immer
( value / system ) + 1
Kurt

nein aber $log_{system}(value)+1$

ZuK

Ich hab mich dann aber korrigiert. Bin dann auch auf deine Formel gekommen. Das berechnen von $log_{system}(value)$ mit den mitteln der c math-lib war mir dann aber doch zu mühsam. ( Ich weiss zwar dass es irgendwie geht, meine Mathematikkentnisse haben aber in den letzten 25 Jahren schwer nachgelassen )
Kurt

life

$log_{system}(value) = \frac{log(value)}{log(system)}$

der geschwindigkeitshit ist das natürlich auch nicht, aber wollte es nur mal angemerkt haben