Функция s_strip (s, del) в C, есть ли более оптимизированная версия, чем эта?

Question

мой первый пост здесь (очень жаль, что я не обнаружил это великое сообщество ранее).

В любом случае, я кодировал функцию C, которая удаляет из строки s любой символ, содержащийся в строке del . Мне было интересно, есть ли место для улучшений по скорости, особенно для части, которая ищет символы, содержащиеся в del , внутри цикла for (я использовал strpbrk (), но pmg мудро предложил strchr ( )).

Охотники за жуками также приветствуются! Я думаю, что это надежно, но вы никогда не знаете.

Вот код (заранее спасибо за любые ответы) ...

Текущая версия

// remove from string s any char contained in string del (return modified s)
// alg:
// parse s via cp1, keep desired *cp1's by copying them via cp2 to the start of s
// null terminate & return the trimmed s

char *s_strip(char *s, const char *del)
{
    char *cp1;                      // for parsing the whole s
    char *cp2;                      // for keeping desired *cp1's

    for (cp1=s, cp2=s; *cp1; cp1++ )
        if ( !strchr(del, *cp1) )   // *cp1 is NOT contained in del (thanks pmg!)
            *cp2++ = *cp1;          // copy it via cp2

    *cp2 = 0;                       // null terminate the trimmed s
    return s;
}

---

Оригинальная версия

char *s_strip(char *s, const char *del)
{
    char *cp1;                              // for parsing the whole s
    char *cp2;                              // for keeping desired *cp1's

    for (cp1=s, cp2=s; *cp1; cp1++ )
        if ( cp1 != strpbrk(cp1, del) ) {   // *cp1 is NOT contained in del
            *cp2 = *cp1;                    // copy it via cp2
            cp2++;
        }

    *cp2 = 0;                               // null terminate the trimmed s
    return s;
}

Answer 1

А как насчет использования strchr() вместо strpbrk()?

Ваша версия без необходимости перебирает входную строку, когда вам нужно только проверить 1-й символ.

/* ... */
if (!strchr(del, *cp1)) *cp2++ = *cp1;
/* ... */

Answer 2

Какой длины будут входные строки и сколько символов вы собираетесь удалить в среднем.Если вы работаете с 8-битными кодовыми наборами и более длинными исходными строками, подумайте о:

char *s_strip(char *s, const char *del)
{
    char map[256] = { 0 };
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    while (*up1 != '\0')
        map[*up1++] = 1;

    for ( ; *up2 != '\0'; up2++)
    {
        if (map[*up2] == 0)
            *up3++ = *up2;
    }
    *up3 = '\0';

    return (char *)up3;
}

Это заменяет вызов функции (strpbrk() или strchr()) простым поиском массива за счет инициализациимассив при входе в функцию.Если обработанные строки довольно длинные, это может легко окупиться за значительно сокращенное время поиска.

Эта версия кода возвращает указатель на ноль в конце строки - что позволяет вам вычислятьдлина сжатой строки при возврате без вызова strlen().Я считаю это более полезным дизайном, чем возвращение указателя на начало строки - я уже знал, где начинается строка, но я больше не знаю, где она заканчивается, но функция s_strip() знает это.(Если бы мы могли начать все сначала, я бы лоббировал тот же дизайн и для strcpy() и strcat().)

Приведение к «unsigned char» гарантирует, что оно работает должным образом на машинах с подписанными неподписанные символы.Я не очень доволен смазыванием приведений, но их трудно избежать (ну, можно было бы избежать назначения бросков s на up3, скопировав `up2).

Возможно, выможет придумать дизайн, который также обрабатывает подписанные символы, например:

char realmap[256] = { 0 };
char *map = &realmap[128];

Вы можете рассчитывать на то, что подписанные символы находятся в диапазоне, так что map[-128] .. map[+127] все еще приземляетсяв массиве realmap.

---

Функция, указанная выше, была исправлена ​​несколько раз с момента ее первой публикации - теперь она, похоже, работает в соответствии с двумя решениями, предложенными в вопросе.Я поместил эти три решения в тестовую привязку, чтобы рассчитать их время, главным образом потому, что мне было любопытно, как будет работать код карты, поскольку в прошлом он проигрывал встроенным функциям кода ассемблера.Картографическое решение очень быстро показывает себя самым быстрым в моей тестовой системе (Mac Mini 2 GHZ Intel Core 2 Duo, MacOS X 10.6.7, GCC 4.1.2).

Среднее время в секундах.Каждому алгоритму было дано 10 прогонов.Размер - это размер исходной строки;строка удаления состояла из 22 символов (по 6 букв в нижнем регистре, букв в верхнем регистре и цифр, плюс 4 знака препинания).Данные представляли собой фиксированную строку, построенную из букв, цифр и знаков препинания в ASCII, повторяемую так часто, как это необходимо для достижения заявленного размера, исключая завершающий ноль.Обратите внимание, что время включает в себя копирование исходной строки каждый раз - в столбце «null» указывается время, потраченное на копирование.

size     map        strchr     strpbrk    null       micro1     micro2
   2     0.000542   0.002292   0.001009   0.000106   0.000639   0.000707
   8     0.000654   0.004125   0.017524   0.000106   0.001012   0.000966
  32     0.001667   0.015815   0.063314   0.000196   0.002549   0.002247
 128     0.006385   0.064513   0.313749   0.000171   0.008455   0.007188
 512     0.022231   0.257910   1.293040   0.000282   0.013284   0.011829
2048     0.089066   1.035052   5.297966   0.000819   0.043391   0.037597

Даже при очень коротких исходных строках алгоритм отображения намного быстрее, чем любой изАлгоритмы strchr() или strpbrk() (в 5-10 раз быстрее, чем алгоритм strchr(), и в 5-50 раз быстрее, чем алгоритм strpbrk()), причем несоответствие увеличивается с ростом размера строки поиска.(Я не ожидал этого результата - потому что в коде карты есть служебные настройки).

Алгоритмы 'micro1' и 'micro2' соответствуют модификациям, предложенным AShelly .Когда строки достаточно длинные (переключение происходит между 128 и 512 байтами), тогда микрооптимизированные версии работают быстрее, чем простая карта.

---

Тестовый код

Свяжитесь со мной (см. Мой профиль), если вам нужен источник для timer.c, timer.h.Я бы обычно встраивал их в библиотеку и связывал с библиотекой, но в этот раз было проще включить файлы в программу.

#include <string.h>

extern char *s_strip1(char *s, const char *del);
extern char *s_strip2(char *s, const char *del);
extern char *s_strip3(char *s, const char *del);

char *s_strip3(char *s, const char *del)
{
    char map[256] = { 0 };
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    while (*up1 != '\0')
        map[*up1++] = 1;

    for ( ; *up2 != '\0'; up2++)
    {
        if (map[*up2] == 0)
            *up3++ = *up2;
    }
    *up3 = '\0';

    return (char *)up3;
}

char *s_strip2(char *s, const char *del)
{
    char *cp1;
    char *cp2;

    for (cp1=s, cp2=s; *cp1; cp1++ )
        if ( !strchr(del, *cp1) )
            *cp2++ = *cp1;

    *cp2 = 0;
    return s;
}

char *s_strip1(char *s, const char *del)
{
    char *cp1;
    char *cp2;

    for (cp1=s, cp2=s; *cp1; cp1++ )
        if ( cp1 != strpbrk(cp1, del) ) {
            *cp2 = *cp1;
            cp2++;
        }

    *cp2 = 0;
    return s;
}

#include <stdio.h>
#include "timer.h"
#include "timer.c"

enum { NUM_REPEATS = 10000 };
typedef char *(*Function)(char *str, const char *del);

static void fill_bytes(char *buffer, size_t buflen)
{
    static const char source[] =
        "abcdefghijklmnopqrstuvwxyz"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "0123456789[]{}\\|,./?><;:'\"=+-_)(*&^%$#@!";
    char *end = buffer + buflen;

    while (buffer < end)
    {
        size_t numbytes = sizeof(source) - 1;
        if ((size_t)(end - buffer) < sizeof(source)-1)
            numbytes = end - buffer;
        memmove(buffer, source, numbytes);
        buffer += numbytes;
    }
}

static void test(Function f, const char *fn, const char *del, size_t numbytes)
{
    Clock clk;
    char refbuf[numbytes];
    char buffer[numbytes];
    char clkbuf[32];
    fill_bytes(refbuf, sizeof(refbuf));
    strcpy(buffer, refbuf);
    clk_init(&clk);
    clk_start(&clk);
    for (size_t i = 0; i < NUM_REPEATS; i++)
    {
        memmove(buffer, refbuf, sizeof(buffer));
        if (f)
            (*f)(buffer, del);
    }
    clk_stop(&clk);
    printf("%-17s (%4zd) = %10s (%.64s)\n", fn, numbytes,
           clk_elapsed_us(&clk, clkbuf, sizeof(clkbuf)), buffer);
}

int main(void)
{
    for (int size = 2; size <= 2048; size = size * 4)
    {
        for (int i = 0; i < 10; i++)
        {
           test(s_strip1, "s_strip1:strpbrk:", "AJQRSTajqrst234567=+[]", size);
           test(s_strip2, "s_strip2:strchr:",  "AJQRSTajqrst234567=+[]", size);
           test(s_strip3, "s_strip3:map",      "AJQRSTajqrst234567=+[]", size);
           test(0,        "s_strip4:null",     "AJQRSTajqrst234567=+[]", size);
        }
    }
    return 0;
}

Микро-оптимизации

extern char *s_strip4(char *s, const char *del);
extern char *s_strip5(char *s, const char *del);

char *s_strip5(char *s, const char *del)
{
    char map[256];
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    memset(map, 1, sizeof(map));

    while (*up1 != '\0')
        map[*up1++] = 0;

    for ( ; *up2 != '\0'; up2++)
    {
        *up3 = *up2;
        up3 += map[*up2];
    }
    *up3 = '\0';

    return (char *)up3;
}

char *s_strip4(char *s, const char *del)
{
    char map[256] = { 0 };
    const unsigned char *up1 = (const unsigned char *)del;
    unsigned char *up2 = (unsigned char *)s;
    unsigned char *up3 = (unsigned char *)s;

    while (*up1 != '\0')
        map[*up1++] = 1;

    for ( ; *up2 != '\0'; up2++)
    {
        *up3 = *up2;
        up3 += !map[*up2];
    }
    *up3 = '\0';

    return (char *)up3;
}

Answer 3

Каждый раз, когда вы вызываете strpbrk, он будет сканировать строку вперед, ища символ в del.Если вы называете это строкой длиной 100 символов, которая не содержит «удаляемых» символов, она будет проверять 100 + 99 + 98 + 97 + ... + 1 символов.

Почему бы не использовать лучшеинформация strpbrk возвращается?Если возвращаемое значение равно нулю, вы можете вернуть исходную строку.В противном случае вы можете использовать все символы вплоть до указателя, возвращаемого strpbrk.

Что-то вроде:

 dest=src=s;
 bad = strpbrk(src,del);
 if (!bad) return s;  //early exit if there is no work.
 while (bad)
 {
    while (src<bad) *dst++=*src++;
    bad = strpbrk(++src,del);
 }
 while (*src) *dst++=*src++; //copy the remainder
 *dst='\0';
 return s;