1
\$\begingroup\$

This is the code for checking if a string is a palindrome. The execution time, for sample cases, is 0.40358 seconds. What must be done to increase the performance?

int main(){
    int c,flag = 0;
    char *ch, *h;
    ch = (char *)malloc(sizeof(char)*101);
    h = ch;
    while((c=getchar())!=EOF){
        *ch = c;
        ch++;
    }
    ch--;
    while(ch>=h){
        if(*ch-- != *h++){flag = 1; break;}
    }
    flag == 1?(printf("NO")):(printf("YES"));
}

This is the code with an execution time of 0.4017 seconds for same test cases:

void main()
{
    char a[100],b[1000];
    int n,i,j=0,f=0;
    scanf("%s",a);
    n=strlen(a);
    for(i=n-1;i>=0;i--)
    {
        b[j]=a[i];
        j++;
    }
    for(i=0;i<n-1;i++)
    {
        if(a[i]==b[i])
        {
            f++;

        }
    }
    if(f==n-1)
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
}

Why is the former slower than the latter? Are the library functions faster?

\$\endgroup\$
  • 5
    \$\begingroup\$ How did you measure the times? Have you considered that 0.0018 seconds could be in the margin of error for your time measurement? \$\endgroup\$ – JS1 Jun 6 '17 at 8:18
  • \$\begingroup\$ Your second example uses void main -- always use int main. \$\endgroup\$ – ringzero Jun 7 '17 at 15:38
  • \$\begingroup\$ @ringzero "always use int main. " --> C specifies that an implementation is allowed other main() signatures. It is doubtful that changing the signature affects OP's goal of "What must be done to increase the performance?" \$\endgroup\$ – chux - Reinstate Monica Jun 9 '17 at 2:54
  • \$\begingroup\$ @chux Posting a program on CodeReview invites comments about any aspect of the code. A program which uses void main -- rather than int main -- is of questionable quality. The OP's concern about speed is perhaps misplaced considering the well-known advice: first make it work, then make it right and finally make it fast. \$\endgroup\$ – ringzero Jun 9 '17 at 17:47
6
\$\begingroup\$

The first version is the better approach and as already pointed out, what you measure here is outside the precision of measuring, so performance-wise, these solutions are equal.

Now some suggestions how to improve the code of the first version:

  • You allocate your buffer in a needlessly complicated way:

    ch = (char *)malloc(sizeof(char)*101);
    

    first of all, there's no point of casting void * in C, it is implicitly convertible to any data pointer type. Casting it could even hide a bug, see this stackoverflow answer for details. Then, sizeof(char) is defined to be 1, so you can leave it out. The whole line would then look like:

    ch = malloc(101);
    

    But why should you use dynamic allocation at all if you use a fixed size? Just use an array, similar to the code in your second version:

    char buf[101];
    

    Note I also suggest a different name here: buf tells the reader that this is a buffer for something (input in your case), while ch would make you think it's the name of a variable holding a single character.

  • You happily overflow your buffer:

    while((c=getchar())!=EOF){
        *ch = c;
        ch++;
    }
    

    You should never write code like this. There are functions for reading a limited amount of data, and as your buffer has a fixed size, you should use such a function, e.g.:

    memset(buf, 0, 101);
    size_t n = fread(buf, 1, 101, stdin);
    char *ch = buf + n;
    

    Without knowing your exact requirements, I guess you didn't intend to analyze "multi-line" palindromes, so using fgets() would be even a better choice:

    if (!(fgets(buf, 101, stdin) && *buf)) exit(1);
    size_t n = strlen(buf);
    if (buf[n-1] == '\n') buf[--n] = 0; // strip newline if present
    char *ch = buf + n;
    

    This is still close to your initial code, in practice, I'd use a larger buffer just to be sure and also define the buffer size as a macro, so I can change it without risking to introduce an overflow bug.

  • Regarding your second version, using scanf("%s", ...) will also overflow any buffer. A safe way of using scanf for reading in a fixed size buffer would be scanf("%100s", buf) if buf has a size of 101. I'd suggest not to use scanf() for this purpose at all. -- thanks for the comment!

  • A minor point since you are interested in performance:

        flag == 1?(printf("NO")):(printf("YES"));
    

    printf() must scan its first argument to know whether there are more arguments to follow, this is unnecessary for a constant output, so just use puts() if you want an automatic newline or fputs() to avoid the newline. In this case, puts() will be fine:

        flag == 1?(puts("NO")):(puts("YES"));
    
  • And as a general advise: Try to find better variable names that really describe the meaning of the variable, like instead of a flag, how about a isPalindrome?

Suggested improved version which also improves on readability:

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

#define BUFSIZE 1024
char buf[BUFSIZE]; // 1K buffer with static storage

int main(void)
{
    if (!(fgets(buf, BUFSIZE, stdin) && *buf))
    {
        // reading a line from stdin failed, give up
        return 1;
    }

    size_t n = strlen(buf);
    if (buf[n-1] == '\n') buf[--n] = 0; // strip newline

    char *front = buf;
    char *back = buf + n;

    int isPalindrome = 1;
    while (back > front)
    {
        if (*--back != *front++)
        {
            isPalindrome = 0;
            break;
        }
    }

    puts(isPalindrome ? "YES" : "NO");
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Good answer; you might want to point out that scanf("%s", &buf) also has an overflow problem, fixable with "%*s", sizeof buf - 1, &buf. \$\endgroup\$ – Toby Speight Jun 6 '17 at 15:40
  • \$\begingroup\$ Good catch, I didn't have a closer look at the second example. \$\endgroup\$ – Felix Palmen Jun 6 '17 at 15:52
  • 1
    \$\begingroup\$ @TobySpeight but I don't think a * would work as expected, as I read the scanf() manual, this just discards the result of the conversion... \$\endgroup\$ – Felix Palmen Jun 6 '17 at 16:10
  • \$\begingroup\$ I was thinking of printf() where the * says that the field width is to come from arguments. Sorry about that! There's a bit of a dance to get safe scanf(): How to prevent scanf causing a buffer overflow in C? \$\endgroup\$ – Toby Speight Jun 6 '17 at 17:08
  • 1
    \$\begingroup\$ @chux forget my complaint about your first comment, you probably meant stdin could actually deliver a 0 byte, yes, that's true, so I'm adding a little check here. \$\endgroup\$ – Felix Palmen Jun 9 '17 at 6:27
7
\$\begingroup\$

You can't really call a difference of 1% slower or faster. You should consider that both codes have exactly the same performance.

The only explanation for a speed difference between those two applications comes from the malloc (which is slightly slower than an array).

IMO, first code is better than second; the second one is quite hard to get (you are basically reversing a string, then comparing the reversed string with the normal one). I actually had to read the code 3 times to understand what was done.

About code review in itself:

  • First code sample:

    You should indent your code in a consistent manner.

    int c,flag = 0;
    char *ch, *h;
    

    Those variables are poorly named; flag could be replaced by is_palindromic, h could be string_start/str_start/str, and ch string_from_end/string_reverse etc....

    while((c=getchar())!=EOF){
    

    It's usually a good idea to separate comparators and equal sign from their operands, so it'd be something like this:

    while((c = getchar()) != EOF){
    
  • Second code sample:

    char a[100],b[1000];
    int n,i,j=0,f=0;
    

    Same as before, you should also avoid declaring 4 variables on the same line (especially considering you have both initialized and non-initialized variables).

\$\endgroup\$
1
\$\begingroup\$

You are comparing all the characters of two the arrays:

for(i=0;i<n-1;i++)
{
    if(a[i]==b[i])
    {
        f++;

    }
}

Instead, you can do something like this :

isPalin = 0 ;
n= strlen(charArray)
for(i=0;i<n/2;i++)
{
    if( charArray[i] != charArray[j] )
    {
        isPalin = 1 ; 
        break ;
    }
    j-- ;
}
puts(isPalin? "YES" : "NO" ) ; 

You only use one array and only traverse till (n/2-1) position of the array compared to your example. Execution time comes down to 0.822 secs.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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