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

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

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

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

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

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

По крайней мере так было год назад, может за это время они уже оптимизировали этот момент.
 
Silent
еще раз повторяю:
существуют алгоритмы поиска эффективнее конечного автомата.
 
Demiurg

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

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

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

-~{}~ 23.02.04 22:08:

>это остаётся тайной разработчиков за семью печатями.
искодники открыты..
 
> Какой алгоритм использует 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;
}

т.е. никаких суперсложных алгоритмов там нет.
И объяснение этому простое.

Процедуры посимвольного сравнения строк настолько быстрые, что "оптимизировать" их никакого смысла нет.
 
Ты думаешь, Лердорф этого не знает?.. ;)
А если знает -- почему не реализовал?
 
Не реализовано потому, что никому до этого дела нет. Общая происводительность скриптов от этого не увеличится.
 
Demiurg, по техническим причинам код проверки не приведу, не обессудь. Но он в точности повторяет код, выложенный на первой странице топика, только исходные данные многократно дублированы. А ты проверял на скорость РВ и поиск подстроки без теории, на голом эксперименте? Если да, то мне интересны результаты
 
Войдите или зарегистрируйтесь для ответа.
Сверху