Как оптимизировать этот кусок кода В c

Question

У меня есть фрагмент кода в C, который удаляет любой повторяющийся символ в строке. Но я делаю это в двух циклах и хотел бы, чтобы он оптимизировался до одного цикла.

void removeDuplicates(char* ptr) 
{ 
int end = 1; 
int length = strlen(ptr); 
int current; 
int i; 
current = 1; 
for(end=1; end<length; end++) 
{ 
    for(i=0; i<end; i++) 
    { 
     if(ptr[end] == ptr[i]) 
     break; 
    } 
    if(i == end) 
    { 
     ptr[current] = ptr[i]; 
     current++; 
    } 
    } 
    ptr[current] = 0; 
} 

int main(int argc, char** argv) 
{ 
    char str[256] = {0,}; 
    gets(str); 
    removeDuplicates(str); 
    printf("%s\n", str); 
    return 1; 
} 

Как я могу сделать это в одной петле

Answer 1

Вы можете сделать это в один проход с чем-то вроде:

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

int main (void) { 
    char str[] = "p123h12p97h62p32h"; // Input string. 
    int found[256];      // Assumes 8-bit char. 
    char *src, *dst;      // Source and destination pointers. 

    // Output initial value and set found flags to false. 

    printf ("Before: [%s]\n", str); 
    memset (found, 0, sizeof(found)); 

    // One loop, processing each source character in string. 

    for (src = dst = str; *src != '\0'; src++) { 
     // If not yet found, flag it found and transfer it, else do nothing. 

     if (!found[(unsigned int)(*src)]) { 
      found[(unsigned int)(*src)] = 1; 
      *dst++ = *src; 
     } 
    } 

    // Insert new end of string, then output it. 

    *dst = '\0'; 
    printf (" After: [%s]\n", str); 

    return 0; 
} 

Это удаляет дубликаты в один проход, используя два указателя, что продвижение независимо через строку:

src 
| 
v 
p123h12p97h62p32h 
^ 
| 
dst 

Указатель src продвигается вперед o каждая итерация цикла. Символ копируется из src в dst, а указатель dst продвигается, только если символ ранее не был замечен (с использованием массива found). Выход:

Before: [p123h12p97h62p32h] 
After: [p123h976] 

Обратите внимание на "assumes 8-bit char" комментарий - это прекрасно, когда вы знаете, что набор символов ASCII (или любой другой 8-битный набор символов), но она не может быть переносимым на более экзотические реализации. Вам просто нужно убедиться, что в массиве found достаточно элементов для всех ваших персонажей. Например, для 10-разрядного типа char потребуется 1024 элемента (210 = 1024).

Answer 2

void removeDuplicates(char* ptr) 
{ 
    int exists[256] = {0}; 
    int end; 
    int current = 0; 
    int length = strlen(ptr); 

    for(end = 0; end < length; end++) 
    { 
     if (exists[ptr[end]]) break; 

     exists[ptr[end]] = 1; 
     ptr[current++] = ptr[end]; 
    } 

    ptr[current] = '\0'; 
} 

int main(int argc, char** argv) 
{ 
    char str[256] = {0,}; 
    gets(str); 
    removeDuplicates(str); 
    printf("%s\n", str); 
    return 1; 
} 

Answer 3

Это то, что я изначально думал делать. Микро-оптимизация позволяет использовать меньше памяти для массива «видимый символ», иначе это та же идея, что и другие.

void removeDuplicates(char* src) { 
    // Bitfield to remember which chars we 've seen, assumes 8-bit char type 
    char bitfield[32] = { 0 }; // 32 * 8 = 256 bits 

    char* dest = src; // initialize "output" ptr 

    while(*src) { 
     // Bitfield manipulation 
     char ch = *src; 
     int pos = ch >> 3; // ch/8 
     int bit = ch & 0x7; // ch % 8 
     char mask = 1 << bit; 

     // If char seen for first time, mark and write to "output" 
     if(!(bitfield[pos] & mask)) { 
      bitfield[pos] |= mask; 
      *dest++ = ch; 
     } 
     ++src; 
    } 

    *dest = 0; // null terminator 
} 

See it in action.