[C] woord omdraaien?

[BezurK]

Ik ben een beetje aan het aankloten (alweeeeer) met C en hetgene wat ik nog nooit goed gesnapt heb zijn de strings. Stel, ik heb een programma dat een woord aan neemt en dat omgedraait output, de code om het woord om te draaien leek mij vrij simpel namelijk:

code:

char word[50];
char helper[50];
int wordsize=strlen(word);
for(i=0; i<wordsize; i++)
  helper[i]=word[wordsize-i];

Waarbij je ervanuit moet gaan dat word een woord bevat natuurlijk. Hierna zou dus in helper het woord in word omgedraaid moeten staan, maar helper blijft leeg! Wat doe ik fout?

[yrew]

Je gaat er van uit dat er iets in word staat, maar is dit ook zo. Stop er wat debug regeltjes tussen en je merkt het vanzelf. Waarmee vul je word trouwens ?

[drZymo]

Een string is een array. En die beginnen in C altijd bij 0. wordsize-i bij i=0 zou element nummer wordsize van word moeten pakken. Maar die is er niet aangezien je laatste element van je woord wordsize-1 is.

het zou dus moeten worden:

code:

helper[i]=word[wordsize-i-1];

Klein voorbeeldje:

word : 'b', 'l', 'a', 'a', 't', '\0' een string eindigt altijd op \0

helper zou bij jou worden: '\0', 't', 'a', 'a', 'l', 'b'
en aangezien \0 het einde van een string is, is helper leeg.

sim-pel

[drZymo]

gebruik anders de functie strrev( char *string ) deze doet het automagisch

[johnwoo]

Kijk eens naar de std functie strrev

[edit] Tss zymo, ikke jou vertellen dat strrev bestaat en jij dan snel voor mij posten he

[drZymo]

Op woensdag 13 februari 2002 15:43 schreef johnwoo het volgende:
Kijk eens naar de std functie strrev

gamma

[BezurK]

Op woensdag 13 februari 2002 15:39 schreef yrew het volgende:
Je gaat er van uit dat er iets in word staat, maar is dit ook zo. Stop er wat debug regeltjes tussen en je merkt het vanzelf. Waarmee vul je word trouwens ?

Heb ik ook gedaan hoor die heb ik alleen niet hierbij gezet voor de overzichtelijkheid, ik verkrijg word trouwens gewoon met argv[1] en ik weet dus altijd zeker dat er iets in word staat

Klein voorbeeldje:
word : 'b', 'l', 'a', 'a', 't', '\0' een string eindigt altijd op \0
helper zou bij jou worden: '\0', 't', 'a', 'a', 'l', 'b'
en aangezien \0 het einde van een string is, is helper leeg.

Ahaaaa, thx!!!
Ik wist wel dat een string eindigde op NULL (\0) maar ik had er niet bij nagedacht dat het dan bij het omdraaien het eerste teken zou worden, stom!
Enne, ik ben dit aan't maken om natuurlijk het werken met strings een beetje onder de knie te krijgen en dan is het gebruiken van standaard functies natuurlijk niet zo goed

[eek]

hmm.. mischien beetje laat maar kwam dit nog tegen uit
oude code, werkte volgens mij wel...

code:

void reverse(char *str) {
    char *x,s,e;
    int i,len;
    
    len = strlen(str);
    x = str;
    
    for ( i=0;i<((int)(len/2));i++) {
        s = (char)*(x+i);
        e = (char)*(x+(len-i-1));
        memcpy(x+i,&e,1);
        memcpy(x+(len-i-1,&s,1);
    }
}

[drZymo]

Op woensdag 13 februari 2002 16:06 schreef eek het volgende:
hmm.. mischien beetje laat maar kwam dit nog tegen uit
oude code, werkte volgens mij wel...

code:

void reverse(char *str) {
    char *x,s,e;
    int i,len;
    
    len = strlen(str);
    x = str;
    
    for ( i=0;i<((int)(len/2));i++) {
        s = (char)*(x+i);
        e = (char)*(x+(len-i-1));
        memcpy(x+i,&e,1);
        memcpy(x+(len-i-1,&s,1);
    }
}

Werkt mischien ook wel

Alleen is memcpy voor een element van 1 char een beetje overkill

een standaard assignment is efficienter

[Feyd-Rautha]

code:

  helper[i]=word[wordsize-i];

volgens mij moet je gewoon de functie strcpy gebruiken om karakters te kopieren...

[stylee]

Avalanche-: volgens mij moet je gewoon de functie strcpy gebruiken om karakters te kopieren...

Voor het kopiëren van een rij karakters (een C-string, met als kenmerk een aflsuitende '\0') gebruik je strcpy. Voor het simpelweg toewijzen van een karakter aan een positie in een array kan je eenvoudigweg een assignment gebruiken.

[Anoniem: 1918]

Op woensdag 13 februari 2002 16:09 schreef drZymo het volgende:

[enorm inefficiente code]

Werkt mischien ook wel

Alleen is memcpy voor een element van 1 char een beetje overkill

een standaard assignment is efficienter

Oei, waarom zo moeilijk doen, het is ook mogelijk op de volgende manier, veel simpeler en gelijk een stukje duidelijker:

code:

void reverse(char* txt) {
    char* a = txt + strlen(txt) - 1;
    char* b = txt;
    while(a > b) {
        *a ^= *b;
        *b ^= *a;
        *a-- ^= *b++;
    }
}

Even een beetje uitleg, die ^= staat voor een assignment met XOR. dus a ^= b is a = a XOR b.
Door de XOR's op deze manier te gebruiken kun je daarmee de elementen "swappen" zonder extra storage te gebruiken.

Bij de laatste regel staat er nog een increment en decrement operator bij. Omdat dit postfix operators zijn (ze staan erachter, ++a is prefix), worden ze uitgevoerd nadat de XOR en de toewijzing gedaan zijn.

Het effect is dus dat steeds 2 elementen geswapt worden, beginnend met het 1e en laatste element. Daarna wordt er naar het midden toe gelopen en worden ook steeds weer 2 elementen geswapt, totdat er bij het midden aangekomen is.

[Soultaker]

Luite's code is qua methode wel interessant, maar ik ben bang dat een implementatie met een tijdelijke variabele toch vele male efficiënter is; die ene byte geheugen kan je echt wel missen, waar nog eens bij komt dat een compiler 'm optimaliseert naar een register (ik heb het geprobeerd).

[Anoniem: 29256]

En als we toch lekker over miniscule pseudo-optimalisaties gaan lullen: de variabele b in luite's code is overbodig; je kan gewoon de parameter variabele txt gebruiken.

[drZymo]

Op donderdag 14 februari 2002 00:24 schreef Soultaker het volgende:
Luite's code is qua methode wel interessant, maar ik ben bang dat een implementatie met een tijdelijke variabele toch vele male efficiënter is; die ene byte geheugen kan je echt wel missen, waar nog eens bij komt dat een compiler 'm optimaliseert naar een register (ik heb het geprobeerd).

OK

Een XOR operatie op 2 registers is sneller als een MOV operatie op een byte. Een van redenen waarom er altijd XOR ax, ax staat in plaats van MOV ax, 0.

(Correct me if i'm wrong)

[Anoniem: 1918]

Op donderdag 14 februari 2002 00:24 schreef Soultaker het volgende:
Luite's code is qua methode wel interessant, maar ik ben bang dat een implementatie met een tijdelijke variabele toch vele male efficiënter is; die ene byte geheugen kan je echt wel missen, waar nog eens bij komt dat een compiler 'm optimaliseert naar een register (ik heb het geprobeerd).

Vele malen efficienter is overdreven. Die XOR operaties kunnen immers ook steeds op 2 registers werken. Maar de methode met een temp var is ongeveer 30% sneller hier. Ik vond het echter leuk om eens een swap zonder temp vars te laten zien

voor de volledigheid:

de code wordt dan:

code:

void reverse2(char* txt) {
    char* a = txt + strlen(txt) - 1;
    char* b = txt;  
    char t;
    while(a > b) {
        t = *b;
        *b++ = *a;
        *a-- = t;
    }
}

Op donderdag 14 februari 2002 01:04 schreef Sneech het volgende:
En als we toch lekker over miniscule pseudo-optimalisaties gaan lullen: de variabele b in luite's code is overbodig; je kan gewoon de parameter variabele txt gebruiken.

Dit heb ik expres gedaan, de 2 letters zijn duidelijker zo, en op deze manier heb je het originele argument nog, wat nuttig kan zijn als je dat bijvoorbeeld nog wilt returnen. In dit geval zal het ook geen winst opleveren, aangezien de compiler in de huidige code die variabele zo kan weg optimaliseren.

Op die manier kun je dan handiger met het resultaat van de reverse functie werken. bv:

cout << reverse(blaat);

[Sponz]

Hier een variant met recursie:

code:

#include <stdio.h>
#include <string.h>

char *reversit(char *a, char *b);

int main()
{
 char test[] = "U vraagt, wij draaien.";

 printf("%s\n",test);
 printf("%s\n",reversit(test,test+strlen(test)-1));
 return 0;
}


char *reversit(char *a, char *b)
{
 char ch;
 if(a < b) {
  ch = *a;
  *a = *b;
  *b = ch;
  reversit(a+1,b-1);
 }
 return a;
}

[Anoniem: 1918]

Op donderdag 14 februari 2002 11:17 schreef Sponz het volgende:
Hier een variant met recursie:
[code met recursie]

Leuk als voorbeeld, maar in de praktijk totaal niet nuttig. Normaalgesproken gebruik je alleen maar recursie als dat veel makkelijker is dan iteratie. In dit geval is het iteratief zelfs makkelijker.

[Anoniem: 36226]

Nu even de correcte code (die ook werkt met een lege string)

code:

void reverse(char* a) {
  char* b = a;

  if(!*a) 
    while(!a[1]) 
    a++;
  while(a > b) {
    *a ^= *b;
    *b ^= *a;
    *a-- ^= *b++;
  }
}

Zo zie je maar weer, pointers zijn erg gevaarlijk... (gebruik java/c# of zo, en als het echt moet, gebruik dan Cyclone)

^{[edit]stukje toegevoegd[/edit]}

[Anoniem: 1918]

Op donderdag 14 februari 2002 13:45 schreef Doekman het volgende:
Nu even de correcte code (die ook werkt met een lege string)

code:

void reverse(char* a) {
  char* b = a;

  if(!*a) 
    while(!a[1]) 
    a++;
  while(a > b) {
    *a ^= *b;
    *b ^= *a;
    *a-- ^= *b++;
  }
}

Nu mag je mij uitleggen waar het dan fout gaat in mijn code als je een lege string hebt....

(hou er rekening mee: een lege string is '\0' op het eerste karakter, dus geen NULL pointer, daar houd ik inderdaad geen rekening mee, maar dat hoeft ook niet in dit soort functies)

Bij een lege string geeft strlen(txt) dus 0 terug

Mijn code was als volgt...

code:

    char* a = txt + strlen(txt) - 1;
    char* b = txt;

Bij de lege string wordt a dan gelijk aan b + 0 - 1, dus b-1.

Aangekomen bij de volgende loop:

code:

  while(a > b) {
    *a ^= *b;
    *b ^= *a;
    *a-- ^= *b++;
  }

Blijkt a direct al kleiner te zijn dan b, dus wordt de hele loop niet uitgevoerd. Niks aan de hand dus.

Zo zie je maar weer, pointers zijn erg gevaarlijk...

(gebruik java/c# of zo, en als het echt moet, gebruik dan Cyclone)

Je kunt ook gewoon C++ met STL gebruiken, dan heb je ook al een stuk minder vaak te maken met dit soort pointer dingen, weliswaar niet met checked pointers, maar het wordt meer verborgen gehouden voor de gebruiker. Alternatief si dan een taal met range checking, elke test kost echter performance, dus je zult waarschijnlijk nog steeds in sommige gevallen terug moeten vallen op unchecked pointers.

edit:

JAAAAAAAAAAAAAAAAAA!!!!!!!!!!!!!!!!!!!!!!
100e post

[Anoniem: 36226]

Op donderdag 14 februari 2002 18:09 schreef luite het vorige:

Aan de ene kant heb je gelijk, aan de andere kant heb ik gelijk. Maar de vraag is:wat is correcte code

Jou code gaat "toevallig" goed bij een lege string (anders had je commentaar moeten toevoegen, om aan te geven dat je een trucje gebruikt had).
Aan het algoritme is dat niet af te zien.

Ik vind dat correcte code niet alleen correct moet werken, maar ook dat het elegant is. Maw: of mijn oplossing, of jou oplossing met een stukje commentaar... (no offence, just an opinion )

[Anoniem: 13700]

Op donderdag 14 februari 2002 18:19 schreef Doekman het volgende:
Jou code gaat "toevallig" goed bij een lege string (anders had je commentaar moeten toevoegen, om aan te geven dat je een trucje gebruikt had).

Bondage & discipline alert. Beweer je echt dat code pas correct is als ze van commentaar voorzien is?

Aan het algoritme is dat niet af te zien.

Dat krijg je als je nooit met pointers werkt, dit is "standard practice".

Ik vind dat correcte code niet alleen correct moet werken, maar ook dat het elegant is. Maw: of mijn oplossing, of jou oplossing met een stukje commentaar... (no offence, just an opinion )

Onder "elegant" wordt normaal verstaan dat je code een efficiente oplossing implementeert, zonder overbodige instructies ed. Overbodige if-statements maken je code dus niet eleganter, en met commentaar heeft het in mijn optiek helemaal niets van doen.

[Anoniem: 1918]

Op donderdag 14 februari 2002 18:19 schreef Doekman het volgende:

[..]

Aan de ene kant heb je gelijk, aan de andere kant heb ik gelijk. Maar de vraag is:wat is correcte code

Jou code gaat "toevallig" goed bij een lege string (anders had je commentaar moeten toevoegen, om aan te geven dat je een trucje gebruikt had).

Trucje? vind ik niet. Het is hier gewoon duidelijk dat hij alleen gaat omdraaien als a > b, dus bij minstens 2 karakters die omgedraait moeten worden. Als a == b (string lengte 1 of als hij in het midden is aangekomen bij een oneven string lengte) dan hoeft hij niets om te draaien, string lengte nul dus al helemaal niet (a < b)

Aan het algoritme is dat niet af te zien.

Ik vind dat je dan niet goed gekeken hebt

Ik vind dat correcte code niet alleen correct moet werken, maar ook dat het elegant is. Maw: of mijn oplossing, of jou oplossing met een stukje commentaar... (no offence, just an opinion )

Dan klopt jouw code ook niet...

Jouw code:

code:

void reverse(char* a) {
  char* b = a;
  if(!*a) 
    while(!a[1]) 
    a++;
  while(a > b) {
    *a ^= *b;
    *b ^= *a;
    *a-- ^= *b++;
  }
}

Het aangepaste deel van jouw code doet vrijwel hetzelfde als:
a = txt + strlen(txt) - 1;

strlen zal namelijk ook gaan zoeken naar een \0 in de string met een vergelijkbare while loop. Bij jou pakt hij dan het karakter dat ervoor staat. Bij mij dus ook met txt + strlen(txt) - 1. Het is gegeven dat strlen bij een lege string 0 teruggeeft. Het enige echt verschil bij een lege string is dat bij jou a = b, en bij mij a = b - 1, wat verder dus geen invloed heeft op de while loop.

Om dit te zien vereist het echter ook goed kijken in de code om te beredeneren wat a wordt als de string lengte 0 is. Bij mij evenveel, dus zie ik niet in waarom jouw code beter zou zijn dan de mijne. De mijne vind ik zelfs duidelijker door het gebruik van een standaard functie met een voorspelbaar resultaat, in plaats van een loop die goed bekeken moet worden voordat het resultaat ervan duidelijk is.

[Soultaker]

Op donderdag 14 februari 2002 01:19 schreef drZymo het volgende:
Een XOR operatie op 2 registers is sneller als een MOV operatie op een byte. Een van redenen waarom er altijd XOR ax, ax staat in plaats van MOV ax, 0.

(Correct me if i'm wrong)

Je vraagt er om =)

"mov ax, 0" is innefficient omdat deze 0 in de opcode gecodeerd wordt, waardoor deze nodeloos lang is (en dus meer verwerking vergt). Deze opcode moet nu uit het geheugen gehaald worden in plaats van uit een ander register en het 'normale' geheugen is significant trager dan het registergeheugen.

We hadden het nu over het swappen van variabelen. Deze moeten SOWIESO in registers worden ingeladen, voordat er xor bewerkingen op los gelaten kunnen worden. De winst van de xor operatie is dus verdwenen aangezien je toch mov commando's zal moeten gebruiken om ze om te wisselen. De meest efficiente methode is natuurlijk gewoon:
mov ax, a
mov a, b
mov b, ax
Maar het is maar de vraag of de compiler dat snapt.

[Anoniem: 36226]

Op donderdag 14 februari 2002 18:34 schreef luite het volgende:

[..]

Trucje? vind ik niet.

Sorry hoor, maar bij een string van lengte 0 wijst je a-pointer naar een stukje geheugen wat niet van jou is! OK, je doet er niets mee, maar ik vind dat niet elegant!

Maar ik ben het met je eens dat je het correcte code kunt noemen (het kan niets verkeerd doen).

_{Alleen ik noem het dus geen correcte code}