CODEWITHSUNDEEP
carraysstring
Lei Kan
Lei Kan

Reputation: 477

Optimize this Remove() method in C

This is a method use to remove the 'key' from char array.

version 1:

/* remove character key by two loop */
char *Remove(char *str, const char key)
{
    int len = strlen(str);
    for (int i = 0; i < len; i++)
        if (str[i] == key)
        {
            for (int j = i--; j <= len; j++)
                str[j] = str[j + 1];
        }
    return str;
}

version 2:

/* remove character key by one loop */
char *Remove(char *str, const char key)
{
    char *p1, *p2;

    p1 = p2 = str;
    while (*p2)
    {
        if (*p1 == *p2 && *p1 != key)
                p1++;
        else if (*p2 != key)
            *p1++ = *p2;
        p2++;
    }
    *p1 = *p2;  // assign '\0' to *p1
    return str;
}

I want to optimize the version 2, any body has any idea?

Upvotes: 0

Views: 116

Answers (2)

Jonathan Leffler
Jonathan Leffler

Reputation: 753665

I respectfully suggest that this loop is simpler. Compared with the functions in the question, it is O(N) time, whereas the code for the first function in the question is O(N*N) if the key character appears. The second is O(N), but the loop body is quite complex.

char *Remove(char *str, char key)
{
    char *dst = str;
    for (char *src = str; *src != '\0'; src++)
    {
        if (*src != key)
            *dst++ = *src;
    }
    *dst = '\0';
    return dst;  // Or src, but knowing the end is more useful!
}

Clearly, if you don't have a C99 compiler, you could place the declaration of src outside the loop.

I used the following code to satisfy myself that the code in randomusername's answer is now correct (and produces the same answer as my code):

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

static char *Remove2(char *s, char key)
{
    char *p1, *p2;
    p1 = p2 = s;
    do
    {
        while (*p2 == key)
            p2++;
        *p1++ = *p2++;
    }
    while (p2[-1]);
    return p2 - 1;
}

static char *Remove1(char *str, char key)
{
    char *dst = str;
    for (char *src = str; *src != '\0'; src++)
    {
        if (*src != key)
            *dst++ = *src;
    }
    *dst = '\0';
    return dst;  // Or src, but knowing the end is more useful!
}

int main(void)
{
    char data1[32] = "AB=CD==EF===GHI\0AAAAA";
    char data2[32] = "AB=CD==EF===GHI===\0AAAAA";
    char data[32];
    char *end;

    memmove(data, data1, sizeof(data));
    end = Remove1(data, '=');
    printf("[%s] => [%s] (%d)\n", data1, data, (int)(end - data));

    memmove(data, data1, sizeof(data));
    Remove2(data, '=');
    printf("[%s] => [%s] (%d)\n", data1, data, (int)(end - data));

    memmove(data, data2, sizeof(data));
    Remove1(data, '=');
    printf("[%s] => [%s] (%d)\n", data2, data, (int)(end - data));

    memmove(data, data2, sizeof(data));
    Remove2(data, '=');
    printf("[%s] => [%s] (%d)\n", data2, data, (int)(end - data));

    return 0;
}

Output:

[AB=CD==EF===GHI] => [ABCDEFGHI] (9)
[AB=CD==EF===GHI] => [ABCDEFGHI] (9)
[AB=CD==EF===GHI===] => [ABCDEFGHI] (9)
[AB=CD==EF===GHI===] => [ABCDEFGHI] (9)

Upvotes: 3

randomusername
randomusername

Reputation: 8087

Why not just use,

p1 = p2 = s;
do
  {
    while (*p2 == key) p2++;
    *p1++ = *p2++;
  }
while (p2[-1]);

I know there are many capitalization errors; I am currently at the mercy of my Blackberry's auto-correct.

Upvotes: 3

Related Questions