Так сложилось, что активно кодировать мне не удается уже лет пять. Так что каждый шанс залезть в код и напакостить там товарищам воспринимается с радостью, как возможность тряхнуть стариной и убедиться что есть еще “ягоды в ягодицах” (ака шило в жопе). Да, и сразу оговорюсь, что статья скорее туториал, не из серии "смотрите ух как круто я могу", а из серии "о, какой удачный вариант показать на простом примере применение технологии, которая у некоторых коллег вызывает затруднения". Моё глубокое убеждение что подобные решения должны входить в арсенал любого разработчика на C#.
Давеча я ревьювил код, который включает в себя многошаговый процесс аппроксимации, в который активно вовлечено постоянное получение коэффициента (Коэффициент выбирается для диапазона значений. Если кому важны детали - речь идет о моделировании движения тела оживальной формы, без собственного движителя, в атмосфере. А выбор идет из таблицы КСФ Игалла по текущей скорости тела (диапазон скоростей соответствует конкретному КСФ, порядка 300 элементов в таблице).
Процесс многошаговый, операция поиска выполняется часто, и ребятишки-разработчики были молодцы, пошли даже дальше чем бинарный поиск, реализовали вычисление целочисленного ключа для диапазона значений и получение коэффициента по этому ключу через Dictionary А поскольку команда Agile, а я, гадкий, еще и SixSigma и очень люблю все видеть в цифрах - то ребята убедительно показали эффективность выбранного решения. На 1 расчет из 1000 точек аппроксимации затраты составляют:
Линейный поиск в таблице - 0.6ms
Линейный поиск цепочкой if-return - 0.1ms
Поиск делением пополам - 0.08ms
Поиск словарем - 0.018ms
На стол ко мне это попало в тот момент, когда проект дополз до этапа “а теперь делаем эти же расчеты еще и на микроконтроллере”. Оказалось что с переносом словаря как-то не очень (да, могли бы подумать и заранее, но они в первый раз столкнулись с микроконтроллерами, так что простим им это упущение).
Спасибо команде, цифры для “думать” они уже посчитали, и я обратил внимание что выигрыш “чистого кода” против поиска в структуре данных - в 6 раз (первые строчки). А экономия словаря против деления пополам - чуть больше 4 раз.
И тут как раз возник тот самый момент “чешутся ручки”, и совпало два фактора - во-первых, я большой поклонник data-driven архитектур, уже лет 20 как. А во-вторых .NET предоставляет совершенно уникальные средства для построения кода “на лету”. Так почему бы не попробовать построить цепочку операторов if для двоичного поиска из таблицы, и сделать это в виде Linq выражения? А ничего не препятствует, на самом деле. А главное, что та же логика потом хорошо подойдет для того, чтобы просто сгенерить код “табличной” функции для более примитивной архитектуры микроконтроллера.
Сказано - сделано. Используем всё тоже старое доброе деление пополам исходного массива коэффициентов. Логика простая - если значение попал в диапазон среднего элемента таблицы - возвращаем коэффициент из среднего элемента. Если меньше диапазона - уходим по цепочке if, построенных из левой части таблицы коэффициентов, если больше диапазона - уходим по цепочке if, построенных из правой части таблицы.
Начнем с оператора if, который проверяет попадание значения в диапазон и возвращает коэффициент, если мы попали. Код очень простой - функция получает параметры range (диапазон), коэффициент, который надо вернуть (value), ссылку на исходное значение (v) и ссылку на точку возврата. Функция строит, соответственно, три Linq элемента - оператор возврата, условие для if и сам if. Получается аналог конструкции
If (v >= from && v < to) return value;public Expression CreateSimpleIf(double from, double to,
double value,
Expression v, LabelTarget returnTarget)
{
var returnStmt = Expression.Return(
returnTarget,
Expression.Constant(value));
var ifCondition = Expression.AndAlso(
Expression.GreaterThanOrEqual(v, Expression.Constant(from)),
Expression.LessThan(v, Expression.Constant(to)));
return Expression.IfThen(ifCondition, returnStmt);
}Теперь построим цепочку операторов для массива диапазонов. Я отдельно обрабатываю ситуации в 1 и 2 элемента, это необязательно, но у меня чисто рефлекс чуть-чуть, но ускорить код там, где можно.
На входе нам нужен уже массив диапазонов, и все те же значение для сравнения и указатель на точку возврата.
Получается аналог конструкции
if (v >= mid.from && v < mid.to)
return mid.value
if (v < mid.from)
return search in (0...mid-1)
else
return search in (mid + 1...length - 1);Span используется что бы избежать пересоздания массивов/списков в которых хранятся коэффициенты и/или чтобы не таскать за собой два дополнительных параметра “начало диапазона в таблице для поиска и конец диапазона в таблице для поиска”.
public Expression CreateSpanExpression(Span<Coefficient> span,
Expression v,
LabelTarget returnTarget)
{
if (span.Length == 1)
return CreateSimpleIf(span[0].RangeFrom,
span[0].RangeTo,
span[0].Value,
v, returnTarget);
else if (span.Length == 2)
{
Expression[] ifs = new Expression[2];
ifs[0] = CreateSimpleIf(span[0].RangeFrom,
span[0].RangeTo,
span[0].Value,
v, returnTarget);
ifs[1] = CreateSimpleIf(span[1].RangeFrom,
span[1].RangeTo,
span[1].Value,
v, returnTarget);
return Expression.Block(ifs);
}
else
{
int mid = span.Length / 2;
Expression[] blocks = new Expression[2];
blocks[0] = CreateSimpleIf(span[mid].RangeFrom,
span[mid].RangeTo,
span[mid].Value,
v, returnTarget);
var leftSide =
CreateSpanExpression(span.Slice(0, mid),
v, returnTarget);
var rightSide =
CreateSpanExpression(span.Slice(mid + 1,
span.Length - mid - 1),
v, returnTarget);
Expression condition =
Expression.LessThan(v,
Expression.Constant(span[mid].RangeFrom));
blocks[1] = Expression.IfThenElse(condition, leftSide, rightSide);
return Expression.Block(blocks);
}
} Ну и осталось дело за малым - превратить это в функцию. Надо создать описание параметров, описание типа возвращаемого значения, создать lambda-выражение и скомпилировать все это в исполняемый код.
public Func<double, double> CreateBTReeExpression()
{
var value = Expression.Parameter(typeof(double), "value");
var returnTarget = Expression.Label(typeof(double));
var ifs = CreateSpanExpression(mCoefficients.ToArray(),
value, returnTarget);
var body = Expression.Block(typeof(double),
new Expression[]
{
ifs,
Expression.Label(returnTarget,
Expression.Constant(0.0))
});
var expression = Expression.Lambda(typeof(Func<double, double>),
body,
new ParameterExpression[] { value });
var functionDelegate = expression.Compile();
return (Func<double, double>) functionDelegate;
}Ок, проверяем, а стоило ли оно хлопот? По замерам у меня получилось 0.012ms, или в 1.5 раза быстрее использования Dictionary. Ну и плюс появившаяся возможность легко адаптировать код для генерация исходного кода функции для микроконтроллера.
Главный недостаток этого метода, мешающий его внедрению, состоит в том, что программисту приходится думать “наоборот” - от действия к условию и писать не код, линейно отражающий процесс, который мы автоматизируем, а строить в голове “дерево” операций. Динозаврам типа меня, еще помнящим программирование в обратной польской записи на программируемых микрокалькуляторах и на языке Форт - в принципе привычно, а вот для более продвинутых коллег это может оказаться мозголомным знанием.
Второй недостаток в том, что, к сожалению, “отладчиком в IDE” по такому коду не походишь, а значит надо возвращаться к старым добрым методам отладки по снятию контрольных показателей и сравнению с ожидаемым эталоном.
Это сильно ограничивает популярность такого подхода, но, как мне кажется, он всё равно стоит внимания, все-таки выгоды по производительности в некоторых ситуациях, как в приведенной задаче, которая, увы, даже не может быть распараллелена в силу природы алгоритма (следующий шаг сильно зависит от того, что насчитали раньше). И для таких задач вопрос повышения производительности решается все теми же “старыми, добрыми методам”.
Ну и лично я считаю это не недостатками, а скорее достоинствами – в итоге, не смотря на затраты времени, такие упражнения повышают эффективность команды и способность её решать новые и необычные задачи. Но навязывать это как silver bullet я конечно не решусь.
P.S.: Ну и да, после того как потешил шаловливые ручки, то посмеялся от души над самой идеей необходимости поиска вообще. Все-таки потому у тела, движущегося по баллистической траектории, скорость хаотически не меняется, а значит надо всего лишь найти коэффициент соответствующий начальной скорости, а потом уныло ползти к началу таблицы, когда скорость падает до следующего диапазона. Но это уже совсем другая, не такая интересная история, о том, чем разработка отличается от кодирования. А так хочется иногда просто покодировать.
