каким боком они относятся к задаче

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

Уменьшают количество данных, необходимых для поиска

расскажи поподробнее плз

Уменьшают количество данных, необходимых для поиска:

отсортированный массив указателей даст еще больший профит в этом плане.

Напиши мне strstr() на кмп - я хоть поржу. Мне даже интересно, хватит ума у «понимателя» обогнать 2 цикла.

http://pastebin.com/GGTDHieU

$ time ./strstr kmp

real	0m0.449s
user	0m0.440s
sys	0m0.009s

$ time ./strstr naive

real	28m49.893s
user	28m49.884s
sys	0m0.009s

Рассмотрим худший случай.

Валяй.

Возьмём строку длины n вида «aaa...aaa» и подстроку длины n/2 вида «aaa...aab».

Ок.

В итоге наивная strstr

Да у тебя больничка - тема не про strstr(), а про:

дан key-value словарь, тебе надо заменить всех вхождения key на value.

В итоге наивная strstr сделает (n/2)*(n/2) сравнений — внутренний цикл крутится по всей подстроке

Какая нахрен «наивная» strstr(), алёша. Почему все бабуины, обосравшись, начинают нести какаю-то херню.

Никаких строк n/2 не бывает, никаких строк вида аааааааааааааа не бывает.

strchr() + memcmp() + примитивная евристика, если юзаешь на говно обоссывает ублюдство аля кмп в говно.

Да и причем тут вообще strstr(), если нахрне поиск не одной строки, а словаря - ты совсем больной?

что есть O(n^2). Обосрамс.

Нет, дурачек, это не квадрат, а n*m. Зачем ты несёшь херню?

При этом причем тут вообще strstr(), повторю ещё раз.

return !!strstr(haystack, needle); - пж - да, да - там 2цикла, а теперь возьми не придуманное аутистом бесполезное говно не имеющие к реальному миру никакого отношения и померий.

Нет, дурачек, это не квадрат, а n*m. Зачем ты несёшь херню?

Где ты в моём выводе m увидел? У меня строка длины n и подстрока длины n/2.

Никаких строк n/2 не бывает, никаких строк вида аааааааааааааа не бывает.

Расскажи это генетикам.

а теперь возьми не придуманное аутистом бесполезное говно не имеющие к реальному миру никакого отношения

Слив засчитан.

А где ты видел кодировку, в которой первая половина не совпадает с ASCII?

ДКОИ-8 с ЕС ЭВМ, совместимая с EBCDIC, которая упомянута, кстати, у K&R. Но и в ней коды цифр '0'...'9' идут подряд.

Такое элементарное дерево позволяет найти слово из N букв за максимум N перемещений!

Рили? Ты совсем кря-кря, либо притворяешься?

Надо найти не слово, а все слова. И что ты мне показал? n*длинна_максимального_слова_из_словаря? Молодец, только я об этом же и говорил.

Берем дерево для буквы А (в нашем примере оно единственное), идем на ветку «ар», в этой ветке у нас в данном случае 1 узел: «арб» и «арб». Заходим в него и выбираем тот узел, где четвертая буква — «у»

Выбираем букву г - и примет ресет. Т.е. поиск всех слов в худшем случае у тебя будет N*max_len(word_set), что является парашей. И надо сделать быстрее.

А если сделать какое-нибудь «красно-черное» дерево, так ваще N уменьшится...

Проблема не в N - проблема в ресетах.

return !!strstr(haystack, needle); - пж - да, да - там 2цикла

Ты бы не позорился хоть, два цикла там у него.
http://osxr.org/glibc/source/string/strstr.c
http://osxr.org/glibc/source/string/str-two-way.h
Алсо на макоси strstr действительно в два цикла, но и тормозит она соответствующе.

Где ты в моём выводе m увидел? У меня строка длины n и подстрока длины n/2.

Какие обсёры, какие обсёры. n - это длинна строки, а m - это длинна под строки. Даже если они имеют одинаковое значение - это частный случай.

Расскажи это генетикам.

aaaaaaaaa в генетике - куллстори. Примерчик привести осилишь?

Даже если они имеют одинаковое значение - это частный случай.

Ну так мы и рассматриваем худший случай. КПМ или Бойера-Мура с правилом Галила, который в glibc, и в худшем случае имеют линейную сложность.

Ты бы не позорился хоть, два цикла там у него.

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

http://osxr.org/glibc/source/sysdeps/x86_64/multiarch/strstr-sse2-unaligned.S

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

Меня не интересует говно.

Ну так мы и рассматриваем худший случай.

Никто его не рассматривает, этот случай единственное, на чем твой кмп не обосрётся.

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

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

и в худшем случае имеют линейную сложность.

Ещё раз, никому не интересен твой худший случай. Точно так же, как никому нахрен не упали в 98% подстроки длиньше 100байт и в 2% длиньше килобайта.

А теперь ты мне пойдёшь и придумаешь реальный юзкейс в котором будет «худший случай».

Подсказываю. Имеем слова: азбука, арбуз, арба, абразив, азалия (в реальности, ясен пень, слов 100500). Строим дерево: А -> {б,з,р} -> {а, б, р} и далее.

Если я правильно понял, ты переизобрел http://en.wikipedia.org/wiki/Trie

и придумаешь реальный юзкейс в котором будет «худший случай»

— Доктор, когда я вот так делаю, у меня болит.
— А вы так не делайте, лалка анскильная.

Угу.

Кому нахрен упёрлось это бесполезное говно, если ты кря-кря и не осиливаешь найти даже используемую функцию, то нахрен ты о чем-то кукарекаешь? http://osxr.org/glibc/source/sysdeps/x86_64/multiarch/strstr-sse2-unaligned.S

И тут ты обосрался. Этот код вызывает __strstr_sse2, в чём можешь убедиться в gdb, которая самая что ни на есть обыкновенная strstr по моей ссылке выше.

gdb -batch -ex 'file /lib/libc.so.6' -ex 'disassemble __strstr_sse2'

...
0x00000000000853f3 <+179>:	mov    %r9,%rsi
0x00000000000853f6 <+182>:	mov    %rax,%rdi
0x00000000000853f9 <+185>:	callq  0x84f60 <two_way_long_needle>
0x00000000000853fe <+190>:	add    $0x68,%rsp
0x0000000000085402 <+194>:	pop    %rbx
...

char s[];
int n;
s[i++] = n % 10 + '0';

В этом куске кода прибавление '0' используется для приведения типов int к char*?

Фрагмент, как можно догадаться, выдран из реализации itoa :-)

'0' + 0 == '0'; '0' + 3 == '3'. Числа от 0 до 9 преобразуются в символы от '0' до '9'. Используется тот факт, что в ASCII цифры расположены подряд.

Вроде того. Вот тебе мой вариант

Ага, то есть приращение в лексикографическом порядке имеет место быть.

И операция обратна к

s[i] - '0'

Спасибо.

Да, очень похоже.

Только там Вы еще добавили функцию, которая преобразованные байты куда-то отсылает.

Что это за микроконтроллер?

в твое реализации — нет. порядок байтов в ascii-строке от формата представления не зависит. Результат будет представлен в правильном формате автоматически.

Да уже все выяснили.

В треде даже Царь отметился :D

И это Керниган и Ритчи реализация, классика.

первая мысль

И еще, по упражнению 3.4 из сабжа.

Для корректной обработки отрицательных чисел, представленных в дополнительном коде насколько корректно (ну или красиво) вместо взятия модуля числа через дефайн и тернарную операцию, вот так

#define abs(x < 0 ? (-x):(x))

Просто переписать с

if ((sign = n) < 0)
n = -n

 n = ~n+1;

 n = ~n+1; 

в дополнительном коде ничем не отличается от

 n = -n 

Про if понятно. Я его просто опустил для краткости.

Я спрашиваю про равноценность битовой операции с «ифом» и дефайна?

Задача

Текст задачи:

В представлении чисел с помощью дополнения до двойки наша версия функции itoa не умеет обрабатывать самое большое по модуля отрицательное число, т.е. (2^word_size)-1.

Объясните, почему это так.

Доработайте функцию так, чтобы она выводила число правильно, независимо от системы, в которой она работает.

P.S. Хотя макрос делает код более ясным.

А зависит ли реализация данной функции (пусть даже в таком примитивном варианте) от порядка байтов машины на которой она выполняется?

Нет, не зависит. Порядок байтов проявляется при касте между int* и char*, например. Арифметические или битовые операции работают идентично.

равноценность битовой операции

по результату, равноценна

по скорости, на x86 -n не медленнее, может даже на такт быстрее, чем ~n+1

по читабельности, -n лучше

ну добавь в самом начале: if (arg == 0x80000000) { return_whatever; }

Вот это я и хотел узнать.

Спасибо.

atoi-test.c:

#include <stdio.h>

int atoi_test (const char *s)
{
	int i, n;
	n = 0;
	for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i)
		n = 10 * n + (s [i] - '0' ) ;
	return n;
}

int main()
{
	const char *str = "12345678";
	int n = atoi_test(str);
	printf("N = %i\n", n);

	return 0;
}

Little Endian:

$ ./atoi-test
N = 12345678

$ file ./atoi-test
atoi-test: ELF 64-bit LSB executable, x86-64

Big Endian:

$ ./atoi-test
N = 12345678

$ file ./atoi-test
atoi-test: ELF 32-bit MSB executable, PowerPC or cisco 4500

Спасибо.

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

Не надо меня на вы, да еще с большой буквы.

Микроконтроллеры разные: STM32F103, STM32F407, несколько STM8Sxxx. Функция, которая байты отсылает, сидит в обработчиках событий: если это USB, то она по сигналу готовности буфер сбрасывает; если это UART, то по прерыванию "буфер свободен" или по заполнению буфера.

#define abs(x)(x < 0 ? -(x):(x))

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

Нужно использовать одноименную библиотечную функцию.

Что еще раз как бы говорит о свежести задач в книге.

Но как теоретическая база она своей ценности не потеряла.

доработать (но там по сути — написать заново) sub filter модуль для nginx

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

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