Я вышел из того проекта, про который писал статью, но уже поучаствовал в подобной работе еще в одном проекте. Все было очень похоже и с похожим результатом. До меня этот новый проект развивался 7 лет и никто системно не занимался оптимизацией запросов. Периодически оптимизировали явные косяки, после жалоб клиентов, но все это было наскоками. За 2 месяца я сумел снизить нагрузку на БД со среднесуточной в 30-40% (часовые пики до 70%) до среднесуточных 15-20% (часовые пики до 40%). Уже два года эта нагрузка держится на этом уровне без дополнительных усилий. Поэтому, я думаю, что во многих проектах такую работу можно проводить нечасто, особенно после того как проект становится зрелым и активная разработка проекта превращается в поддержку. Хотя, в каждом проекте своя ситуация и свои особенности. Так что как с любыми "узко заточенными" специалистами решать проблему можно либо через out-source, если необходимость в таком специалисте возникает нечасто. Либо держать такого спеца в команде всеми силами, если его знания нужны постоянно и готовить ему дублера из молодых инженеров.
да, я тоже про это думал, но мне менеджер в магазине сказал что их вентиляторы нормально по ШИМ работают, хотя конечно управление через 10 вольт- намного "правильнее". Я уже думал даже взять обычную лампочку яндекса и конвертировать ее яркость в 0-10 вольт- оптрон на коленках ))
Отличный кейс! Спасибо!
Буквально вчера задумался об умной вентиляции с Алисой и пока не смог найти ответ. Как бы вы посоветовали решить такую задачку…
Хочу управлять через Алису скоростью вентилятора, ну то есть сказать "Алиса, включи вентилятор на 3-ей скорости." Чисто технически мне просто нужен ШИМ, который будет на бесколлекторный двигатель подавать ШИМ сигнал с нужной скважностью. Но как завязать Алису с таким исполнителем я пока не понимаю.
Да, вы правы, backtracking бьет по производительности поиска. Но тут возникает вопрос, какая производительность вам нужна? Возможно вы делаете разметку синтаксиса для сайта- тогда вы просто кешируете результат в базе и как быстро вы его сформировали- за 10 мс или 100 мс- не так уж важно. Не все пишут реальный компилятор или редактор кода, где скорость действительно важна. Я например обычно пишу статические анализаторы, которые собирают статистику или находят ошибки в коде. В таких задачах вообще неважно придет отчет через минуту или через полторы минуты. Самый лучший способ выиграть бой- уклониться от него. Не надо биться за скорость, если она вам на самом деле не важна.
Если же скорость важна- искользуйте движки на ДКА- там нет бэктрекинга и быстрее чем ДКА вы вряд ли что-то сможете создать в общем случае. Для каких-нибудь примитивных языков- вполне возможно, но для реальных ЯП-XML-HTML-JSON-HTML-Markdown-YML очень сомневаюсь. Регэкспы для ДКА не такие мощные, но их мне обычно хватает.
Что заставляет думать вас, что я вам навязываю свою точку зрения или претендую на истину в последней инстанции. Я рассказал про один из способов, который вы можете либо использовать либо нет. Ни в коем случае не предлагаю никому срочно бросать AntLR и начинать использовать Regex.
Пусть расцветают тысячи цветов!
Мира вам!
Дело в том, что для ДКА в отличии от НКА все равно насколько сложные регэкспы вы ему скормите и готов спорить решение с ДКА в общем случае будет всегда быстрее.
Вот посмотрите например на скорость работы алгоритмов поиска подстроки в строке.
Чего только не придумали разные авторы. Но Автоматный алгоритм Ахо-Корасика всегда выдает одну и ту же самую быструю скорость для худшего случая. Да- иногда, для особых случаев, некоторые алгоритмы на основе эвристик находят строку быстрее, но в худшем случае они проваливаются. Автомату все равно с чем иметь дело- он все находит (бьет по токенам) за один проход.
Такие вещи должны разрешаться синтаксическим анализом, а не лексическим. Токенайзер- тупой как пробка. Есть поток символов, он просто дробит поток на куски и каждому куску сопоставляет тип.
Помните что Билл Гейтс говорил, что он не понимает зачем компьютеру может понадобиться больше 640КБ памяти )))
Если серьезно, но представьте что вместо
Такое преобразование можно сделать довольно легко с помощью лексического анализатора. После преобразования, в тексте символ < всегда будет означать открытие тега, и не будет встречаться в значениях атрибутов, тексте или в закрывающем теге. Закрывающий тег будет отличаться от открывающего и однозначно соответствовать открывающему (можно будет использовать back reference).
Так вот после этого преобразования вы легко пишете регэксп, с помощью которого находите все теги и его границы (закрывающий теш), находите его атрибуты, содержание, внутренние теги… Вам придется применить одни и теже регулярные выражения много раз к одному и тому же тексту (к разным его частям), это будет не оптимальный алгоритм, но в итоге вы сможете получить полную структуру HTML документа.
Говоря кратко, чистым regexp-ом нельзя проанализировать HTML (как и любой другой нерегулярный язык), но регулярные выражения могут очень упростить синтаксический анализ, выполняя 90% всей работы.
со всяческими группировками с открывающими/закрывающими скобками всевозможных видов и их вложенностью в произвольном порядке;
В Java есть именованные скобки (named capturing group) и с их помощью можно не переживать за скобки внутри регэкспов, которые прилетают снаружи.
Либо объявить контракт, что в регэкспах для типов лексем мы не используем скобки, либо используем non-captuiring скобки (вместо (select|from) пишем (?:select|from) ) — тогда проблем не будет.
с разного вида комментариями в коде;
самый сложный комментарий я видел в HTML вот регэксп который его распознает:
с меняющейся семантикой одних и тех же конструкций в зависимости от контекста
У меня такое было при написании парсера JavaDoc комментариев, когда внутри комментария вида:
/**
*
* @param name Описание параметра
*/
Нужно было анализировать структуру. В этом случае я просто создавал второй лексер, который заточен под Javadoc.
Самый сложный случай — COBOL, где есть зависимость от колонки, то есть там первые восемь символов в строке- это просто нумерация строк, потом 72 символа- текст программы, потом с 80-го символа- комментарии. Пришлось повозиться, чтобы сделать подсветку синтаксиса, но тоже решилась проблема.
Ну и как я уже написал очень помогает в таких случаях LOOKAHEAD/LOOKBEHIND, хотя они очень замедляют скорость работы.
и, естественно, с комбинациями всего этого «адового ада».
Жизнь-боль, парсинг-труд :) На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов, не прибегая ко всяким LL1/LR0… Скорость конечно сильно падает, зато проще раз в пятьсот )))
У нас эта связка никогда не меняется- доставка не имеет шансов быть привязанной к другому счету-запросу-заявке, счет к другому запросу и запрос к другой заявке… Так что тут все оправдано.
На ютубе есть видео «от проектного IT-бизнеса к продуктовому», так вот там один докладчик сформулировал интересную мысль: «директор по продукту- это человек, главная обязанность которого- всех посылать на хрен».
Генерацию желательно запускать заранее, чтобы на момент ввода накладной наименование товара было в таблице. Но мы предусмотрели возможность ввода накладной, без этого требования. Но тогда просто накладная не попадает на следующий шаг, пока не будет добавлена «правильная» запись в таблицу товаров.
Поля для отбора мы тоже генерируем- есть дополнительная таблица атрибутов товара (да, это антипаттерн Entity-Attribute-Value)
CREATE TABLE `good_attribute` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(32) NOT NULL,
`value` varchar(32) NOT NULL,
`good_id` int(11) NOT NULL,
PRIMARY KEY (`id`),
)
Но пока эта таблица не используется- оставлена на будущее, т.к. мы используем обычный текстовый поиск, т.е. пользователь вводит что-то вроде
Шур 4 10
И мы показываем ему первые 10 вариантов, где встречаются эти подстроки. Работает довольно быстро- из нескольких миллионов позиций выборка происходит за 1-5 секунд.
Разные таблицы для параметров мы не используем т.к. заранее мы не знаем какие параметры нужны будут пользователю (для метизов это одни параметры, для труб или оборудования- совсем другие), а генерацией таблиц «на лету» мы решили не увлекаться.
Information
Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Я вышел из того проекта, про который писал статью, но уже поучаствовал в подобной работе еще в одном проекте. Все было очень похоже и с похожим результатом. До меня этот новый проект развивался 7 лет и никто системно не занимался оптимизацией запросов. Периодически оптимизировали явные косяки, после жалоб клиентов, но все это было наскоками. За 2 месяца я сумел снизить нагрузку на БД со среднесуточной в 30-40% (часовые пики до 70%) до среднесуточных 15-20% (часовые пики до 40%). Уже два года эта нагрузка держится на этом уровне без дополнительных усилий.
Поэтому, я думаю, что во многих проектах такую работу можно проводить нечасто, особенно после того как проект становится зрелым и активная разработка проекта превращается в поддержку. Хотя, в каждом проекте своя ситуация и свои особенности. Так что как с любыми "узко заточенными" специалистами решать проблему можно либо через out-source, если необходимость в таком специалисте возникает нечасто. Либо держать такого спеца в команде всеми силами, если его знания нужны постоянно и готовить ему дублера из молодых инженеров.
Про Blynk от вас впервые услышал, пойду изучать.
А вот про 5 скоростей нигде не видел, можете линком поделиться?
да, я тоже про это думал, но мне менеджер в магазине сказал что их вентиляторы нормально по ШИМ работают, хотя конечно управление через 10 вольт- намного "правильнее". Я уже думал даже взять обычную лампочку яндекса и конвертировать ее яркость в 0-10 вольт- оптрон на коленках ))
Отличный кейс! Спасибо!
Буквально вчера задумался об умной вентиляции с Алисой и пока не смог найти ответ. Как бы вы посоветовали решить такую задачку…
Хочу управлять через Алису скоростью вентилятора, ну то есть сказать "Алиса, включи вентилятор на 3-ей скорости." Чисто технически мне просто нужен ШИМ, который будет на бесколлекторный двигатель подавать ШИМ сигнал с нужной скважностью. Но как завязать Алису с таким исполнителем я пока не понимаю.
Да, вы правы, backtracking бьет по производительности поиска. Но тут возникает вопрос, какая производительность вам нужна? Возможно вы делаете разметку синтаксиса для сайта- тогда вы просто кешируете результат в базе и как быстро вы его сформировали- за 10 мс или 100 мс- не так уж важно. Не все пишут реальный компилятор или редактор кода, где скорость действительно важна. Я например обычно пишу статические анализаторы, которые собирают статистику или находят ошибки в коде. В таких задачах вообще неважно придет отчет через минуту или через полторы минуты. Самый лучший способ выиграть бой- уклониться от него. Не надо биться за скорость, если она вам на самом деле не важна.
Если же скорость важна- искользуйте движки на ДКА- там нет бэктрекинга и быстрее чем ДКА вы вряд ли что-то сможете создать в общем случае. Для каких-нибудь примитивных языков- вполне возможно, но для реальных ЯП-XML-HTML-JSON-HTML-Markdown-YML очень сомневаюсь. Регэкспы для ДКА не такие мощные, но их мне обычно хватает.
Что заставляет думать вас, что я вам навязываю свою точку зрения или претендую на истину в последней инстанции. Я рассказал про один из способов, который вы можете либо использовать либо нет. Ни в коем случае не предлагаю никому срочно бросать AntLR и начинать использовать Regex.
Пусть расцветают тысячи цветов!
Мира вам!
Дело в том, что для ДКА в отличии от НКА все равно насколько сложные регэкспы вы ему скормите и готов спорить решение с ДКА в общем случае будет всегда быстрее.
Вот посмотрите например на скорость работы алгоритмов поиска подстроки в строке.
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8
Чего только не придумали разные авторы. Но Автоматный алгоритм Ахо-Корасика всегда выдает одну и ту же самую быструю скорость для худшего случая. Да- иногда, для особых случаев, некоторые алгоритмы на основе эвристик находят строку быстрее, но в худшем случае они проваливаются. Автомату все равно с чем иметь дело- он все находит (бьет по токенам) за один проход.
Такие вещи должны разрешаться синтаксическим анализом, а не лексическим. Токенайзер- тупой как пробка. Есть поток символов, он просто дробит поток на куски и каждому куску сопоставляет тип.
Есть регэксп движки на ДКА (сам делал). Вряд ли вы что-то сделаете быстрее ДКА.
Косил косой косой косой )))
Лексический анализатор тут беспомощен- вся надежда на синтаксический!
Я всю жизнь парсеры пишу ))) Написал штук 20-30 для разных языков, чего-чего, а парсеров я точно не боюсь )))
Помните что Билл Гейтс говорил, что он не понимает зачем компьютеру может понадобиться больше 640КБ памяти )))
Если серьезно, но представьте что вместо
Вы преобразуете в вид
Такое преобразование можно сделать довольно легко с помощью лексического анализатора. После преобразования, в тексте символ < всегда будет означать открытие тега, и не будет встречаться в значениях атрибутов, тексте или в закрывающем теге. Закрывающий тег будет отличаться от открывающего и однозначно соответствовать открывающему (можно будет использовать back reference).
Так вот после этого преобразования вы легко пишете регэксп, с помощью которого находите все теги и его границы (закрывающий теш), находите его атрибуты, содержание, внутренние теги… Вам придется применить одни и теже регулярные выражения много раз к одному и тому же тексту (к разным его частям), это будет не оптимальный алгоритм, но в итоге вы сможете получить полную структуру HTML документа.
Говоря кратко, чистым regexp-ом нельзя проанализировать HTML (как и любой другой нерегулярный язык), но регулярные выражения могут очень упростить синтаксический анализ, выполняя 90% всей работы.
По порядку:
В Java есть именованные скобки (named capturing group) и с их помощью можно не переживать за скобки внутри регэкспов, которые прилетают снаружи.
Либо объявить контракт, что в регэкспах для типов лексем мы не используем скобки, либо используем non-captuiring скобки (вместо (select|from) пишем (?:select|from) ) — тогда проблем не будет.
самый сложный комментарий я видел в HTML вот регэксп который его распознает:
Можно поиграться
Вот пример для JS строк
С примером
У меня такое было при написании парсера JavaDoc комментариев, когда внутри комментария вида:
Нужно было анализировать структуру. В этом случае я просто создавал второй лексер, который заточен под Javadoc.
Самый сложный случай — COBOL, где есть зависимость от колонки, то есть там первые восемь символов в строке- это просто нумерация строк, потом 72 символа- текст программы, потом с 80-го символа- комментарии. Пришлось повозиться, чтобы сделать подсветку синтаксиса, но тоже решилась проблема.
Ну и как я уже написал очень помогает в таких случаях LOOKAHEAD/LOOKBEHIND, хотя они очень замедляют скорость работы.
Жизнь-боль, парсинг-труд :) На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов, не прибегая ко всяким LL1/LR0… Скорость конечно сильно падает, зато проще раз в пятьсот )))
Поля для отбора мы тоже генерируем- есть дополнительная таблица атрибутов товара (да, это антипаттерн Entity-Attribute-Value)
Но пока эта таблица не используется- оставлена на будущее, т.к. мы используем обычный текстовый поиск, т.е. пользователь вводит что-то вроде
И мы показываем ему первые 10 вариантов, где встречаются эти подстроки. Работает довольно быстро- из нескольких миллионов позиций выборка происходит за 1-5 секунд.
Разные таблицы для параметров мы не используем т.к. заранее мы не знаем какие параметры нужны будут пользователю (для метизов это одни параметры, для труб или оборудования- совсем другие), а генерацией таблиц «на лету» мы решили не увлекаться.