[Beginner] strcmp in reverse order

[yrob]

Hello everybody,

I am new in C, but I need to modify a code to make it faster.
After adding timers, it seems that one of the biggest time consumer in this code is where strcmp is used: it compares MANY strings.

As an example here could be one list of strings: "object_out", "object_in", "object_1", "object_204", "object_log", "backup" ...

My understanding of strcmp is that it compares one by one the characters until it finds a difference. If for instance I want to look for "object_204" and "object_out", it will compare the "o", "b", ... "_" and then will find a difference between "2" and "o" and return 0.

So my idea was, since the differences will most of the time come from the end of the string (all prefixes are not the same, but most of them yes), to compare instead the end first, and go in reverse order.

Do you think this will be faster? Also as a beginner, I am afraid I will create an imperfect version of this function and would gladly get some help to be as efficient as possible.

Thanks!

[john.c]

Couldn't you just store the strings reversed?

We can only determine the best way to speed up your program if you specify the entire thing. For instance if there's a reasonable fixed number of strings they could be tokenized, each represented by an integer.

The problem with comparing from the end is that you need to find the end first, which means scanning both strings to find their ends (at least of the shortest one).

#include <stdbool.h>
#include <stdio.h>
 
// returns true if equal, false if not equal
bool revcmp(const char *a, const char *b) {
    const char *astart = a;
    while (*a++ & *b++) ; // & to avoid short-circuiting
    while (a > astart && *--a == *--b) ;
    return *a == *b;
}
 
int main() {
    printf("%d\n", revcmp("12345", "123"));
    printf("%d\n", revcmp("123",   "12345"));
    printf("%d\n", revcmp("12345", "21345"));
    printf("%d\n", revcmp("12345", "92345"));
    printf("%d\n", revcmp("12345", "12345"));
    return 0;
}

[hamster_nz]

It is quite likely that you will still have the same problem. You don't want to speed up the comparison, but reduce the number of comparisons.

What is the bigger problem you are trying to solve?

[aghast]

Are you comparing the strings in order to sort them, or are you comparing the strings just to determine if they are equal or not?

If you are trying to produce an ordering, then you'll have to process the characters in order, since that's how we determine string ordering. But if you just want to know about equality/inequality, there are a lot of possible solutions.

1. You could "intern" the strings and just compare pointers.
2. You could use your trick of comparing starting at the back end.
3. You could "hash" the strings and use that to quickly determine inequality, with a full compare only if the hash values match.

[Structure]

compare instead the end first, and go in reverse order.

speed up the comparison

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

int revstrcmp(char *string1, char *string2 ) {
    if (strlen(string1) != strlen(string2)) return 0;
    for (int i=strlen(string1); i>0; i--) {
        if (string1[i] != string2[i]) return 0;
    } return 1 ;
}

int main() {

    char string1[] = "object_142";
    char string2[] = "object_out";

    if (revstrcmp( string1, string2 )) {
        printf( "Equal" );
    } else {
        printf( "Not Equal" );
    }
    
    printf( "\n" );
    return 0;

}

[christop]

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

int revstrcmp(char *string1, char *string2 ) {
    if (strlen(string1) != strlen(string2)) return 0;
    for (int i=strlen(string1); i>0; i--) {
        if (string1[i] != string2[i]) return 0;
    } return 1 ;
}

int main() {

    char string1[] = "object_142";
    char string2[] = "object_out";

    if (revstrcmp( string1, string2 )) {
        printf( "Equal" );
    } else {
        printf( "Not Equal" );
    }
    
    printf( "\n" );
    return 0;

}

Using strlen() to find the end of a string before comparing the strings from the end is going to take just about as long as comparing two strings with strcmp().

Also, your (Structure's) revstrcmp function has a bug. Try comparing the strings "Xbject_42" and "Ybject_42". You'll get "Equal".

A better solution might be one of (or a combination of) these:

• Storing the strings in reverse (john.c mentioned this in #2)
• Storing the strings in a hash table (aghast mentioned this in #4)
• Storing the strings sorted and use bsearch() to find the matching string

Making the string comparison faster only buys you a linear increase in speed, while using a hash table (O(1)) or a binary search (O(log n)) gets you much bigger increase in speed, especially when n is large.