Determining the length of an array for memory efficiency

Question

Write a function in C language that:

• Takes as its only parameter a sentence stored in a string (e.g., "This is a short sentence.").
• Returns a string consisting of the number of characters in each word (including punctuation), with spaces separating the numbers. (e.g., "4 2 1 5 9").

I wrote the following program:

 int main()    
    {  
            char* output;  
            char *input = "My name is Pranay Godha";  
            output = numChar(input);  
            printf("output : %s",output);  
            getch();  
            return 0;  
    }  


char* numChar(char* str)   
{   
        int len = strlen(str);  
    char* output = (char*)malloc(sizeof(char)*len);   
    char* out = output;  
    int count = 0;  

    while(*str != '\0')  
    {
        if(*str != ' ' )
        {
            count++;
        }
        else
        {

            *output = count+'0';
            output++;
            *output = ' ';
            output++;
            count = 0;

         }
         str++;
   }  
   *output = count+'0';  
   output++;  
   *output = '\0';  
   return out;  
}  

I was just wondering that I am allocating len amount of memory for output string which I feel is more than I should have allocated hence there is some wasting of memory. Can you please tell me what can I do to make it more memory efficient?

Answer 1

I see lots of little bugs. If I were your instructor, I'd grade your solution at "C-". Here's some hints on how to turn it into "A+".

 char* output = (char*)malloc(sizeof(char)*len); 

Two main issues with the above line. For starters, you are forgetting to "free" the memory you allocate. But that's easily forgiven.

Actual real bug. If your string was only 1 character long (e.g. "x"), you would only allocate one byte. But you would likely need to copy two bytes into the string buffer. a '1' followed by a null terminating '\0'. The last byte gets copied into invalid memory. :(

Another bug:

*output = count+'0'; 

What happens when "count" is larger than 9? If "count" was 10, then *output gets assigned a colon, not "10".

Start by writing a function that just counts the number of words in a string. Assign the result of this function to a variable call num_of_words.

Since you could very well have words longer than 9 characters, so some words will have two or more digits for output. And you need to account for the "space" between each number. And don't forget the trailing "null" byte.

If you think about the case in which a 1-byte unsigned integer can have at most 3 chars in a string representation ('0'..'255') not including the null char or negative numbers, then sizeof(int)*3 is a reasonable estimate of the maximum string length for an integer representation (not including a null char). As such, the amount of memory you need to alloc is:

 num_of_words = countWords(str);
 num_of_spaces = (num_of_words > 0) ? (num_of_words - 1) : 0;
 output = malloc(num_of_spaces + sizeof(int)*3*num_of_words + 1); // +1 for null char

So that's a pretty decent memory allocation estimate, but it will definitely allocate enough memory in all scenarios.

I think you have a few other bugs in your program. For starters, if there are multiple spaces between each word e.g.

"my     gosh"

I would expect your program to print "2 4". But your code prints something else. Likely other bugs exist if there are leading or trailing spaces in your string. And the memory allocation estimate doesn't account for the extra garbage chars you are inserting in those cases.

Update:

Given that you have persevered and attempted to make a better solution in your answer below, I'm going to give you a hint. I have written a function that PRINTs the length of all words in a string. It doesn't actually allocate a string. It just prints it - as if someone had called "printf" on the string that your function is to return. Your job is to extrapolate how this function works - and then modify it to return a new string (that contains the integer lengths of all the words) instead of just having it print. I would suggest you modify the main loop in this function to keep a running total of the word count. Then allocate a buffer of size = (word_count * 4 *sizeof(int) + 1). Then loop through the input string again to append the length of each word into the buffer you allocated. Good luck.

void PrintLengthOfWordsInString(const char* str)
{
    if ((str == NULL) || (*str == '\0'))
    {
        return;
    }

    while (*str)
    {
        int count = 0;

        // consume leading white space
        while ((*str) && (*str == ' '))
        {
            str++;
        }

        // count the number of consecutive non-space chars
        while ((*str) && (*str != ' '))
        {
            count++;
            str++;
        }

        if (count > 0)
        {
            printf("%d ", count);
        }
    }
    printf("\n");
}

Answer 2

As long as none of the words in the sentence are longer than 9 characters, the length of your output array needs only to be the number of words in the sentence, multiplied by 2 (to account for the spaces), plus an extra one for the null terminator.

So for the string

My name is Pranay Godha

...you need only an array of length 11.

If any of the words are ten characters or more, you'll need to calculate how many extra char your array will need by determining the length of the numeric required. (e.g. a word of length 10 characters clearly requires two char to store the number 10.)

The real question is, is all of this worth it? Unless you're specifically required (homework?) to use the minimal space required in your output array, I'd be minded to allocate a suitably large array and perform some bounds checking when writing to it.

Answer 3

The answer is: it depends. There are trade-offs.
Yes, it's possible to write some extra code that, before performing this action, counts the number of words in the original string and then allocates the new string based on the number of words rather than the number of characters.
But is it worth it? The extra code would make your program longer. That is, you would have more binary code, taking up more memory, which may be more than you gain. In addition, it will take more time to run.

By the way, you have a memory leak in your program, which is more of a problem.