Меню
Что нового?

Помогите с паттэрном

Demiurg

Guest
Найч
хорошо, поиск большой подстроки в большом объеме данных. Что будет быстрее ?
Кстати, никто из любителей регулярных выражений пока не вспомнил, что при подставновке произвольного теката в паттерн его(текст) надо еще и экранировать.
 

Silent

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

preg_match("/[Ww][Oo][Rr][Dd].*[Ww][Oo][Rr][Dd]/s",$data);

для больших строк это быстрее, чем

preg_match("/word.*word/si",$data);

По крайней мере так было год назад, может за это время они уже оптимизировали этот момент.
 

Demiurg

Guest
Silent
еще раз повторяю:
существуют алгоритмы поиска эффективнее конечного автомата.
 

Silent

Новичок
Demiurg

А я ведь не зря добавил в свое выражение ".*", потому что ожидал от тебя этого. Я говорю про случаи, когда нам НУЖНО использовать реги. И тогда тот способ, что я привел, оказывается быстрее, чем модификатор "i".

P.S. А если говорить про мой способ, который не нуждается в приведении строки в нижний регистр, и твой способ, где сначала нужно создать копию строки, перевести ее в нижний регистр а потом уже искать с помощью быстрого алгоритма, то еще не известно, что будет быстрее.
 

Demiurg

Guest
Silent
в твоем случае кроме всего еще будет много откатов, если word окажется не в конце текста. Да и отошел ты от темы, надо было искать _точное_ совпадене без учета регистра.
 

Silent

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

Demiurg

Guest
приведенный тобой пример не ищет точное совпадение.
 

Silent

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

Найч

Алгоритмик :-)
Demiurg
>хорошо, поиск большой подстроки в большом объеме данных. Что будет быстрее ?
Возможно, я криво мерял все это дело, но при поиске в 10к строки порядка 500 символов реги заметно опережают поиск подстроки с приведением регистра. Как ни прискорбно мне это признавать.
По-моему, причина в том, что strtolower мы заставляем проверять _весь_ текст, потом до встречи совпадения идем strpos'ом (или до конца - неважно). В то время как РВ необходимые преобразования делают по ходу. В определенный момент запаса алгоритма strpos оказывается недостаточно. Опять же, тут много спорных моментов.
Например, как именно работают реги. Какой алгоритм использует strpos. Как проводить тест. Ведь я брал статический текст в котором в первой сотне символов встречается искомое вхождение.
Против регов вижу пока только одно - задачи на обработку большой массы встречаються редко.
Кстати, Demiurg, я когда-то рассматривал алгоритмы поиска, и, если мне не изменяет память, самый быстрый из широко известных обгонял посимвольное сравнение раз в 12. С учетом тормозной strtolower можно найти предел инфы, где реги будут проигрывать.
И еще. Неужели реги так вот посимвольно сравнивают? Что-то слабо вериться...
 

SiMM

Новичок
Автор оригинала: Найч
Опять же, тут много спорных моментов.
Например, как именно работают реги. Какой алгоритм использует strpos.
Нажмите для раскрытия...
К сожалению, из мануала это не ясно - это остаётся тайной разработчиков за семью печатями. Да и мало кого, думаю, подобные детали интересуют.
Неужели реги так вот посимвольно сравнивают? Что-то слабо вериться...
Нажмите для раскрытия...
По моему, у них нет другого выбора, хотя наверняка какая-то оптимизация preg-выражений существует (было бы интересно почитать на русском что-нибудь из теории по этому вопросу), но как правило универсальные алгоритмы медленнее неуниверсальных.
 

Demiurg

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

>Неужели реги так вот посимвольно сравнивают? Что-то слабо вериться...
в классике так, достаточно понять как работает движок. Хотя не отрицаю, что в его реализации могут быть оптимизаторы, которые и производят поиск по тем самым быстрым алгоритмам.

-~{}~ 23.02.04 22:08:

>это остаётся тайной разработчиков за семью печатями.
искодники открыты..
 

гоша

Guest
> Какой алгоритм использует strpos

Код: 
static inline char * php_memnstr(char *haystack, char *needle, int needle_len, char *end)
{
	char *p = haystack;
	char ne = needle[needle_len-1];

	end -= needle_len;

	while (p <= end) {
		if ((p = memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
			if (!memcmp(needle, p, needle_len-1)) {
				return p;
			}
		}
		
		if (p == NULL) {
			return NULL;
		}
		p++;
	}
	return NULL;
}
т.е. никаких суперсложных алгоритмов там нет.
И объяснение этому простое.

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

гоша

Guest
Ты думаешь, Лердорф этого не знает?.. ;)
А если знает -- почему не реализовал?
 

Demiurg

Guest
Не реализовано потому, что никому до этого дела нет. Общая происводительность скриптов от этого не увеличится.
 

Найч

Алгоритмик :-)
Demiurg, по техническим причинам код проверки не приведу, не обессудь. Но он в точности повторяет код, выложенный на первой странице топика, только исходные данные многократно дублированы. А ты проверял на скорость РВ и поиск подстроки без теории, на голом эксперименте? Если да, то мне интересны результаты
 
Войдите или зарегистрируйтесь для ответа.
Сверху