Комментарии 114
Шикарно!
Имхо, вместо инкрементального поиска года/месяца/etc. лучше использовать Segment Tree для быстрого поиска начала и конца интервала.
Не совсем так. Segment tree я так понимаю строит дерево с листьями для каждого интервала. В нашем случае это по идее нарушит требование эффективности для расписания с 1мс интервалом — дерево получится слишком большим. Википедия пишет что
A segment tree T on a set I of n intervals uses O(n log n) storage.
Беря N = 3155760000000 (DateTime.Parse("2100-01-01") - DateTime.Parse("2000-01-01")).TotalMilliseconds
Получаем 35 268 гигабайт на то, чтобы сохранить все интервалы для кейса "звездочка во всех расписаниях".
А вот что можно улучшить — так это использовать бинарный поиск вместо инкремента. О чем хотел написать в раздел улучшений, но забыл. Спасибо, что напомнили. Изначально не сделано так же из соображений лимита по времени — написан самый просто перебор, в котором меньше всего шансов ошибиться, да и не факт, что будет лучше. Скорее всего имеет смысл так только изначальный год подбирать, а дальше оставлять текущий алгоритм.
Ммм, не уверен, что понял. Звёздочка должна быть представлена одним интервалом в дереве: [0 ; int.MaxValue].
Ну хорошо, пусть будет *.*.* * *:*:*.*/2 — т.е. только четные миллисекунды. Получится куча интервалов по 1 мс, правильно ведь?
Я бы сделал так:
1) Для каждого сегмента шаблона (год, месяц, день, час, минута, секунда, миллисекунда) завёл бы segment tree с таким интерфейсом:
enum SearchDirection
{
Forward,
Backward,
}
class SegmentTree
{
public void AddSegment(int from, int to, ISegment segment) {...}
// Возвращает сегмент, в который попадает number.
// Если number не попадает ни в один сегмент, возвращает ближайший с учётом searchDirection.
public ISegment GetSegment(int number, SearchDirection searchDirection) { ... }
}
interface ISegment
{
int? GetFirstMatch(int number, SearchDirection searchDirection);
}
// Класс, представляющий интервал годов/месяцев/дней/часов/минут/секунд/миллисекунд. Интервал может быть представлен единственным числом.
class Interval : ISegment
{
// from == to для случая, когда значение указано без диапазона
Interval(int from, int to) {...}
int? GetFirstMatch(int number, SearchDirection searchDirection)
{
return number;
}
}
// Класс, представляющий интервал годов/месяцев/дней/часов/минут/секунд/миллисекунд с учётом шага
class IntervalWithStep : ISegment
{
IntervalWithStep(int from, int to, int step) {...}
int? GetFirstMatch(int number, SearchDirection searchDirection)
{
var offset = number - this.from;
if (offset % this.step == 0)
{
// Если попали в шаг, возвращаем number
return number;
}
// Если не попали в шаг, возвращаем ближайшее подходящее значение с округлением. Если это значение выходит за пределы интервала, возвращаем null.
var increment = searchDirection == SearchDirection.Forward ? 1 : -1;
var result = this.from + (offset / this.step + increment) * this.step;
return result < this.from || result > this.to ? null : result;
}
}
2) При конструировании дерева наполнял бы его разными типами нодов: для простых констант и интервалов - Interval, для интервалов с шагом - IntervalWithStep.
То есть, для случая "*.*.* * *:*:*.*/2" все деревья, кроме дерева миллисекунд, содержали бы по одному ноду Interval, у которого from=0, to=int.MaxValue.
Дерево для миллисов содержало бы один нод IntervalWithStep (from=0, to=int.MaxValue, step=2).
3) Поиск похож на ваш: сначала ищем интервал для года, вызываем у него GetFirstMatch(date.Year), дальше делаем то же самое для месяца, дня и т.д. Если на каком-то из этапов GetFirstMatch возвращает null (т.е. вышли за пределы интервала), то берем следующий сегмент. Где-то мог ошибиться в логике, но вроде бы должно работать.
Ну вот таким образом формат уже больше схож на тот, что я использовал. Теперь вопрос — а нужно ли нам тут дерево? Может bool[] вполне достаточно? :)
Учитывая, что количество лет потенциально неограниченно, мне кажется, дерево всё же предпочтительнее :)
Ну и не совсем понятно, как вы организуете бинарный поиск в случаях интервалов с шагом: например, 0-999/2.
Предположим, я передал дату 2000-01-01 00:00:00:001.
Очевидно, она не подпадает под шаблон. В каком диапазоне делать поиск? [2;999]? Среднее значение будет 500. Оно подпадает под шаблон, но по сути неверное, т.к. следующее верное значение - 2.
Но у нас количество лет как раз ограниченное, и эту информацию имеет смысл использовать в задаче. Ведь опять же, вспоминая доменную область — мы пишем кусок планировщика задач. Планировать задачи в 999999 год после нашей эры никто наверное не собирается. Хотя я верю в оптимизм людей, конечно же.
Точно, не заметил ограничения в задаче.
Тем не менее, если бинарный поиск не подходит, то линейный поиск подходящей миллисекунды в среднем обойдётся в 500 итераций цикла для случая, когда в шаблоне указано единственное конкретное значение. В случае с деревом сложность будет O(1).
Согласен, я изначально тоже использовал дерево (как в Quartz), но мне не понравилось это решение. Давайте предположим такое расписание:
*/4.*/4.*/4 */4 */4:*/4:*/4.*/4
Как будет выглядеть дерево для него?
Это будет не одно дерево, а 8 деревьев, в каждом по одному ноду IntervalWithStep (from=0, to=int.MaxValue, step=4).
Хм, а step как работать будет? Потому что я вот смотрю на описание Segment Tree в википедии и там step не виду.
И потом, допустим у нас в дереве хранится два значения IntervalWithStep (from=0, to=int.MaxValue, step=4) и IntervalWithStep (from=3, to=int.MaxValue, step=2).
Как нам теперь узнать, какое из них наступит раньше для, скажем, знчения 17?
Ок, для таких случаев должны возвращаться оба интервала. Step работает уже на следующем уровне: когда мы получили интервал, определяем, попадает ли искомая компонента даты под шаг. Если попадает, возвращаем её. Если нет, возвращаем ближайшее число, удовлетворяющее шагу и направлению поиска.
А что нам в итоге тут дерево дает? Нам все равно в итоге нужно все интервалы параллельно проверять, потому что у нас нет информации какой из них наступает раньше. В этом случае у нас их два, но может быть и три, и четыре, и так далее. Как например быть в случае шаблона 1,3,6,8,11,13,16,18,...?
Кажется, что оно не очень хорошо будет работать, как минимум нужно пытаться писать некоторую "смерживалку", которая будет пытаться объединить интервалы. И то на подобных интервалах с рваным шагом (2-3 между каждым) она вряд ли что-то сможет сделать. А задача разбить это на минимальное количество шаблонов — нетривиальная сама по себе кмк. И немного выходит за рамки тестового.
Но опять же, критерий истинности — практика, если покажете код который это считает я смогу произвести замеры и сравнить.
Надо будет проверять только пересекающиеся интервалы. В случае с большим количеством значений через запятую будет просто много нодов в дереве, но в результате поиск вернёт только один интервал за O(logN).
Пока что я не готов написать рабочий код из-за отсутствия времени. Может, на выходных доберусь, если тема будет ещё актуальна :)
Можно за O(1) же делать. Сначала получили как у автора булевый массив. Потом (еще при парсинге) прошлись туда-обратно и предподсчитали для каждого индекса, где стоит следующая/предыдущая еденица в массиве.
Места будет в 33 раза больше занимать, да, но там суммарно будет ну 4kb, вместо 125 байт. Не страшно.
Пока у меня вот такой результат получается. В некоторых тестах дерево работает медленнее, даже чем в FindNextOld, но зато в сложных случаях показывает 15х производительность.
P.S. Я пока сделал только поиск вперед. Все тесты проходятся нормально.
Можете дописать тесты на 1,3,6,8,11,13,16,18? В каждом месяце\дне\часе\минуте? Интересно, что выйдет.
Да, тут всё плохо :) Для даты 2001-01-01 ваш алгоритм сразу находит единицу, поэтому работает быстро. Моему приходится искать в дереве, и единица будет самым глубоким левым нодом, поэтому ищется долго.
Шаблон был таким:
*.1,3,6,8,11.1,3,6,8,11,13,16,18 1,3,6,8,11,13,16,18:1,3,6,8,11,13,16,18:1,3,6,8,11,13,16,18
Цикл по миллисекундам ничего не делает кроме проверки флага в массиве, тут итерации нет смысла считать если их не много тысяч. Итераций где идут изменения даты/времени — не более чем 283 в самом худшем случая когда минимальный год сравнивают с максимальным.
Зачем делать 283 итерации, если можно сделать один поиск в дереве, содержащем один элемент?
Хотя, конечно, без понимания, в каких условиях будет использоваться код, и без проведения перформанс-тестов, невозможно сказать, что будет эффективнее - массивы или деревья. Если в шаблоне будет указано, например, 990 значений миллисекунд через запятую, то поиск значения в дереве в среднем займёт ~5 итераций (при глубине дерева log2(990) ~ 10), а поиск в массиве ~1 (т.к. почти все ячейки будут true).
Я уже предлагал ваш вариант с эффективным хранением календаря в комментах первой статьи, но меня заминусовали. Они будут создавать массив флагов на 5 кБ, потом героически осуществлять поиск в нем с помощью milliseconds++, а потом писать статью на эту тему.
Только вместо "дерево", надо говорить "массив". Данные надо хранить в восьми массивах.
Потому что 283 итерации - это константа. Которая зачастую перебьется тем фактом, что вы вместо простой и кэш-френдли структуры массива использовуете развесистое дерево.
Т.е. нужно бенчать, конечно же, но если честно, на глаз дерево не дает сильной выгоды.
Напрашивается анализ исходных данных и выбор формата в зависимости от того что пришло. Конструктор чуть медленее, зато поиск быстрее.
Чтобы совсем упороться по оптимизации.
Поиск в цикле — тоже O(1) — тут же ограничен размер массива. Но дерево может быть быстрее на неокторых тестах, да.
Можно держать массив следующих точек (и отдельно прошлых). Заранее посчитать, как-то так:
_nextAllowedPoints = new short[_allowedPoints.Length];
short lastPoint = -1;
for (short i = (short)(_allowedPoints.Length - 1); i >=0; i--)
{
if (_allowedPoints[i])
{
lastPoint = i;
_nextAllowedPoints[i] = 0;
}
else if (lastPoint < 0)
{
_nextAllowedPoints[i] = lastPoint; // -1
}
else
{
_nextAllowedPoints[i] = (short)(lastPoint - i);
}
}(уже сказали выше)
Upd:
Ах да, в тексте про это ниже увидел
Странно, что в C# из java не передрали метки циклов (тогда без goto можно было бы ссылаться на внешние циклы в break и continue):
mainloop: for (int v : a) {
for (int w : b) {
if (v == w)
continue mainloop;
}
System.out.println(v);
}
За отрезок времени в 51 год можно было создать процессор, который изначально думает текстом, и отдать ему все Unix системы.
Классно, но меня все же смущает GOTO, это по Кнуту преждевременная оптимизация в случае тестого задания. Интересно, как бы автор подошел к данной части если бы использовал F#.
Во-первых не вижу, чем goto тут является оптимизацией — это решение эргономической проблемы "проверяем условие а потом опять проверяем его же чтобы продолжить цикл". То что мы 1 проверку лишнюю убираем просто приятный бонус, основной смысл — не копипастить лишний раз, вводя дополнительную вероятность ошибки.
Во-вторых не вижу, чем тут F# бы отличался — на нем все точно так же будет, только с привкусом ML синтаксиса.
Во-вторых не вижу, чем тут F# бы отличался
Я имел в виду только оптимизацию с ГОТО. Не уверен, что в вашем случае получилось бы заменить ГОТО на более элегантное решение с двойной взаимоисключающей хвостовой рекурсией. Как в данной статье:
- http://sharp-gamedev.blogspot.com/2011/08/forgotten-control-flow-construct.html
Раз уж речь зашла про монады, почему бы не попробовать хвостовую рекурсию(с ее оптимизацией) вместо ГОТО.
Ну если мы про ФП и F# в частности, то там стоило бы воспользоваться правилом использовать для контроля флоу типы, а не стейтменты (не знаю, как по русски сказать).
Например сделать enum WhatToDo { Continue, Break }. Тогда можно вынести внутренню часть цикла в функцию:
private (DateTime, WhatToDo) ClosestBody<TIsIncrementing>(DateTime t1)
where TIsIncrementing : struct, IBool
{
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = yearChanger.Change<TIsIncrementing>(t1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = monthChanger.Change<TIsIncrementing>(t1);
if (t1.Year != year)
{
return (t1, WhatToDo.Continue);
}
}
// ...Тогда сам цикл становится просто:
private DateTime Closest<TIsIncrementing>(DateTime t1) where TIsIncrementing : struct, IBool
{
while (true)
{
var (t2, whatToDo) = ClosestBody<TIsIncrementing>(t1);
if (whatToDo == WhatToDo.Continue)
{
t1 = t2;
}
else
{
return t2;
}
}
}Достаточно умный компилятор смог бы выоптимизировать использование этого энума и получить примерно то же, что и мы. Но шарповый джит, увы, так не умеет, поэтому тут будет терятся перф во-первых на перекидывание таплов туда-сюда, во-вторых на сам вызов функции. Но чисто функционально будет эквивалентно — все тесты проходят (см. бранч)
Так-себе-код и нормальный код по времени пишутся одинаково долго, но с одним из них работать комфортнее в будущем, а в другой будет противно заглядывать с доработками. Правда, нужно иметь опыт, чтобы было из чего выбирать — чтобы взять хорошее решение про его существование нужно знать.
В рамку и на стену.
Как-то странно в одной статье видеть рассуждения около AggressiveInlining используя парсер, который медленней в 50 раз.
К сожалению, после замены старого джита на RyuJit он сильно потупел и не догадывается без подсказки соптимизировать подобные кейсы
Я бы не стал делать такие поспешные выводы. Может x86 и туппее (но он устрел и мало кому нужен в 2021 году), но x64 инлайнит правильно. А вот .NET Framework как раз генерирует какую-то дичь.
Не увидел в статье ссылки на полные исходники, можно ткнуть?
Да, я сделал апдейт минут 20 назад, совсем забыл их приложить. См. вложение.
Как-то странно в одной статье видеть рассуждения около AggressiveInlining используя парсер, который медленней в 50 раз.
Я отдельно написал, почему я считаю это неважным — какая разница, отрабатывает парсер за 0.5мкс или за 50мкс, если его вызывают один раз на старте приложения или при изменении расписания в файлике? У какого-нибудь FileWatcher'а который будет мониторить изменения этого файла разрешающая способность меньше, чем время работы всего этого парсера. Поэтому я считаю, что считать тут разницу в разах — задача неблагодарная, оба парсера справляются с работой за достаточное для любого разумного (и не очень) сценария использования.
В чем и суть — оптимизировать надо то, что нужно оптимизировать. По заветам Фаулера и Макконела. Несмотря на замедление парсинг в 50 раз я бы ожида как раз увеличение производительности в общем случае. Дествительно, положим что мой поиск следующего события занимает 900нс, а оригинальные — 1000нс. Также возьмем, что расписание обновляется каждую секунду, а нагрузка на сервер составляет 10к запросов в секуду. Тогда получаем суммарное потраченное в секунду на работу: для старого 500*1+10000*1000, нового: 17000*1+10000*900. Посуммировав, выходит 10 000 500нс для старого кода и 9 017 000нс для нового.
Всё таки возможен случай если заявят экстремальные требования по памяти и парсинг нужно будет перенести прямо в методы поиска ближайшего времени, запоминая в конструкторе только исходную строку.
Так перенос в методы не скорит работу, а только замедлит. Если интервьювер этого не понимает то нужно просто поблагодарить его за потраченное время, встать и уйти.
Я действительно не вижу сценария с изменением расписания каждые 500 наносекунд, который выглядит реалистичным. Если у них другой бизнес-процесс где это требуется то было бы любопытно услышать. Но по факту с такими требованиями им действительно не сишарп, а раст надо было бы брать. Отсюда вывод, что это маловероятно.
Собственно, опять же свои прикидки/оценки/гипотезы все озвучил в статье, и решение сделано исходя из них, и других критериев вроде поддерживаемости, про которые я тоже написал. Если какие-то из них неверны — ну, значит и решение может быть нужно будет изменить в соответствии с условиями. Я исходил из того, что мне казалось наиболее рациональным/вероятным. Но я не ванга, это правда.
Экстремальные требования по памяти обычно приводят к замене шарпов на что-то с AOT компиляцией и детерминированной работой с памятью.
Прошу прощения, немного пропустил этот момент:
Я бы не стал делать такие поспешные выводы. Может x86 и туппее (но он устрел и мало кому нужен в 2021 году), но x64 инлайнит правильно. А вот .NET Framework как раз генерирует какую-то дичь.
Он инлайнит правильно, потому что вы ему подсунули атрибут "инлайни блин!". А вот если его убрать, то и код получается другой. Мне казалось, что старый x64 джит справлялся без подсказок. Но, видимо, это ложная память — нашарплабе не могу воспроизвести. Так что видимо стоит извиниться перед рюджитом — старый судя по всему был не лучше)
Он инлайнит правильно, потому что вы ему подсунули атрибут "инлайни блин!".
Тут тоже не все однозначно — возможно .NET заинлайнит и такое, если это будет часто вызываться, т.к. доступна tiered компиляция.
А вообще можно призвать Nagg — может он лучше знает :)
Да, понятно, что он может заинлайнит. Проблема в том, что может и нет — а нам нужны какие-то гарантии. А для гарантий нужно обвешиваться атрибутами.
Впрочем, не то, что это было слишком сложно. Но в уме держать нужно.
В .NET 6.0 инлайнер стал намного агрессивнее (см. https://github.com/dotnet/runtime/pull/52708 и https://github.com/dotnet/runtime/pull/55478) и инлайнит такое без проблем теперь.
О, вот это любопытно, спасибо. Хотя там вроде про PGO (не наш случай) и свитчи (возможно, наш, но нужно проверять). По крайней мере на sharplab'е я не нашел ветки, на которой без атрибута оно бы соптимизировалось. Даже на найтли коммите мастера от 8 августа.
1) Нет, там не только PGO
2) На шарплабе нет возможности выбирать рантаймы новее .NET 5.0 релиз.
свитч тут не причем, в том коде он разворачивается в обычные ифы розлином
Да, вы правы. Похоже что #7651 это как раз то, что нужно. Ну супер.
В очередной раз снимаю шляпу перед вашим мастерством. Приятно читать статьи и видеть подобные пуллреквесты.
У кого есть опыт по тестовым заданиям, скажите, как заказчики отнесутся к реализации парсинга через комбинаторы из библиотеки Pidgin?
Обычно, когда работодатель хочет хардкора, он так и говорит, "запили на ванильных шарпах". Если ничего такого не говорят, то вы вольны выбирать сторонние библиотеки на ваш выбор. Это кстати тоже может быть частью проверки ваших навыков на "велосипедность".
Этот вопрос надо уточнять у работодателя. Некоторые разрешают, а некоторые категорически против использования каких-либо библиотек. А некоторые не могу внятно ответить, можно ли что-либо использовать. У меня как-то был случай, что дали задание - написать экспорт из бд в *.XLSX. По поводу использования библиотек - сказали сделать на мое усмотрение. Написал с использованием библиотеки ClosedXML и код получился вообще простой. В итоге задание не зачли! Сказали с ClosedXML любой дурак напишет) Переделывать не стал, послал их)
Эта статья похожа на текущую. Или автор один и сидит под разными учётками? А то странно как-то получается: 2 статьи на одну тему и примерно в одно время.
О нет, нас раскрыли!
Может быть, стоит прочитать хотя бы первый абзац статьи перед тем как писать комментарий? На текущий момент там есть, в том числе, та самая ссылка которую вы привели...
Безусловно стоит, но на момент написания комментария ее там не было. К сожалению, сейчас я это доказать уже не смогу.
Да ну? А я могу доказать, что он там был. Вот гист, где я изначально правил очепятки и прочее в статье. Идем в самую первую ревизию, и видим там вот это:
Я буквально начал текст с этого, потому что хотел, чтобы автор той статьи заменшнился и пришел почитать.
Так что да, стоило прочесть первый абзац.
Ну интервьюверы тоже люди, пожалейте их. :)
Мысли и действия вполне разумны, но почему-то вылились в безумно размытый и сложный код.
Спасибо за отзыв.
А можеет ткнуть пальцем конкретно, где сложность? И в чем размытость? Потому что самая сложная часть — парсинг — намного проще, чем оригинальный авторский код. И точно куда проще регулярки, которая бы парсила то же самое. А что до остального — один цикл с парой брейков и функция с целым одним генериком.
А что формат сложный — ну, это к авторам вопрос) Был бы проще формат — был бы проще парсер.
Почему-то на мой взгляд код с if-ами куда проще читаем, чем этот.
Класс, хочу тоже когда-нибудь так шарить)
Код читаем: его реально можно прочитать. Нужен парсинг — пошли посмотрели 50 строчек тут, нужно понять как маппится — 20 строчек там, нужно понять, как ищем расписания — ничего проще, вот ещё немного кода.Я пошёл смотреть код ещё до прочтения статьи, и открыл вот это. Неподготовленный человек это не поймёт. Куча интерфейсов, подменяющих неясно зачем bool и структур, которые называются в стиле «менятель года», но в случае с FalseType (?) они меняют вообще миллисекунды (??), при этом создавая новый DateTime (???).
Я к чему. После прочтения статьи мне стало ясно и для чего такие структуры, и для чего goto. К принятым решениям вопросов нет, но чтобы такой код стал читаем — его нужно аккуратно и понятно документировать. Конечно, этот код — просто иллюстрация к статье, бла бла бла, но это должно быть, всё-таки, стандартным подходом.
P.S. IBool бы я вообще заменил на Direction, а TrueType и FalseType на Forward и Back или типа того, уж очень вводит в заблуждение.
Куча интерфейсов — это два?)
А в остальном все верно, как я в конце написал, есть куда улучшать/расширять. Как опять же говорили классика, разница по стоимости между программой и программным продуктом — отличается на порядки. Я решил простенькую проблему, которую просили в изначальной постановке, а вот со сложнейшими проблемами правильного именования вещей разобраться так просто не всегда выходит. Типы названы от балды, потому что на момент их написания заканчивался последний 8й час, отведенный на работу, и нужно было просто запустить, удостовериться что результаты остаются корректными и начать писать статью. Конечно же, можно и нужно лучше, просто я поленился.
Куча интерфейсов — это два?)Ага, но тут слово «куча» относится и к интерфейсам, и к структурам, т.е. подразумевается прочтение «куча интерфейсов и структур».
Что я могу тут ответить — чем дальше сидишь над тестовым заданием, тем труднее соблюдать хорошие практики, рассовывать сущности по правильным файлам, корректно их именовать и вот это все. Вспоминая известную картинку
так-себе-код и нормальный код по времени пишутся одинаково долгоНормальный код всё-таки требует большего внимания к «мелочам», и — увы — займёт больше времени, но на дистанции это оправдается
Если читать снизу вверх, то похоже на эволюцию продукта от стартапа с одним разработчиком до SCRUM команды с комит полиси.
Я, все же, обычно дописываю до точки, и причесываю код и структуру проекта перед отправкой. А если ставят дедлайны, лучше попросить больше времени или забить на потенциально стрессовое место работы. Еще нужно понимать, что если у вас получается долго, то это не значит, что у другого кандидата выйдет быстрее при одинаковом качестве результата. Возможно авторы задания просто недооценили его сложность.
Там в конце так и просится коммит "Не так уже и нужна мне эта работа..."
Монадический парсер — очень клево.
Вы вот повторяете, что решение на регулярках выглядело бы ужасным. См. мое: https://gist.github.com/vlova/544d693cc4083caafa477383b2e1c216. Неужели вам и вправду кажется, что такое решение ощутимо сложнее и read-only? (Но я согласен, что у регулярок есть много других недостатков в сравнении с полновесным парсером)
К слову, о перфомансе парсера. Из того, что я прочитал о Pidgin, часть замедления идет от того, что он не полностью компилируется. В теории, если кто-то упрется в перфоманс Pidgin, то может быть резонно подправить его внутренности, а не переписывать код. В таком случае решение @novarне будет выигрывать вообще никак.
Ну, да, согласен, думал, что выйдет хуже. Но все равно кода довольно много (45..177 — больше сотни строк). И тут как раз минус в том, что нельзя собрать парсер из "кубиков" — нужно парсить сразу всё или ничего. Получилось выделить отдельно ParseCronSubRange — это конечно намного упростило результирующую регулярку. Но вот основной формат, увы, приходится матчить по принципу "пан или пропал".
Но да, в таком аккуратном виде это в принципе можно читать и расширять.
К слову, о перфомансе парсера. Из того, что я прочитал о Pidgin, часть замедления идет от того, что он не полностью компилируется. В теории, если кто-то упрется в перфоманс Pidgin, то может быть резонно подправить его внутренности, а не переписывать код. В таком случае решение novarне будет выигрывать вообще никак.
Ну в теории возможно вообще всё, языки ведь тьюринг-полные) Вопрос тут только в том, насколько легко можно подлезть туда, чтобы это можно было сделать. Я обожаю зиро-кост стейт машины, что асинк, что парсеры, что итераторы — в общем, любые монадки которые оптимизируются в ноль в рантайме это прям огромное удовольствие. Пару лет назад был доклад ребят, который писали красивый код в ду-нотации который в их монаде интерпретировался как ассемблер конкретного процессора, и генерировался оптимальный код, лучше, чем тот, что выдает компилятор на этой платформе. Это прям замечательный доклад был, жалко, я записи в интернете не смог найти. Этим же кстати крут раст — там итераторы/асинки оптимизируются зирокостно так, что иногда могут быть более производительными, чем ручная реализация. Просто потому, что компилятору разрешено несколько больше, чем обычному пользователю, при этом он достаточно умный чтобы сгенерировать код не хуже ручного.
Но все равно кода довольно много (45..177 — больше сотни строк).
Кода много, потому что используется только C#. Очевидно, что Pidgin как решение для парсинга будет предоставлять определенный сахар.
Кроме того, этот код является эквивалентом ParserHelper.cs 23-117 + ScheduleFormat.cs 21-71. Итого, у вашего решения 144 строки, у моего 132. Можно играться в подсчет строк и дальше, но вряд-ли найдется подсчет, показывающий существенную разницу.
И тут как раз минус в том, что нельзя собрать парсер из "кубиков" — нужно парсить сразу всё или ничего. Получилось выделить отдельно ParseCronSubRange — это конечно намного упростило результирующую регулярку. Но вот основной формат, увы, приходится матчить по принципу "пан или пропал".
Это ошибочное восприятие. Основной формат матчится целиком, потому что разбивать матчинг на блоки поменьше — это не очень осмысленно. Но мы, конечно же можем их разбить, просто получится чуть больше кода.
А вот в вашем случае вам просто необходимо разбивать на отдельные кубики, потому что если не разбить, то не получится пометить кубик как Optional.
Вопрос тут только в том, насколько легко можно подлезть туда, чтобы это можно было сделать.
Нужно реализовать свой IQueryable, который будет при создании query делать агрессивный инглайнинг Expression<Func<>> внутрь друг друга. В принципе, я не вижу такой уж сложности в задаче. Но работы предстоит дофига, конечно.
В случае миллисекунд их отсутствие значит не [0, 1, … 999], а [0].
В остальных случаях экономия будет несущественная, зато просядет производительность и читабельность (за счет дополнительного if).
Ну да, мы сэкономим немного памяти (до 2кб суммарно) и слегка ускорим кейс со звездочками. Но при этом мы ощутимо замедлим все остальные сценарии, потому что теперь у нас будет _allowedPoints?[point - Begin] ?? true, и факт разрешенности точки будет прятаться за ifом.
Плюс у нас не получится иметь текущий интерфейс с разрешением конкретных точек, придется его менять, чтобы передавать _allowedPoints в конструкторе. В целом, ничего страшного, но нужно это учитывать.
В общем, выигрываем мы на этом или нет — спорно, мне кажется, что так не стоит делать. Но без замеров сказать ничего не получится, в любом спорной ситуации нужно расчехлять профайлер и проверять, догадка — залог оверинженерного кода в будущем)
Upd. Выше уже написали, и да, там верно написали про отдельный случай с миллисекундами. Как раз из-за того что мы вшили ?? true в структуру, которая раньше была очень простой и не имела логики никакой, вся логика была в отдельном слое (SRP). А теперь мы часть логики переложили туда и немножко продолбались, и тут уже либо костылять конкретно под миллисекунды (например, принимать в конструкторе аргумент "что делать если нулл"), либо просто так не делать.
Теперь интересно послушать мнение того, кто это задание выдавал.
Это switch expression. Не должен быть тотальным с точки зрения компилятора. Рантайм просто кинет исключение, если не найдёт подходящего кейса. См. https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/switch-expression#non-exhaustive-switch-expressions
Хотя там написано, что в случае нетотальности получишь варнинг. И не очень понятно, как это проверяется, так что возможно ваш вопрос ещё актуален.
В сишарпе он вставляет неявно дефолтный кейс с паникой (выбрасыванием эксепшна). Так что тут просто варнинг а-ля [-Wincomplete-patterns] Pattern match(es) are non-exhaustive. Тотальность соответственно никак не проверяется, более того, тотальности тут и нет, т.к. никакого аналога скаловым кейс классам тут нет и никто не запрещает реализовать интерфейс другими типами. Так что тут все на честном слове джентельмена "других реализаций писать не будем" и дисциплине, увы.
Отдельно хочу отметить линейную структуру поиска без триллиона if — почувствуйте сами, насколько велика разница в восприятии
так первоначальный вариант тоже предлагали переписать с инвертированием условий и continue после неудачи. мне такой вариант (без вложенных циклов) нравится больше.
сравните
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = monthChanger.Change<TIsIncrementing>(t1);
if (t1.Year != year)
{
goto LoopStart;
}
}vs
if (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = monthChanger.Change<TIsIncrementing>(t1);
continue;
}да, ваше решение будет немного производительнее, в реальной же жизни особой разницы не будет (что и показывает ваш бенчмарк).
Бенчмарк показывает улучшение в 2 раза в некоторых случаях, так что сложно сказать, что он ничео не показывает. Нужно просто больше форматов сравнить (хотя бы штук 30), но подбирать грамотно опять же данные для бенчмарка этот нетривиально, и выполняться оно будет часами. Никто не спорит, что можно было оставить оригинальный алгоритм, просто инвертировав условия, я просто немного иначе сделал.
За счет своей монадичности (т.е. композабельности)
Обожаю эти пояснения)
Вооружившись магией ООП берем и за 2 минуты реализуем нужный функционал
…
В итоге через пару дней проглядывая код
Хм. Статьи про плохих hr и плохие тестовые на Хабре любят.
А что если автору на работе надо было написать поддерживаемый код. Но вместо переделки старого он выдумал историю и стал ждать элегантное решение в комментариях ? А тут как раз ещё статья появилась. А может ещё и не одна появится
Даже если так, то ничего плохого я не вижу. Люди посмотрели, примерили разные алгоритмы и паттерны, поделились своим мнением. Все вынесли какие то уроки для себя, произошло развитие. Ну а я, как автор исходной статьи, не стал бы пытаться выгораживать свой код и оправдываться если бы хотел лишь получить улучшенный вариант.
Что это решение, что оригинальное — обладает одним существенным недостатком. Вместо того, чтобы быстро передвигаться к следующему числу в интервале, мы делаем инкремент и проверку, пока не найдем подходящее число. Это довольно тупо — мы же следующее число знаем.
Я решил сделать следующее. Взять SortedSet. С помощью SortedSet быстро находить следующее/предыдущее число в интервале. Потом еще отдельно проверил вариацию, что будет, если добавить мемоизацию. Итого, версия с чисто SortedSet в отдельных случаях дает ускорение x10; в большинстве случаев - наравне. Версия с SortedSet + мемоизация в отдельных случаях дает ускорение x20, в большинстве случаев - x2-x3.
Бенч FindNext
| Method | Pattern | DateString | Mean | Error | StdDev | Ratio | RatioSD |
|---------------------------------- |--------------------- |----------- |------------:|----------:|----------:|------:|--------:|
| FindNextNovar0 | *.*.1 0:0:0 | 2001-01-01 | 17,993.6 ns | 175.25 ns | 155.35 ns | 1.00 | 0.00 |
| FindNextPzixel | *.*.1 0:0:0 | 2001-01-01 | 18,085.6 ns | 101.72 ns | 84.94 ns | 1.01 | 0.01 |
| FindNextPzixelLovaSortedSet | *.*.1 0:0:0 | 2001-01-01 | 2,090.6 ns | 22.42 ns | 20.97 ns | 0.12 | 0.00 |
| FindNextPzixelLovaSortedSetCached | *.*.1 0:0:0 | 2001-01-01 | 1,365.3 ns | 27.37 ns | 58.32 ns | 0.08 | 0.00 |
| | | | | | | | |
| FindNextNovar0 | *.*.1 0:0:0 | 2080-05-05 | 2,594.6 ns | 50.99 ns | 60.70 ns | 1.00 | 0.00 |
| FindNextPzixel | *.*.1 0:0:0 | 2080-05-05 | 978.1 ns | 5.79 ns | 5.42 ns | 0.37 | 0.01 |
| FindNextPzixelLovaSortedSet | *.*.1 0:0:0 | 2080-05-05 | 730.2 ns | 14.18 ns | 13.92 ns | 0.28 | 0.01 |
| FindNextPzixelLovaSortedSetCached | *.*.1 0:0:0 | 2080-05-05 | 476.1 ns | 2.17 ns | 1.93 ns | 0.18 | 0.00 |
| | | | | | | | |
| FindNextNovar0 | *.4.6(...)-20/3 [31] | 2001-01-01 | 824.9 ns | 14.71 ns | 12.28 ns | 1.00 | 0.00 |
| FindNextPzixel | *.4.6(...)-20/3 [31] | 2001-01-01 | 489.4 ns | 7.31 ns | 6.48 ns | 0.59 | 0.01 |
| FindNextPzixelLovaSortedSet | *.4.6(...)-20/3 [31] | 2001-01-01 | 940.0 ns | 13.61 ns | 13.36 ns | 1.14 | 0.02 |
| FindNextPzixelLovaSortedSetCached | *.4.6(...)-20/3 [31] | 2001-01-01 | 390.7 ns | 6.33 ns | 7.03 ns | 0.47 | 0.01 |
| | | | | | | | |
| FindNextNovar0 | *.4.6(...)-20/3 [31] | 2080-05-05 | 1,414.5 ns | 14.78 ns | 13.10 ns | 1.00 | 0.00 |
| FindNextPzixel | *.4.6(...)-20/3 [31] | 2080-05-05 | 1,112.4 ns | 22.10 ns | 27.95 ns | 0.79 | 0.02 |
| FindNextPzixelLovaSortedSet | *.4.6(...)-20/3 [31] | 2080-05-05 | 1,313.8 ns | 6.49 ns | 5.75 ns | 0.93 | 0.01 |
| FindNextPzixelLovaSortedSetCached | *.4.6(...)-20/3 [31] | 2080-05-05 | 624.6 ns | 9.78 ns | 8.67 ns | 0.44 | 0.01 |
| | | | | | | | |
| FindNextNovar0 | *.9.*(...)0.000 [24] | 2001-01-01 | 1,898.9 ns | 9.64 ns | 8.55 ns | 1.00 | 0.00 |
| FindNextPzixel | *.9.*(...)0.000 [24] | 2001-01-01 | 1,249.0 ns | 23.94 ns | 21.22 ns | 0.66 | 0.01 |
| FindNextPzixelLovaSortedSet | *.9.*(...)0.000 [24] | 2001-01-01 | 927.7 ns | 7.54 ns | 5.88 ns | 0.49 | 0.00 |
| FindNextPzixelLovaSortedSetCached | *.9.*(...)0.000 [24] | 2001-01-01 | 396.4 ns | 7.85 ns | 13.75 ns | 0.20 | 0.01 |
| | | | | | | | |
| FindNextNovar0 | *.9.*(...)0.000 [24] | 2080-05-05 | 1,661.2 ns | 22.89 ns | 21.41 ns | 1.00 | 0.00 |
| FindNextPzixel | *.9.*(...)0.000 [24] | 2080-05-05 | 999.3 ns | 19.71 ns | 18.44 ns | 0.60 | 0.02 |
| FindNextPzixelLovaSortedSet | *.9.*(...)0.000 [24] | 2080-05-05 | 979.9 ns | 19.18 ns | 32.04 ns | 0.59 | 0.03 |
| FindNextPzixelLovaSortedSetCached | *.9.*(...)0.000 [24] | 2080-05-05 | 393.0 ns | 7.74 ns | 10.07 ns | 0.23 | 0.01 |
| | | | | | | | |
| FindNextNovar0 | 2100.(...)9.999 [23] | 2001-01-01 | 26,448.1 ns | 411.22 ns | 384.66 ns | 1.00 | 0.00 |
| FindNextPzixel | 2100.(...)9.999 [23] | 2001-01-01 | 25,061.1 ns | 485.91 ns | 631.82 ns | 0.95 | 0.03 |
| FindNextPzixelLovaSortedSet | 2100.(...)9.999 [23] | 2001-01-01 | 1,910.0 ns | 37.01 ns | 34.62 ns | 0.07 | 0.00 |
| FindNextPzixelLovaSortedSetCached | 2100.(...)9.999 [23] | 2001-01-01 | 627.6 ns | 7.83 ns | 6.54 ns | 0.02 | 0.00 |
| | | | | | | | |
| FindNextNovar0 | 2100.(...)9.999 [23] | 2080-05-05 | 22,327.4 ns | 436.84 ns | 597.95 ns | 1.00 | 0.00 |
| FindNextPzixel | 2100.(...)9.999 [23] | 2080-05-05 | 20,506.1 ns | 403.14 ns | 431.36 ns | 0.93 | 0.03 |
| FindNextPzixelLovaSortedSet | 2100.(...)9.999 [23] | 2080-05-05 | 1,957.0 ns | 34.26 ns | 30.37 ns | 0.09 | 0.00 |
| FindNextPzixelLovaSortedSetCached | 2100.(...)9.999 [23] | 2080-05-05 | 648.9 ns | 12.93 ns | 22.31 ns | 0.03 | 0.00 |Модификациям в основном подверглись два файла, их можно глянуть здесь: PzixelLovaSchedule.cs и здесь ScheduleInterval.cs.
Подозреваю, что заменить мемоизацию на предпосчет, то вообще очень шустро будет.
Хорошее решение, опять же, не влезло по бюджету времени)
Вот этот момент любопытный:
private int NextPointUncached(int point)
{
if (point >= End)
{
return point + 1;
}
return _allowedPoints.GetViewBetween(point + 1, End).Cast<int?>().FirstOrDefault()
?? Math.Max(point + 1, End);
}Итак, что тут происходит? Вот допустим у нас разрешены только первые 3 месяца, а мы тыкаем в четвертый. Тогда эта функция возвращает 12 (по числу месяцев). Хотя это не является валидной точкой. Т.е. функция выходит не возвращает следующую валидную дату, а просто меняет её на ту, которая ближе (по идее) к ней, но не гарантирует, что мы попали куда нужно. После чего мы попадаем туда же второй раз, нам возвращается цифра 13, мы перескакиваем год и дальше начинаем пересчет с самого начала.
Подход в любом случае классный, думал про него, но опять же решил, что это сложнее чем то что я готов сейчас реализовывать) Спасибо за то, что поделились
Да, на границах там ярый костыль, потому что сильно морочиться не хочется. И получилось квадратно-гнездовое.
Если по-хорошему. В случае, если у нас разрешены первые 3 месяца (1,2,3), а мы тыкаем в 4-й, то мы должны увеличить год и перенести на первый месяц. Т.е. должны выдать что-то типа (End + _allowedPoints.Min). Но это не будет работать для дней (потому что 32 и потому что разное количество дней в месяце) — а это уже черт знает как поправить.
Подозреваю, что заменить мемоизацию на предпосчет, то вообще очень шустро будет.
ну это очевидная идея хранить вместо флага «подходит/не подходит» номер следующего подходящего, ЕМНИП в комментариях к первоначальной статье её высказывали.
но (особенно с учётом того, что поиск нужен в две стороны) ИМХО это оверкилл для тестового задания.
да и не для тестового, я бы остановился на варианте с минимумом LoC (ну и с максимально понятным/простым кодом, хотя, конечно, это субъективный показатель). а если уж нужны будут жёсткие оптимизации — идти дальше (в 99.999999% случаев они не нужны)
Чтобы не использовать goto, можно вынести содержимое верхнего while в отдельную функцию и делать return
Задание нормальное, как на джуна так и на сениора (c)
)))))
Не знаю шарпа, но прочитал с удовольствием, спасибо. :)
Единственно, у вас тут противоречие)
Задание нормальное, как на джуна так и на сениора: просто у них решение будет отличаться.
В общем, задание в целом странноватое: слишком сложное для джуна, слишком долгое для сениора.
А нельзя эту задачу решить без построения велосипедов? Прикрутить имеющийся парсинг или либу?
И я так и не понял, где история эпичного фейла прочитав всю статью
история фейла в соседней статье https://habr.com/ru/post/571342/
что за Char('*').Map , почему у меня такого нет?
Я решил велосипедами.
Также фэйл: "Ваше решение не работает".
https://github.com/Vladislav-Petrovykh/ScheduleProject
Кто нибудь тестил все возможные вариации заданных форматов года/месяца/дня и т.д.?
Все варианты проверить невозможно :) Можно проверить только достаточно много. Я взял авторские тесты кои проверяют емнип штук 30 разных форматов. Можно было бы заморочиться и взять какие-нибудь проптесты, чтобы они генерировали примеры. Было бы чуть надежнее, там можно было бы проверить на сотнях разных инпутов, но это уже точно не вписывается в рамки тестового.
Почему не все тестовые задания одинаково полезны: разбор одного фееричного провала