поправь pls

выкини isalpha ( ну и #include <ctype.h> тоже тогда) а в усливии while в nxt() :

(*++s>' ')

о я уже пару исправлений в свою функцию воткнул, ща новый пул пришлю

И что? ;) Твоё супер-пупер специализирование решение сливает половине генерик решений на «real-live input». А по коротким test-case'ам, да самое быстрое «hard-codet» решение. SuperHackKiller такой SuperHackKiller.

           input «BOOT_IMAGE=/debug/vmlinuz-3.2.0-debug-amd64 debug=UUID=42debug5-6ee1-464c-bc41-debug42debug ro debug»
          cutout .................... pass     8.64 ms
     wordstrings .................... pass    12.20 ms
     remove_word .................... pass    12.68 ms
         undebug .................... pass    13.00 ms
        debugdel .................... pass    13.56 ms
          strcut .................... pass    17.22 ms
          remove .................... pass    21.76 ms
    str_drop_str .................... pass    24.64 ms
           split .................... pass    29.88 ms

обновил.

а кто-нить может объяснить почему memset пробелами или заплолнение строки в for, работает медленнее, чем memcpy?

замержил. =)

ты кстати свои варианты модифицировал? а то что-то мой подход проигрывать начал?

блин заблудился в 3ёх соснах

#############

в nxt while

(*++s!=' '&&*s)

зы. фиг на скорость . коли режим только пробелокрая так и быть.

Поправил только cutout() под обновлённый ТЗ. (Передобавил оригинальный ваниант cutout_orig, который слишком много вырезает, для сравнения.)

можешь поправиьь в вебинтерфейсе гитхаба, мне сложно за всем уследить? ну или я ночью сделаю.

хаха, я добавил -march и -mtune, смотрю, все медленнее работать стало, а оказывается это кол-во тестов сменилось.

Ты же понимаешь, что я обоссу любое твоё/не твоё решение. Это даже близко не оптимальное, ибо вы о5 будете вонять: «симды для слабых, нужно выравнивание - говно твой код, 64битный код, только для х86» и прочее. Поэтому я просто наваял байду, который даже не претендовала на топ.

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

Ещё раз повторю - запили нормальный тест, либо давай я запилю, если мне будет не лень.

Поясню тебе, суть в том, что в твоём новом тесте одна замена и 95% времени - это пробежда по 2-м «словам» в 40% всей строки - т.е. у меня сдесь происходит тупо сравнение с инкрементом - это кусок говнища.

У пацанов же там strstr/strchr, который при многих заменах даст минус + либная функция, а там кто-то кукарекал, что типа «без либных вы не переплюните». Вот тебе фикс:

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

Врёшь, что сливает половине - у меня она сливает только cutout и на проценты.

Вот выхлоп с фиксом:

input "BOOT_IMAGE=/debug/vmlinuz-3.2.0-debug-amd64 debug=UUID=42debug5-6ee1-464c-bc41-debug42debug ro debug"
             nop .................... fail     3.01 ms
          cutout .................... pass     6.11 ms
         undebug .................... pass     9.54 ms
           split .................... pass    11.78 ms
       delsubstr .................... fail    20.90 ms
         process .................... fail    27.86 ms
          strdel .................... fail     9.65 ms
          remove .................... pass    12.82 ms
     wordstrings .................... pass     6.19 ms
             cut .................... fail    13.35 ms
            cut2 .................... fail    54.13 ms
       strremove .................... fail    27.23 ms
     remove_word .................... pass     9.58 ms
          strcut .................... fail    10.82 ms
     anon_strcut .................... pass     7.98 ms
    str_drop_str .................... pass    17.13 ms
        undebugq .................... pass     9.02 ms
          strcut .................... pass     9.84 ms
        debugdel .................... pass     4.53 ms

Ещё учитывай то, что моя быстрее «твоей» не в 1.34раза, а в (6.11−3.01)÷(4.53−3.01)=2раза.

И да, зачем ты мой ипак забанил? Форфан?

Кстати, что-то мистическое происходит:

Оригинальный код:

input "BOOT_IMAGE=/debug/vmlinuz-3.2.0-debug-amd64 debug=UUID=42debug5-6ee1-464c-bc41-debug42debug ro debug"
             nop .................... fail     2.84 ms
          cutout .................... pass     6.54 ms
         undebug .................... pass     9.29 ms
           split .................... pass    12.35 ms
       delsubstr .................... fail    20.20 ms
         process .................... fail    35.67 ms
          strdel .................... fail    11.17 ms
          remove .................... pass    12.79 ms
     wordstrings .................... pass     6.60 ms
             cut .................... fail    13.58 ms
            cut2 .................... fail    55.61 ms
       strremove .................... fail    45.35 ms
     remove_word .................... pass     9.75 ms
          strcut .................... fail    11.08 ms
     anon_strcut .................... pass     7.92 ms
    str_drop_str .................... pass    17.07 ms
        undebugq .................... pass     8.86 ms
          strcut .................... pass    12.53 ms
        debugdel .................... pass     6.61 ms

Код, где я поменял только мою функцию, но почему-то это тянет за собою cutout, причем я проверил 10раз - во всех случаях разница почти 1мс. Что-то как-то неочень.

input "BOOT_IMAGE=/debug/vmlinuz-3.2.0-debug-amd64 debug=UUID=42debug5-6ee1-464c-bc41-debug42debug ro debug"
             nop .................... fail     2.98 ms
          cutout .................... pass     6.11 ms
         undebug .................... pass    10.13 ms
           split .................... pass    11.57 ms
       delsubstr .................... fail    20.83 ms
         process .................... fail    27.78 ms
          strdel .................... fail     9.61 ms
          remove .................... pass    13.09 ms
     wordstrings .................... pass     6.42 ms
             cut .................... fail    13.75 ms
            cut2 .................... fail    59.85 ms
       strremove .................... fail    28.00 ms
     remove_word .................... pass    11.18 ms
          strcut .................... fail    11.10 ms
     anon_strcut .................... pass     8.17 ms
    str_drop_str .................... pass    17.57 ms
        undebugq .................... pass     9.10 ms
          strcut .................... pass     9.93 ms
        debugdel .................... pass     4.64 ms

Как называется абстракция примененная для решения задачи. Хочу покурить теорию, чтобы лучше понять код, гимнастика для ума, короче.

Автомат состояний?!

Ты же понимаешь, что я обоссу любое твоё/не твоё решение.

В этом и вся твоя суть. Изыди. You are not welcome here.

http://en.wikipedia.org/wiki/Finite-state_machine

DFA (deterministic finite automaton) aka конечный автомат. Ничего умного в моем коде кстати нет, а первая версия так и вообще неправильная — например подстроку «aabcd» в строке «aaabcd» она не находит. Второй код вроде правильный, но там уже и задача несколько проще.

Кстати, что-то мистическое происходит:

gettimeofday не монотонен и по хорошему надо бы считать не среднее за пробеги, а медиан

Не в этом дело - ты абсалютно не умеешь писать бенчи. Эти жалкие и бездарные выхлопы точек, 50байт бенчмарк, strdup() на 50байт, фри и маллок на 50байт. Пацан просто не осилил:

char for_test[strlen(t->string) + 4096];
...
strcpy(for_test, t->string);
...

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

У пацана функция выдаёт 5гигов, 5гигов на 100байтах. Это просто эпичный фейл. Оверхед самого бенчмарка просто 300-500%. Это просто даунизм.

Трезвый холостяк в интернете в пятничный вечер хуже пьяного школьника на линейке.

замержил. =)

Хех, и теперь оно падает на nop-е. Коммит 42db3f1e50.

Кто-то портит хип. Мимо памяти пишут три функции (cut, cut2, str_drop_str), какая именно из них вызывает падение — х.з. Комментирование любого из тестов или любой из функций убирает падение.

Тоже нарывался. Где-то что-то не туда пишет. mtrace молчит, а городить fork/pthreades, что бы разделить их друг от друга, как-то не очень хочеться.

Что и где найти легко: `gcc -O2 -ggdb -o contest *.c && valgrind --log-file=valgrind.log ./contest` ловит все места с багами. Только что с ними делать...

Таки запилил fork. Каждый тест бежит теперь отдельным процессом. Поможет хотя бы от «накапливающихся» ошибок.

И valgrind у меня не взлетает:

valgrind:  A must-be-redirected function
valgrind:  whose name matches the pattern:      strlen
valgrind:  in an object with soname matching:   ld-linux-x86-64.so.2
valgrind:  was not found whilst processing
valgrind:  symbols from the object with soname: ld-linux-x86-64.so.2

А как его лечить — не понятно. (В интернетах рылся, но ничего не нашёл). Если что — Debian/amd64. Вроде у valgrind'а какие-то проблемы с 64 бита.

Финалный рейтинг (плюс-минус лапоть — от раза до раза замеренное время чуть-чуть плавает).

name            | func name       | passed    | gros time   | slower      
---             | ---             | ---       | ---         | ---         
anonymous       | nop             |  ***  *   |   136.12 ms |    -39.02 % 
beastie         | cutout          | ********* |   335.27 ms |     50.18 % 
beastie         | cutout_orig     | *   * *   |   405.59 ms |     81.68 % 
beastie         | undebug         | ********* |   338.16 ms |     51.47 % 
beastie         | split           |  ******** |   681.69 ms |    205.36 % 
Eddy_Em         | delsubstr       |    ** *   |   785.19 ms |    251.72 % 
Gvidon          | process         | *   * *   |  1006.85 ms |    351.00 % 
KennyMinigun    | strdel          | *   * *   |   349.09 ms |     56.37 % 
nokachi         | remove          | ****** *  |   488.56 ms |    118.85 % 
qulinxao        | wordstrings     | ********* |   312.89 ms |     40.15 % 
true_admin      | cut             | *   * *   |   455.05 ms |    103.83 % 
true_admin      | cut2            | *   * *   |  1062.44 ms |    375.91 % 
wota            | strremove       | *   * *   |   835.42 ms |    274.21 % 
wota            | remove_word     | ********* |   352.17 ms |     57.75 % 
anonymous       | strcut          | *   * *   |   424.82 ms |     90.29 % 
anonymous       | anon_strcut     | ********* |   295.01 ms |     32.15 % 
puzan           | str_drop_str    | ********* |   463.46 ms |    107.60 % 
qnikst          | undebugq        | ********* |   344.70 ms |     54.40 % 
mix-mix         | strcut          | ********* |   402.85 ms |     80.45 % 
Carb            | debugdel        | ********* |   223.25 ms |      0.00 % 

Если будет ещё интерессно — присылайте пул-реквесты.

Код: https://github.com/dim13/lor-contest

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

Просто ув.анонимус пишет неэффективно, и perf-test всё ещё некорректен, некоторым подыгрывает :) в длинный тест надо добавлять выражение которое вообще не содержит искомого, а «debug» множить в начало,середину и конец строки (либо три варианта и считать среднее).

скорость надо гонять на больших string и needle

Мне кажется, надо рассматривать два случая

можно на самом деле много граничных вариантов сделать типа сплошные пробелы и debug, но на самом деле лучше собрать реальные примеры kernel commandline.

P.S. сейчас в тестах 3 длинных примера, на мелкие можно особо внимания не обращать и рассматривать как тестирование корректности.

отправил очередной вариант.. блин из-за мелких тестов Carb выиграывает

name            | func name       | passed    | gros time   | slower      
---             | ---             | ---       | ---         | ---         
anonymous       | nop             |  ***  *   |   762.04 ms |    -40.08 % 
beastie         | cutout          | **********|  2092.82 ms |     64.57 % 
beastie         | cutout_orig     | *   * *   |  2290.78 ms |     80.14 % 
beastie         | undebug         | **********|  1942.30 ms |     52.74 % 
beastie         | split           |  *********|  3173.63 ms |    149.57 % 
Eddy_Em         | delsubstr       |    ** *   |  4415.36 ms |    247.21 % 
Gvidon          | process         | *   * *   |  8867.02 ms |    597.28 % 
KennyMinigun    | strdel          | *   * *   |  2325.63 ms |     82.88 % 
nokachi         | remove          | ****** *  |  2712.29 ms |    113.29 % 
qulinxao        | wordstrings     | **********|  1975.62 ms |     55.36 % 
true_admin      | cut             | *   * *   |  2631.92 ms |    106.97 % 
true_admin      | cut2            | *   * *   |  6804.82 ms |    435.11 % 
wota            | strremove       | *   * *   |  8113.82 ms |    538.05 % 
wota            | remove_word     | **********|  1912.95 ms |     50.43 % 
anonymous       | strcut          | *   * *   |  2125.05 ms |     67.11 % 
anonymous       | anon_strcut     | **********|  1788.46 ms |     40.64 % 
puzan           | str_drop_str    | **********|  2717.10 ms |    113.67 % 
qnikst          | undebugq (userspace)| **********|  1415.76 ms |     11.33 % 
qnikst          | undebugq        | **********|  1448.14 ms |     13.88 % 
mix-mix         | strcut          | **********|  2669.43 ms |    109.92 % 
Carb            | debugdel        | **********|  1271.66 ms |      0.00 % 

ага ,

решали при помощи

либо конечный автомат либо (не будет показывать пальцем) фанатства на итераторах(т.е последовательность чего-либо) либо (пока тут решения не представили но если ЭТО будет продолжатся найдутся невытерпевшие) генерация исходного кода компилирующее регулярное выражение (которые по началу были эквивалентны КА пока не добавили бекреференсы и ещё кое-что) в С(либо маш)-код.

зы. про герерацию выше уже было . есть ещё rc2c , ну и царю на заметку.

у тебя антипатия к «на галерах „и тесты подкручиваеш соответственно.

зы. а так хе хе хе.

ззы. собою доволен , решение достаточное и „красивое“.

Ну что ж, почти. ;) Добавил ещё, что бы учитывались только тесты с более чем 40 символов.

Carb            | debugdel        | **********|   162.18 ms |      0.00 % 
qnikst          | undebugq uspace | **********|   166.84 ms |      2.87 %    
qnikst          | undebugq        | **********|   183.22 ms |     12.97 %

зато можно на фейсбуке лайкать))))

да нифига, длинные тесты его решение будет лучше обрабатывать :)

всё теперь уже послезавтра если только, что меня удивило, что а). у меня на компе разница между userspace и библиотечным копированием минимальна,

б). то, что когда я ввел функцию, которая «не теряет сдвиг» это замедлило решение

int strmatch2(char **p, const char *n) {
	char* t = *p;
	for (;*n != '\0';n++,t++) {
		if (*t != *n) { *p = t; return 0;}
	}
	*p = t;
	return 1;
}

в). то, что я не осилил написать нормальный сдвиг.

У нас теперь новый фаворит — wota. Царя спихнули с кресла. ;D И даже как-то по-ioccc-шному красиво. ;)

name            | func name       | passed    | gros time   | slower
---             | ---             | ---       | ---         | ---         
wota            | undebug_wota    | **********|   123.80 ms |      0.00 %
Carb            | debugdel        | **********|   158.16 ms |     27.75 %
qnikst          | undebugq uspace | **********|   172.72 ms |     39.51 %    
qnikst          | undebugq        | **********|   185.24 ms |     49.63 %
anonymous       | anon_strcut     | **********|   250.52 ms |    102.36 %
wota            | remove_word     | **********|   275.58 ms |    122.60 %
beastie         | cutout          | **********|   278.94 ms |    125.31 % 
qulinxao        | wordstrings     | **********|   279.39 ms |    125.68 %
beastie         | undebug         | **********|   289.20 ms |    133.60 % 
mix-mix         | strcut          | **********|   375.87 ms |    203.61 % 
puzan           | str_drop_str    | **********|   432.59 ms |    249.43 %

Тред мудаков и задротов

subj

царю привет.

Объясни пожалуйста в этом коде

static void 
undebug_wota(char *s)
{
	long v = *((long*)s);
	if( ( v & 0x000000FFFFFFFFFF ) == 0x6775626564 )
	{
		char s5 = ( v & 0x0000FF0000000000 ) >> 40;
		if( s5 )
		{
			if( s5 == 32 )
				memset( s, ' ', 5 );
				
			s += 6;
		}
		else
		{
			*s = 0;
			return;
		}
	}

	while(( s = strchr( ++s, ' ' ) ))
	{
		v = *((long*)s);
		if( ( v & 0x0000FFFFFFFFFFFF ) == 0x677562656420 )
		{
			char s6 = ( v & 0x00FF000000000000 ) >> 48;
			if( !s6 )
			{
				*s = 0;
				break;
			}
			else if( s6 == ' ' )
			{
				memset( s + 1, ' ', 5 );
				s += 6;
			}
		}
	}
}

Не по адресу

это не моё - «оно само» и да моё не такое «debug» ориентированное.

используется факт что long 8байтный (что несколько не культурно культурней было бы typedef long int64)

и нет в первой копипасте маскуют с 5 байтами debug и затем проверяют шестой байт - если пробел - это ^debug.* если ноль то это ^debug$

в цикле же начинают же уже масковать 6байт " debug" - ибо маскование только после нахождения очередного «не единого» разрыва вида " "

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

0xFF - это все еденицы байт.

0xFF - это все еденицы байт.

Это я знаю. Ага, за прочее спасибо

не дебаг наоборот а арабская запись чисел литлэндиан

Неточно выразился. Хорошо, а можно сказать «зеркально отраженный debug»?

(подбор синонимов иногда лучше позволяет вникнуть в суть вопроса) Добавлено:

Хотя я, видимо, ошибся, так как тут именно арабское представление числа,а не строки

То есть, фактически автор повышает быстродействие именно за счет использования побитовых операций, можно так сказать?

нет.

скорее из возможности работать с сущностями больше байта размером

Спасибо за консультацию :)

«зеркально отраженный debug»

ну нет же

у тебя есть строка это последовательность терминируемае нуль-байтом символов которые тоже байты

вот теперь вместо строки символов запиши

последовательность байтовых шестнацетиричных чисел (man od или man hd)

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

яндекс счёт указать?

Понятно. Ну так я же вроде исправился в том посте под «Добавлено». Правда описал не в таком развернутом виде как ты. Яндекс.Счет можно, но ближе к лету тогда появятся свободные пару долларов и ситуация в стране к чему-то скотится ;)

Я смотрю меня задвинули совсем. Вот вам новый код. Снова без библиотек и хардкода.

name             | func name        | passed           | gros time    | slower      
---              | ---              | ---              | ---          | ---         
wota             | undebug_wota     | **********       |    147.47 ms |      0.00 % 
Carb             | debugdel         | **********       |    182.31 ms |     23.63 % 
qnikst           | undebugq uspace  | **********       |    202.17 ms |     37.10 % 
qnikst           | undebugq         | **********       |    207.84 ms |     40.94 % 
puzan            | str_mask_str     | **********       |    239.10 ms |     62.13 % 
anonymous        | anon_strcut      | **********       |    286.97 ms |     94.60 % 
beastie          | cutout           | **********       |    316.72 ms |    114.77 % 
wota             | remove_word      | **********       |    322.71 ms |    118.83 % 
beastie          | undebug          | **********       |    358.03 ms |    142.79 % 
qulinxao         | wordstrings      | **********       |    361.20 ms |    144.94 % 
mix-mix          | strcut           | **********       |    422.47 ms |    186.48 % 
puzan            | str_drop_str     | **********       |    490.60 ms |    232.68 % 
beastie          | wipeout          | **********       |    625.36 ms |    324.06 %