Немного о решении, которое могло бы занять призовое место на конкурсе Hola по программированию
Invite pending
Под конец 2015 года компания Hola организовала конкурс по программированию., и я решил попробовать поучаствовать в нем (к слову сказать, это мой первый опыт в участии в более менее серьезных конкурсах). К сожалению, я занял лишь 20-е место по результатам конкурса. К еще большему моему сожалению, мое решение могло бы занять третье место. Если бы я не сделал глупой ошибки.
Под катом немного о моем решении и интересных, на мой взгляд, выводах по итогам конкурса.
А наделал я вот что. Так как фильтр должен быть бытсрым (главное условие конкурса), то надо было обзавестись хоть какой-то отправной точкой. Ну и естественным образом это простое решение на регулярных выражениях с полным перебором адресов и тестированием по всем правилам.
Сказано — сделано.
Но это же явно самое неоптимальное решение, значит надо его улучшить, раскрыть весь его потенциал. Значит проведем оптимизацию: убираем лишние проверки, там где они не нужны; сводим количество использования регулрок к минимуму; оптимизируем обход объекта по ключам и прочие тривиальные вещи.
Вот, теперь у нас есть работающее решение с более менее вменяемым быстродействием (в комментарих к конкурсной статье люди менялись своими достижениями). Можно окунуться глубже и попробовать другие подходы, например исключающие использование «медленных» регулярок.
Однако я присмотрелся и увидел, что в общем-то код и так быстро работает, согу ли я написать что-то быстрее? Усомнился я в себе и решил оставить такой подход.
Но все равно потенциал же есть еще и у текущего решения. Конечно же, мемоизация. Она-то мне и поможет. А тут я перехитрил сам себя, начал мудрить с тем, что же мне кешировать, что бы и работало быстро и прирост давало. Ну и перемудрил, получалось медленнее оригинала без кеша.
Попробовал я пару подходов с замудренной мемоизацией и разочаровался в ней настолько, что самый простой кеш к целому письму не применил, отправил решение как было.
Тут-то я и занял 20-е место. В комментариях к первоначальным результатм конкурса добрый хабровчанин rmaksim указал на мою оплошность. Я конечно не плакал, но расстроился. Поправил решение и отправл для участия вне конкурса.
Мог бы занять 3-е место. Думаю, если бы еще там подкрутить чего, мог бы и второе занять.
Почитал я комментарии, посмотрел решения и вот что подумалось. А ведь какое просто решение у меня, без каких-либо алгоритмических заморочек и прочего, а какой при этом результат шикарный (представим, что я кеш не забыл).
Вот и получается, везде пишут, что регулярки медленные, что можно сделать быстрее, приводят алгоритмы. А толку? И почему так? Из-за языка? Код медленнее работает, чем выполнение регулярок в движке?
Честно говоря, я не думал, что мое решение может так высоко подняться как раз из-за его простоты и бесхитростности, а получилось иначе.
Вот такой инетерсный поворот, на мой взгляд.
Под катом немного о моем решении и интересных, на мой взгляд, выводах по итогам конкурса.
Что же я наделал?
А наделал я вот что. Так как фильтр должен быть бытсрым (главное условие конкурса), то надо было обзавестись хоть какой-то отправной точкой. Ну и естественным образом это простое решение на регулярных выражениях с полным перебором адресов и тестированием по всем правилам.
Сказано — сделано.
Но это же явно самое неоптимальное решение, значит надо его улучшить, раскрыть весь его потенциал. Значит проведем оптимизацию: убираем лишние проверки, там где они не нужны; сводим количество использования регулрок к минимуму; оптимизируем обход объекта по ключам и прочие тривиальные вещи.
Вот, теперь у нас есть работающее решение с более менее вменяемым быстродействием (в комментарих к конкурсной статье люди менялись своими достижениями). Можно окунуться глубже и попробовать другие подходы, например исключающие использование «медленных» регулярок.
Однако я присмотрелся и увидел, что в общем-то код и так быстро работает, согу ли я написать что-то быстрее? Усомнился я в себе и решил оставить такой подход.
Но все равно потенциал же есть еще и у текущего решения. Конечно же, мемоизация. Она-то мне и поможет. А тут я перехитрил сам себя, начал мудрить с тем, что же мне кешировать, что бы и работало быстро и прирост давало. Ну и перемудрил, получалось медленнее оригинала без кеша.
Попробовал я пару подходов с замудренной мемоизацией и разочаровался в ней настолько, что самый простой кеш к целому письму не применил, отправил решение как было.
Тут-то я и занял 20-е место. В комментариях к первоначальным результатм конкурса добрый хабровчанин rmaksim указал на мою оплошность. Я конечно не плакал, но расстроился. Поправил решение и отправл для участия вне конкурса.
Мог бы занять 3-е место. Думаю, если бы еще там подкрутить чего, мог бы и второе занять.
А выводы-то?
Почитал я комментарии, посмотрел решения и вот что подумалось. А ведь какое просто решение у меня, без каких-либо алгоритмических заморочек и прочего, а какой при этом результат шикарный (представим, что я кеш не забыл).
Вот и получается, везде пишут, что регулярки медленные, что можно сделать быстрее, приводят алгоритмы. А толку? И почему так? Из-за языка? Код медленнее работает, чем выполнение регулярок в движке?
Честно говоря, я не думал, что мое решение может так высоко подняться как раз из-за его простоты и бесхитростности, а получилось иначе.
Вот такой инетерсный поворот, на мой взгляд.