Flaws in algorithm and algorithm performance

Question

char *stringmult(int n)
{
    char *x = "hello ";
    for (int i=0; i<n; ++i)
    {
     char *y = new char[strlen(x) * 2];
     strcpy(y,x);
     strcat(y,x);
     delete[] x;
     x=y;
    }
    return x;
}

I'm trying to figure out what the flaws of this segment is. For one, it deletes x and then tries to copy it's values over to y. Another is that y is twice the size of x and that y never gets deleted. Is there anything that I'm missing? And also, I need to figure out how to get algorithm performance. If you've got a quick link where you learned how, I'd appreciate it.

Answer 1

y needs one more byte than strlen(x) * 2 to make space for the terminating nul character -- just for starters.

Anyway, as you're returning a newed memory area, it's up to the caller to delete it (eek).

What you're missing, it seems to me, is std::string...!-)

As for performance, copying N characters with strcpy is O(N); concatenating N1 characters to a char array with a previous strlen of N2 is O(N1+N2) (std::string is faster as it keeps the length of the string in an O(1)-accessible attribute!-). So just sum N+N**2 for N up to whatever your limit of interest is (you can ignore the N+ part if all you want is a big-O estimate since it's clearly going to drop away for larger and larger values of N!-).

Answer 2

For starters delete[] x; operates for the first time round the loop on some static memory. Not good.

It looks like an attempt to return a buffer containing 2^n copies of the string "hello ". So the fastest way to do that would be to figure out the number of copies, then allocate a big enough buffer for the whole result, then fill it with the content and return it.

void repeat_string(const std::string &str, int count, std::vector<char> &result)
{
    result.resize(str.size() * count);
    for (int n = 0; n < count; n++)
        str.copy(&result[n * s.size()], s.size());
}

void foo(int power, std::vector<char> &result)
{
    repeat_string("hello ", 1 << (power + 1), result); 
}

Answer 3

1. no need to call strlen() in a loop - only call it once;
2. when new is called no space is requested for the null-character - will cause undefined behaviour;
3. should use strcpy instead of strcat - you already know where to copy the second string and findig the end of string by strcat requires extra computation;
4. delete[] is used on a statically allocated string literal - will cause undefined behaviour;
5. memory is constantly reallocated although you know the result length well in advance - memory reallocation is quite expensive

You should instead compute the result length at once and allocate memory at once and pass the char* as an in-parameter:

char* stringMult(const char* what, int n)
{
     const size_t sourceLen = strlen( what );
     int i;
     size_t resultLen = sourceLen;
     // this computation can be done more cleverly and faster
     for( i = 0; i < n; i++ ) {
        resultLen *= 2;
     }
     const int numberOfCopies = resultLen / sourceLen;
     char* result = new char[resultLen + 1];
     char* whereToWrite = result;
     for( i = 0; i < numberOfCopies; i++ ) {
        strcpy( whereToWrite, what );
        whereToWrite += sourceLen;
     }
     return result;
}

Certain parts of my implementation can be optimized but still it is much better and (I hope) contains no undefined-behaviour class errors.

Answer 4

char * stringmult (int n)
{
    int i;
    size_t m;
    for (i = 0, m = 1; i < n; ++i; m *= 2);
    char * source = "hello ";
    int source_len = strlen(source);
    char * target = malloc(source_len*m+1) * sizeof(char));
    char * tmp = target;
    for (i = 0; i < m; ++i) {
        strcpy(tmp, source);
        tmp += source_len;
    }
    *tmp = '\0';
    return target;
}

Here a better version in plain C. Most of the drawbacks of your code have been eliminated, i.e. deleting a non-allocated pointer, too many uses of strlen and new. Nonetheless, my version may imply the same memory leak as your version, as the caller is responsible to free the string afterwards.

Edit: corrected my code, thanks to sharptooth.

Answer 5

char* string_mult(int n)

{

const char* x = "hello ";

char* y;

    int i;



for (i = 0; i < n; i++)

{

 if ( i == 0)

 {

  y = (char*) malloc(strlen(x)*sizeof(char));

  strcpy(y, x);

 }

 else

 {

  y = (char*)realloc(y, strlen(x)*(i+1));

  strcat(y, x);

 }

}

return y;

}

Answer 6

Nobody is going to point out that "y" is in fact being deleted?

Not even one reference to Schlmeiel the Painter?

But the first thing I'd do with this algorithm is:

int l = strlen(x);
int log2l = 0;
int log2n = 0;
int ncopy = n;
while (log2l++, l >>= 1);
while (log2n++, n >>= 1);
if (log2l+log2n >= 8*(sizeof(void*)-1)) {
    cout << "don't even bother trying, you'll run out of virtual memory first";
}