Dalsi zahada v C -> Prevod long int na string

[Milan B.]

On 24.7.2011 22:38, Jan Waclawek wrote:
> To je sice pekne, ale povodna staznost bola na pomalost. Optimalizacia uz potom nie je zalezitost par minut a je strojovo zavisla.

Aha, takze riesenim je asi vyplakavat po roznych forach.

Dakujem za poucenie.

A kde beriete istotu, ze tieto funkcie - ktore ste mimochodom odporucali 
aj VY SAM - budu v knizniciach implementovane inac? Namatkovo som pozrel 
implementaciu vo vasom oblubenom SDCC a tam je implementovana IMO este 
horsie.

Mimochodom, povodna staznost nebola na rychlost itoa, ale na rychlost 
printf (tuto cast ste rafinovane odmazali). Tazatel sa iba domnieval ze 
algoritmy s delenim budu pomale. Sancu vyskusat itoa a spol. nermal, 
lebo jeho kniznice ich nemaju. Tak som mu nejaku implementaciu ponukol. 
Co vas na tom tak sere?

Ta implementacia samozrejme nie ie najrychlejsia. Na uvod sa da 
odstranit obracanie retazca s tym, ze sa bude zapisovat od konca (ale 
vysledok nebuda zacinat na zaciatku bufra) - a hned je to o par taktov 
rychlejsie.

Alebo mozme uplne odstranit delenie a nahradit ho odpocitanim po radoch 
(obmedzme sa len na desiatkovu sustavu a 16-bitovy integer):

char *utoa(char *s, unsigned n)
{
int cnt, i, j=0;
static t[]={10000u,1000u,100u,10u};

for (i=0; i<4;i++) {
cnt=0;
while(n>=t[i]) {
cnt++;
n-=t[i];
}
if (cnt || j ) {
s[j++]=cnt+'0';
}
}
s[j++]=n+'0';
s[j]=0;
return s;
}

Ak je praca s indexovanymi polami na danej platforme prilis draha, tak 
je mozne cyklus for nahradit styrmi po sebe iducimi cyklami while s 
konstantami (samozrejme, za cenu vyssej spotreby programovej pamate):

char *utoa(char *s, unsigned n)
{

int cnt, i, j=0;

cnt=0;
while(n>=10000u) {
cnt++;
n-=10000u;
}
if (cnt || j) {
s[j++]=cnt+'0';
}
cnt=0;
while(n>=1000u) {
cnt++;
n-=1000u;
}
if (cnt || j) {
s[j++]=cnt+'0';
}
cnt=0;
while(n>=100u) {
cnt++;
n-=100u;
}
if (cnt || j) {
s[j++]=cnt+'0';
}
cnt=0;
while(n>=10u) {
cnt++;
n-=10u;
}
if (cnt || j) {
s[j++]=cnt+'0';
}
s[j++]=n+'0';
s[j]=0;
return s;
}


Neviem, ktore riesenie bude na danej platforme najrychlejsie, zavisi to 
hlavne od rychlosti implementacie delenia. Ale to sa da zistit velmi 
jednoducho - vyskusat.

Len pre zaujimavost, na mojej testovacej x86_64 virtualke (ktora ma, 
samozrejme, HW delenie) trvalo 1000 prevodov celeho rozsahu -32767 az 
32767 (t.j. 65534000 prevodov):

verzia s delenim (a HW delenim): ~2.6 sekundy
verzia s odpocitavanim po radoch s tabulkou: ~4 sekundy
verzia s odpocitavanim po radoch 4 cykly po sebe: ~2.1 sekundy ---> VITAZ

更好吗？

-m-


> wek
>
>
> On Sun, 24 Jul 2011 17:21:27 +0200
> "Milan B."<milan na bastl.sk>  wrote:
>
>> On 24.7.2011 11:37, Michal Gregor wrote:
>>> Tak jsem program upravil na funkce itoa() a utoa().
>>> Kompilator ale hlasi chybu. Tyto funkce nezna.
>> Netreba z toho robit tragediu. Su to jednoduchucke funkcie a a daju sa
>> spichnut za par minut.
>>>> Jan Waclawek konfera na efton.sk
>>>> Úterý Červen 21 14:17:51 CEST 2011
>>>> Neviem ako pri Vasom prekladaci, ale obvykle maju kniznice>k C
>>>> (najma na
>>>> jednocipy) na tento ucel funkciu ltoa() (a>potom aj rozne ito(), ftoa()
>>>> apod.), presne kvoli tomu ze>xxprintf() je nafuknuty a pomaly mamut.
>>>> Ak nie, tak asembler, alebo trpiet pripadnou pomalostou>delenia.
>>>> wek
>>>
>>> ----- Original Message ---------------
>>>> Jak prevadite long int na string? Nasel jsem priklady s delenim, ale
>>>> asi to
>>>> bude taky pekne pomale.
>>>> (Jeste mam havarijni plan zmenit vystupni format na hexa cisla.)
>>>>
> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz
> Hw-list na list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list