Как стать автором
Обновить

Когда программисту нечего делать или оптимизируем код при помощи Linq.Expression

.NET

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

Теги:C#linqcompilation
Хабы: .NET
Всего голосов 10: ↑8 и ↓2+6
Просмотры5.9K

Похожие публикации

Лучшие публикации за сутки