Einen String umdrehen

Message
Author
Bender

Einen String umdrehen

#1 Post by Bender »

Hallo
kann mir jemand sagen, wie ich nen string komplett umdrehe, d.h. zeichen6 = zeichen1 zeichen5 = zeichen2 zeichen4 = zeichen 3 ... ?
da gibt es doch ne anweisung oder??
mfg
Bender

bakunin
Posts: 597
Joined: 16. Aug 1999 6:44
Location: Lorsch (Südhessen)
Contact:

Re: Einen String umdrehen

#2 Post by bakunin »

Hi!

Da gibt es keine vorgefertige Version für. Sowas wird ja auch nicht gerade häufig gebraucht. Aber sowas kann man ja leicht selbst schreiben. Hier mal eine GCC-Variante:

<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
#include <stdio.h>
#include <string.h>
#include <assert.h>

void
reverse_string (char *s)
{
void swap_chars (char *a, char *b)
{
char c = *a;

*a = *b;
*b = c;
}
char *end;

for (end = s + strlen (s) - 1; end > s; end--, s++)
swap_chars (s, end);
}

int
main (int argc, char *argv[<!--no--><!--no-->])
{
assert (argc == 2); /* Require 1 argument. */
reverse_string (argv[<!--no-->1<!--no-->]);
printf ("%s\<!--no-->n", argv[<!--no-->1<!--no-->]);

return 0;
}
</font><hr></pre></blockquote>

Cheers,
GNU/Wolfgang

Descartes

Re: Einen String umdrehen

#3 Post by Descartes »

@GNU/Wolfgang
> Hier mal eine GCC-Variante:
Was ist bei deiner Lösung denn GCC-spezifisch ? Sieht für mich nach ganz normalem C aus.
Zur Sicherheit habe ich den Quellcode mit aktiviertem "-Wall -pedantic" durch den GNU Compiler (und auf Windows zusätzlich durch den Microsoft- bzw. Borland-Compiler) gejagt.

Mit einem Template lässt sich swap_chars(int*, int*) noch kürzer umschreiben.
<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
/* Function : String umkehren
Based on : C Quellcode von GNU/Wolfgang

Tested
Platforms :
- GNU/Linux (i386)
GNU gcc version 2.95.3 20010315 (SuSE)

- Microsoft Windows (i386)
GNU gcc version 2.95.3-5 (cygwin special)
Microsoft 32-Bit C/C++-Compiler Version 12.00.8168 fuer x86
Borland C++ 5.5 for Win32
*/

#include <cassert>
#include <iostream>

// 1.) das ganze mal als inline Funktion (kann man schliesslich oefters verwenden)
// 2.) Parameterübergabe mit Referenzen statt Zeiger (echtes Call-by-Reference)

inline void swap_chars (char& a, char& b)
{
char help = a;
a = b;
b = help;
};

// 3.) eine allgemeinere Form von swap_chars(char&,char&)
// indem ein template<class T> benutzt wird

template<class T>
inline void swap (T& a, T& b)
{
T help = a;
a = b;
b = help;
};

void reverse_string (char* s)
{
char* end;
for (end = s + strlen (s) - 1; end > s; end--, s++)
{
// ohne templates:
// swap_chars(*s, *end);

// mit templates:
swap (*s, *end);
}
};

int main (int argc, char** argv)
{
assert (argc == 2); /* Require 1 argument. */

reverse_string (argv<font size="1">);

std::cout << argv<font size="1"> << std::endl;

return 0;
}
</font><hr></pre></blockquote>

sulu
Posts: 64
Joined: 29. Oct 2001 10:13
Location: Dornbirn

Re: Einen String umdrehen

#4 Post by sulu »

Hi Descartes.

Du rufst die Funktion swap() N-mal für einen String mit N Elementen auf.
Ist das wirklich performant?
Macht das nicht einen Mordslärm auf dem Stack ?
Das würde mich wirklich interessieren.
Gruss und Dank
Sulu

Descartes

Re: Einen String umdrehen

#5 Post by Descartes »

> Du rufst die Funktion swap() N-mal für einen String mit N Elementen auf.
Jo. Hat aber eigentlich ist es der Lösungsansatz von GNU/Wolfgang. Ich habe das ganze nur dann noch ein bisschen auf C++ getrimmt und aus dem Funktionsaufruf der echten Funktion swap_chars eine inline Funktion swap gemacht.

> Ist das wirklich performant?
Kommt darauf an, wie lange die Strings sind, die Bender reversieren möchte. IMHO dürfte die Laufzeit für "normale" Stringlängen bei aktuellen CPU-Taktraten im Gigahertz-Bereich vernachlässigbar sein.
Bender ging es darum, dass es überhaupt funktioniert. Jetzt kann man sich ja daran setzen und die Performance versuchen zu optimieren -- oder eine andere Strategie sich auszudenken wie man diese Funktion alternativ realisieren könnte.

> Macht das nicht einen Mordslärm auf dem Stack ?
IMHO nicht mehr, als wenn man swap() mit einem Macro realisiert hätte (ich lasse mich hierzu aber gerne belehren). Im Gegensatz zu einem Macro hast du aber ein Typprüfung zur Kompilierzeit.

inline Funktion

Ein Funktionsaufruf kostet Zeit. Der Zustand des Aufrufers muß gesichert und Parameter müssen eventuell kopiert werden. Das Programm springt an eine andere Stelle und nach Ende der Funktion wieder zurück zur Anweisung nach dem Aufruf. Der relative Verwaltungsaufwand fällt umso stärker ins Gewicht, je weniger Zeit die Abarbeitung des Funktionskörpers selbst verbraucht. Der absolute Aufwand macht sich mit steigender Anzahl der Aufrufe bemerkbar, zum Beispiel in Schleifen. Um diesen Aufwand zu vermeiden, können Funktionen als inline deklariert werden.
inline bewirkt, daß bei der Compilation der Aufruf durch den Funktionskörper ersetzt wird, also gar kein echter Funktionsaufruf erfolgt. Die Parameter werden entsprechend ersetzt, auch die Syntaxprüfung bleibt erhalten.

Descartes

Re: Einen String umdrehen

#6 Post by Descartes »

Aaarg. Ich sehe gerade dass das Board mir die main-Routine verändert hat...Warum werden im CODE-Abschnitt auch die UltraBoard-Tags erkannt ??

<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
// ... code wie oben ...

int main (int argc, char** argv)
{
assert (argc == 2); /* Require 1 argument. */

reverse_string (argv[<!--no-->1<!--no-->]);

std::cout << argv[<!--no-->1<!--no-->] << std::endl;

return 0;
}
</font><hr></pre></blockquote>

bakunin
Posts: 597
Joined: 16. Aug 1999 6:44
Location: Lorsch (Südhessen)
Contact:

Re: Einen String umdrehen

#7 Post by bakunin »

Hi!

>Was ist bei deiner Lösung denn GCC-spezifisch ?

Die geschachtelte Funktion ist eine GCC-Erweiterung.

> Zur Sicherheit habe ich den Quellcode mit aktiviertem "-Wall -pedantic" durch den GNU Compiler (und auf Windows zusätzlich durch den Microsoft- bzw. Borland-Compiler) gejagt.

Deinen oder meinen Code? Du hast die Schachtelung ja entfernt. GNU C++ kann übrigens keine geschachtelten Funktionen. (Sofern sich das mit GCC 3 nicht geändert hat.)

> Mit einem Template lässt sich swap_chars(int*, int*) noch kürzer umschreiben.

Ich will aber kein C++ verwenden. <img src="http://www.pl-forum.de/UltraBoard/Images/Wilk.gif" border="0" align="middle"> Ich habe absichtlich eine C-Variante geschrieben. Ich mag C++ nämlich nicht.

Cheers,
GNU/Wolfgang

sulu
Posts: 64
Joined: 29. Oct 2001 10:13
Location: Dornbirn

Re: Einen String umdrehen

#8 Post by sulu »

@Descartes .

Hi !

Ein Macro ist nur ein Platzhalter für Source-Code. Wenn Du swap(a,b) als Macro realisierst dann erstzt der Precompiler den Macroaufruf druch den im Macro befindlichen Code. Macros dienen eher der Lesbarkeit, sind also keine Funktionen per se. Damit fällt auch die ganze Stack-Aufbereitung/Abfrage weg.
=> Macros sind schneller.

@Wolfgang

Mag kein C++. Irgendwann werden wir wohl auch dieses Land erkunden müssen. Der steinige Weg vom Lendenschurz zum Grobleinenhemd. <img src="http://www.pl-forum.de/UltraBoard/Images/Wilk.gif" border="0" align="middle">

Gruss
Sulu

trinity
Posts: 821
Joined: 12. Oct 2001 10:04

Re: Einen String umdrehen

#9 Post by trinity »

@Sulu
Wieso sollten Makros schneller sein inline-code?

Finde es auch immer wieder interessant, wie andere Leute Programmieren.
Last edited by trinity on 29. Jan 2002 8:53, edited 1 time in total.
"Korrekt, Freundlich, Kostenfrei", wähle genau zwei. (Lutz Donnerhacke in dcsf)

sulu
Posts: 64
Joined: 29. Oct 2001 10:13
Location: Dornbirn

Re: Einen String umdrehen

#10 Post by sulu »

Ups.
Hi Lutz !
Hab mich nicht genau ausgedrückt.
Ich meine im Vergleich von Macros zu konventionellen Funktionsaufrufen, die einen eigenen Datenbereich haben und die ganze Schnittstellenaktivität haben.
Gruss
Sulu

PS: Wenn ich Performance-Sorgen habe dann schau ich schon mal das Assembler-Listing an. Ich bin kein Assembler-Crack aber man kann die Auswirkungen der Programmierungsweise auf den Maschinencode studieren.

arni

Re: Einen String umdrehen

#11 Post by arni »

So gehts auch etwas kompakter ;)

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


void reverse_string (char* s)
{
char c;
char* end = s+strlen(s)-1;

while (s < end && (c = *s))
*s++ = *end, *end-- = c;
}


int
main (int argc, char *argv[])
{
assert (argc == 2); /* Require 1 argument. */
reverse_string (argv<font size="1">);

printf ("%s
", argv<font size="1">);

return 0;
}

Descartes

Re: Einen String umdrehen

#12 Post by Descartes »

Das Board hat dein \<!--no-->n und [<!--no-->1<!--no-->] verschluckt...

<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
#include <iostream>
#include <cassert>

void reverse_string( char* str );

int main( int argc, char** argv )
{
assert( argc==2 ); /* Require 1 argument. */
reverse_string( argv[<!--no-->1<!--no-->] );
std::cout << argv[<!--no-->1<!--no-->] << std::endl;
return 0;
}

void reverse_string( char* str )
{
char temp;
char* end = str+strlen(str)-1;

while( str < end )
{
temp = *str;
*(str++) = *end;
*(end--) = temp;
}
}
</font><hr></pre></blockquote>

arni

Re: Einen String umdrehen

#13 Post by arni »

@Descartes
Dein C++ Code ist aber um einiges langsamer ;)
<blockquote><pre><font size="1" face="">code:</font><hr><font face="Courier New" size="2">
8x
time ./main "abcdefghijklmopqrstuvwxyz"

c++: 0.005s (schankend zwischen 0.003-0.007)
c: 0.002s (stabil)
</font><hr></pre></blockquote>

<a href="mailto:arni@arnisoft.de">arni</a><!--url-->

Descartes

Re: Einen String umdrehen

#14 Post by Descartes »

$ gcc --version
2.95.3
$ g++ --version
2.95.3
$ gcc -O2 -march=pentium -mcpu=pentium -funroll-loops -o main_c main.c
$ g++ -O2 -march=pentium -mcpu=pentium -funroll-loops -o main_cpp main.cpp

8x
time ./main_cpp "abcdefghijklmopqrstuvwxyz"
time ./main_c "abcdefghijklmopqrstuvwxyz"

c++: 0.016s (schwankend +/- 0.001)
c: 0.009s (schwankend +/- 0.001)

Testsystem: Pentium 166 MMX

Descartes

Re: Einen String umdrehen

#15 Post by Descartes »

time Commando 10x ausgeführt

c++ (ganz oben mit inline und template) : 0.318s ... 0.327s (schwankend)
c++ (c++ version des c-proggies) : 0.316s ... 0.347s (schwankend)
c: 0.312s ... 0.331s (schwankend)

Testsystem: Pentium 166 MMX

Verwendeter Aufruf:

time ./main_c "<hier kommt ein 100KB Text>" >/dev/null

Als Text wurde <a href="http://www.gnu.org/events/rms-nyu-2001-transcript.txt" target="_blank"><!--auto-->http://www.gnu.org/events/rms-nyu-2001- ... <!--auto--> verwendet. Die im Text vorkommenden doppelten Hochkommas wurden ersetzt zu einfachen Hochkommas.

Post Reply