Thread: [Beginner] strcmp in reverse order

  1. #1
    Registered User
    Join Date
    May 2021
    Posts
    1

    Post [Beginner] strcmp in reverse order

    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!

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,155
    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).
    Code:
    #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;
    }
    Last edited by john.c; 05-07-2021 at 07:45 PM.
    The errors of great men are venerable because they are more fruitful than the truths of little men. - Nietzsche

  3. #3
    Registered User
    Join Date
    Sep 2020
    Posts
    291
    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?

  4. #4
    Registered User
    Join Date
    Apr 2021
    Posts
    56
    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.

  5. #5
    null pointer Structure's Avatar
    Join Date
    May 2019
    Posts
    339

    Post

    compare instead the end first, and go in reverse order.
    speed up the comparison
    Code:
    #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;
    
    }
    Last edited by Structure; 05-13-2021 at 04:36 AM.
    "without goto we would be wtf'd"

  6. #6
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    788
    Quote Originally Posted by Structure View Post
    Code:
    #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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reverse the Order of Lines
    By poiqwe in forum C Programming
    Replies: 6
    Last Post: 01-25-2015, 05:20 PM
  2. Replies: 1
    Last Post: 05-30-2010, 10:22 PM
  3. Printing in reverse order
    By JFonseka in forum C Programming
    Replies: 1
    Last Post: 08-17-2007, 04:30 AM
  4. reverse the order of an array
    By dustyd in forum C++ Programming
    Replies: 4
    Last Post: 01-23-2003, 11:14 AM
  5. how do I reverse order of my array
    By jgonzales in forum C++ Programming
    Replies: 6
    Last Post: 09-25-2002, 03:48 PM

Tags for this Thread