1
\$\begingroup\$

I have a task to write the function: int read_palindrome(); // input comes from stdin

which will read one line from standard input and returns 1 if the line is a palindrome and 0 otherwise. A line is terminated by the newline character (’\n’) and the does not include the newline.

There are requirements to be met:

There is no assumption about the length of the input. You are also not allowed to read the input twice, e.g. read the input, forget you read the input but remember the length, read the input again. which results in the input being read twice.

You are also not allowed to create a very large buffer to store the input reasoning that the input line might be expected to be smaller than a very large buffer. The reason for this restriction is that we will consider the memory usage of the program.

The task is to come out with a correct program with the best CPU time and memory usage.

I have attempted my code below. May I know if there is anything I could improve on here to optimise for correctness, CPU and memory?

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

int read_palindrome();
int check_palindrome2(char *, int);

int main() 
{
    if (read_palindrome()) printf("input is a palindrome");
    else printf("input is not a palindrome");
    return 0;
}



int read_palindrome() {
    unsigned int len_max = 128;
    unsigned int current_size = 0;
    char *pStr = malloc(len_max); 
    current_size = len_max;
    int i;
    char c;
    if (pStr != NULL) {
        while (( c = getchar() ) != '\n') { 
            pStr[i] = (char)c;
            i++;
            if(i == current_size) {
                current_size = i+len_max;
                pStr = realloc(pStr, current_size);
            }
        }

        pStr[i] = '\0';
        free(pStr);
    }
    return check_palindrome2(pStr,i);
}   


int check_palindrome2(char *s, int length) {
    for (int i = 0; i < length; i++) {
        if (s[i]!= s[length-i-1]) {
            return 0;
        }
    }
    return 1;
}
\$\endgroup\$
  • \$\begingroup\$ In check_palindrome2(), you only need to perform the comparison until length/2 \$\endgroup\$ – Damien Jan 30 at 14:46
  • \$\begingroup\$ @Damien ok, noted, anything else? \$\endgroup\$ – Prashin Jeevaganth Jan 30 at 14:55
  • 1
    \$\begingroup\$ To read, fgets() may be more efficient. To be tested. \$\endgroup\$ – Damien Jan 30 at 15:02
  • \$\begingroup\$ @Damien Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements in answers. \$\endgroup\$ – 200_success Jan 30 at 22:48
  • \$\begingroup\$ @200_success Until now, I mainly contributed to SO. There, partial answers are very rapidly downvoted! I had to suppress some of my answers. Usage may be different on this site as the kind of question ("how to improve ...") is different. Anyway, i tried to develop my comments and proposed an answer as you suggested \$\endgroup\$ – Damien Jan 31 at 9:01
3
\$\begingroup\$
  • free(pStr) is misplaced. Once it is freed, you may not touch it anymore. Calling check_palindrome2(pStr) after freeing causes an undefined behavior.

    Consider

        int rc = check_palindrome2(pStr, i);
        free(pStr);
        return rc;
    
  • check_palindrome2 could be called with a null pointer, but doesn't test it.

  • current_size += len_max is more clear than current_size = i+len_max.

  • read_palindrome is a misnomer. It doesn't read a palindrome. It reads a string of an unknown length. Now, SRP mandates splitting it into independent read_line and is_palindrome functions.

  • You test malloc for a failure. Keep in mind that realloc may fail as well.

        char * tmp = realloc(....);
        if (tmp == NULL) {
            free(pStr);
            return error;
        }
        pStr = tmp;
    

    NB: a simple pStr = realloc(....) is not good. If realloc fails, you'd have a memory leak.

\$\endgroup\$
  • \$\begingroup\$ for read_palindrome, I can't change the function because the driver code was provided and I have to implement read_palindrome according to the signature, not sure if the rest of the things depend on that flaw. \$\endgroup\$ – Prashin Jeevaganth Jan 30 at 17:08
  • \$\begingroup\$ @PrashinJeevaganth That's unfortunate. The third bullet is not applicable. Still keep it in mind. \$\endgroup\$ – vnp Jan 30 at 17:30
  • \$\begingroup\$ so are you suggesting that free(pStr) should not be placed? I'm not sure of its application as I always see malloc and freein pairs. And how would you recommend accounting for realloc fails \$\endgroup\$ – Prashin Jeevaganth Jan 30 at 17:34
  • \$\begingroup\$ @PrashinJeevaganth See edit. \$\endgroup\$ – vnp Jan 30 at 17:38
  • \$\begingroup\$ Just to clarify, when you meant check_palindrome2 should handle a null pointer, do u mean I should include a line if (s==NULL) return 0`? \$\endgroup\$ – Prashin Jeevaganth Jan 30 at 17:42
2
\$\begingroup\$

A first point concern palindrome checking. In check_palindrome2(), you only need to perform the comparison until length/2.
From a performance point of view, this part is unlikely to be critical compared to the other ones. However, if it is a homework, useless to stress your Professor.

A critical point concerns the number of reallocation, which clearly decreases the time efficiency of your programme. You cannot avoid it as memory usage is an important criteria according to the requirements. Effectively, allocating a buffer of some Mbytes to read a few bytes is wasting memory. However, increasing memory size by step of 128 bytes to read 1 Gbytes is really not efficient. It is such a situation when one has to find the best trade-off between time efficiency and memory efficiency. One possibility is to make this trade-off adaptive. You start with a small increment (128 in your program), as you did, but then, if you detect that too many reallocations occur, you increase the increment, for example by doubling it. You can do it several times. Maybe pay attention to set a maximum value of this increment.

Another critical point is the efficiency of reading the input. You do it character per character. It may be more efficient to read n characters in a raw, for example with fgets(). Pay attention in this case that in the last reading, it is likely that you will read less than n characters. You will have to test it carefully.

Last but not least, pay attention to avoid memory leakage or premature free. This point was clearly stated in the previous answer.

\$\endgroup\$
  • \$\begingroup\$ Note: fgets() has its corner weaknesses 1) Code certainly needs to walk it to find strings length. 2) It uses a size of type int which is problematic for huge strings when using robust size_t dynamically as you suggest. 3) Should input unexpectedly include a null character, fgets() affords no ready solution to its detection. \$\endgroup\$ – chux Jan 31 at 21:37
  • \$\begingroup\$ @chux Note that we don't have a lot of information about the kind of data to deal with. Concerning the dynamic increase of the increment, my concern was the number of reallocations. Even if this increment is huge, we can continue to read a reasonable number of characters in a row. This being said, I agree with the difficulty to use fgets(). Maybe overskilled for this problem \$\endgroup\$ – Damien Jan 31 at 21:51
0
\$\begingroup\$

"There is no assumption about the length of the input." is not reasonable - there is alwasy some reasonable limiting factor - perhaps more than UINT_MAX.

This code assumes current_size <= UINT_MAX by using unsigned.

Using size_t would make more sense as that is the type used by *alloc() and the right-size type for array indexing/pointer math.

// unsigned int len_max = 128;
// unsigned int current_size = 0;
size_t len_max = 128;
size_t current_size = 0;

Use _Bool for boolean functions

// int check_palindrome2(char *s, int length) {
_Bool check_palindrome2(char *s, int length) {
// or with <stdbool.h>
bool check_palindrome2(char *s, int length) {

Use const

For referenced data that does not change, use const for potential optimizations , wider code application and function clarity.

// int check_palindrome2(char *s, int length) {
int check_palindrome2(const char *s, int length) {

Double loop check speed

Perform length/2 checks, not length checks as in for (int i = 0; i < length; i++)

With above improvements:

#include <stdbool.h>

bool check_palindrome2(const char *s, size_t length) {
  const char *end = s + length;
  while (end > s) {
    end--;
    if (*end != *s) {
      return false;
    }
    s++;
  }
  return true;
}
\$\endgroup\$
0
\$\begingroup\$

You are storing characters in a string, and then checking them for being a palindrome. This is CPU efficient, but memory inefficient.

To store a palindrome really only requires at most n/2 + 2 characters, maximum (for odd length palindromes, n/2 + 1 for evens). If you check each character input against (*note) str[-1] (even) and str[-2] (odd), you could track how many duplicate characters you had seen, and only lengthen the string on a mismatch.

(*note: using Perl/Python notation that str[-1] is last character in str, etc.)

This would take more CPU, but would save memory in the case of very long palindromes.

For example, with the odd palindrome abcba you only need to store the abc string. The rest could be comparisons going backwards until you reach start-of-string and '\n' at the same time.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.