Re: [c-prog] Recursion - Reverse String Example

[[EMAIL PROTECTED]]

> Mickey Mathieson a écrit :
> ...
> 
> The second if test is not needed MY MISTAKE!!!
> Not paying complete attention.
> 
> If you think you can come up with a BETTER RECUSIVE
> SOLUTION lets see it! Otherwise your blowing wind.
> 
> 

Ok let's try a complet test suite....
(I have already post a probably better - faster - recursive
solution )

// BEGIN CODE
#include <time.h>
#include <sys/time.h>

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

char chaine[] = "eorvneoiruvnieabuvraiebrvlaebvlae\
iebrvlaebvlaebrvlaebrvlajehbreorvneoiruvnieabuvraie\
iebrvlaebvlaebrvlaebrvlajehbreorvneoiruvnieabuvraie\
iebrvlaebvlaebrvlaebrvlajehbreorvneoiruvnieabuvraie";

// your iterative reverse
char *RevStr(char *str )
{
  int len = strlen(str);
  for (int i = 0; i < len/2; i++)
  {
    char C = str[i];
    str[i] = str[len-i-1];
    str[len-i-1] = C;
  }
  return(str);
}

// mine iterative reverse (no strlen cost)
char* reverse( char* str )
{
  char* begin = str, *end = str;
  while( *end ) ++end; // go to the end
  while( end > begin )
  { // swap begin and end until they join
    char c = *--end;
    *end = *begin;
    *begin++ = c;
  }
  return str;
}

// your Recursive Reverse String
char *RevStr(int count, char *str)
{
  if (!count) return(str);
  char Value = str[count-1];
  RevStr(count-1, str);
  str[strlen(str) - count] = Value;
  return(str);
}

// mine recursive reverse between
// [begin,end] ( div by 2 numbers and depth calls )
char* reverse_r( char* begin, char* end )
{
  if ( end <= begin ) return begin;
  char c = *end; *end = *begin; *begin = c; //swap
  reverse_r( begin+1, end-1 );
  return begin;
}

// A simple scope-chrono
struct Chrono {
  timeval tv_begin;
  Chrono() { gettimeofday( &tv_begin, 0 ); }
  ~Chrono()
  {
    timeval tv_end;
    gettimeofday( &tv_end, 0 );

    time_t      elapsedSecond  = tv_end.tv_sec -
tv_begin.tv_sec;
    useconds_t elapseduSecond = tv_end.tv_usec -
tv_begin.tv_usec;   
    if ( elapseduSecond < 0 ) {
      elapseduSecond += 1000000;
      --elapsedSecond;
    }
    cout << " Duration = " << elapsedSecond << "," 
         << setfill( '0' ) << setw( 6 ) << elapseduSecond <<
endl;
  }
};

// some launchers
void test( char* (*fct)(char* ), int num ) {
  Chrono c;

  for ( int i = 0; i < num; ++i )
    fct( chaine );
}

void test_r1( int num ) {
  Chrono c;

  size_t size = strlen( chaine );
  for ( int i = 0; i < num; ++i )
    RevStr( size, chaine );
}

void test_r2( int num ) {
  Chrono c;

  size_t size = strlen( chaine );
  for ( int i = 0; i < num; ++i )
    reverse_r( chaine, chaine + size - 1 );
}

// -------------------
int main( int argc, char*argv[])
{
  int numLoop = (argc>1?atoi(argv[1]):10000);

  // tests
  cout << RevStr( strlen( chaine ), chaine ) << endl;
  cout << reverse_r( chaine, &chaine[0] + strlen(chaine)-1 )
<< endl;
  cout << RevStr( chaine ) << endl;
  cout << reverse( chaine ) << endl;

  test( RevStr, numLoop );      // your iterative
  test( reverse, numLoop );     // mine iterative
  test_r1( numLoop );           // your recursive
  test_r2( numLoop );           // mine recursive
}


// END CODE

Using 50000 iterations on a relative short string

first result in second at your (iterative only) advantage on
hp-ux using aCC
 Duration = 0,051188
 Duration = 0,059516
 Duration = 2,055472
 Duration = 1,4294049812

second result in second at mine advantage on linux using g++ 3.4

 Duration = 0,037910
 Duration = 0,013299
 Duration = 3,811505
 Duration = 0,023039

under an unix flavor you can make your own tests (or port
the chrono
under windows)

Regards,
David


------------------------ ALICE C'EST ENCORE MIEUX AVEC CANAL+ LE BOUQUET ! 
---------------
Découvrez vite l'offre exclusive ALICEBOX et CANAL+ LE BOUQUET, en cliquant ici 
http://alicebox.fr
Soumis à conditions.