LINUX.ORG.RU

конкурс по си

 ,


7

4

На опеннете есть новость про то как сотрудник redhat шлёт левые патчи в ядро чтобы обойти проблемы systemd (http://www.opennet.ru/opennews/art.shtml?num=39476). Собстно, вот патчик:

http://lkml.iu.edu//hypermail/linux/kernel/1404.0/01327.html

Имхо, это ужас. Вот уж действительно товарищ принял упорин. Во-первых, он так и не понял почему редактирование /proc/cmdline это зло. Во-вторых, код ужасен, не? Неужели в сях нет способа проще вырезать подстроку? Ну и само по себе использование «магических» цифр 4 и 5 позорит код.

Так вот, конкурс по вырезанию произвольного слова из строки объявляю открытым! Учтите что слово может встречаться несколько раз.

★★★★★

Последнее исправление: beastie (всего исправлений: 2)

Ответ на: комментарий от true_admin

О как, пойти чтоль тогда каких витаминов себе купить)

Licwin ★★★★★
()
Ответ на: комментарий от qnikst

Код падает на тесте «debug». Нужно больше патчей!

---
Если бы строители строили дома так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

anonymous
()
Ответ на: комментарий от Eddy_Em

Давай еще задачку

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

true_admin ★★★★★
() автор топика
Ответ на: комментарий от true_admin

Не, у меня что-то туго с выдумыванием простеньких задачек. Решил бы кто за меня кое-что посложней...

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от beastie

https://github.com/dim13/lor-contest/blob/master/README.md
LOR Contest for a Medal of Lennart

Благодарю за выложенный код. У меня многие результаты другие, возможно, из-за версии gcc, архитектуры или ещё чего-то. Как и прогнозировалось, undebug2 рулит по скорости, особенно в закомментированном варианте if-а. Из-за того, что условия не были известны заранее, все функции, выделяющие память, находятся в заведомо проигрышных условиях по скорости.

Ещё интересно было добавить туда тест функции:

char *nop(char *where, char *what){return where;}
чтобы оценить, сколько времени в тесте занимает обслуживающий код.

К тому же функция nop() по пройденным тестам обошла половину конкурсантов.

anonymous
()
Ответ на: комментарий от qnikst

все работает, патчи были исключительно на скорость работы.

Как это работает? Смотрю по коду: in==«debug», входим в первый for, p==in, доходим до for(;*(p)==' ';(p)++); который вылетает за границу массива, потому что пробелов в строке нет.

anonymous
()
Ответ на: комментарий от Eddy_Em

Зайди на talentbuddy.co и выбери задачу по вкусу.

true_admin ★★★★★
() автор топика
Ответ на: комментарий от anonymous

у нас null-terminated строка вообще-то, доходим до \0 и никуда не выходим, а \0 != ' '. в тестах бисти возвращаем char * у меня void вот и вся разница, ща пул реквест туда пошлю.

qnikst ★★★★★
()
Ответ на: комментарий от qnikst
name            | func name       | passed      | gros time   | slower      
---             | ---             | ---         | ---         | ---         
beastie         | cutout          |       6 |  315.14 ms |      5.74 % 
beastie         | undebug         |       6 |  354.15 ms |     18.83 % 
beastie         | split           |       5 |  496.53 ms |     66.60 % 
Eddy_Em         | delsubstr       |       2 |  595.15 ms |     99.70 % 
Gvidon          | process         |       2 |  429.74 ms |     44.19 % 
KennyMinigun    | strdel          |       2 |  283.05 ms |     -5.02 % 
nokachi         | remove          |       6 |  427.46 ms |     43.43 % 
qulinxao        | wordstrings     |       3 |  335.28 ms |     12.50 % 
true_admin      | cut             |       2 |  416.45 ms |     39.74 % 
true_admin      | cut2            |       2 |  646.39 ms |    116.89 % 
wota            | strremove       |       2 |  538.53 ms |     80.70 % 
wota            | remove_word     |       6 |  298.03 ms |      0.00 % 
anonymous       | strcut          |       2 |  380.94 ms |     27.82 % 
qnikst          | undebugq        |       4 |  278.80 ms |     -6.45 % 
qnikst ★★★★★
()

Ну у вас тут и велосипеды на пол-экрана, друзья. Вот моё: корректно обрабатываются слова, начало с концом, а так же всякие граничные варианты. Всё тлен, в общем.

char *strcut(char *str, const char *cut)
{
    char *token, *rest = str;
    size_t slen = strlen(str);
    size_t clen = strlen(cut);

    if (!clen) return str;
    while ((token = strsep(&rest, " \t"))) {
        size_t tlen = rest - token - 1;
        if (!strcmp(token, cut)) {
            slen -= clen + 1;
            tlen  = slen - (token - str) + 1;
            rest  = memmove(token, rest, tlen);
        } else if (!rest) continue;
        token[tlen] = token[tlen] ? '\0' : ' ';
    }

    return str;
}

mix_mix ★★★★★
()
Ответ на: комментарий от qnikst

у нас null-terminated строка вообще-то, доходим до \0 и никуда не выходим, а \0 != ' '.

Точно. Мой косяк. Падает не на «debug», а на «debugfs».

anonymous
()
Ответ на: комментарий от anonymous

да нифига, там тоже не падает. Хотя косяки были и изначально решало не ту задачу, а при переходе к нужной я пару раз обломался делая return; вместо return in;

В общем в пул реквесте решение, которое проходит все тесты и к моему удивлению оказалось самым быстрым.

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

В общем в пул реквесте решение, которое проходит все тесты и к моему удивлению оказалось самым быстрым.

Самое быстрое пока что это, особенно с закомментированным вариантом if-а.

да нифига, там тоже не падает.

Вылетает за границу строки, не падает только при везении. Показать ошибку? ;-)

anonymous
()
Ответ на: комментарий от mix_mix

в таком виде сегфолтится, + ворнинги:

mix-mix.c: In function ‘strcutm’:
mix-mix.c:6:19: warning: incompatible implicit declaration of built-in function ‘strlen’ [enabled by default]
mix-mix.c:10:19: warning: assignment makes pointer from integer without a cast [enabled by default]
mix-mix.c:15:21: warning: incompatible implicit declaration of built-in function ‘memmove’ [enabled by default]

функцию переименовал в strcutm, т.к. в main strings.h используется

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

a). «это» сегфолтится

На каком тесте? При переписывании с void на char* надо не забыть в начале char*orig=where; и в конце return orig. Либо wrapper написать.

б). «это» ищет только debug

А больше ничего и не требуется.

в). да, показать

Тест «debugfs». Входим в основной for, p=in, пробелов нет, первый for(;) пропускаем, заходим в if(*p=='d'), ни один из вложенных if-ов не срабатывает, выходим на второй for(;), пропускаем всё до конца строки, *p=0, делаем p++ и, оп, мы за границей строки, дальше *p может быть чем угодно.

anonymous
()
Ответ на: комментарий от qnikst

в таком виде сегфолтится, + ворнинги:

Ну ещё бы.

т.к. в main strings.h используется

Так ты подключи человеческий string.h, и всё будет работать.

mix_mix ★★★★★
()
Ответ на: комментарий от anonymous

На каком тесте? При переписывании с void на char* надо не забыть в начале char*orig=where; и в конце return orig. Либо wrapper написать.

на первом же, попробуй сделать printf(«%s»,orig); вконцеt

А больше ничего и не требуется.

все предоставленные решения позволяют удалять разную подстроку, хотя тесты и не проверют.

Тест «debugfs». Входим в основной for, p=in, пробелов нет, первый for(;) пропускаем, заходим в if(*p=='d'), ни один из вложенных if-ов не срабатывает, выходим на второй for(;), пропускаем всё до конца строки, *p=0, делаем p++ и, оп, мы за границей строки, дальше *p может быть чем угодно.

согласен.

qnikst ★★★★★
()
Ответ на: комментарий от mix_mix

давай ты сам форкнешь репозиторий?

#include <stdlib.h>

char *strcutm(char *str, const char *cut)
{
    char *token, *rest = str;
    size_t slen = strlen(str);
    size_t clen = strlen(cut);

    if (!clen) return str;
    while ((token = strsep(&rest, " \t"))) {
        size_t tlen = rest - token - 1;
        if (!strcmp(token, cut)) {
            slen -= clen + 1;
            tlen  = slen - (token - str) + 1;
            rest  = memmove(token, rest, tlen);
        } else if (!rest) continue;
        token[tlen] = token[tlen] ? '\0' : ' ';
    }

    return str;
}
cc -O2   -c -o mix-mix.o mix-mix.c
mix-mix.c: In function ‘strcutm’:
mix-mix.c:6:19: warning: incompatible implicit declaration of built-in function ‘strlen’ [enabled by default]
mix-mix.c:10:19: warning: assignment makes pointer from integer without a cast [enabled by default]
mix-mix.c:15:21: warning: incompatible implicit declaration of built-in function ‘memmove’ [enabled by default]
cc -O2 -g3 -ggdb -o contest main.o beastie.o Eddy_Em.o Gvidon.o KennyMinigun.o nokachi.o qulinxao.o true_admin.o wota.o anonymous.o qnikst.o mix-mix.o
qnikst@nixos ~/tmp/c/undebug/lor-contest $ ./contest 

           input "debug"
          cutout .................... pass     7.17 ms
         undebug .................... pass     9.43 ms
           split .................... fail    12.57 ms
       delsubstr .................... fail    17.49 ms
         process .................... pass     9.17 ms
          strdel .................... pass     8.18 ms
          remove .................... pass    12.87 ms
     wordstrings .................... pass     8.64 ms
             cut .................... fail    11.52 ms
            cut2 .................... fail    11.71 ms
       strremove .................... pass     9.00 ms
     remove_word .................... pass     9.08 ms
          strcut .................... pass     9.52 ms
        undebugq .................... pass     8.02 ms
Segmentation fault
qnikst ★★★★★
()
Ответ на: комментарий от qnikst

блин так не честно, оно сравнялось с вариантом от бисти :)

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

Александр, есть такое понятие: стандартная библиотека, есть соответственно и заголовочные файлы стандартной библиотеки. Так вот string.h является каноническим, strings.h нет. Ты уж или сделай по-человечески, или не берись. Не прими за обиду. На всякий случай повторю: если для моего кода инклудить *стандартный* заголовочный файл со *стандартной* функцией strsep, сто лет как имеющую сигнатуру

char *strsep(char **stringp, const char *delim)
а не устаревшее говно из твоей strings.h
char *__strsep_1c (char **__s, char __reject);
то всё будет собираться без ошибок и правильно работать.

mix_mix ★★★★★
()

Выложу-ка и я свой вариант. Вариант совсем не использует библиотечные вызовы. Готов к включению в общую тестилку.

char* str_drop_str(char* str, char* sub)
{
    char* p_dst = str;
    char* p_src = str;
    char src;

    char* p_sub = sub;
    int sub_len = 0;

    int delim = 1;

    do {
        src = *p_src;
        
        if (!*p_sub && (src == ' ')) {
            p_dst -= sub_len;
            p_sub = sub;
            sub_len = 0;
        } else
            if (delim && (src == *p_sub)) {
                p_sub ++;
                sub_len ++;
            } else {
                delim = (src == ' ') ? 1 : 0;
                p_sub = sub;
                sub_len = 0;
            }

        if (p_dst != p_src)
            *p_dst = src;

        p_src ++;
        p_dst ++;

    } while(*p_src);

    if (!*p_sub) p_dst -= sub_len;
    
    *p_dst = 0;

    return str;
}

Можно наверное пооптимизировать слегка.

Puzan ★★★★★
()
Последнее исправление: Puzan (всего исправлений: 1)
Ответ на: комментарий от Puzan

Вот, кстати, результаты:

name            | func name       | passed      | gros time   | slower      
---             | ---             | ---         | ---         | ---         
beastie         | cutout          |       6 |   50.59 ms |      1.23 % 
beastie         | undebug         |       6 |   54.69 ms |      9.44 % 
beastie         | split           |       5 |   84.37 ms |     68.83 % 
Eddy_Em         | delsubstr       |       2 |  118.86 ms |    137.83 % 
Gvidon          | process         |       2 |   59.26 ms |     18.57 % 
KennyMinigun    | strdel          |       2 |   44.90 ms |    -10.17 % 
nokachi         | remove          |       6 |   63.37 ms |     26.81 % 
qulinxao        | wordstrings     |       3 |   51.24 ms |      2.53 % 
true_admin      | cut             |       2 |   63.82 ms |     27.71 % 
true_admin      | cut2            |       2 |  106.02 ms |    112.14 % 
wota            | strremove       |       2 |   56.93 ms |     13.91 % 
wota            | remove_word     |       6 |   52.17 ms |      4.40 % 
anonymous       | strcut          |       2 |   56.61 ms |     13.27 % 
puzan           | str_drop_str    |       6 |   49.98 ms |      0.00 % 
Puzan ★★★★★
()
Ответ на: комментарий от qnikst
name            | func name       | passed      | gros time   | slower      
---             | ---             | ---         | ---         | ---         
beastie         | cutout          |           7 |    79.63 ms |     18.24 % 
beastie         | undebug         |           7 |    73.54 ms |      9.20 % 
beastie         | split           |           6 |   122.14 ms |     81.37 % 
Eddy_Em         | delsubstr       |           3 |   155.01 ms |    130.18 % 
Gvidon          | process         |           3 |   120.34 ms |     78.70 % 
KennyMinigun    | strdel          |           3 |    68.93 ms |      2.35 % 
nokachi         | remove          |           6 |   107.43 ms |     59.52 % 
qulinxao        | wordstrings     |           4 |    80.24 ms |     19.15 % 
true_admin      | cut             |           3 |    98.09 ms |     45.65 % 
true_admin      | cut2            |           3 |   159.91 ms |    137.46 % 
wota            | strremove       |           3 |   113.80 ms |     68.99 % 
wota            | remove_word     |           7 |    76.66 ms |     13.83 % 
anonymous       | strcut          |           3 |    81.52 ms |     21.06 % 
qnikst          | undebugq        |           7 |    67.34 ms |      0.00 % 
mix-mix         | strcut          |           7 |    83.22 ms |     23.57 % 

я доволен, можно идти заниматься делами.

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

на первом же, попробуй сделать printf(«%s»,orig); вконцеt

Работает же! Мы про один и тот же код говорим?

char* undebug2(char *where, char *unused)
{
    char *orig = where, *p = where, prev;
    for (prev = ' '; *p; prev = *p++)
        if (prev==' ' && p[0]=='d' && p[1]=='e' && p[2]=='b' && p[3]=='u' && p[4]=='g' && (p[5]==' '||p[5]==0))
            p += 4;
        else
            *where++ = *p;
    *where = 0;
    return orig;
}

все предоставленные решения позволяют удалять разную подстроку, хотя тесты и не проверют.

Да, действительно. Но с универсальным сравнением функция вместо 8 строк занимает 14 строк, и выглядит совсем не так красиво. Хотя работает, как ни странно, так же быстро.

anonymous
()

Кстати, следует помнить, что IRL кроме пробелов в качестве разделителей могут быть ещё и табы, в таком случае только мой код проходит тест, но я ни на что претендовать не буду, т.к. true_admin говорил только про пробелы, так что сейчас всё честно.

Возможность тупо забить подстроку пробелами даёт ключ к быстрому решению, т.к. не нужно звать дорогой memmove. Поэтому давайте лучше меряться количеством строк/читаемостью решений.

mix_mix ★★★★★
()
Ответ на: комментарий от qnikst

я доволен, можно идти заниматься делами.

Ваша система вам подыгрывает. А моя подыгрывает мне. )

name            | func name       | passed  | gros time  | slower      
---             | ---             | ---     | ---        | ---         
nop             | nop             |       3 |  55.739 ms |    -25.46 % 
beastie         | cutout          |       6 | 106.711 ms |     42.71 % 
beastie         | undebug         |       6 | 154.889 ms |    107.13 % 
beastie         | split           |       5 | 169.506 ms |    126.68 % 
Eddy_Em         | delsubstr       |       2 | 300.139 ms |    301.38 % 
Gvidon          | process         |       2 | 131.547 ms |     75.92 % 
KennyMinigun    | strdel          |       2 |  86.259 ms |     15.35 % 
nokachi         | remove          |       6 | 163.586 ms |    118.77 % 
qulinxao        | wordstrings     |       3 |  90.608 ms |     21.17 % 
true_admin      | cut             |       2 | 189.324 ms |    153.18 % 
true_admin      | cut2            |       2 | 502.057 ms |    571.41 % 
wota            | strremove       |       2 | 104.326 ms |     39.52 % 
wota            | remove_word     |       6 | 196.751 ms |    163.12 % 
anonymous       | strcut          |       2 | 184.772 ms |    147.10 % 
anonymous       | undebug2        |       6 |  77.295 ms |      3.37 % 
anonymous       | undebug2uni     |       6 |  74.777 ms |      0.00 % 
qnikst          | undebugq        |       6 | 101.577 ms |     35.84 % 
mix_mix         | strcut          |       6 | 120.765 ms |     61.50 % 
Puzan           | str_drop_str    |       6 |  92.498 ms |     23.70 % 
anonymous
()
Ответ на: комментарий от mix_mix

и да memset быстрее ручного запробеливания.

но главное преимущество strstr использует внутри two-way - это по любому лучше чем квадратичный в отличии от strncmp

qulinxao ★★☆
()
Ответ на: комментарий от qulinxao

ибо isalpha да?

В «строке в кавычках» достаточно отслеживать только пробелы и табы, всякие \v, \r и \n не нужны.

mix_mix ★★★★★
()
Ответ на: комментарий от mix_mix

чёткого тз не было :)

если у меня заменить isalpha на ==0x20 то 1. все тесты в интерпретации куинста будут ок и чутка время уменьшится (ибо вместо вызова затем индекса и битовой маски и возврата и сравнения одно простое сравнение).

даже и не знаю кто на этих тестах станет первым вота или ещё кто :)

qulinxao ★★☆
()
Ответ на: комментарий от qnikst

коль такая пьянка

поправь у меня в место isalpha(*++s)

поставь просто *++s==' '

любопытно насколько 1 или 2 % уменьшится время :)

qulinxao ★★☆
()
Ответ на: комментарий от qnikst

твоё быстрее на 12%, но давай без константной строки ;)

Не красивое оно без константной строки. :) Универсальный сравниватель двух строк всё портит.

char* anon_strcut(char *where, char *what)
{
    char *dst = where, *p = where, prev;
    for (prev = ' '; *p; prev = *p++)
        if (prev == ' ') {
            char *s1 = p, *s2 = what;
            while (*s2 && *s1 == *s2) {++s1; ++s2;}
            if (!(*s2 || (*s1 != ' ' && *s1)))
                p = s1 - 1;
            else
                *dst++ = *p;
        }
        else
            *dst++ = *p;
    *dst = 0;
    return where;
}

anonymous
()
Ответ на: комментарий от qulinxao

ибо isalpha да?

А isalpha это баг. Потому что цифры, точки... «debug1 debug.debug»

anonymous
()
Ответ на: комментарий от mix_mix

на github тест на производительность некорректен.

Чтоб сравнить реализации на скорость надо гонять на больших string и needle, а то на коротких вы немного не ту скорость меряете :)

MKuznetsov ★★★★★
()
Ответ на: Мне таки стало очень интерессно! ☺ от beastie

Я хотел обидется на вас, но это я не мог обойти стороной.

А теперь самое интересное - качество твоего кода, а как следствие качество твоего теста - нулёвое:

[code=] Gros Relults ----

name | func name | passed | gros time | slower --- | --- | --- | --- | --- beastie | cutout | 6 | 29.38 ms | 83.56 % beastie | undebug | 6 | 25.82 ms | 61.37 % beastie | split | 5 | 41.80 ms | 161.21 % Eddy_Em | delsubstr | 2 | 54.84 ms | 242.66 % Gvidon | process | 2 | 30.66 ms | 91.61 % KennyMinigun | strdel | 2 | 22.09 ms | 38.04 % nokachi | remove | 6 | 35.42 ms | 121.36 % qulinxao | wordstrings | 3 | 25.29 ms | 58.05 % true_admin | cut | 2 | 35.15 ms | 119.62 % true_admin | cut2 | 2 | 53.65 ms | 235.24 % wota | strremove | 2 | 33.98 ms | 112.35 % wota | remove_word | 6 | 26.94 ms | 68.36 % anonymous | strcut | 2 | 27.56 ms | 72.20 % carb | debugdel | 6 | 16.00 ms | 0.00 % null | null | 3 | 12.60 ms | -21.24 %

null - это пустая функция, царь:

inline uint8_t _strcmp(char * str) {
  return (*(str + 0) == 'd') && (*(str + 1) == 'e') && (*(str + 2) == 'b') && (*(str + 3) == 'u') && (*(str + 4) == 'g');
}

char * debugdel(char * str) {
  char * ret = str;
  if(_strcmp(str + 0) && (*(str + 5) == ' ' || *(str + 5) == '\0'))
      memset(str + 0, ' ', 5), str += 5;
  while(*(++str) != '\0')
    if((*(str + 0) == ' ') && _strcmp(str + 1) && (*(str + 6) == ' ' || *(str + 6) == '\0'))
      memset(str + 1, ' ', 5), str += 5;
  return ret;
}

char * carb_wrapper(char *hey, char *needle) {
  return debugdel(hey);
}

У тебя оверхед на тест в 3.7 раза больше, чем результат моей функции. В среднем по больнице - 100% оверхед на тест. Сравнивать эти циферки так объективно.

Кстати, для справочки - функции обработки данных измеряют в байтах, а не секундах, а так же мериют качество функции относительно мемсета. Сложность этой функции по ио - в худжем случаее х2, в лучшем х1 - т.е. ты должен мерить в байтах, приэтом твой тест должен выводить скость мемсета/2 для той памяти, в которой ты мериешь.

Ты мериешь в л1д - выкатывай результат л1д.

anonymous
()
Ответ на: комментарий от anonymous

Немножечко фейл вышел:

Gros Relults
----

name            | func name       | passed      | gros time   | slower      
---             | ---             | ---         | ---         | ---         
beastie         | cutout          |       6 |   29.38 ms |     83.56 % 
beastie         | undebug         |       6 |   25.82 ms |     61.37 % 
beastie         | split           |       5 |   41.80 ms |    161.21 % 
Eddy_Em         | delsubstr       |       2 |   54.84 ms |    242.66 % 
Gvidon          | process         |       2 |   30.66 ms |     91.61 % 
KennyMinigun    | strdel          |       2 |   22.09 ms |     38.04 % 
nokachi         | remove          |       6 |   35.42 ms |    121.36 % 
qulinxao        | wordstrings     |       3 |   25.29 ms |     58.05 % 
true_admin      | cut             |       2 |   35.15 ms |    119.62 % 
true_admin      | cut2            |       2 |   53.65 ms |    235.24 % 
wota            | strremove       |       2 |   33.98 ms |    112.35 % 
wota            | remove_word     |       6 |   26.94 ms |     68.36 % 
anonymous       | strcut          |       2 |   27.56 ms |     72.20 % 
carb            | debugdel        |       6 |   16.00 ms |      0.00 % 
null            | null            |       3 |   12.60 ms |    -21.24 % 
anonymous
()
Ответ на: комментарий от MKuznetsov

Добавил ещё одни тест достаточно длинный и максимально приближённый к исходной задаче.

           input «BOOT_IMAGE=/debug/vmlinuz-3.2.0-debug-amd64 debug=UUID=42debug5-6ee1-464c-bc41-debug42debug ro debug»
             nop .................... fail     3.59 ms
          cutout .................... pass     8.49 ms
         undebug .................... pass    12.55 ms
           split .................... pass    32.19 ms
       delsubstr .................... fail    32.42 ms
         process .................... fail    59.58 ms
          strdel .................... fail    15.11 ms
          remove .................... pass    18.32 ms
     wordstrings .................... fail    23.69 ms
             cut .................... fail    17.86 ms
            cut2 .................... fail    60.69 ms
       strremove .................... fail    41.78 ms
     remove_word .................... pass    12.82 ms
          strcut .................... fail    18.54 ms
    str_drop_str .................... pass    24.83 ms
        undebugq .................... fail     9.16 ms
          strcut .................... pass    16.80 ms
beastie ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.