Так сложилось, что активно кодировать мне не удается уже лет пять. Так что каждый шанс залезть в код и напакостить там товарищам воспринимается с радостью, как возможность тряхнуть стариной и убедиться что есть еще “ягоды в ягодицах” (ака шило в жопе). Да, и сразу оговорюсь, что статья скорее туториал, не из серии «смотрите ух как круто я могу», а из серии «о, какой удачный вариант показать на простом примере применение технологии, которая у некоторых коллег вызывает затруднения». Моё глубокое убеждение что подобные решения должны входить в арсенал любого разработчика на 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. Ну и да, после того как потешил шаловливые ручки, то посмеялся от души над самой идеей необходимости поиска вообще. Все-таки потому у тела, движущегося по баллистической траектории, скорость хаотически не меняется, а значит надо всего лишь найти коэффициент соответствующий начальной скорости, а потом уныло ползти к началу таблицы, когда скорость падает до следующего диапазона. Но это уже совсем другая, не такая интересная история, о том, чем разработка отличается от кодирования. А так хочется иногда просто покодировать. 🙂