Всем привет, это PsyHaSTe и сегодня я хотел бы рассказать о том, куда меня занесла нелегкая в процессе оптимизации и рефакторинга кода решения тестового задания из статьи товарища novar (кто пропустил — рекомендую ознакомиться). Какие проблемы были у этого решения? Почему все-таки человеку отказали в работе? Что можно с этим сделать? Ответы на эти и многие другие вопросы оказались слишком длинными для комментария и вылились в статью с подробным разбором, примерами и альтернативной реализацией задания.
Если вам интересно кто в здравом уме мог для выполнения поставленной задачи написать код сочетающий монады с goto, а также одновременно сократил объем кода и увеличил его производительность, то добро пожаловать под кат. И, конечно же, самое вкусное, связанное с оптимизациями на базе работы JIT — в конце. Итоговую версию решения тестового можно посмотреть на гитхабе по ссылке.
Итак, начнем с изначальной постановки задачи. Т.к. в исходной постановке она звучит как "сделай то не знаю что, см. вложение" то дам краткую выжимку на основании этого самого тестового задания:
Реализовать класс для задания и расчета времени по расписанию. Расписание задано в стиле crontab (точный формат см. во вложении), требуется находить ближайшие в будущем или прошлом моменты, попадающие в это расписание. Обращаю Ваше внимание, что класс должен быть эффективным и не использовать много памяти и ресурсов даже тогда, когда в расписании задано много значений. Например очень много значений с шагом в одну миллисекунду.
Класс (без километровых XML комментов) который нам предлагается реализовать выглядит так:
public class Schedule
{
public Schedule() : this("*.*.* * *:*:*.*")
{
}
public Schedule(string scheduleString) { }
public DateTime NearestEvent(DateTime t1) { }
public DateTime NearestPrevEvent(DateTime t1) { }
public DateTime NextEvent(DateTime t1) { }
public DateTime PrevEvent(DateTime t1) { }
}Пожалуй, начнем со своей реализации, а потом сравним с версией из оригинальной статьи.
Что мы тут видим? В частности, конструктор отделен от использования. Это нас должно навести на мысль, что операция парсинга происходит не так часто, т.к. нам имеет смысл создать инстанс с разобранным расписанием. Откуда можно заключить, что основные оптимизации (и эффективность) должны касаться занимаемого в памяти места и времени работы методов (но не конструктора). Почему? Как минимум, потому что у нас дан класс Schedule, а для авторов тестового задания было бы странно говорить про эффективность типа, который постоянно нагружает GC — логичнее было бы использовать структуру. Ну и в целом, с точки зрения здравого смысла логично, что расписания задаются не так часто, как по ним ищут (можно посмотреть на практику использования того же крона, формат которого нам предлагают реализовать). Следовательно, конструктор вызывается сравнительно редко.
С этим решили. Теперь нам нужно выбрать структуру данных, по которой можно эффективно искать расписания. "Список событий" мы отметаем сразу из-за ремарки про 1мс интервалы — можно посчитать сколько миллисекунд с 2000 по 2100 год (диапазон дат из нашего задания), это слишком дофига. Поэтому, вооружившись гуглом, идем и смотрим, как реализовали "правильные ребята". Я лично для этого ознакомился с двумя файлами: файлами самого крона и библиотекой Quartz. Откуда заключаем, что самый разумный формат — просто хранить признаки подходит ли нам некоторая временная точка (год, день, ...) или нет. Вооружившись магией ООП берем и за 2 минуты реализуем нужный функционал:
public readonly struct ScheduleInterval
{
public int Begin { get; }
public int End { get; }
private readonly bool[] _allowedPoints;
public ScheduleInterval(int begin, int end)
{
Begin = begin;
End = end;
_allowedPoints = new bool[end - begin + 1];
}
public bool IsPointAllowed(int point) =>
_allowedPoints[point - Begin];
public bool ChangePointAllowance(int point, bool value) =>
_allowedPoints[point - Begin] = value;
// пара вспомогательных методов опущена
}Отлично, у нас есть замечательная структура, по которой удобно искать. Но на входе у нас всего лишь строка. Как нам из одного получить другое? Ну, на самом деле у нас есть несколько вариантов, по пунктам:
- Писать разбор руками — долго, муторно, подвержено ошибкам. А ещё очень долго. Из плюсов — можно выжать максимальный перформанс, максимальную гибкость (важно для бектрекинга, хороших ошибок и всего этого). Но, мы не компилятор пишем, поэтому плюсы нам не очень важны (вспоминая, что парсинг вызывается только в конструкторе), а вот минусы очень жесткие. Тем более, что в рамках тестового мы ограничены по времени. Поэтому — нет
- Писать разбор регулярками — во-первых, учитывая все нюансы формата, регуляркой парсить её замучаешься. Во-вторых, реуглярка фигово композируется — да, можно куски объявить строковыми константами и потом интерполировать куда-то в результирующую регулярку, но моя практика показывает, что обычто это совершенно нечитаемо выходит. И в-третьих, сам результат работы реуглярки придется парсить — из всех этих матчей придется выдирать группы, пытаться сопоставить их друг с другом. Вариадичность формата добивает окончательно.
- Писать разбор парсер-генератором — это всякие ANTLR и т.п. — моё скромное ИМХО что это оверкилл для такой задачи. В целом можно было бы использовать, но я не очень уверенно себя чувствую в декларативном написании грамматик
- Писать разбор парсер-комбинатором — а вот это уже более-менее. Производительность разбора приемлемая (хотя существенно медленнее, чем ручной разбор), легко композируется, легко эмбедится в решение. Пожалуй, его и возьмем. Что там в дотнете есть? Окей гугл, "parser combinator C#". О, некий Pidgin в первой строчке. Звезд достаточно, последние коммиты свежие — берём.
Парсер-комбинатор
Итак, что такое парсер-комбинатор? Это простой монадический тип, который позволяет описывать преобразование из потока токенов (в нашем случае char[]) в некий структурированный вывод. За счет своей монадичности (т.е. композабельности) их можно сцеплять друг с другом, получая более продвинутые парсеры. Чем мы и займемся. Начнем с простого — научимся парсить звёздочки.
// вспомогательный класс, который будет хранить наши парсеры
public static class ParserHelper
{
// Парсер встречает значение char '*' Результат парсера - юнит
// (т.е. тип, имеющий ровно одно значение) - брат близнец void,
// но в отличие от него может использоваться везде, где ожидается тип
public static Parser<char, Unit> Asterisk { get; } =
Char('*').Map(_ => Unit.Value);
}Отлично, давайте напишем пару тестов, чтобы удостовериться, что мы не ошиблись:
[Fact]
public void Asterisk()
{
ParserHelper.Asterisk.ParseOrThrow("*");
Assert.Throws<ParseException>(() =>
ParserHelper.Asterisk.ParseOrThrow("hello"));
}Отлично, парсинг успешен. Теперь нам нужно научиться парсить цифры. Нет ничего проще:
// парсим список цифр, идущих подряд.
// Затем вызываем int.Parse, чтобы преобразовать их в число
Parser<char, int> NumberParser { get; } =
Digit.AtLeastOnce().Map(s => int.Parse(new string(s.ToArray())));Хорошо, теперь мы и цифры умеем парсить. Что дальше? Теперь нам нужно научиться парсить интервал из двух чисел, разделенными дефисом. Обратим внимание, что число "12" должно трактоваться как интервал "12-null", т.е. мы должны разрешить концу интервала отсутствовать. Опять же, реализуем:
Parser<char, (int begin, int? end)> IntervalParser { get; } =
from begin in NumberParser
from end in Char('-').Then(NumberParser).Optional()
select (begin, end);О, а это уже интереснее. Что LINQ у нас тут делает? А вот и наша монадичность проявилась — чтобы скомбинировать наши парсеры мы можем воспользоваться ду-нотацией (которая в простонародье в .Net мире называется LINQ syntax) и построить более сложный парсер на базе простых. Подробнее про связь LINQ, монад и прочих высоких материй с нашими колхозными языками я писал тут.
Итак, вернемся к нашему парсеру. Что же он делает? Сначала мы пытаемся попарсить первое число. Если у нас не получилось этого сделать то парсер сразу же завершится с ошибкой. Если же удалось, то мы можем перейти ко второй строчке вычисления и выполнить Char('-').Then(NumberParser) — то есть попробовать попарсить число, следующее за дефисом. Т.к. в случае ошибки мы хотим получить null (а не ошибку парсинга) то добавляем Optional. Ну и в конце описываем, в каком виде мы хотим получить результат — в моем случае, тапл из инта и нуллейбл инта для начала и конца интервала соответственно.
Замечательно, написали тесты, убедились, что умеем теперь парсить интервалы. Что там у нас ещё было. Ага, шаг интервала. Пишется через /, может основываться либо на открытом интервале *, либо на диапазоне. Ну что ж, так и запишем… Хотя давайте сначала отдельный тип для этого заведем, а то таплы на 3 аргументы уже некрасиво в публичном апи выглядят:
public record ScheduleFormatEntry(int? Begin, int? End, int? Step);Теперь можно и парсер записать:
Parser<char, ScheduleFormatEntry> WholeIntervalParser { get; } =
from interval in
Asterisk.Map(_ => (begin: default(int?), end: default(int?)))
.Or(IntervalParser.Map(x => ((int?) x.begin, x.end)))
from step in Char('/').Then(NumberParser).Optional()
select new ScheduleFormatEntry(interval.begin, interval.end, step);Код достаточно самоочевидный: сначала пытаемся пропарсить звездочку, если не вышло, то парсим то же место уже как диапазон чисел. Звездочку маппим на пару из двух нуллов, а интервал оставляем как есть, только первый компонент конвертируем int -> int?, иначе типы не сходятся. Затем смотрим, есть ли шаг интервала: если нет, то записываем в шаг null, если есть то его и указываем.
Снова тесты, снова все работает, просто потому что мы сложного ничего не делаем: мы начинали с элементарных кубиков (звездочка/циферки), а затем просто собираем их вместе в более мощные абстракции. Сила монад! Кстати, прошу обратить внимание, насколько просто и естественно в ду нотации выглядит код: просто пишем сделай то, сделай это, а об ошибке оно позаботиться само, в фоне. Просто берешь и описываешь желаемую логику, а как добиться нужного результата монада догадается сама, т.к. интерпретация заложена в ней самой и не засоряет код. Чем-то похоже на АОП, которое лет 10 назад у всех на слуху было.
Так, интервалы мы умеем парсить, что дальше? Список интервалов! Ну, что просят то и пишем:
Parser<char, ScheduleFormatEntry[]> IntervalsSequenceParser { get; } =
WholeIntervalParser.SeparatedAndOptionallyTerminatedAtLeastOnce(Char(','))
.Map(x => x.ToArray())
.SelectMany(ValidateWildcards(), ((entries, _) => entries));Ради разнообразия записал парсер не используя do нотацию. Тут мы просто говорим, что список интервалов — это результат применения парсера одного интервала на нескольких элементах, разделенными запятой. Ну и для каждого затем прогоняем валидацию, что в интервале не более одной звездочки, запрещая комбинации вроде 1,2,*,3-5,*.
В общем, остальные парсеры пишутся совершенно аналогично и в результате дописываем парсеры даты, дня недели и времени (а также соответствующие формату вспомогательные структуры):
Parser<char, ScheduleDate> DateParser { get; } =
from years in Validate(IntervalsSequenceParser, ValidateBoundsParser("Year", Constant.MinYear, Constant.MaxYear))
from _ in Char('.')
from months in Validate(IntervalsSequenceParser, ValidateBoundsParser("Month", Constant.MinMonth, Constant.MaxMonth))
from __ in Char('.')
from days in Validate(IntervalsSequenceParser, ValidateBoundsParser("Day", Constant.MinDay, Constant.MaxDay))
select new ScheduleDate(years, months, days);
Parser<char, ScheduleFormatEntry[]> DayOfWeekParser { get; } =
Validate(IntervalsSequenceParser, ValidateBoundsParser("Day of week", Constant.MinDayOfWeek, Constant.MaxDayOfWeek));
Parser<char, ScheduleTime> TimeParser { get; } =
from hours in Validate(IntervalsSequenceParser, ValidateBoundsParser("Hour", Constant.MinHour, Constant.MaxHour))
from _ in Char(':')
from min in Validate(IntervalsSequenceParser, ValidateBoundsParser("Min", Constant.MinMinute, Constant.MaxMinute))
from __ in Char(':')
from sec in Validate(IntervalsSequenceParser, ValidateBoundsParser("Sec", Constant.MinSec, Constant.MaxSec))
from millis in Char('.').Then(Validate(IntervalsSequenceParser, ValidateBoundsParser("Millis", Constant.MinMillis, Constant.MaxMillis)))
.Optional()
select new ScheduleTime(hours, min, sec, millis ?? new[] {ScheduleFormatEntry.SinglePoint(0)});
Parser<char, ScheduleFormat> FullFormatParser { get; } =
from date in Try(DateParser).Before(Char(' ')).Optional()
from dayOfWeek in Try(DayOfWeekParser.Before(Char(' '))).Optional()
from time in TimeParser
select new ScheduleFormat(
date ?? new ScheduleDate(
new []{ScheduleFormatEntry.Always},
new []{ScheduleFormatEntry.Always},
new []{ScheduleFormatEntry.Always}
),
dayOfWeek ?? new []{ScheduleFormatEntry.Always},
time);В комментариях, пожалуй, нуждается только последний. По заданию у нас компоненты даты и дня недели являются необязательными. Если мы их не смогли распарсить, значит их не было и мы используем значение "звёздочка" по-умолчанию. Т.е. если компонент не задан, это эквивалетно * во всех позициях, где это возможно. Звездочка в наших вспомогательных структурах задается значением ScheduleFormatEntry.Always. Единственной сложностью тут является валидация границ значений в каждом, но валидация — это всегда боль и печаль. Если бы мы её убрали то получилось бы вот настолько просто:
Parser<char, ScheduleTime> TimeParser { get; } =
from hours in IntervalsSequenceParser
from _ in Char(':')
from min in IntervalsSequenceParser
from __ in Char(':')
from sec in IntervalsSequenceParser
from millis in Char('.').Then(IntervalsSequenceParser).Optional()
select new ScheduleTime(
hours,
min,
sec,
millis ?? new[] {ScheduleFormatEntry.SinglePoint(0)});Засим мы завершаем наше знакомство с монадами, поскольку наш FullFormatParser умеет парсить всё, что требовалось по заданию. И пора переходить к следующей части
Маппинг вспомогательного формата
Вспомните, что наш исходный формат выглядел как набор точек во времени с признаком разрешено/запрещено, а мы попарсили кучу непонятных интервалов вида "начало-конец-шаг". Что делаем? Правильно, преобразуем одно в другое:
public record MergedSchedule(
ScheduleInterval Years,
ScheduleInterval Months,
ScheduleInterval Days,
ScheduleInterval DayOfWeek,
ScheduleInterval Hours,
ScheduleInterval Minutes,
ScheduleInterval Seconds,
ScheduleInterval Milliseconds)
{
public static MergedSchedule FromFormat(ScheduleFormat format) =>
{
return new(
GetMerged(format.Date.Years, Constant.MinYear, Constant.MaxYear),
GetMerged(format.Date.Months, Constant.MinMonth, Constant.MaxMonth),
GetMerged(format.Date.Days, Constant.MinDay, Constant.MaxDay),
GetMerged(format.DayOfWeek, Constant.MinDayOfWeek, Constant.MaxDayOfWeek),
GetMerged(format.Time.Hours, Constant.MinHour, Constant.MaxHour),
GetMerged(format.Time.Minutes, Constant.MinMinute, Constant.MaxMinute),
GetMerged(format.Time.Seconds, Constant.MinSec, Constant.MaxSec),
GetMerged(format.Time.Milliseconds, Constant.MinMillis, Constant.MaxMillis)
);
}
private static ScheduleInterval GetMerged(ScheduleFormatEntry[] intervals, int begin, int end)
{
if (intervals.Length == 1 && intervals[0] == ScheduleFormatEntry.Always)
{
return ScheduleInterval.CreateAllowedInterval(begin, end);
}
var result = new ScheduleInterval(begin, end);
foreach (var scheduleFormatEntry in intervals)
{
var (b, e, s) = (scheduleFormatEntry.Begin,
scheduleFormatEntry.End,
scheduleFormatEntry.Step) switch
{
(null, null, {} s1) => (begin, end, s1),
({} b2, null, null) => (b2, b2, 1),
({} b3, {} e3, null) => (b3, e3, 1),
({} b4, {} e4, {} s4) => (b4, e4, s4),
_ => throw new InvalidOperationException(
$"Bad period {scheduleFormatEntry} cannot be parsed")
};
for (int i = b; i <= e; i += s)
{
result.ChangePointAllowance(i, true);
}
}
return result;
}
}Не надо пугаться, тут много копипасты из-за особенностей задачи. но в целом ничего сложного не происходит: мы просто идем по всем интервалам и проставляем булев признак — разрешено ли значение в этой дате или нет. Конечно же, на все пишем тесты, они помогут понять, правильно ли мы реализовали или нет:
[Fact]
public void SinglePoint()
{
var format = new ScheduleFormat(new ScheduleDate(
new[] {ScheduleFormatEntry.SinglePoint(2020)},
new[] {ScheduleFormatEntry.SinglePoint(9)},
new[] {ScheduleFormatEntry.SinglePoint(1)}
),
new[] {ScheduleFormatEntry.SinglePoint(1)},
new ScheduleTime(
new[] {ScheduleFormatEntry.SinglePoint(10)},
new[] {ScheduleFormatEntry.SinglePoint(0)},
new[] {ScheduleFormatEntry.SinglePoint(0)},
new[] {ScheduleFormatEntry.SinglePoint(0)}
));
var merged = MergedSchedule.FromFormat(format);
AssertSingleValidPoint(merged.Years, 2020);
AssertSingleValidPoint(merged.Months, 9);
AssertSingleValidPoint(merged.Days, 1);
AssertSingleValidPoint(merged.DayOfWeek, 1);
AssertSingleValidPoint(merged.Hours, 10);
AssertSingleValidPoint(merged.Minutes, 0);
AssertSingleValidPoint(merged.Seconds, 0);
AssertSingleValidPoint(merged.Milliseconds, 0);
}
// ... и ещё с десяток тестов, проверяющих другие возможные результаты парсингаНу и как обычно, тесты зеленые — всё хорошо. Опять же, потому что ошибиться тут негде: тривиальное преобразование одной структуры в другую, тут уже даже не используется формат, который нам на входе дан по заданию, мы используем только наши внутренние структуры. Что дает нам очередную гибкость — при изменении формата по любым причинам если это не затрагивает внутренне представление (а только разделитель, скажем, поменялся), то эти тесты продолжат работать, как и раньше. Сила декомпозиции!
Ну, парсинг мы написали, на наш формат хранения перевели, осталась мелочь, написать поиск ближайшего события? Давайте сделаем
Ищем события
Назад в будущее
Подглядев у Quartz как они ищут дни недели пишем аналогично, сначала подбираем год:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
return t1;
}
}затем добавляем месяц:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (t1.Year == year && !_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
}
if (t1.Year != year)
{
continue;
}
return t1;
}
}Затем день:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
...
// search for day
var month = t1.Month;
// тут весьма тяжеловесное условие, но честно лень его расписывать иначе
while (t1.Month == month && !(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddDays(1);
}
if (t1.Month != month)
{
continue;
}
}
}Обратите внимание на паттерн
while (someCond && !realCond) { ...}
if (!someCond) { continue }К моменту написания секунд меня порядком подзадолбало постоянно это писать. И тут вступает в дело герой из заголовка статьи: я вспомнил, что мне может помочь: goto! На этом моменте меня должны сразу закидать помидорами, насовать минусов в карму, откомментить "Вон Дейкстра что писал, ты чего творишь?! Позор" ну и все в таком духе. Но, по зрелому размышлению я решил, что оно во-первых убирает лишнее сравнение, во-вторых, делает код чище. Посмотрите сами, вот так выглядит поиск до дней:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddDays(1);
if (t1.Month != month)
{
goto LoopStart;
}
}
}
}Никогда не думал, что такое скажу — но гоуту и правда помогает в данном случае. Обычно он не нужен — рефакторинг внутренней логики в функцию обычно отлично работает. Но не в нашем случае, да, потому что нам нужно вызвать continue на внешнем цикле, а не внутреннем. Кроме того, вызов функции наверняка не будет заинлайнен (особенно в случае с днями), из-за чего у нас появляются накладные расходы, которых хотелось бы избежать. В идеале это должно было бы решиться макросом или языковой фичей вроде:
mainLoop: while (true)
{
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
if (t1.Year != year)
{
continue mainLoop;
}
}
}Но увы, ни того, ни другого у нас нет. В итоге да, гоуту оказывается самым читаемым (на мой взгляд) из альтернатив. И при этом зирокост, что немаловажно.
Итоговый код функции:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddDays(1);
if (t1.Month != month)
{
goto LoopStart;
}
}
// search for hour
var day = t1.Day;
while (!_innerSchedule.Hours.IsPointAllowed(t1.Hour))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, 0, 0).AddHours(1);
if (t1.Day != day)
{
goto LoopStart;
}
}
// search for minute
var hour = t1.Hour;
while (!_innerSchedule.Minutes.IsPointAllowed(t1.Minute))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, 0).AddMinutes(1);
if (t1.Hour != hour)
{
goto LoopStart;
}
}
// search for second
var minute = t1.Minute;
while (!_innerSchedule.Seconds.IsPointAllowed(t1.Second))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, t1.Second).AddSeconds(1);
if (t1.Minute != minute)
{
goto LoopStart;
}
}
// search for ms
var second = t1.Second;
while (!_innerSchedule.Milliseconds.IsPointAllowed(t1.Millisecond))
{
t1 = t1.AddMilliseconds(1);
if (t1.Second != second)
{
goto LoopStart;
}
}
return t1;
}
}Вперед в прошлое
Аналогично пишем функцию для поиска назад во времени:
public DateTime NearestPrevEvent(DateTime t1)
{
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddMilliseconds(-1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMilliseconds(-1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddMilliseconds(-1);
if (t1.Month != month)
{
goto LoopStart;
}
}
// search for hour
var day = t1.Day;
while (!_innerSchedule.Hours.IsPointAllowed(t1.Hour))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, 0, 0).AddMilliseconds(-1);
if (t1.Day != day)
{
goto LoopStart;
}
}
// search for minute
var hour = t1.Hour;
while (!_innerSchedule.Minutes.IsPointAllowed(t1.Minute))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, 0).AddMilliseconds(-1);
if (t1.Hour != hour)
{
goto LoopStart;
}
}
// search for second
var minute = t1.Minute;
while (!_innerSchedule.Seconds.IsPointAllowed(t1.Second))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, t1.Second).AddMilliseconds(-1);
if (t1.Minute != minute)
{
goto LoopStart;
}
}
// search for ms
var second = t1.Second;
while (!_innerSchedule.Milliseconds.IsPointAllowed(t1.Millisecond))
{
t1 = t1.AddMilliseconds(-1);
if (t1.Second != second)
{
goto LoopStart;
}
}
return t1;
}
}Тут стоит сделать отступление на комментарий товарища sepulkary
У вас два большущих метода, отличающихся только знаком
Однако внимательный читатель сразу заметит, что функции отличаются ещё одной немаловажной особенностью. Посмотрим, как вычисляются годы в будущее:
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}И в прошлое:
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddMilliseconds(-1);
}Ведь дело в том, что если нам не подходит текущий год, то мы должны начать поиск с первого дня первого месяца следующего года.
А вот если мы ищем назад, то нам нужно 31 декабря 23:59:59.9999999999… То есть логика достаточно сильно различается.
Это можно было бы отрефачить во что-то вида t1 = yearChangingLambda(t1) — т.е. передавать лямбдой необходимое изменение, чтобы ликвидировать различие между функциями. Но тут нас кусает требование об оптимальности — на каждой итерации в горячем цикле вызывать лямбду это не вариант совершенно. Да и в целом передавать кучу лямбд аргументами выглядит некрасиво. Есть ли решение, которое нас устроит? И конечно же, ответ — мы можем всё.
Zero-cost решение проблемы различия функций
В мире дотнета есть довольно известная оптимизация, которую зачастую рассказывают на всяких конфах вроде DotNext. Это оптимизации джитом генериков для структур. Так как для структур невозможно наследование, джит может выкидывать целые куски кода, которые выполняются после проверки на конкретный тип. Например, давайте посмотрим на тайплевел Bool:
public interface IBool
{
}
public struct TrueType : IBool
{
}
public struct FalseType : IBool
{
}Что мы можем полезного сделать с этими типами? Например, использовать их для тайплевел вычислений. Давайте напишем функцию, которая опускает значение с уровня типов до уровня значений:
public struct Test
{
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static bool IsTrue<T>() where T : struct, IBool =>
default(T) switch
{
TrueType _ => true,
FalseType _ => false
};
}
...
public bool Foo() => Test.IsTrue<TrueType>()К сожалению, RyuJit не догадывается без подсказки соптимизировать подобные кейсы. Надеюсь, это будет исправлено в будущих версиях
Во что, по-вашему, будет скомпилирована функция Foo? А вот во что:
C.Foo()
L0000: push ebp
L0001: mov ebp, esp
L0003: mov eax, 1
L0008: pop ebp
L0009: retЧто мы видим? Компилятор просто грузит константу 1 (true) на стек и возвращает. Т.е. он увидел, что из всех веток switch достижима только одна (там где TrueType) и выкинул все остальные, заменив весь свитч на исполняемую ветвь. Затем он увидел, что переменная TrueType _ не используется и убрал её. После чего ему оставалось только заинлайнить тривиальную функцию return true, поэтому даже вызова функции мы в итоге не увидели, а только одинокую константу 1.
Возвращаясь к нашей проблеме: а что, если мы вынесем вычисления дат туда же? Сказано-сделано:
public interface IDateTimeChanger
{
DateTime Change<TIsIncrementing>(DateTime t1)
where TIsIncrementing : struct, IBool;
}
public struct YearsChanger : IDateTimeChanger
{
[MethodImpl(MethodImplOptions.AggressiveInlining
| MethodImplOptions.AggressiveOptimization)]
public DateTime Change<TIsIncrementing>(DateTime t1)
where TIsIncrementing : struct, IBool
{
var baseValue = new DateTime(t1.Year, 1, 1);
return default(TIsIncrementing) switch
{
TrueType _ => baseValue.AddYears(1),
FalseType _ => baseValue.AddMilliseconds(-1)
};
}
}
// ... для других компонентов даты аналогичноTIsIncrementing Это либо TrueType либо FalseType, которые передают нам соответственно признак если мы ищем вперед во времени (NearestEvent) или назад (NearestPrevEvent).
Как теперь выглядит наша функция? Вот так:
private DateTime Closest<TIsIncrementing>(DateTime t1)
where TIsIncrementing : struct, IBool
{
var yearChanger = default(YearsChanger);
var monthChanger = default(MonthChanger);
var dayChanger = default(DayChanger);
var hourChanger = default(HourChanger);
var minuteChanger = default(MinuteChanger);
var secondChanger = default(SecondChanger);
var millisecondChanger = default(MillisecondChanger);
while (true)
{
LoopStart: ;
// search for year
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)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = dayChanger.Change<TIsIncrementing>(t1);
if (t1.Month != month)
{
goto LoopStart;
}
}
// search for hour
var day = t1.Day;
while (!_innerSchedule.Hours.IsPointAllowed(t1.Hour))
{
t1 = hourChanger.Change<TIsIncrementing>(t1);
if (t1.Day != day)
{
goto LoopStart;
}
}
// search for minute
var hour = t1.Hour;
while (!_innerSchedule.Minutes.IsPointAllowed(t1.Minute))
{
t1 = minuteChanger.Change<TIsIncrementing>(t1);
if (t1.Hour != hour)
{
goto LoopStart;
}
}
// search for second
var minute = t1.Minute;
while (!_innerSchedule.Seconds.IsPointAllowed(t1.Second))
{
t1 = secondChanger.Change<TIsIncrementing>(t1);
if (t1.Minute != minute)
{
goto LoopStart;
}
}
// search for second
var second = t1.Second;
while (!_innerSchedule.Milliseconds.IsPointAllowed(t1.Millisecond))
{
t1 = millisecondChanger.Change<TIsIncrementing>(t1);
if (t1.Second != second)
{
goto LoopStart;
}
}
return t1;
}
}Чьё использование тривиально:
public DateTime NearestEvent(DateTime t1) => Closest<TrueType>(t1);
public DateTime NearestPrevEvent(DateTime t1) => Closest<FalseType>(t1);И, на этом с реализацией всё. Осталось посмотреть, как оно работает всё в сборе, ну и сравнить с предыдущими версиями
Сравниваем с оригинальным решением автора
Парсинг
Во всех бенчмарках версия novar считается базовой, от неё считаются все остальные. И первое, что мы сравним, это время парсинга:
BenchmarkDotNet=v0.13.0, OS=Windows 10.0.19043.1110 (21H1/May2021Update)
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET 5.0 : .NET 5.0.8 (5.0.821.31504), X64 RyuJIT| Method | Pattern | Mean | Error | StdDev | Ratio |
|---|---|---|---|---|---|
| ParsingOld | ..*(...)-20/3 | 506.9 ns | 9.84 ns | 9.21 ns | 1.00 |
| ParsingNew | ..*(...)-20/3 | 17,263.0 ns | 132.16 ns | 123.62 ns | 34.06 |
| ParsingOld | ..1 0:0:0 | 365.6 ns | 4.83 ns | 4.28 ns | 1.00 |
| ParsingNew | ..1 0:0:0 | 15,150.4 ns | 17.63 ns | 16.49 ns | 41.45 |
| ParsingOld | .9.(...)0.000 | 400.5 ns | 6.84 ns | 8.89 ns | 1.00 |
| ParsingNew | .9.(...)0.000 | 17,347.5 ns | 166.40 ns | 155.65 ns | 43.19 |
| ParsingOld | 2100.(...)9.999 | 322.3 ns | 2.28 ns | 1.90 ns | 1.00 |
| ParsingNew | 2100.(...)9.999 | 19,551.1 ns | 71.56 ns | 66.93 ns | 60.66 |
Какой кошмар, ужас, в 50 раз медленнее! Выкинуть это дело на помойку, опять монадки неприменимы в реальном мире! — сказал бы кто-нибудь, и я бы с ним не согласился. Да, время парсинга кратно хуже, но, во-первых обратите внимание что оно все ещё в пределах 20 микросекунд и его достаточно чтобы перепаршивать наш дорогой формат хоть 50000 раз в секунду. Во-вторых, наш парсер в отличие от оригинального имеет кучу преимуществ: он композабелен, он легко читаем/расширяем, а главное в случае ошибки разбора сообщает вам конкретно место и подстроку, которую не смог разобрать. Оригинальный же парсер конечно же ничего не трекает и просто бросает ошибку "что-то пошло не так". А как известно, почти ничего не бывает задаром.
В общем, хотя парсер и ощутимо медленнее, он все ещё годен для любого реалистичного использования. А учитывая предполагаемый паттерн использования данного типа — мы решили задачу с более чем достойным запасом.
Идем дальше — поиск следующего значения:
Определение ближайшего события
Я взял несколько случайных паттернов из тех, что были даны как примеры в задании, и после прогона бенчмарков получил следующие результаты:
| Method | Pattern | DateString | Mean | Error | StdDev | Ratio |
|---|---|---|---|---|---|---|
| FindNextOld | ..1 0:0:0 | 2001-01-01 | 15,711.7 ns | 196.24 ns | 173.96 ns | 1.00 |
| FindNextNewCopypasted | ..1 0:0:0 | 2001-01-01 | 15,219.1 ns | 295.22 ns | 373.35 ns | 0.96 |
| FindNextNewTypelevel | ..1 0:0:0 | 2001-01-01 | 14,427.3 ns | 173.55 ns | 162.34 ns | 0.92 |
| FindNextOld | ..1 0:0:0 | 2080-05-05 | 2,291.2 ns | 21.13 ns | 19.77 ns | 1.00 |
| FindNextNewCopypasted | ..1 0:0:0 | 2080-05-05 | 1,598.7 ns | 3.23 ns | 2.87 ns | 0.70 |
| FindNextNewTypelevel | ..1 0:0:0 | 2080-05-05 | 909.9 ns | 3.29 ns | 2.75 ns | 0.40 |
| FindNextOld | *.4.6(...)-20/3 | 2001-01-01 | 740.6 ns | 4.03 ns | 3.57 ns | 1.00 |
| FindNextNewCopypasted | *.4.6(...)-20/3 | 2001-01-01 | 573.2 ns | 4.30 ns | 4.02 ns | 0.77 |
| FindNextNewTypelevel | *.4.6(...)-20/3 | 2001-01-01 | 448.4 ns | 1.21 ns | 1.08 ns | 0.61 |
| FindNextOld | *.4.6(...)-20/3 | 2080-05-05 | 1,279.1 ns | 12.11 ns | 11.33 ns | 1.00 |
| FindNextNewCopypasted | *.4.6(...)-20/3 | 2080-05-05 | 1,127.8 ns | 4.40 ns | 4.11 ns | 0.88 |
| FindNextNewTypelevel | *.4.6(...)-20/3 | 2080-05-05 | 998.4 ns | 10.09 ns | 9.43 ns | 0.78 |
| FindNextOld | .9.(...)0.000 | 2001-01-01 | 1,720.7 ns | 5.47 ns | 4.85 ns | 1.00 |
| FindNextNewCopypasted | .9.(...)0.000 | 2001-01-01 | 1,187.7 ns | 6.18 ns | 5.16 ns | 0.69 |
| FindNextNewTypelevel | .9.(...)0.000 | 2001-01-01 | 1,132.8 ns | 17.35 ns | 15.38 ns | 0.66 |
| FindNextOld | .9.(...)0.000 | 2080-05-05 | 1,461.2 ns | 10.35 ns | 9.17 ns | 1.00 |
| FindNextNewCopypasted | .9.(...)0.000 | 2080-05-05 | 931.9 ns | 3.31 ns | 2.77 ns | 0.64 |
| FindNextNewTypelevel | .9.(...)0.000 | 2080-05-05 | 871.6 ns | 1.26 ns | 1.18 ns | 0.60 |
| FindNextOld | 2100.(...)9.999 | 2001-01-01 | 22,167.7 ns | 221.81 ns | 207.48 ns | 1.00 |
| FindNextNewCopypasted | 2100.(...)9.999 | 2001-01-01 | 20,821.5 ns | 211.02 ns | 197.39 ns | 0.94 |
| FindNextNewTypelevel | 2100.(...)9.999 | 2001-01-01 | 20,544.2 ns | 274.01 ns | 228.81 ns | 0.93 |
| FindNextOld | 2100.(...)9.999 | 2080-05-05 | 20,451.8 ns | 404.82 ns | 397.59 ns | 1.00 |
| FindNextNewCopypasted | 2100.(...)9.999 | 2080-05-05 | 18,717.9 ns | 357.62 ns | 382.65 ns | 0.91 |
| FindNextNewTypelevel | 2100.(...)9.999 | 2080-05-05 | 18,040.7 ns | 328.40 ns | 307.19 ns | 0.88 |
FindNextOld — это оригинальная реализация автора, FindNextNewCopypasted — последняя реализация до того, как мы воспользовались мощью типчиков, и FindNextNewTypelevel собственно итоговая тайплевел версия. Обратите внимание, что и копипастная, и тайплевел версии имеют абсолютно одинаковый перформанс. Все потому, что они компилируется в эквивалентный код. А ведь при этом мы убрали копипасту и смогли переиспользовать код, написав одну функцию для обоих вариантов. Совершенно бесплатно и без смс.
Теперь если сравнивать с авторским вариантом — то разница обусловлена тем, что в версии автора при нахождении любого расхождения начинается поиск с самого начала. В моем же случае я отслеживаю старшее значение (год для месяца, месяц для дня и т.п.) и запускаю полный перерасчет, только если этот компонент изменился. В некоторых случаях это будет давать выигрыш, в каких-то будет наоборот медленнее. Но в целом порядок времени выполнения схож, хотя на тестовых данных подход с сохранением показал лучшие результаты. Думаю, несложно будет подобрать искусственный пример, где изначальный подход будет выигрывать.
Идем дальше
Определение ближайшего предыдущего события
| Method | Pattern | DateString | Mean | Error | StdDev | Ratio |
|---|---|---|---|---|---|---|
| FindPrevOld | ..1 0:0:0 | 2001-01-01 | 18,665.30 ns | 319.700 ns | 283.405 ns | 1.00 |
| FindPrevNewCopypasted | ..1 0:0:0 | 2001-01-01 | 17,179.13 ns | 341.540 ns | 607.086 ns | 0.91 |
| FindPrevNewTypelevel | ..1 0:0:0 | 2001-01-01 | 16,855.01 ns | 257.361 ns | 240.735 ns | 0.90 |
| FindPrevOld | ..1 0:0:0 | 2080-05-05 | 15,755.87 ns | 301.288 ns | 370.008 ns | 1.00 |
| FindPrevNewCopypasted | ..1 0:0:0 | 2080-05-05 | 15,346.73 ns | 300.132 ns | 390.256 ns | 0.97 |
| FindPrevNewTypelevel | ..1 0:0:0 | 2080-05-05 | 15,106.44 ns | 300.014 ns | 357.146 ns | 0.96 |
| FindPrevOld | *.4.6(...)-20/3 | 2001-01-01 | 3,331.73 ns | 65.306 ns | 84.916 ns | 1.00 |
| FindPrevNewCopypasted | *.4.6(...)-20/3 | 2001-01-01 | 9,366.22 ns | 114.040 ns | 101.093 ns | 2.82 |
| FindPrevNewTypelevel | *.4.6(...)-20/3 | 2001-01-01 | 9,558.23 ns | 183.513 ns | 188.454 ns | 2.87 |
| FindPrevOld | *.4.6(...)-20/3 | 2080-05-05 | 2,825.13 ns | 38.673 ns | 36.175 ns | 1.00 |
| FindPrevNewCopypasted | *.4.6(...)-20/3 | 2080-05-05 | 9,586.06 ns | 190.697 ns | 441.970 ns | 3.31 |
| FindPrevNewTypelevel | *.4.6(...)-20/3 | 2080-05-05 | 9,244.82 ns | 181.060 ns | 185.935 ns | 3.27 |
| FindPrevOld | .9.(...)0.000 | 2001-01-01 | 14,793.93 ns | 270.777 ns | 253.285 ns | 1.00 |
| FindPrevNewCopypasted | .9.(...)0.000 | 2001-01-01 | 15,019.59 ns | 286.670 ns | 341.261 ns | 1.02 |
| FindPrevNewTypelevel | .9.(...)0.000 | 2001-01-01 | 16,325.45 ns | 320.146 ns | 393.168 ns | 1.11 |
| FindPrevOld | .9.(...)0.000 | 2080-05-05 | 15,135.30 ns | 293.223 ns | 411.058 ns | 1.00 |
| FindPrevNewCopypasted | .9.(...)0.000 | 2080-05-05 | 15,041.15 ns | 281.947 ns | 276.910 ns | 0.98 |
| FindPrevNewTypelevel | .9.(...)0.000 | 2080-05-05 | 14,010.77 ns | 259.528 ns | 277.692 ns | 0.92 |
| FindPrevOld | 2000.(...)9.999 | 2001-01-01 | 119.83 ns | 2.358 ns | 3.066 ns | 1.00 |
| FindPrevNewCopypasted | 2000.(...)9.999 | 2001-01-01 | 73.59 ns | 1.540 ns | 3.778 ns | 0.64 |
| FindPrevNewTypelevel | 2000.(...)9.999 | 2001-01-01 | 84.58 ns | 1.569 ns | 1.391 ns | 0.70 |
| FindPrevOld | 2000.(...)9.999 | 2080-05-05 | 2,261.26 ns | 44.415 ns | 52.872 ns | 1.00 |
| FindPrevNewCopypasted | 2000.(...)9.999 | 2080-05-05 | 2,202.63 ns | 40.608 ns | 33.910 ns | 0.98 |
| FindPrevNewTypelevel | 2000.(...)9.999 | 2080-05-05 | 2,456.63 ns | 48.368 ns | 47.504 ns | 1.09 |
Тут мы видим схожие с предыдущим пунктом результаты, хотя на некоторых инпутах результат не быстрее в 2 раза, а медленнее. Видимо, это связано как раз с различием в принятии решения об откате на поиск с самого начала.
С этой частью задания кстати связана одна история: до того, как я сделал тайплевел почему-то у меня постоянно различалось время выполнения поиска в прямом и обратном порядке. Да и даже когда я объединил — все равно никак не получалось одинаковой скорости добиться — прямой проход был всегда немного быстрее, а обратный — в 10 раз медленнее. В итоге через пару дней проглядывая код совершенно случайно нашел, в чем же косяк. Вот фикс(а затем более правильный фикс), и очередное подтверждение того, что копипаста — зло.
Итоги сравнения с оригинальным кодом
В общем, оглядываясь на результаты выше, можно увидеть улучшение во всех измерениях, которые мне кажутся важными:
- Код соблюдает SRP: есть небольшие модули, каждый из которых отвечает за свою небольшую часть. Юникс-вей, все дела. Парсер парсит, модели отражают то, что им нужно, а не то что нужно кому-то (кому надо — тот смаппит)
- Код композируем: можно спокойно поменять формат, добавить новый, поменять правила парсинга — все это инкапсулировано в отдельной части. Можно поменять логику хранения с булевых массивов на какие-нибудь бинарные деревья как в Quartz, при этом б0льшую часть кода не придется менять вообще
- Код читаем: его реально можно прочитать. Нужен парсинг — пошли посмотрели 50 строчек тут, нужно понять как маппится — 20 строчек там, нужно понять, как ищем расписания — ничего проще, вот ещё немного кода. Оригинальный код, честно говоря, я осилил не сразу, и то часть с парсингом я просто свернул — к сожалению, это слишком круто для меня)
- Отдельно хочу отметить линейную структуру поиска без триллиона if — почувствуйте сами, насколько велика разница в восприятии
- Странно отдельно упоминать это в 2021 году, но нет магических констант: все вынесено в отдельное место и можно поменять в единственном месте (в оригинальном коде с этим было немного печально)
- Дописаны тесты на негативные кейсы — то, чего кстати не хватило автору. То что мы парсим что нужно — это хорошо, но ещё нужно проверять, что не парсим чего не нужно
- Есть повод использовать монады: без комментариев :)
Ну есть конечно же и пространство для улучшений, потому как делалось все в рамках жесткого лимита времени, т.к. тратить на задание дни не считаю целесообразным:
- Убрать
int.Parse(new String(char[])): очевидное место, где совершаются аллокации и много ненужных действий - Оптимизировать работу с дейттаймами: использовать константы TicksPerDay/TicksPerHour/… и битовые/арифметические операции чтобы отсекать неподходящие даты. Конструкторы даты постоянно проверяют инварианты, про которые по построению известно что они корректны. Можно на этом сэкономить
- Лучший нейминг
- Больше тестов
- Более хорошие ошибки парсинга для краевых случаев
- Правильные эксепшны в некоторых случаях, которые сейчас кидают слишком общие ошибки (навроде OutOfBoundsException)
- Тысячи их
Пара слов о комментариях к оригинальной статье
Хотелось бы ещё прокомментировать некоторые комменты к оригинальной статье:
Честно говоря, тестовое задание ни о чем. Видимо ищут джуна, чтобы валить на него косяки и пенать его без повода, вы не подошли, не расстраивайтесь.
Задание нормальное, как на джуна так и на сениора: просто у них решение будет отличаться. Да и вряд ли джун осилит правильный парсинг нужного формата — запутается, что за чем должно идти. Хотя и адекватного сениора, который бы стал делать тестовые задания нужно ещё поискать. Я лично делаю, только если меня заинтересовала проблема. Задачку как у автора я скорее всего проигнорировал бы, будь это задача не показательная, чтобы попробовать свои силы, а для трудоустройства. В общем, задание в целом странноватое: слишком сложное для джуна, слишком долгое для сениора. Возможно, они искали крепкого миддла без особых амбиций, но этого мы наверное уже не узнаем.
Лень было погружаться в код до полного понимания, но почему есть ощущение, что добрую логику парсинга можно было просто сделать регулярками.
Опять же, описано в статье, но стоит отдельно отметить, что даже если на регулярках получится сделать задание, то доработать его в будущем — на моей практике проще выкинуть регулярку и написать новую, чем разобраться в старой) И только после написания новой будет понятно, что в старой имелось в виду. И адекватной ошибки, как например у парсера в данной статье
var result = FullFormatParser.ParseOrThrow("asfas.01.01 00:00:00.000");
// Parse error.
// unexpected a
// expected "*", or digit
// at line 1, col 1с регулярками не получится никогда
И, чтобы два раза не вставать, как говорится; вопрос к изначальной постановке задачи — не очень понимаю, зачем здесь конструктор, вижу место только для нескольких статических методов, которые принимают на вход время и строку расписания, отдавая время, удовлетворяющее условию. static не всегда хорошо, но вроде здесь вполне к месту, работаем прямо с чистыми функциями
Как было показано на бенчмарке выше, время выполнения парсинга порядка 18 мкс, а время поиска по уже разобранному выражению — 200нс, т.е. на 2 десятичных порядка меньше. Совершенно логично сохранить результат парсинга и переиспользовать его — расписания и по логике-то вряд ли меняются каждую микросекунду. Поэтому сохранение разбора в конструкторе класса — абсолютно правильно.
Подобное задание предполагает использование паттернов проектирования. Вы не применили ни одного. Могли бы прикрутить какой-нибудь Builder, Strategy, Singleton, Factory method, хоть что-то, что показало бы ваш опыт работы с паттернами.
Нет, не предполагает — в этом задании нет смысла ни в одном из архитектурных паттернов, хотя бы потому, что архитектурой тут и не пахнет: нужно просто попарсить строчку и написать реализацию пары функций. Наворачивать тут паттерны — это идти по пути FizzBuzzEnterpriseEdition. Если бы я давал такое задание и увидел в качестве решения паттерны, то я бы сделал только один вывод: "Знает про паттерны, но не умеет ими пользоваться". Навернуть паттерн просто потому, что ты его знаешь — антипаттерн сам по себе.
Заключение
В общем, я надеюсь данная статья была полезна. Я ни в коем случае не претендую на то, что у меня лучшее (или даже просто хорошее) решение, но на мой взгляд в условиях ограничений по времени и желанию этим заниматься — вполне пристойное, и более качественная по важным для меня измерениям, как то: поддерживаемость, чистота, расширяемость кода,… Весь код был написан примерно за ~6-8 часов, т.е. около того же времени, что сделал автор: примерно 4 часа я разбирался с парсингом, незнакомая библиотека, незнакомые апи — приходилось экспериментировать. Остальное соответственно реализация второй части задания. Мне важно было добиться хорошего результата в условиях тех же ограничений, что и автор. По результатам этого я бы хотел сделать несколько тезисов:
- монады — это круто и полезно. Ду-нотац… простите, LINQ-ситаксис — крайне удобный способ записи композирующихся вычислений. Не IEnumerable единым живы
- гоуту как ни странно иногда может помочь даже в 2021 году в коде, который пытается выжать перформанс (забавно было увидеть его же в NCrontab — независимо пришли к одному решению с его разработчиками)
- так-себе-код и нормальный код по времени пишутся одинаково долго, но с одним из них работать комфортнее в будущем, а в другой будет противно заглядывать с доработками. Правда, нужно иметь опыт, чтобы было из чего выбирать — чтобы взять хорошее решение про его существование нужно знать.
- производительный код — не обязательно лапша из ифов, низкоуровневой работы со строками и вручную реализованными версиями функций из стд. Можно получить перформанс в достаточно высокоуровневых конструкциях, просто по-другому взглянув на приложение.
- Имплиситы (YearChanger/MonthChanger/..., хотя в случае шарпа они скорее эксплиситы, хех) — ваши друзья. Пользуйтесь ими, чтобы получать zero-cost полиморфизм во время компиляции. Также они бывают полезными для определения интерфейса со статическими свойствами. Скоро будет нативно в языке, а пока — ну вот так.
Upd. Совсем забыл приложить ссылку на репозиторий: https://github.com/Pzixel/TestApp
Комментарии (114)
lam0x86
10.08.2021 11:17+6Имхо, вместо инкрементального поиска года/месяца/etc. лучше использовать Segment Tree для быстрого поиска начала и конца интервала.
PsyHaSTe Автор
10.08.2021 11:30+4Не совсем так. 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 гигабайт на то, чтобы сохранить все интервалы для кейса "звездочка во всех расписаниях".
А вот что можно улучшить — так это использовать бинарный поиск вместо инкремента. О чем хотел написать в раздел улучшений, но забыл. Спасибо, что напомнили. Изначально не сделано так же из соображений лимита по времени — написан самый просто перебор, в котором меньше всего шансов ошибиться, да и не факт, что будет лучше. Скорее всего имеет смысл так только изначальный год подбирать, а дальше оставлять текущий алгоритм.
lam0x86
10.08.2021 11:49Ммм, не уверен, что понял. Звёздочка должна быть представлена одним интервалом в дереве: [0 ; int.MaxValue].
PsyHaSTe Автор
10.08.2021 12:12Ну хорошо, пусть будет
*.*.* * *:*:*.*/2— т.е. только четные миллисекунды. Получится куча интервалов по 1 мс, правильно ведь?lam0x86
10.08.2021 13:00+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 (т.е. вышли за пределы интервала), то берем следующий сегмент. Где-то мог ошибиться в логике, но вроде бы должно работать.
PsyHaSTe Автор
10.08.2021 13:04+1Ну вот таким образом формат уже больше схож на тот, что я использовал. Теперь вопрос — а нужно ли нам тут дерево? Может
bool[]вполне достаточно? :)lam0x86
10.08.2021 13:13Учитывая, что количество лет потенциально неограниченно, мне кажется, дерево всё же предпочтительнее :)
Ну и не совсем понятно, как вы организуете бинарный поиск в случаях интервалов с шагом: например, 0-999/2.
Предположим, я передал дату 2000-01-01 00:00:00:001.
Очевидно, она не подпадает под шаблон. В каком диапазоне делать поиск? [2;999]? Среднее значение будет 500. Оно подпадает под шаблон, но по сути неверное, т.к. следующее верное значение - 2.
PsyHaSTe Автор
10.08.2021 13:24+6Но у нас количество лет как раз ограниченное, и эту информацию имеет смысл использовать в задаче. Ведь опять же, вспоминая доменную область — мы пишем кусок планировщика задач. Планировать задачи в 999999 год после нашей эры никто наверное не собирается. Хотя я верю в оптимизм людей, конечно же.
lam0x86
10.08.2021 13:30Точно, не заметил ограничения в задаче.
Тем не менее, если бинарный поиск не подходит, то линейный поиск подходящей миллисекунды в среднем обойдётся в 500 итераций цикла для случая, когда в шаблоне указано единственное конкретное значение. В случае с деревом сложность будет O(1).
PsyHaSTe Автор
10.08.2021 13:32Согласен, я изначально тоже использовал дерево (как в Quartz), но мне не понравилось это решение. Давайте предположим такое расписание:
*/4.*/4.*/4 */4 */4:*/4:*/4.*/4Как будет выглядеть дерево для него?
lam0x86
10.08.2021 13:34+2Это будет не одно дерево, а 8 деревьев, в каждом по одному ноду IntervalWithStep (from=0, to=int.MaxValue, step=4).
PsyHaSTe Автор
10.08.2021 13:42Хм, а step как работать будет? Потому что я вот смотрю на описание Segment Tree в википедии и там step не виду.
И потом, допустим у нас в дереве хранится два значения
IntervalWithStep (from=0, to=int.MaxValue, step=4)иIntervalWithStep (from=3, to=int.MaxValue, step=2).Как нам теперь узнать, какое из них наступит раньше для, скажем, знчения 17?
lam0x86
10.08.2021 13:47Ок, для таких случаев должны возвращаться оба интервала. Step работает уже на следующем уровне: когда мы получили интервал, определяем, попадает ли искомая компонента даты под шаг. Если попадает, возвращаем её. Если нет, возвращаем ближайшее число, удовлетворяющее шагу и направлению поиска.
PsyHaSTe Автор
10.08.2021 14:03+3А что нам в итоге тут дерево дает? Нам все равно в итоге нужно все интервалы параллельно проверять, потому что у нас нет информации какой из них наступает раньше. В этом случае у нас их два, но может быть и три, и четыре, и так далее. Как например быть в случае шаблона
1,3,6,8,11,13,16,18,...?Кажется, что оно не очень хорошо будет работать, как минимум нужно пытаться писать некоторую "смерживалку", которая будет пытаться объединить интервалы. И то на подобных интервалах с рваным шагом (2-3 между каждым) она вряд ли что-то сможет сделать. А задача разбить это на минимальное количество шаблонов — нетривиальная сама по себе кмк. И немного выходит за рамки тестового.
Но опять же, критерий истинности — практика, если покажете код который это считает я смогу произвести замеры и сравнить.
lam0x86
10.08.2021 14:11+1Надо будет проверять только пересекающиеся интервалы. В случае с большим количеством значений через запятую будет просто много нодов в дереве, но в результате поиск вернёт только один интервал за O(logN).
Пока что я не готов написать рабочий код из-за отсутствия времени. Может, на выходных доберусь, если тема будет ещё актуальна :)
wataru
11.08.2021 13:34+2Можно за O(1) же делать. Сначала получили как у автора булевый массив. Потом (еще при парсинге) прошлись туда-обратно и предподсчитали для каждого индекса, где стоит следующая/предыдущая еденица в массиве.
Места будет в 33 раза больше занимать, да, но там суммарно будет ну 4kb, вместо 125 байт. Не страшно.
lam0x86
10.08.2021 21:13+2
Пока у меня вот такой результат получается. В некоторых тестах дерево работает медленнее, даже чем в FindNextOld, но зато в сложных случаях показывает 15х производительность.
P.S. Я пока сделал только поиск вперед. Все тесты проходятся нормально.
PsyHaSTe Автор
11.08.2021 11:02Можете дописать тесты на
1,3,6,8,11,13,16,18? В каждом месяце\дне\часе\минуте? Интересно, что выйдет.
lam0x86
11.08.2021 11:38+2Да, тут всё плохо :) Для даты 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
novar
10.08.2021 13:34Цикл по миллисекундам ничего не делает кроме проверки флага в массиве, тут итерации нет смысла считать если их не много тысяч. Итераций где идут изменения даты/времени — не более чем 283 в самом худшем случая когда минимальный год сравнивают с максимальным.
lam0x86
10.08.2021 13:56+1Зачем делать 283 итерации, если можно сделать один поиск в дереве, содержащем один элемент?
Хотя, конечно, без понимания, в каких условиях будет использоваться код, и без проведения перформанс-тестов, невозможно сказать, что будет эффективнее - массивы или деревья. Если в шаблоне будет указано, например, 990 значений миллисекунд через запятую, то поиск значения в дереве в среднем займёт ~5 итераций (при глубине дерева log2(990) ~ 10), а поиск в массиве ~1 (т.к. почти все ячейки будут true).
teology
10.08.2021 15:15Я уже предлагал ваш вариант с эффективным хранением календаря в комментах первой статьи, но меня заминусовали. Они будут создавать массив флагов на 5 кБ, потом героически осуществлять поиск в нем с помощью milliseconds++, а потом писать статью на эту тему.
Только вместо "дерево", надо говорить "массив". Данные надо хранить в восьми массивах.
nsinreal
10.08.2021 16:20Потому что 283 итерации - это константа. Которая зачастую перебьется тем фактом, что вы вместо простой и кэш-френдли структуры массива использовуете развесистое дерево.
Т.е. нужно бенчать, конечно же, но если честно, на глаз дерево не дает сильной выгоды.
lam0x86
10.08.2021 16:35+3Так двоичное дерево легко представляется в виде массива, где корневой элемент под индексом 0, два дочерних под индексами 1 и 2, следующие 4 дочерних под индексами 3-6 и т.д. Таким образом, у элемента T[i] дочерние будут T[i*2 + 1] и T[i*2 + 2].
Вполне себе кэш-френдли.
BugM
11.08.2021 02:27+2Напрашивается анализ исходных данных и выбор формата в зависимости от того что пришло. Конструктор чуть медленее, зато поиск быстрее.
Чтобы совсем упороться по оптимизации.
KHabrUser
11.08.2021 13:56+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); } }
tbl
10.08.2021 11:34Upd:
Ах да, в тексте про это ниже увидел
Странно, что в C# из java не передрали метки циклов (тогда без
gotoможно было бы ссылаться на внешние циклы вbreakиcontinue):mainloop: for (int v : a) { for (int w : b) { if (v == w) continue mainloop; } System.out.println(v); }lam0x86
10.08.2021 11:52+7Таких пропоузлов насчитал штук десять на гитхабе. Большинство закрыто с резолюшном: не будем делать, потому что это тот же самый goto. В данном случае использование goto не является зашкваром.
AVI-crak
10.08.2021 11:50-4За отрезок времени в 51 год можно было создать процессор, который изначально думает текстом, и отдать ему все Unix системы.
vba
10.08.2021 12:04-3Классно, но меня все же смущает GOTO, это по Кнуту преждевременная оптимизация в случае тестого задания. Интересно, как бы автор подошел к данной части если бы использовал F#.
PsyHaSTe Автор
10.08.2021 12:15+4Во-первых не вижу, чем goto тут является оптимизацией — это решение эргономической проблемы "проверяем условие а потом опять проверяем его же чтобы продолжить цикл". То что мы 1 проверку лишнюю убираем просто приятный бонус, основной смысл — не копипастить лишний раз, вводя дополнительную вероятность ошибки.
Во-вторых не вижу, чем тут F# бы отличался — на нем все точно так же будет, только с привкусом ML синтаксиса.vba
10.08.2021 12:40Во-вторых не вижу, чем тут F# бы отличался
Я имел в виду только оптимизацию с ГОТО. Не уверен, что в вашем случае получилось бы заменить ГОТО на более элегантное решение с двойной взаимоисключающей хвостовой рекурсией. Как в данной статье:
- http://sharp-gamedev.blogspot.com/2011/08/forgotten-control-flow-construct.html
Раз уж речь зашла про монады, почему бы не попробовать хвостовую рекурсию(с ее оптимизацией) вместо ГОТО.PsyHaSTe Автор
10.08.2021 12:56+2Ну если мы про ФП и 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; } } }Достаточно умный компилятор смог бы выоптимизировать использование этого энума и получить примерно то же, что и мы. Но шарповый джит, увы, так не умеет, поэтому тут будет терятся перф во-первых на перекидывание таплов туда-сюда, во-вторых на сам вызов функции. Но чисто функционально будет эквивалентно — все тесты проходят (см. бранч)
dom1n1k
10.08.2021 12:35+16Так-себе-код и нормальный код по времени пишутся одинаково долго, но с одним из них работать комфортнее в будущем, а в другой будет противно заглядывать с доработками. Правда, нужно иметь опыт, чтобы было из чего выбирать — чтобы взять хорошее решение про его существование нужно знать.
В рамку и на стену.
KvanTTT
10.08.2021 12:46+7Как-то странно в одной статье видеть рассуждения около
AggressiveInliningиспользуя парсер, который медленней в 50 раз.К сожалению, после замены старого джита на RyuJit он сильно потупел и не догадывается без подсказки соптимизировать подобные кейсы
Я бы не стал делать такие поспешные выводы. Может x86 и туппее (но он устрел и мало кому нужен в 2021 году), но x64 инлайнит правильно. А вот .NET Framework как раз генерирует какую-то дичь.
Не увидел в статье ссылки на полные исходники, можно ткнуть?
PsyHaSTe Автор
10.08.2021 13:00+4Да, я сделал апдейт минут 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нс для нового.novar
10.08.2021 13:18Всё таки возможен случай если заявят экстремальные требования по памяти и парсинг нужно будет перенести прямо в методы поиска ближайшего времени, запоминая в конструкторе только исходную строку.
PsyHaSTe Автор
10.08.2021 13:28+3Так перенос в методы не скорит работу, а только замедлит. Если интервьювер этого не понимает то нужно просто поблагодарить его за потраченное время, встать и уйти.
Я действительно не вижу сценария с изменением расписания каждые 500 наносекунд, который выглядит реалистичным. Если у них другой бизнес-процесс где это требуется то было бы любопытно услышать. Но по факту с такими требованиями им действительно не сишарп, а раст надо было бы брать. Отсюда вывод, что это маловероятно.
Собственно, опять же свои прикидки/оценки/гипотезы все озвучил в статье, и решение сделано исходя из них, и других критериев вроде поддерживаемости, про которые я тоже написал. Если какие-то из них неверны — ну, значит и решение может быть нужно будет изменить в соответствии с условиями. Я исходил из того, что мне казалось наиболее рациональным/вероятным. Но я не ванга, это правда.
Gorthauer87
10.08.2021 13:46+2Экстремальные требования по памяти обычно приводят к замене шарпов на что-то с AOT компиляцией и детерминированной работой с памятью.
PsyHaSTe Автор
10.08.2021 17:31Прошу прощения, немного пропустил этот момент:
Я бы не стал делать такие поспешные выводы. Может x86 и туппее (но он устрел и мало кому нужен в 2021 году), но x64 инлайнит правильно. А вот .NET Framework как раз генерирует какую-то дичь.
Он инлайнит правильно, потому что вы ему подсунули атрибут "инлайни блин!". А вот если его убрать, то и код получается другой. Мне казалось, что старый x64 джит справлялся без подсказок. Но, видимо, это ложная память — нашарплабе не могу воспроизвести. Так что видимо стоит извиниться перед рюджитом — старый судя по всему был не лучше)
KvanTTT
10.08.2021 17:52Он инлайнит правильно, потому что вы ему подсунули атрибут "инлайни блин!".
Тут тоже не все однозначно — возможно .NET заинлайнит и такое, если это будет часто вызываться, т.к. доступна tiered компиляция.
А вообще можно призвать Nagg — может он лучше знает :)
PsyHaSTe Автор
10.08.2021 17:54Да, понятно, что он может заинлайнит. Проблема в том, что может и нет — а нам нужны какие-то гарантии. А для гарантий нужно обвешиваться атрибутами.
Впрочем, не то, что это было слишком сложно. Но в уме держать нужно.
Nagg
10.08.2021 18:54+3В .NET 6.0 инлайнер стал намного агрессивнее (см. https://github.com/dotnet/runtime/pull/52708 и https://github.com/dotnet/runtime/pull/55478) и инлайнит такое без проблем теперь.
PsyHaSTe Автор
10.08.2021 19:03+1О, вот это любопытно, спасибо. Хотя там вроде про PGO (не наш случай) и свитчи (возможно, наш, но нужно проверять). По крайней мере на sharplab'е я не нашел ветки, на которой без атрибута оно бы соптимизировалось. Даже на найтли коммите мастера от 8 августа.
Nagg
10.08.2021 19:09+21) Нет, там не только PGO
2) На шарплабе нет возможности выбирать рантаймы новее .NET 5.0 релиз.
свитч тут не причем, в том коде он разворачивается в обычные ифы розлином
novar
10.08.2021 12:55+1У кого есть опыт по тестовым заданиям, скажите, как заказчики отнесутся к реализации парсинга через комбинаторы из библиотеки Pidgin?
vba
10.08.2021 13:04+2Обычно, когда работодатель хочет хардкора, он так и говорит, "запили на ванильных шарпах". Если ничего такого не говорят, то вы вольны выбирать сторонние библиотеки на ваш выбор. Это кстати тоже может быть частью проверки ваших навыков на "велосипедность".
xFFFF
10.08.2021 14:30+6Этот вопрос надо уточнять у работодателя. Некоторые разрешают, а некоторые категорически против использования каких-либо библиотек. А некоторые не могу внятно ответить, можно ли что-либо использовать. У меня как-то был случай, что дали задание - написать экспорт из бд в *.XLSX. По поводу использования библиотек - сказали сделать на мое усмотрение. Написал с использованием библиотеки ClosedXML и код получился вообще простой. В итоге задание не зачли! Сказали с ClosedXML любой дурак напишет) Переделывать не стал, послал их)
robesper
10.08.2021 14:16-18Эта статья похожа на текущую. Или автор один и сидит под разными учётками? А то странно как-то получается: 2 статьи на одну тему и примерно в одно время.
mayorovp
10.08.2021 15:07+10Может быть, стоит прочитать хотя бы первый абзац статьи перед тем как писать комментарий? На текущий момент там есть, в том числе, та самая ссылка которую вы привели...
robesper
17.08.2021 08:39-2Безусловно стоит, но на момент написания комментария ее там не было. К сожалению, сейчас я это доказать уже не смогу.
PsyHaSTe Автор
17.08.2021 10:31+4Да ну? А я могу доказать, что он там был. Вот гист, где я изначально правил очепятки и прочее в статье. Идем в самую первую ревизию, и видим там вот это:
Я буквально начал текст с этого, потому что хотел, чтобы автор той статьи заменшнился и пришел почитать.
Так что да, стоило прочесть первый абзац.
gwg605
10.08.2021 14:18+1Ну интервьюверы тоже люди, пожалейте их. :)
Мысли и действия вполне разумны, но почему-то вылились в безумно размытый и сложный код.PsyHaSTe Автор
10.08.2021 14:26+7Спасибо за отзыв.
А можеет ткнуть пальцем конкретно, где сложность? И в чем размытость? Потому что самая сложная часть — парсинг — намного проще, чем оригинальный авторский код. И точно куда проще регулярки, которая бы парсила то же самое. А что до остального — один цикл с парой брейков и функция с целым одним генериком.
А что формат сложный — ну, это к авторам вопрос) Был бы проще формат — был бы проще парсер.
Magistr_AVSH
10.08.2021 14:47-5Почему-то на мой взгляд код с if-ами куда проще читаем, чем этот.
MacIn
10.08.2021 18:55+2Полагаю, это вопрос привычки и навыков использования обеих предложенных парадигм. В части именно разбора — данный вариант и впрямь сложнее читается, если ты привык работать с императивными решениями.
Sing
10.08.2021 16:27+8Понравился и подход, и описание, не понравился только код. Немного побуду занудой.
Код читаем: его реально можно прочитать. Нужен парсинг — пошли посмотрели 50 строчек тут, нужно понять как маппится — 20 строчек там, нужно понять, как ищем расписания — ничего проще, вот ещё немного кода.
Я пошёл смотреть код ещё до прочтения статьи, и открыл вот это. Неподготовленный человек это не поймёт. Куча интерфейсов, подменяющих неясно зачем bool и структур, которые называются в стиле «менятель года», но в случае с FalseType (?) они меняют вообще миллисекунды (??), при этом создавая новый DateTime (???).
Я к чему. После прочтения статьи мне стало ясно и для чего такие структуры, и для чего goto. К принятым решениям вопросов нет, но чтобы такой код стал читаем — его нужно аккуратно и понятно документировать. Конечно, этот код — просто иллюстрация к статье, бла бла бла, но это должно быть, всё-таки, стандартным подходом.
P.S. IBool бы я вообще заменил на Direction, а TrueType и FalseType на Forward и Back или типа того, уж очень вводит в заблуждение.PsyHaSTe Автор
10.08.2021 16:41Куча интерфейсов — это два?)
А в остальном все верно, как я в конце написал, есть куда улучшать/расширять. Как опять же говорили классика, разница по стоимости между программой и программным продуктом — отличается на порядки. Я решил простенькую проблему, которую просили в изначальной постановке, а вот со сложнейшими проблемами правильного именования вещей разобраться так просто не всегда выходит. Типы названы от балды, потому что на момент их написания заканчивался последний 8й час, отведенный на работу, и нужно было просто запустить, удостовериться что результаты остаются корректными и начать писать статью. Конечно же, можно и нужно лучше, просто я поленился.
Sing
10.08.2021 17:33+2Куча интерфейсов — это два?)
Ага, но тут слово «куча» относится и к интерфейсам, и к структурам, т.е. подразумевается прочтение «куча интерфейсов и структур».PsyHaSTe Автор
10.08.2021 17:35Что я могу тут ответить — чем дальше сидишь над тестовым заданием, тем труднее соблюдать хорошие практики, рассовывать сущности по правильным файлам, корректно их именовать и вот это все. Вспоминая известную картинку
Sing
10.08.2021 17:42+2Это, кстати, можно вынести в итоги. В частности, я бы заметил, что для тестового задания не стоит себя вгонять в нереальные рамки. Либо разбивать «сидение» на части. В целом, писать сначала как получится, а потом возвращаться и смотреть свежим взглядом. Это всё, к слову, противоречит вот этому выводу:
так-себе-код и нормальный код по времени пишутся одинаково долго
Нормальный код всё-таки требует большего внимания к «мелочам», и — увы — займёт больше времени, но на дистанции это оправдается
t-nick
10.08.2021 22:22+2Если читать снизу вверх, то похоже на эволюцию продукта от стартапа с одним разработчиком до SCRUM команды с комит полиси.
t-nick
10.08.2021 22:29+1Я, все же, обычно дописываю до точки, и причесываю код и структуру проекта перед отправкой. А если ставят дедлайны, лучше попросить больше времени или забить на потенциально стрессовое место работы. Еще нужно понимать, что если у вас получается долго, то это не значит, что у другого кандидата выйдет быстрее при одинаковом качестве результата. Возможно авторы задания просто недооценили его сложность.
nsinreal
10.08.2021 16:58+3Монадический парсер — очень клево.
Вы вот повторяете, что решение на регулярках выглядело бы ужасным. См. мое: https://gist.github.com/vlova/544d693cc4083caafa477383b2e1c216. Неужели вам и вправду кажется, что такое решение ощутимо сложнее и read-only? (Но я согласен, что у регулярок есть много других недостатков в сравнении с полновесным парсером)
К слову, о перфомансе парсера. Из того, что я прочитал о Pidgin, часть замедления идет от того, что он не полностью компилируется. В теории, если кто-то упрется в перфоманс Pidgin, то может быть резонно подправить его внутренности, а не переписывать код. В таком случае решение @novarне будет выигрывать вообще никак.
PsyHaSTe Автор
10.08.2021 17:05+1Ну, да, согласен, думал, что выйдет хуже. Но все равно кода довольно много (45..177 — больше сотни строк). И тут как раз минус в том, что нельзя собрать парсер из "кубиков" — нужно парсить сразу всё или ничего. Получилось выделить отдельно ParseCronSubRange — это конечно намного упростило результирующую регулярку. Но вот основной формат, увы, приходится матчить по принципу "пан или пропал".
Но да, в таком аккуратном виде это в принципе можно читать и расширять.
К слову, о перфомансе парсера. Из того, что я прочитал о Pidgin, часть замедления идет от того, что он не полностью компилируется. В теории, если кто-то упрется в перфоманс Pidgin, то может быть резонно подправить его внутренности, а не переписывать код. В таком случае решение novarне будет выигрывать вообще никак.
Ну в теории возможно вообще всё, языки ведь тьюринг-полные) Вопрос тут только в том, насколько легко можно подлезть туда, чтобы это можно было сделать. Я обожаю зиро-кост стейт машины, что асинк, что парсеры, что итераторы — в общем, любые монадки которые оптимизируются в ноль в рантайме это прям огромное удовольствие. Пару лет назад был доклад ребят, который писали красивый код в ду-нотации который в их монаде интерпретировался как ассемблер конкретного процессора, и генерировался оптимальный код, лучше, чем тот, что выдает компилятор на этой платформе. Это прям замечательный доклад был, жалко, я записи в интернете не смог найти. Этим же кстати крут раст — там итераторы/асинки оптимизируются зирокостно так, что иногда могут быть более производительными, чем ручная реализация. Просто потому, что компилятору разрешено несколько больше, чем обычному пользователю, при этом он достаточно умный чтобы сгенерировать код не хуже ручного.
nsinreal
10.08.2021 17:43+1Но все равно кода довольно много (45..177 — больше сотни строк).
Кода много, потому что используется только C#. Очевидно, что Pidgin как решение для парсинга будет предоставлять определенный сахар.
Кроме того, этот код является эквивалентом ParserHelper.cs 23-117 + ScheduleFormat.cs 21-71. Итого, у вашего решения 144 строки, у моего 132. Можно играться в подсчет строк и дальше, но вряд-ли найдется подсчет, показывающий существенную разницу.
И тут как раз минус в том, что нельзя собрать парсер из "кубиков" — нужно парсить сразу всё или ничего. Получилось выделить отдельно ParseCronSubRange — это конечно намного упростило результирующую регулярку. Но вот основной формат, увы, приходится матчить по принципу "пан или пропал".
Это ошибочное восприятие. Основной формат матчится целиком, потому что разбивать матчинг на блоки поменьше — это не очень осмысленно. Но мы, конечно же можем их разбить, просто получится чуть больше кода.
А вот в вашем случае вам просто необходимо разбивать на отдельные кубики, потому что если не разбить, то не получится пометить кубик как Optional.
Вопрос тут только в том, насколько легко можно подлезть туда, чтобы это можно было сделать.
Нужно реализовать свой IQueryable, который будет при создании query делать агрессивный инглайнинг Expression<Func<>> внутрь друг друга. В принципе, я не вижу такой уж сложности в задаче. Но работы предстоит дофига, конечно.
anonymous
00.00.0000 00:00nsinreal
10.08.2021 17:45+1В случае миллисекунд их отсутствие значит не [0, 1, … 999], а [0].
В остальных случаях экономия будет несущественная, зато просядет производительность и читабельность (за счет дополнительного if).
PsyHaSTe Автор
10.08.2021 17:46Ну да, мы сэкономим немного памяти (до 2кб суммарно) и слегка ускорим кейс со звездочками. Но при этом мы ощутимо замедлим все остальные сценарии, потому что теперь у нас будет
_allowedPoints?[point - Begin] ?? true, и факт разрешенности точки будет прятаться заifом.
Плюс у нас не получится иметь текущий интерфейс с разрешением конкретных точек, придется его менять, чтобы передавать_allowedPointsв конструкторе. В целом, ничего страшного, но нужно это учитывать.В общем, выигрываем мы на этом или нет — спорно, мне кажется, что так не стоит делать. Но без замеров сказать ничего не получится, в любом спорной ситуации нужно расчехлять профайлер и проверять, догадка — залог оверинженерного кода в будущем)
Upd. Выше уже написали, и да, там верно написали про отдельный случай с миллисекундами. Как раз из-за того что мы вшили
?? trueв структуру, которая раньше была очень простой и не имела логики никакой, вся логика была в отдельном слое (SRP). А теперь мы часть логики переложили туда и немножко продолбались, и тут уже либо костылять конкретно под миллисекунды (например, принимать в конструкторе аргумент "что делать если нулл"), либо просто так не делать.
0xd34df00d
11.08.2021 00:06+1public struct Test { [MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)] public static bool IsTrue<T>() where T : struct, IBool => default(T) switch { TrueType _ => true, FalseType _ => false }; }
У меня тут такой глупый вопрос как у не знающего C# — это же switch expression? Если да, то он должен быть тотальным? Если да, то откуда компилятор знает, что других реализацийIBoolнет?nsinreal
11.08.2021 01:04+1Это switch expression. Не должен быть тотальным с точки зрения компилятора. Рантайм просто кинет исключение, если не найдёт подходящего кейса. См. https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/switch-expression#non-exhaustive-switch-expressions
Хотя там написано, что в случае нетотальности получишь варнинг. И не очень понятно, как это проверяется, так что возможно ваш вопрос ещё актуален.
PsyHaSTe Автор
11.08.2021 01:20+3В сишарпе он вставляет неявно дефолтный кейс с паникой (выбрасыванием эксепшна). Так что тут просто варнинг а-ля
[-Wincomplete-patterns] Pattern match(es) are non-exhaustive. Тотальность соответственно никак не проверяется, более того, тотальности тут и нет, т.к. никакого аналога скаловым кейс классам тут нет и никто не запрещает реализовать интерфейс другими типами. Так что тут все на честном слове джентельмена "других реализаций писать не будем" и дисциплине, увы.
edo1h
11.08.2021 03:45+1Отдельно хочу отметить линейную структуру поиска без триллиона 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; }да, ваше решение будет немного производительнее, в реальной же жизни особой разницы не будет (что и показывает ваш бенчмарк).
PsyHaSTe Автор
11.08.2021 10:56Бенчмарк показывает улучшение в 2 раза в некоторых случаях, так что сложно сказать, что он ничео не показывает. Нужно просто больше форматов сравнить (хотя бы штук 30), но подбирать грамотно опять же данные для бенчмарка этот нетривиально, и выполняться оно будет часами. Никто не спорит, что можно было оставить оригинальный алгоритм, просто инвертировав условия, я просто немного иначе сделал.
edo1h
11.08.2021 06:00+3Вооружившись магией ООП берем и за 2 минуты реализуем нужный функционал
…
В итоге через пару дней проглядывая код
alex-khv
11.08.2021 13:37+1Хм. Статьи про плохих hr и плохие тестовые на Хабре любят.
А что если автору на работе надо было написать поддерживаемый код. Но вместо переделки старого он выдумал историю и стал ждать элегантное решение в комментариях ? А тут как раз ещё статья появилась. А может ещё и не одна появится
novar
11.08.2021 14:48+2Даже если так, то ничего плохого я не вижу. Люди посмотрели, примерили разные алгоритмы и паттерны, поделились своим мнением. Все вынесли какие то уроки для себя, произошло развитие. Ну а я, как автор исходной статьи, не стал бы пытаться выгораживать свой код и оправдываться если бы хотел лишь получить улучшенный вариант.
nsinreal
11.08.2021 16:47+5Что это решение, что оригинальное — обладает одним существенным недостатком. Вместо того, чтобы быстро передвигаться к следующему числу в интервале, мы делаем инкремент и проверку, пока не найдем подходящее число. Это довольно тупо — мы же следующее число знаем.
Я решил сделать следующее. Взять 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.
Подозреваю, что заменить мемоизацию на предпосчет, то вообще очень шустро будет.
PsyHaSTe Автор
11.08.2021 17:10+1Хорошее решение, опять же, не влезло по бюджету времени)
Вот этот момент любопытный: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, мы перескакиваем год и дальше начинаем пересчет с самого начала.
Подход в любом случае классный, думал про него, но опять же решил, что это сложнее чем то что я готов сейчас реализовывать) Спасибо за то, что поделились
nsinreal
11.08.2021 17:20Да, на границах там ярый костыль, потому что сильно морочиться не хочется. И получилось квадратно-гнездовое.
Если по-хорошему. В случае, если у нас разрешены первые 3 месяца (1,2,3), а мы тыкаем в 4-й, то мы должны увеличить год и перенести на первый месяц. Т.е. должны выдать что-то типа (End + _allowedPoints.Min). Но это не будет работать для дней (потому что 32 и потому что разное количество дней в месяце) — а это уже черт знает как поправить.
edo1h
11.08.2021 17:16+1Подозреваю, что заменить мемоизацию на предпосчет, то вообще очень шустро будет.
ну это очевидная идея хранить вместо флага «подходит/не подходит» номер следующего подходящего, ЕМНИП в комментариях к первоначальной статье её высказывали.
но (особенно с учётом того, что поиск нужен в две стороны) ИМХО это оверкилл для тестового задания.да и не для тестового, я бы остановился на варианте с минимумом LoC (ну и с максимально понятным/простым кодом, хотя, конечно, это субъективный показатель). а если уж нужны будут жёсткие оптимизации — идти дальше (в 99.999999% случаев они не нужны)
nsinreal
11.08.2021 19:39Да, конечно, это оверкил и практически не нужно. Как и трюки с IBool и агрессивным инлайнингом.
В рабочем коде для первой итерации я бы оставил просто TODO
DnAp
12.08.2021 07:59Чтобы не использовать goto, можно вынести содержимое верхнего while в отдельную функцию и делать return
bravmi
14.08.2021 08:29+1Не знаю шарпа, но прочитал с удовольствием, спасибо. :)
Единственно, у вас тут противоречие)
Задание нормальное, как на джуна так и на сениора: просто у них решение будет отличаться.
В общем, задание в целом странноватое: слишком сложное для джуна, слишком долгое для сениора.
olegbask
15.08.2021 20:32А нельзя эту задачу решить без построения велосипедов? Прикрутить имеющийся парсинг или либу?
И я так и не понял, где история эпичного фейла прочитав всю статью
tnm
17.08.2021 18:30Я решил велосипедами.
Также фэйл: "Ваше решение не работает".
https://github.com/Vladislav-Petrovykh/ScheduleProject
Кто нибудь тестил все возможные вариации заданных форматов года/месяца/дня и т.д.?PsyHaSTe Автор
17.08.2021 18:33Все варианты проверить невозможно :) Можно проверить только достаточно много. Я взял авторские тесты кои проверяют емнип штук 30 разных форматов. Можно было бы заморочиться и взять какие-нибудь проптесты, чтобы они генерировали примеры. Было бы чуть надежнее, там можно было бы проверить на сотнях разных инпутов, но это уже точно не вписывается в рамки тестового.
debagger
Шикарно!