конкурс по си

А, ну тады нет смысла бенчмарки делать. Каждый сделал так, как понял. А у кого-то родилось классическое "ну не шмогла я".

Развлекаемся?

Как на счёт таких вариантов?

void strcut(char *where, const char *what)
{
    size_t whatlen = strlen(what);
    char *p, *prevp = NULL, *end = where + strlen(where);
    for (p = where, where = prevp; p = strstr(p, what); where += p - prevp, p += whatlen, prevp = p)
        if (prevp)
            memmove(where, prevp, p - prevp);
    if (prevp)
        memmove(where, prevp, end - prevp + 1);
}

void undebug(char *where)
{
    char *p = where;
    while (*p)
        if (p[0] == 'd' && p[1] == 'e' && p[2] == 'b' && p[3] == 'u' && p[4] == 'g')
            p += 5;
        else
            *where++ = *p++;
    *where = 0;
}

Во втором варианте сравнение можно ещё ускорить методом:

...
        if (*(int*)p == 'ubed' && p[4] == 'g')
...

Да, кстати, если хотите вырезать только на границе слов, надо просто искать не «debug», а " debug ", с пробелами, и при вырезании один пробел оставлять.

Мой прогноз: первый вариант самый компактный из универсальных, второй — самый быстрый.

надо просто искать не «debug», а " debug ",

это слово может встретится вначале строки, а может и в конце.

138.94 ms

Аж душу согрело :) Not bad.

Два дополнительных хардкода решают.

нет смысла бенчмарки делать.

Не ведись на речи неадеквата выше. Задача вполне себе чёткая. Это не олимпиада и не спортивное программирование. Тут дан простор для действий. Применяй инженерный подход для её решения.

Сами же решения можно сравнивать не только по скорости, но и по функциональности (или, если хочешь, глючности).

Два дополнительных хардкода решают.

Или исходная строка изначально дополняется пробелами слева и справа, или, например, размещается в буфере, изначально заполненном пробелами.

Плохой вариант, это всю строку копировать против двух простых проверок.

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

Вас может заинтересовать https://olimex.wordpress.com/tag/wpc/

Плохой вариант, это всю строку копировать против двух простых проверок.

Да, копировать — плохой вариант. Поставить два пробела в исходной строке слева и справа — лучше. Конечно же, мы заранее разместим строку в памяти так, чтобы это было возможно.

// мсти ??

Я надеялся быть backtroled ;)

Многовато допусловий.

А не быстрее ли, вместо

*where++ = *p++;

будет делать memcpy когда пришли к концу строки или закончили матчить дебаг?

Задача вполне себе чёткая.

Поставь её.

Я надеялся быть backtroled ;)

А вот сразу нельзя было расшифровать это странное слово:

An action taken by a person who is being trolled. The person being trolled uses the exact same trolling technique that the troll is using thus confusing the troll and making him look bad in front of everyone else.

?

Я думаю, еще быстрей было бы в два прохода сделать: 1) построить таблицу с "мусором", 2) при помощи memmove собрать в кучу оставшиеся куски.

А не быстрее ли, вместо

*where++ = *p++;

будет делать memcpy когда пришли к концу строки или закончили матчить дебаг?

Думаю, что не быстрее. Жду результатов сравнения. И интересно было бы взглянуть на код сравнивателя.

И как будет выглядеть сбор в кучу?

Я думаю, еще быстрей было бы в два прохода сделать: 1) построить таблицу с «мусором», 2) при помощи memmove собрать в кучу оставшиеся куски.

Talk is cheap. Show me the code! (c) Linus

char *sub, *dst = malloc(strlen(src)+1), *result = dst; assert(dst);

Не уверен. Так лучше не будет?
*dst = alloca(strlen(src)+1)

Поставь её.

Дана ascii-строка состоящая из слов и пар «ключ=значение». Разделителем служит один или больше пробелов. Нужно выпилить слово debug из исходной строки. Кол-во «лишних» пробелов в результирующей строке роли не играет. В коде использовать только вот эти функции: http://www.cs.bham.ac.uk/~exr/teaching/lectures/systems/08_09/docs/kernelAPI/...

В случае неоднозначности формулировки задания результат интерпретируется в пользу участника.

Проверочные тесты:

"debug" => ""
"debugfs" => "debugfs"
"debug=1" => "debug=1"
"debug systemd.debug" => " systemd.debug" 
"debug 123 debug 456" => " 123 456"

Мой прогноз: первый вариант самый компактный из универсальных, второй — самый быстрый.

Поправка: самый компактный из неквадратических вариантов. Квадратический, который каждый раз копирует всю строку до конца, компактнее, медленнее, но компактнее.

Мы не можем возвращать результат функции alloca потому что она выделяет место на стэке. Соотв., после выхода из функции данные скоро превратятся в тыкву, да и размер стэка может быть ограничен.

Если мы говорим о ядре, то, по-моему, там не рекомендуется ничего выделять на стэке больше чем одна страница памяти. Но я в этом не уверен, лучше погугли. Читал про это в lwn в статье про ядерные аллокаторы памяти.

1) построить таблицу с «мусором», 2) при помощи memmove собрать в кучу оставшиеся куски.

Мне кажется, это будет то же самое что и 1) найти ближайший needle и скопировать всё что было до него 2) перепрыгнуть через needle 3) повторить шаг 1

А вот это уже мой вариант, алгоритмически мне нравится максимально. Жаль, я не писатель.

Дана ascii-строка состоящая из слов и пар «ключ=значение». Разделителем служит один или больше пробелов. Нужно выпилить слово debug из исходной строки. Кол-во «лишних» пробелов в результирующей строке роли не играет. В коде использовать только вот эти функции: http://www.cs.bham.ac.uk/~exr/teaching/lectures/systems/08_09/docs/kernelAPI/...

Можно вообще без функций:

void undebug2(char *where)
{
  char *p = where, prev;
  for (prev = ' '; *p; prev = *p++)
    //if (prev==' ' && *(int*)p == 'ubed' && (*(short*)(p+4)==' g' || *(short*)(p+4)=='\0g'))
    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;
}

А это уже чёткая формальная постановка. Можешь же, когда захочешь. Пока на тормозную жидкость не идёшь.

ps: если я понимаю код по ссылке в старте, то он делает несколько другое.

А вот это уже мой вариант, алгоритмически мне нравится максимально. Жаль, я не писатель.

Мой strcut?

Похоже на то. Вроде красивый идиоматичный код, а читать его тяжёло.

Не inplace вариант в предельном случае длинной строки без вхождения должен быть быстрее. (один memcpy против посимвольного копирования) В другом предельном случае ('a'*100, «a») быстрее будет второй вариант.

https://github.com/dim13/lor-contest/blob/master/README.md

например «vmlinuz-3.2.0-debug-amd64», то ниодин не справляется

дык по посту в мыле вырезается «№nedle№» где №==(' '|$|^) т.е пробел либо начало, конец('\0') строки.

если же гнать скорость то у меня нужно заменить в nxt isalpha на isspace ( это мелочь)

и не не ставить ' ' в своём цикле, а мемset известный (n) размер как у wota.

from:"      debugfs            =1 systemd.           "
  to:"      debugfs            =1 systemd.           "     

ээ и почему тогда у тебя :

qulinxao             clobber           - fails   "      debugfs            =1 systemd.           "

т.е если это результирующая не правильная то какая правильная исходная? , а если неправильное поведение (не выкусывание debugfs ) то с чего это оно должно быть выкусано?

снимаю шляпу перед beastie

Пойнт в том, что мудрить не нужно, а верить авторам платформы - наоборот, нужно.

посмотрел на glibc strstr , а внутри у неё неонка:

http://fossies.org/dox/glibc-2.19/str-two-way_8h_source.html

на больших иглах преимущества strstr vs strcmp будет расти. ибо log n? vs n

хороший урок.

однако вспоминая Степанова с его Programming Conversations : мерти! ибо часто библиотеки это компромисс.

А разве вариант beastie рабочий?

Я бы тоже написал strstr и movmem в цикле. Вполне возможно, что сделал бы похожие (или те же) ошибки.

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

чей-нибудь вариант вообще справился с исходной задачей ???

исходный посыл, слово «debug» в итоговой строке валит систему и должно быть вырезано. И как контрпример «systemd dedebugbug must die».

Из всех вариантов только мой это правильно вырезает.
Если debug встречается внутри слова, например «vmlinuz-3.2.0-debug-amd64», то ниодин не справляется.

это очевидно без моего, кстати вот статистика по строкам кода LOC:

Eddy_Em 27
Gvidon 13
KennyMinigun 28
anonymous 11
beastie cutout 22
beastie undebug 17
beastie split 23
nokachi 43
qulinxao 25
true_admin #1 17
true_admin #2 13
wota #1 13
wota #2 11

Как собирал, какие использовал тестовые строки?

Тред не читал, патч, надеюсь, не приняли?

нашлось времечко, нашёл и пропатчил старую функцию под выдвинутые условия :)

буков(строк) много, потому как оригинал под длинные последовательсти байт (не ASCIIZ строки - внутри допустим \0)

зато патч - 1 строка :-)

#include <string.h>

inline unsigned
backcmp(char *s1,char *s2,unsigned len) {
	while( *s1--==*s2-- && len)
		len--;
	return len;
}
unsigned
eatbytes(char *word,unsigned wordlen,char *str,unsigned len)
{
	unsigned prefix;	// length of unique word prefix
	char lastchar;
	char *fin,*s;
	// check args
	if (word==NULL || wordlen==0 || str==NULL || len==0 || wordlen>len) return len;
	// init vars
	lastchar=*(word+wordlen-1);
	for(fin=word;*fin!=lastchar;)	// like strchr but \0 allowed
		fin++;
	prefix=fin-word;
	word=word+wordlen-1; // pointed to lastchar for backcmp()
	fin=str+len;
	s=str+wordlen-1;
	// search/replace loop
	while(s<fin) {
		while(s<fin && *s!=lastchar)
			s++;
		if (s==fin) break;
		if (
#ifdef LOR_PATCH
			/* word should by arrouned in spaces */
			(s+1==fin || *(s+1)==' ') && (s==str+wordlen-1 || *(s-wordlen)==' ') &&
#endif
			backcmp(s,word,wordlen)==0) {
			// found
			s++;
			memcpy(s-wordlen,s,fin-s);
			fin-=wordlen;
			s-=prefix;
		} else {
			s+=prefix;
		}
	}
	// return final length
	return fin-str;
}
/**** LOR TEST ****/
#include <stdio.h>
#include <stdlib.h>

void test_lor() {
	static char *tests[] = {
		"debug","debugfs","debug=1","debug systemd.debug","debug 123 debug 456",NULL
	};
	char r[]="debug",*s;
	int t;
	for(t=0;(s=tests[t])!=NULL;t++) {
		int len;
		s=strdup(s);	// make writable copy
		printf("string=\"%s\"\n",s);
		len=eatbytes(r,strlen(r),s,strlen(s));
		printf("result=\"%.*s\"\n\n",len,s);
		free(s);
	}
}

int main() {
	test_lor();
	return 0;
}

Ты считал только кол-во строк основной функции или весь выложенный файл целиком?

Потом, я, например, ради краткости несколько стейтментов писал в одну строку. В реальности я так не делаю.

Ты считал только кол-во строк основной функции или весь выложенный файл целиком?

функции

Потом, я, например, ради краткости несколько стейтментов писал в одну строку. В реальности я так не делаю.

там код отформачен через indent

mono, наведи тут порядок

да, зачётно ты вбросил.

патч, надеюсь, не приняли?

нет, слава богу.

вернулся в модераторы

Привет :). По-моему, ты уже третий раз этому удивляешься :)

Давай еще задачку. Все не танцпол. И для ума полезно, и в рамках приличия...

+1 (тред не читал)

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

void undebug(char *in) {
    char *p = in;
    size_t c = 0;
    size_t l = strlen(in);
    for (p = in; *p; p++, c++) {
        for (; *(p) == ' ' && *(p); (p)++);
        if (*p == 'd') {
            if (l < c + 5) { return; }
            if (strncmp("debug", p, 5) == 0) {
                if (p[5] == ' ') {
                  memmove(p,p+6,l-4); // we need to copy \0
                  l -= 5;
                } else if (p[5] == '\0') {
                  *p = '\0';
                  return;
                }
            }
        } else {
            for (; *(p) != ' ' && *(p); (p)++);
        }
    }
}

main() {
   static char *tests[] = {
      "debug","debugfs","debug=1","debug systemd.debug","debug 123 debug 456","debu",NULL
      };
   char r[]="debug",*s;
   int t;
   for(t=0;(s=tests[t])!=NULL;t++) {
     int len;
     s = strdup(s);  // make writable copy
     printf("string=\"%s\"\n",s);
     undebug(s);
     printf("result=\"%s\"\n\n",s);
     free(s);
   }
}

и сразу патч:

diff --git a/undebug.c b/undebug.c
index e130829..8fa860b 100644
--- a/undebug.c
+++ b/undebug.c
@@ -4,24 +4,23 @@
 
 void undebug(char *in) {
     char *p = in;
-    size_t c = 0;
-    size_t l = strlen(in);
+    size_t c = 0, l = strlen(in);
     for (p = in; *p; p++, c++) {
         for (; *(p) == ' ' && *(p); (p)++);
         if (*p == 'd') {
             if (l < c + 5) { return; }
-            if (strncmp("debug", p, 5) == 0) {
+            if (p[1]='e' && p[2] == 'b' && p[3] == 'u' && p[4] == 'g') {
                 if (p[5] == ' ') {
                   memmove(p,p+6,l-4); // we need to copy \0
                   l -= 5;
+                  continue;
                 } else if (p[5] == '\0') {
                   *p = '\0';
                   return;
                 }
             }
-        } else {
-            for (; *(p) != ' ' && *(p); (p)++);
         }
+        for (; *(p) != ' ' && *(p); (p)++);
     }
 }

ну и вместо

         for (; *(p) == ' ' && *(p); (p)++);

должно быть

         for (; *(p) == ' '; (p)++);