---

Hej alle

Jeg er (omsider) gået i gang med at skrive mit
usenetstatistikprogram fra skrab (!).

Hvis man er meget pedantisk, koster det så tid at caste til
unsigned?

Her er den aktuelle stump kode (se linje 4):

char *name, *pos, *ps;

1 pos=strchr(name,'@');
2 if (pos) *pos='©'; // Pas på signed.
3 if (pos && strchr(name,' ')) {
4 while (pos>name && (unsigned) *pos>' ') --pos;
5 ps=strchr(pos+1,' ');
6 if (ps) name=ps+1;
7 else *pos=0;
8 }

I øvrigt havde jeg noget værre hyr med en test hvor jeg havde
prøvet at angive startstrengen til et indlæg sådan:

NEWMSG[]="\0x0\0x19\0x0\0x0\0x2";

Når jeg samlede op med fgetc() og sammenlignede med NEWMSG, gav
det kun falsk. Hvis jeg derimod sammenlignede med 0, 25, 0, 0 og
2 direkte, virkede det. Nu definerer jeg så NEWMSG0, NEWMSG1 osv.
i stedet, og det virker, men det er ikke tilfredsstillende.

PS: Startstrengen er nok noget specielt Forte Agent-noget.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:

> Hej alle
>
>
> Hvis man er meget pedantisk, koster det så tid at caste til
> unsigned?
>
> Her er den aktuelle stump kode (se linje 4):
>
> char *name, *pos, *ps;
>
> 1 pos=strchr(name,'@');
> 2 if (pos) *pos='©'; // Pas på signed.
> 3 if (pos && strchr(name,' ')) {
> 4 while (pos>name && (unsigned) *pos>' ') --pos;
> 5 ps=strchr(pos+1,' ');
> 6 if (ps) name=ps+1;
> 7 else *pos=0;
> 8 }

Hvis man er meget pedantisk giver det ikke nogen mening at teste om
*pos er større end ' ', man kan ikke vide om ' ' er større eller
mindre end 'a' eller 'Z'.
Man kan heller ikke vide om en char er signed eller unsigned.
Det ville måske være lettere hvis du altid brugte unsigned char.
Man kan ikke vide om det tager tid at lave en cast, C-standarden
specificerer ikke performance.

> I øvrigt havde jeg noget værre hyr med en test hvor jeg havde
> prøvet at angive startstrengen til et indlæg sådan:
>
> NEWMSG[]="\0x0\0x19\0x0\0x0\0x2";
>
> Når jeg samlede op med fgetc() og sammenlignede med NEWMSG, gav
> det kun falsk. Hvis jeg derimod sammenlignede med 0, 25, 0, 0 og
> 2 direkte, virkede det. Nu definerer jeg så NEWMSG0, NEWMSG1 osv.
> i stedet, og det virker, men det er ikke tilfredsstillende.
>
Brugte du strcmp()? I så fald kan det ikke undre, den ser NEWMSG som
en tom streng, den kan ikke vide om der kommer noget efter det
første \0.
Du kunne måske bruge memcmp(NEWMSG, whateverinput, sizeof(NEWMSG))

/b

---

Bertel Brander skrev:

>Hvis man er meget pedantisk giver det ikke nogen mening at teste om
>*pos er større end ' ', man kan ikke vide om ' ' er større eller
>mindre end 'a' eller 'Z'.

Okay, men det gør nu ikke så meget her fordi systemet (Windows)
er givet på forhånd, der er kun én mulig bruger (mig), og det
skal næppe porteres. Men jeg er glad for oplysningen.

>Man kan ikke vide om det tager tid at lave en cast, C-standarden
>specificerer ikke performance.

Næ, men man kan jo godt afgøre at "a+=10" er hurtigere end "for
(n=0; n<10; ++n) ++a;" selv om standarden ikke forlanger det. Det
var noget i den retning jeg tænkte på, men vi snakker måske om så
små tidsrum ved cast at det er umuligt at vide?

>> NEWMSG[]="\0x0\0x19\0x0\0x0\0x2";

>Brugte du strcmp()?

Niks.

>Du kunne måske bruge memcmp(NEWMSG, whateverinput, sizeof(NEWMSG))

Tak, det vil jeg kikke på.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>
>>Man kan ikke vide om det tager tid at lave en cast, C-standarden
>>specificerer ikke performance.
>
>
> Næ, men man kan jo godt afgøre at "a+=10" er hurtigere end "for
> (n=0; n<10; ++n) ++a;" selv om standarden ikke forlanger det. Det
> var noget i den retning jeg tænkte på, men vi snakker måske om så
> små tidsrum ved cast at det er umuligt at vide?

Man kan ikke vide om a += 10 er hurtigere end for-løkken, hvis
der ikke er sideeffekter (f.ex a eller n er volatile, #defined
til at være funktioner eller lign.) har kompileren lov til at
springe loopen over og lave præsis den samme kode.

Tilbage til det oprindelige spørgsmål:
Der er sansynligvis ingen performance forskel på koden med og uden cast.

/b

---

> men vi snakker måske om så
> små tidsrum ved cast at det er umuligt at vide?

Du kan da bare se på assembler koden.

Så kan du da hurtigt afgøre om det giver en ændring at cast'e (jeg tvivler
på det).

---

Klaus Petersen skrev:

>Du kan da bare se på assembler koden.

Jeg har ikke beskæftiget med ret meget med assembler siden jeg
skrottede min 8080'er.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Den Tue, 05 Aug 2003 00:32:58 +0200 skrev Bertel Lund Hansen:
>>Man kan ikke vide om det tager tid at lave en cast, C-standarden
>>specificerer ikke performance.
>
>Næ, men man kan jo godt afgøre at "a+=10" er hurtigere end "for
>(n=0; n<10; ++n) ++a;" selv om standarden ikke forlanger det. Det
>var noget i den retning jeg tænkte på, men vi snakker måske om så
>små tidsrum ved cast at det er umuligt at vide?

Ofte vil en cast kunne gøres helt uden at det giver ekstra kode,
beregningen laves bare præcis som om variablen var signed i stedet
for unsigned (eller omvendt). For CPU'en er der jo bare tale om et
antal bytes.

Men det er ikke nødvendigvis altid det kan lade sig gøre på denne
måde, og det er faktisk kun dem der har lavet compileren der ved
hvornår.

Derfor er det umuligt at sige noget om.

Mvh
Kent
--
"Intelligence is the ability to avoid doing work, yet get the work done"
- Linus Torvalds

---

Kent Friis skrev:

[Om cast og tidsforbrug]

>Derfor er det umuligt at sige noget om.

Tak til dig og de andre for oplysningerne. Jeg blev klogere.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.
http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

---

Bertel Lund Hansen wrote:
> Jeg er (omsider) gået i gang med at skrive mit
> usenetstatistikprogram fra skrab (!).

Lyder godt.

> Hvis man er meget pedantisk, koster det så tid at caste til
> unsigned?

Selve castet tager ikke tid, for det eneste det gør, er
at give oversætteren information om, hvilken type det
castede skal opfattes som. Castet påvirker derfor,
hvilken kode der spyttes til at behandle den castede
værdi.

Eksempelvis spyttes der forskellig maksinkode ud for

(unsigned)(-1) + 1 ; plus_af_unsigned_og_unsigned(-1, 1)
og
-1 + 1 ; plus_af_signed_og_unsigned(-1, 1)

Om plus_af_unsigned_og_unsigned og plus_af_signed_og_unsigned
er lige hurtige er ikke sådan at sige.

Altså, selve castet tager ikke tid, men castet kan påvirke
den frembragte kode i nærheden - med en dertil hørende
hastigsforskel.

--
Jens Axel Søgaard

---

> Eksempelvis spyttes der forskellig maksinkode ud for
>
> (unsigned)(-1) + 1 ; plus_af_unsigned_og_unsigned(-1, 1)
> og
> -1 + 1 ; plus_af_signed_og_unsigned(-1, 1)

Jeg har aldrig hørt om en processor som har forskellige plus-operatorer til
signed og unsigned.
Det smukke ved den repræsentation af negative tal som man bruger i 8080 og
efterfølgende processorer er at plus og minus fungerer ens uanset om
værdierne er signed eller unsigned. Hastigheden er også den samme, da
processoren ikke aner hvad værdierne er for nogle.
Men der eksisterer muligvis andre processorer som fungerer anderledes.

Niels Dybdahl

---

Niels Dybdahl wrote:
>>Eksempelvis spyttes der forskellig maksinkode ud for
>>
>> (unsigned)(-1) + 1 ; plus_af_unsigned_og_unsigned(-1, 1)
>>og
>> -1 + 1 ; plus_af_signed_og_unsigned(-1, 1)
>
>
> Jeg har aldrig hørt om en processor som har forskellige plus-operatorer til
> signed og unsigned.

Indrømmet uheldigt eksempel.

For den sags skyld er det ikke engang sikkert, at der bliver spyttet en
ADD-instruktion ud, det kunne også bruge en INC-instruction.

> Det smukke ved den repræsentation af negative tal som man bruger i 8080 og
> efterfølgende processorer er at plus og minus fungerer ens uanset om
> værdierne er signed eller unsigned. Hastigheden er også den samme, da
> processoren ikke aner hvad værdierne er for nogle.
> Men der eksisterer muligvis andre processorer som fungerer anderledes.

Det vil jeg tro. Tokomplementrepræsentation er smart, men jeg det
foresvæver mig, at nogle (ældre?) maskiner brugte andre
repræsentationer (binary-coded-decimal), fordi de skulle bruges
til økomomiske beregninger. Men om der er forskel på de
to plus-operationer med den repræsentation ved jeg ikke.

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message
news:3f302abf$0$97263$edfadb0f@dread12.news.tele.dk...
[klip]
> Det vil jeg tro. Tokomplementrepræsentation er smart, men jeg det
> foresvæver mig, at nogle (ældre?) maskiner brugte andre
> repræsentationer (binary-coded-decimal), fordi de skulle bruges
> til økomomiske beregninger. Men om der er forskel på de
> to plus-operationer med den repræsentation ved jeg ikke.

Hvis det nu var bitvis rotation mod højre (>>) i stedet for addition
ville der være forskel alt efter om typen var signed eller ej. Hvis
vi var på et 32-bit system ville fx
(int)0x80000000 >> 4 == 0xF8000000, mens
(unsigned)0x80000000 >> 4 == 0x08000000.

Anders

---

Anders Borum wrote:

> Hvis det nu var bitvis rotation mod højre (>>) i stedet for addition
> ville der være forskel alt efter om typen var signed eller ej. Hvis
> vi var på et 32-bit system ville fx
> (int)0x80000000 >> 4 == 0xF8000000, mens
> (unsigned)0x80000000 >> 4 == 0x08000000.

Der var et ordenligt eksempel. Tak.

--
Jens Axel Søgaard

---

"Bertel Lund Hansen" <nospamfor@lundhansen.dk> wrote in message
news:0bktivgu78m999tvidj43j236p6u28cn56@news.stofanet.dk...
> Hej alle
>
> Jeg er (omsider) gået i gang med at skrive mit
> usenetstatistikprogram fra skrab (!).
>
> Hvis man er meget pedantisk, koster det så tid at caste til
> unsigned?
>
> Her er den aktuelle stump kode (se linje 4):
>
> char *name, *pos, *ps;
>
> 1 pos=strchr(name,'@');
> 2 if (pos) *pos='©'; // Pas på signed.
> 3 if (pos && strchr(name,' ')) {
> 4 while (pos>name && (unsigned) *pos>' ') --pos;
> 5 ps=strchr(pos+1,' ');
> 6 if (ps) name=ps+1;
> 7 else *pos=0;
> 8 }
>
> I øvrigt havde jeg noget værre hyr med en test hvor jeg havde
> prøvet at angive startstrengen til et indlæg sådan:
>
> NEWMSG[]="\0x0\0x19\0x0\0x0\0x2";
>
> Når jeg samlede op med fgetc() og sammenlignede med NEWMSG, gav
> det kun falsk. Hvis jeg derimod sammenlignede med 0, 25, 0, 0 og
> 2 direkte, virkede det. Nu definerer jeg så NEWMSG0, NEWMSG1 osv.
> i stedet, og det virker, men det er ikke tilfredsstillende.
>
> PS: Startstrengen er nok noget specielt Forte Agent-noget.

Med respekt,
bliver denne stump kode kaldet mange gange?

For mig at se trænger den nemlig mere til at blive gjort letlæselig end at
blive optimeret på. Det er svært intuitivt at se name, pos og ps' specifikke
opgaver. Og med mindre der er tale om kode der skal kaldes ekstremt mange
gange vil optimering sandsynligvis gøre koden endnu mere besværlig at
arbejde med til ingen verdens nytte.

Søren

---

Søren Johansen skrev:

>Med respekt,
>bliver denne stump kode kaldet mange gange?

Ja, 29'854 gange.

>For mig at se trænger den nemlig mere til at blive gjort letlæselig end at
>blive optimeret på.

Jeg skriver et program der skal behandle 90+ MB data ad gangen
med optælling til et hav af arrays/structs og endelig produktion
af overskuelige dataudskrifter i HTML-format.

>Det er svært intuitivt at se name, pos og ps' specifikke opgaver.

De er 'løbere' ved en strenghåndtering.

>Og med mindre der er tale om kode der skal kaldes ekstremt mange
>gange vil optimering sandsynligvis gøre koden endnu mere besværlig at
>arbejde med til ingen verdens nytte.

Koden har sin endelige form, men jeg ville lige vide hvor meget
betydning en typecast har. Hvis du vil have lidt mere at gyse
over, er hele den aktuelle funktion her. Den skal

1. standardisere en id_streng (nametrim)
2. sikre at @ ændres til ©
3. uddrage navn - subsidiært mail hvis ikke navnet findes.
4. tjekke om brugeren allerede er registreret.
5. allokere og gemme brugeren hvis han er ny.

void registrer_skribent (char *id_streng) {
char buffer[NAMELEN], *pos, *ps, *name;
int nr;
if (strlen(id_streng)>NAMELEN) id_streng[NAMELEN-1]=0;
nametrim(id_streng);
name=buffer;
strcpy(name,id_streng);
pos=strchr(name,'@');
if (pos) *pos='©'; // Pas på signed.
if (pos && strchr(name,' ')) {
while (pos>name && (unsigned) *pos>' ') --pos;
ps=strchr(pos+1,' ');
if (ps) name=ps+1;
else *pos=0;
}
for (nr=0; nr<skribenter; ++nr)
if (strcmp(id_streng,skribent[nr]->id)==0) break;
if (nr<skribenter)
++skribent[nr]->messages;
else {
if (strlen(id_streng)>NAME_LIMIT) id_streng[NAME_LIMIT-1]=0;
skribent[nr]=malloc(sizeof(skribenttype));
skribent[nr]->id=malloc(strlen(id_streng)+1);
skribent[nr]->name=malloc(strlen(name)+1);
strcpy(skribent[nr]->id,id_streng);
strcpy(skribent[nr]->name,name);
skribent[nr]->messages=1;
++skribenter;
}
skribentnummer=nr;
}

Du er velkommen til at komme med forslag. Jeg regner ikke med at
implementere dem, men jeg vil meget gerne lære noget.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.
http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

---

---

Jens Christian Larsen skrev:

>som 'nr' og 'ps', der ingen betydning bærer i sig selv. Du tilgår flere
>globale variable, som gør funtionen svær at forstå i sig selv, du benytter
>malloc uden at teste om den får allokeret hukommelsen, så du har en
>potentiel skrivning til en NULL pointer.

Jeg ved det godt, men programmet er et redskabsprogram til mig
selv, og jeg har 'hukommelse nok'. Frigørelsen sker først ved
nedlukningen, men det er ingen fejl, for oplysningerne skal
bruges helt til programmet er færdigt.

I øvrigt ville jeg blive nødt til at lukke ned med en fatal fejl
hvis der vitterligt manglede hukommelse, for jeg kan ikke bruge
en statistik over mangelfulde data til noget.

Vil I (på den baggrund) betragte det som en fejl at jeg ikke
tester ved malloc()? Eller måske blot en uvane jeg bør lægge af
af hensyn til mere professionel produktion?

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Den Wed, 06 Aug 2003 12:40:09 +0200 skrev Bertel Lund Hansen:
>Jens Christian Larsen skrev:
>
>Vil I (på den baggrund) betragte det som en fejl at jeg ikke
>tester ved malloc()? Eller måske blot en uvane jeg bør lægge af
>af hensyn til mere professionel produktion?

Det sidste. Hvis man lige fra starten gør det til en vane altid at
checke for malloc()==0, buffer overflows osv, glemmer man det ikke
den dag man sidder og laver en eller anden netværks-daemon med
mulighed for at own'e hele maskinen.

MVh
Kent
--
Journalist: En der har forstand på at skrive artikler, men typisk
ikke på det artiklerne handler om.

---

Bertel Lund Hansen <nospamfor@lundhansen.dk> wrote:
> Vil I (på den baggrund) betragte det som en fejl at jeg ikke
> tester ved malloc()? Eller måske blot en uvane jeg bør lægge af
> af hensyn til mere professionel produktion?

Soeg efter malloc i dette afsnit af David Wheeler's secure programming:

<URL:http://www.dwheeler.com/secure-programs/Secure-Programs-HOWTO/dangers-c.html>

--
I prefer the dark of the night, after midnight and before four-thirty,
when it's more bare, more hollow. http://a.mongers.org

---

> pos=strchr(name,'@');
> if (pos) *pos='©'; // Pas på signed.
> if (pos && strchr(name,' ')) {
> while (pos>name && (unsigned) *pos>' ') --pos;
> ps=strchr(pos+1,' ');
> if (ps) name=ps+1;
> else *pos=0;
> }

Så vidt jeg kan se bliver name helt tom, hvis den kun indeholdt en
emailadresse fra starten.
Du kunne istedet slutte med:

if (ps) name=ps+1;
else if (pos>name) *pos=0;

Niels Dybdahl

---

Niels Dybdahl skrev:

>> if (pos && strchr(name,' ')) {

>Så vidt jeg kan se bliver name helt tom, hvis den kun indeholdt en
>emailadresse fra starten.

Tilstedeværelsen af et mellemrum (efter trimning) sikrer at der
også er et navn.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.
http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

---

On Tue, 05 Aug 2003 16:38:50 +0200, Bertel Lund Hansen
<nospamfor@lundhansen.dk> wrote:

Hov, der er mulighed for buffer overflow.
Forestil dig NAMELEN 3 og id_streng "abc".

> char buffer[NAMELEN]

Skal være NAMELEN+1.

> if (strlen(id_streng)>NAMELEN) id_streng[NAMELEN-1]=0;
> :
> name=buffer;
> strcpy(name,id_streng);


/Peder Skyt

---

Peder Skyt, Z=nospam skrev:

>Hov, der er mulighed for buffer overflow.

Ja og nej. Id_streng er alias for en buffer på 10000 tegn, og
NAME-begrænsningerne er kun lavet af hensyn til udskriften. Men
du har ret i at logikken halter lidt.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.
http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

---

Hej

Jens Christian Larsen <madcow@control.auc.dk> writes:
[snip]
> Du skal selvfølgelig også huske at free dit allokerede hukommelse (i
> den rigtige rækkefølge) et sted i din kode, men det går jeg ud fra der
> er der styr over.
[snap]

Hmhm. Hvad er det her med "den rigtige rækkefølge" nu for noget? Det
har jeg aldrig hørt om før? Er det vitalt? Og er det kun ved brug af
free/malloc, eller også ved f.eks. C++'s new/delete?

--
Ulrik Jensen
ulrik@qcom.dk - http://www.minefilm.tk
"It's only a movie, and, after all, we're all grossly overpaid."

---

Ulrik Jensen skrev:

>Hmhm. Hvad er det her med "den rigtige rækkefølge" nu for noget?

Der er ingen rigtig rækkefølge - ud over at det ikke må ske før
data kan undværes.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

---

Jens Christian Larsen skrev:

>Der er en rigtig rækkefølge og en forkert rækkefølge i dit tilfælde, hvis
>jeg ikke tager meget fejl. Du skal frigive name og id strengene inden du
>frigiver hukommelsen til den struktur (skribenttype), der indeholder
>pointerne til dem. Ellers risikerer du at frigive tilfældige addresser.

Åh ja, det er da også rigtigt.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Hej

Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:
> Der er ingen rigtig rækkefølge - ud over at det ikke må ske før
> data kan undværes.

Arh. Se det var jeg så godt klar over :)

--
Ulrik Jensen
ulrik@qcom.dk - http://www.minefilm.tk
"It's only a movie, and, after all, we're all grossly overpaid."

---

"Bertel" == Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:

> Hej alle
> Jeg er (omsider) gået i gang med at skrive mit
> usenetstatistikprogram fra skrab (!).

> Hvis man er meget pedantisk, koster det så tid at caste til
> unsigned?

Det skulle gerne ske på compiletime.

> Her er den aktuelle stump kode (se linje 4):

> char *name, *pos, *ps;

> 1 pos=strchr(name,'@');
> 2 if (pos) *pos='©'; // Pas på signed.
> 3 if (pos && strchr(name,' ')) {
> 4 while (pos>name && (unsigned) *pos>' ') --pos;
> 5 ps=strchr(pos+1,' ');
> 6 if (ps) name=ps+1;
> 7 else *pos=0;
> 8 }

Hvad er det iøvrigt lige du ønsker at opnå med ovenstående kodestump?

Så vidt jeg kan se, så vil du have pointeren til det første element i
en ' '-separeret streng, der indeholder @, og derudover erstatte den
første forekomst af @ med ©?

Hvis det er det eneste, kan du gøre det meget pænere (og hurtigere)
ved at undgå den O(n^2) tidskompleksitet som strchr() giver med
følgende (utestede) kode:

int index, start = 0, snabel = 0;

for (index = 0; index++; '\0' != streng[index]) {

/* Marker den potentielle strengstart */
if ((' ' == streng[index]) &&( 0 == snabel)) {
start = index + 1;
}

/* Ingen @ -> har et element med @ */
if (('@' == streng[index]) {
streng[index] = '©';
snabel = index;
}

/* Terminer strengen, medmindre den ender på '@' (Nu '©') */
if ((' ' == streng[index]) &&( 0 != snabel) && (index > snabel+1)) {
streng[index] = '\0';
return &streng[start];
}
}

Der skal files lidt på grænseværditilfældene, men hvis jeg ellers har
fået rigtigt fat på hvad du vil opnå, er ovenstående i bedste fald
garanteret dobbelt så hurtigt som din algoritme. Denne ser nemlig kun
en gang på hvert tegn.

--
/Wegge <http://outside.bakkelygaard.dk/~wegge/>

---

Anders Wegge Jakobsen skrev:

> Hvad er det iøvrigt lige du ønsker at opnå med ovenstående kodestump?

Undersøge en streng som indeholder navn og mailadresse. Det er
ikke givet at begge elementerne er med, og det vides ikke i
hvilken rækkefølge de kommer. Navnet skal isoleres, men hvis det
ikke findes, skal mailadressen træde i stedet. Og @ skal
udskiftes med noget andet så resultatet kan lægges frem på en
hjemmeside. Det vides heller ikke om der kun forekommer ét
mellemrum ad gangen.

Jeg har postet hele funktionen i et andet svar - og nametrim()
gennemløber også hele strengen for at det ikke skal være løgn.
Det blev for kompakt og komplekst at lave det hele i ét hug.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.
http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

---

---

"Jens" == Jens Christian Larsen <madcow@control.auc.dk> writes:

> On 5 Aug 2003, Anders Wegge Jakobsen wrote:
>> ved at undgå den O(n^2) tidskompleksitet som strchr() giver med

> Hvilken implementation af strchr() har tidskompleksitet på O(n^2)? Jeg
> mener langt de fleste implementeringer har O(n), uden dog at være sikker.
> Det er i hvert fald det eneste der giver mening for mig.

strchr() er ganske rigtigt O(n), men kaldes inde fra en O(n) løkke,
hvorved det samlede resultat bliver O(n^2).

--
/Wegge <http://outside.bakkelygaard.dk/~wegge/>

---

---

"Jens Christian Larsen" <madcow@control.auc.dk> skrev:
> On 5 Aug 2003, Anders Wegge Jakobsen wrote:
>
> > strchr() er ganske rigtigt O(n), men kaldes inde fra en O(n) løkke,
> > hvorved det samlede resultat bliver O(n^2).
>
> Men Bertel kalder jo ikke strchr() for hver char i sin id_streng. Han
> bruger den et konstant antal gange uafhængigt af længden af strengen
> hvilket giver tidskompleksiteten O(n) som jeg læser koden. Hvordan kommer
> du frem til at tidskompleksiteten af strchr() kaldene i hans funktion
> bliver proportional med kvadratet af strengens længde?

Min navnebroder glemmer at spørge sig selv hvad "n" står for, og
ganger æbler med appelsiner. Hvis n står for det gennemsnitlige antal
tegn i en id_streng, og m for antallet af kald til funktionen, så er
tidsforbruget O(mn). Hvis b står for antallet af tegn i alle
id_strengene tilsammen, så er det samlede strchr tidsforbrug O(b),
hvilket slet ikke er så slemt, ja i sammenhængen faktisk ligegyldigt.

Det er punkt 4 på Bertels liste (tjekke om brugeren allerede er
registreret) der står for tidsforbruget, da det bruger lineær
søgning. Lad d være antallet af distinkte brugere, så er det samlede
tidsforbrug her O(dbn). Før der er skiftet til en mere effektiv
datastruktur (fx søgetræ eller hashtabel) er det overhovedet ikke værd
at optimere på punkterne 1-3 og 5.

mvh. Anders

---

> Det er punkt 4 på Bertels liste (tjekke om brugeren allerede er
> registreret) der står for tidsforbruget, da det bruger lineær
> søgning. Lad d være antallet af distinkte brugere, så er det samlede
> tidsforbrug her O(dbn). Før der er skiftet til en mere effektiv
> datastruktur (fx søgetræ eller hashtabel) er det overhovedet ikke værd
> at optimere på punkterne 1-3 og 5.

Og det, at programmet bliver færdigt med lineær søgning, antyder at der
overhovedet ikke er grund til at optimere de andre punkter.

Niels Dybdahl

---

"Jens" == Jens Christian Larsen <madcow@control.auc.dk> writes:

> On 5 Aug 2003, Anders Wegge Jakobsen wrote:
>> strchr() er ganske rigtigt O(n), men kaldes inde fra en O(n) løkke,
>> hvorved det samlede resultat bliver O(n^2).

> Men Bertel kalder jo ikke strchr() for hver char i sin id_streng. Han
> bruger den et konstant antal gange uafhængigt af længden af strengen
> hvilket giver tidskompleksiteten O(n) som jeg læser koden. Hvordan kommer
> du frem til at tidskompleksiteten af strchr() kaldene i hans funktion
> bliver proportional med kvadratet af strengens længde?

Det gør jeg ikke længere, nu hvor jeg er blevet vågen. Jeg må have
siddet og transponeret if og while, mens jeg læste Bertels oprindelige
indlæg.

--
/Wegge <http://outside.bakkelygaard.dk/~wegge/>

---

> strchr() er ganske rigtigt O(n), men kaldes inde fra en O(n) løkke,
> hvorved det samlede resultat bliver O(n^2).

Jeg tror du skal kigge på Bertels kode én gang til. Løkken stopper før
strchr.

Niels Dybdahl

---

Bertel Lund Hansen wrote:

> Jeg er (omsider) gået i gang med at skrive mit usenetstatistikprogram
> fra skrab (!).

Jeg har nok misset en tråd et eller andet sted, men hvad skal det
program egentligt lave?

--
PeKaJe

When the bosses talk about improving productivity, they are never
talking about themselves.

---

Peter Jensen skrev:

>Jeg har nok misset en tråd et eller andet sted, men hvad skal det
>program egentligt lave?

Det har jeg ikke sagt før. Det skal lave statistik over indlæg og
skribenter på usenet. Det (meget) foreløbige resultat kan ses
her:

http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

og de gamle statistikker - lavet i Pascal der løb panden mod DOS'
hukommelsesmur - kan se her:

http://lundhansen.dk/bertel/statistik/statistik.htm

De viser hvordan det færdige resultat skal se ud.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.

---

Bertel Lund Hansen wrote:

>> Jeg har nok misset en tråd et eller andet sted, men hvad skal det
>> program egentligt lave?
>
> Det har jeg ikke sagt før. Det skal lave statistik over indlæg og
> skribenter på usenet. Det (meget) foreløbige resultat kan ses her:
>
> http://lundhansen.dk/bertel/statistik/usenetstatistik.htm

OK, det var ikke helt det samme som jeg havde tænkt på, men det ligner
da lidt.

> og de gamle statistikker - lavet i Pascal der løb panden mod DOS'
> hukommelsesmur - kan se her:

Hukommelsesmur? Er det da ikke en opgave der kan splittes *meget* op?

> http://lundhansen.dk/bertel/statistik/statistik.htm
>
> De viser hvordan det færdige resultat skal se ud.

Hvis du vil have lidt inspiration, så kig lidt på Turquoise SuperStat:
http://www.softwolves.pp.se/sw/software/turquoise

Det er Open Source, så man kan om ikke andet lære lidt af kildekoden.

--
PeKaJe

If it is a Miracle, any sort of evidence will answer, but if it is a
Fact, proof is necessary. -- Samuel Clemens

---

Peter Jensen skrev:

>Hukommelsesmur? Er det da ikke en opgave der kan splittes *meget* op?

Det kunne den måske godt. I den sidste version gemte jeg optalte
data i 5 temporære filer som blev læst bagefter én ad gangen i én
fælles hentestruktur. De helt færdige data blev skrevet ud til en
tekstfil som et andet program læste og konverterede til HTML.

Det var en revision af en version der havde det hele i
hukommelsen. Størrelsen af arrays blev bestemt af nogle
konstanter som jeg fedtede på plads ved hjælp af trial an error.

Hvor meget energi ville du have brugt på at revidere den kode da
det tredje gang viste sig at programmet ikke længere kunne klare
mængden af data fra usenet?

Jeg prøvede en gang med FreePascal som skulle kunne læse TP-kode
og som ikke har hukommelsesbegrænsning. Det imponerede mig at
programmet oversatte koden uden vrøvl - men imponeringen dalede
da det ikke virkede.

--
Bertel
Min usenetstatistik er på vej tilbage - lidt begrænset i starten.
http://lundhansen.dk/bertel/statistik/usenetstatistik.htm