LINUX.ORG.RU

K&R C Вопрос

 , , ,


0

2
/* atoi: преобразует строку s в целое число */

int atoi (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;
}

Возник вопрос на интуитивном уровне:

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

cast beastie

Перемещено JB из talks

★★★★★

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

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

А выкати это куда-то

http://www.lib.ru/INPROZ/MARKTWAIN/adventtomsaw_eng.txt_Ascii.txt

#!/usr/bin/env python
import random

with open("adventtomsaw_eng.txt_Ascii.txt") as f:
	s = f.read()
words = s.split()
marks = ("CENSORED", "O RLY", "####", "????????")
for k in range(2000):
	line = " ".join(random.choice(words) for j in range(3))
	line = line.replace("'", "\\'")
	print("   sub_filter '{}' '{}';".format(line, random.choice(marks)))

i-rinat ★★★★★
()
Ответ на: комментарий от TrueTsar1C

С учётом регистра?

Регистронезависимо в пределах ASCII.

i-rinat ★★★★★
()
Ответ на: комментарий от TrueTsar1C

Кстати, какой там сейчас state-of-the-art алгоритм для поиска многих строк сразу? Можешь закодить его, если задача слишком простая.

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

подписался на тред. если перенесете обсуждение куда-нибудь, скастаните, пожалуйста

MyTrooName ★★★★★
()
Ответ на: комментарий от i-rinat

Кстати, какой там сейчас state-of-the-art алгоритм для поиска многих строк сразу?

И я хочу. А то на ум приходит только построение дерева шаблонов и пропускание каждого очередного символа по этому дереву.

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

Да пофиг мне, что там в хрюникоде вашем. Я его даже палкой тыкать не собираюсь! Пусть валяется, воняет...

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

Боюсь, даже если выкопать, там уже нечего резать...

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

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

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

А то на ум приходит только построение дерева шаблонов и пропускание каждого очередного символа по этому дереву.

Алгоритм Ахо-Корасик это усовершенствование описанного тобой подхода, с обратными связями, чтобы не откатываться к корню дерева. Ему уже больше сорока лет. В начале 2000-х были свежие работы на тему поиска строк.

i-rinat ★★★★★
()
Ответ на: комментарий от MyTrooName

как на таких архитектурах называется 8-битный тип

По аналогии с тем, как на x86 называется 5-битный тип. Никак.

i-rinat ★★★★★
()

Если ты скастуешь char* к int* — тогда будет зависить, а в твоем случае — нет.

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

Там говорят про размер char'а и кодировки, а не порядок байт. Если предположить что кодировка ASCII ­— то ничего от порядка байт не зависит, т.к. ты не разбираешь int по байтам прямым приведеним указателей или union'ами.

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

Нет там такого типа.

(Хотя к 8-битным половинам char-a обратиться можно, с помощью особой магии, и в техасовских, например, доках они обтекаемо описываются словами «8-bit entities».)

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

Я вот об этом:

K&R C Вопрос (комментарий)

Если ты скастуешь char* к int* — тогда будет зависить, а в твоем случае — нет.

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

Не вижу, чем каст мог радикально изменить картину, если char там по-старинке на 8 бит.

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

Нахрена читать по байту если есть возможность читать словами?

это типичный случай преждевременной оптимизации. Современные процессоры всё равно читать по байтам не умеют, и будут читать словами. А компилятор это сам оптимизирует. Если в коде жёстко захордкорить, то появятся проблемы.

emulek
()
Ответ на: комментарий от i-rinat

Кстати, какой там сейчас state-of-the-art алгоритм для поиска многих строк сразу?

Понятия не имею - можешь найти, если хочешь. Я нихрена в этом не понимаю.

Можешь закодить его, если задача слишком простая.

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

Если не лень можешь помочь поискать.

Собственно как будет время - запилю. И ещё пару вопросов - т.е. если у нас в словаре есть «ab», «abc», «abcd» - то какой у нас поиск жадный/нет?

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

построение дерева шаблонов

Что это?

Задача примитивное ленейное говно и даже бревна тут не надо, авось если ты решишь:

Какбэ как я вижу основную проблему - это ресет поиска после фейла. Т.е. на строке «abcdeeee» на поиске слова «abcdf» - мы будем ресетится на «*bcdeeee»->«**cdeeee» и т.д. Т.е. худний случай n*максимальная_длинна_слова_в_словаре.

И чёт поглядев на всякие корасики в википедии я так и не понял как они это решают, собственно как твоё дерево это решает?

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

если у нас в словаре есть «ab», «abc», «abcd» - то какой у нас поиск жадный/нет?

Вообще без разницы. Можно считать это неопределённым поведением.

i-rinat ★★★★★
()
Ответ на: комментарий от emulek

это типичный случай преждевременной оптимизации.

Нет, эти типичный случай эмулека, аля «слышал звон, да не знаю где он».

Современные процессоры всё равно читать по байтам не умеют

Процессоры читают так, как ты читаешь в коде. И по байтам тоже.

и будут читать словами

Нет, будут читать тем, что ты напишешь.

А компилятор это сам оптимизирует.

Дак конпелятор или процессор? Ты уж определись. И да, конпелятор ничего не оптимизирует.

Если в коде жёстко захордкорить, то появятся проблемы.

Какие проблемы - чего «захордкорить»? Что ты несёшь.

Давай я тебе расскажу с чего в твоей башке эта херня про «нечитает» взялась. Не читает процессор память/n+1левелкеш не кешлайнами, но это никакого отношения к коду не имеет, ибо у тебя нет никакого доступа к памяти и читает твой код всегда л1. В дефолтных условиях.

А читает процессор так, как читаешь ты в коде. Ещё раз.

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

лалка анскильная. может, за тебя еще код написать?

Ты его чтоли напишешь? Маловероятно, поэтому нахрен ты мне пишешь?

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

И чёт поглядев на всякие корасики в википедии я так и не понял как они это решают, собственно как твоё дерево это решает?

Капец. И вот ЭТО вот еще что-то кукарекает за программирование?

А может царь вообще не настоящий?

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

примитивное ленейное говно
худний случай n*максимальная_длинна_слова_в_словаре

Это называется квадратичная сложность.

чёт поглядев на всякие корасики в википедии я так и не понял как они это решают

Изучи для начала классику: http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

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

Это называется квадратичная сложность.

Это не квадратичная сложность, алёша.

Изучи для начала классику: http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Да ты я посмотрю прошаренный, балаболка. Нахрен ты эту херню выкатил? К чему вообще? Ты реально настолько туп, либо притворяешься?

Тут нет такой проблемы, ибо нет вообще ресета, нахрен ты высираешься, если нихрена не понимаешь в теме? Алёша.

При фейле сравнения начинается с i+1.

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

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

И тебе я даю возможность обосраться - ты мне пишешь, как и анонимус реплейс, т.е. просто дан key-value словарь, тебе надо заменить всех вхождения key на value.

Вперёд, ты же не просто кукарекаешь.

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

Это не квадратичная сложность, алёша.

Рассмотрим худший случай. Возьмём строку длины n вида «aaa...aaa» и подстроку длины n/2 вида «aaa...aab». В итоге наивная strstr сделает (n/2)*(n/2) сравнений — внутренний цикл крутится по всей подстроке, внешний по каждому символу половины строки (дальше не имеет смысла) — что есть O(n^2). Обосрамс.

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

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

Смухлевать решил?

i-rinat ★★★★★
()
Ответ на: комментарий от TrueTsar1C

Ты его чтоли напишешь? Маловероятно, поэтому нахрен ты мне пишешь?

конечно, не стану писать. ты думал на меня свою работу спихнуть?

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

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

Для чистоты эксперимента выложи свою реализацию strstr на двух циклах. Не хочу, чтобы ты кукарекал при замере производительности, что код плохой.

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

А царь-то не настоящий!

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

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

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

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

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

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

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

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

чиво?

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

я не царь, я знаю, что такое RBT, а если бы не знал, то гуглить умею. расскажи лучше, каким боком они относятся к задаче и как позволят «уменьшить N»

MyTrooName ★★★★★
()
Последнее исправление: MyTrooName (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.