Динамическое программирование си шарп

Динамическое программирование — C#

Задание 1. В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Входные данные Во входном файле INPUT.TXT задано два числа N и M – размеры таблицы (1 ≤ N ≤ 20, 1 ≤ M ≤ 20). Затем идет N строк по M чисел в каждой – размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол. Пример INPUT.TXT OUTPUT.TXT 3 4 1 1 1 1 5 2 2 100 9 4 2 1 8

Код к задаче: «Динамическое программирование»

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Tablicalab6msd < class Program < static void Main(string[] args) < int s=2, st=2; int i, j; int[,] mas = new int[s, st]; int c=0,sum; Console.WriteLine("Введите элементы матрицы:"); for (i = 0; i < s; i++) < for (j = 0; j < st; j++) < mas[i, j] = int.Parse(Console.ReadLine()); >> for (i = 0; i < s; i++) < for (j = 0; j < st; j++) < sum=mas[i,j]+=Min(mas[i,j-1],mas[i-1,j])+mas[i,j]; //if (mas[i, j + 1] < mas[i + 1, j]) < j++; mas[i, j+1] =c; >//else < i++; mas[i+1,j]=c; >> > Console.WriteLine(sum); Console.ReadLine(); > > >

Источник

Динамическое программирование на C#.

Рассмотрим ещё одну задачу. Имеется два массива целых чисел – массив А и массив Б. Наша задача подсчитать количество элементов массива Б, совпадающих с каким либо элементом массива А.

public int Search(int[] a, int[] b) < int count = 0; foreach (int i in b) < foreach (int j in a) < if (i == j) < count++; break; >>> return countt;>

Ясно, что быстродействие данного алгоритма зависит главным образом от внутреннего цикла. Потому можно предположить, что быстродействие существенно возросло, ели бы нам удалось заменить внутренний цикл примерно вот такой гипотетический код

Разработчики компиляторов достигли больших успехов в оптимизации оператора switch. Он выполняется много быстрее соответствующего цикла. Этим мы и хотим воспользоваться. Мешает одно – в операторе case могут фигурировать только константные выражения, а значения элементов массива нам при компиляции не известны.

Но известны в во время исполнения! Поэтому мы принимаем решение написать код этого switch’а во время исполнения. Надеюсь, что теперь вас это уже совсем не удивляет. Остаётся только вопрос «как?». Ответ — switch будем писать прямо на C#! Готовы? Тогда вперёд!

Пример динамического программирования на C#.

using System;using System.Reflection;using System.Text;using System.CodeDom.Compiler;using Microsoft.CSharp; namespace DynUnloop < // Проверка в цикле class SearchLooping < public int Search(int[] a, int[] b) < int count = 0; foreach (int i in b) < foreach (int j in a) < if (i == j) < count++; break; >> > return count; > > // Проверка cгенерированным switch’ом public interface IChecker < bool Check(int valMax); >class SearchFlat < IChecker WriteCode(int[] a) < StringBuilder code = new StringBuilder(); code.Append("\n namespace DynUnloop"); code.Append("\n < class Checker: IChecker"); code.Append("\n < bool IChecker.Check(int n)"); code.Append("\n < switch (n)"); code.Append("\n <"); foreach (int j in a) code.Append("\n case " + j + ":"); code.Append("\n return true;"); code.Append("\n >«); code.Append(«\n return false;»); code.Append(«\n > > >\n»); //Console.Write(code.ToString()); // проверяем сгенерированный код CSharpCodeProvider cs = new CSharpCodeProvider(); ICodeCompiler csc = cs.CreateCompiler(); CompilerParameters pars = new CompilerParameters(); pars.ReferencedAssemblies.Add(Assembly.GetExecutingAssembly().Location); CompilerResults result = csc.CompileAssemblyFromSource(pars, code.ToString()); // компилируем! if (result.Errors.Count!= 0) < foreach(CompilerError err in result.Errors) Console.WriteLine(err.ToString()); return null; >Assembly asm = Assembly.LoadFrom(result.PathToAssembly); return (IChecker)asm.CreateInstance(«DynUnloop.Checker»); > public int Search(int[] arr1, int[] arr2) < if (this.code == null) this.code = WriteCode(arr1); int result = 0; foreach (int i in arr2) < if (this.code.Check(i)) // используем сгенерированный код result++; >return result; > IChecker code = null; > class Test < [STAThread] static void Main(string[] args) < int[] a = < // Подсчитываем вхождения этих чисел в масссив arr2.74, 97, 93, 86, 2, 78, 48, 14, 21, 58, 60, 5, 39, 4, 66, 9, 31, 15, 69, 27, 37, 46, 62, 61, 81, 17, 88, 19, 44, 8 >; int[] b = < // В этом массиве ищем числа из, содержащиеся в arr1. 98, 53, 79, 47, 0, 39, 28, 18, 39, 49, 56, 17, 33, 19, 72, 13, 28, 48, 21, 80, 10, 3, 67, 76, 83, 6, 40, 58, 23, 74, 81, 88, 13, 48, 59, 83, 47, 1, 38, 63, 70, 21, 23, 30, 86, 71, 15, 25, 32, 73, 23, 55, 52, 19, 90, 95, 84, 2, 63, 93, 98, 69, 93, 64, 66, 66, 3, 84, 58, 88, 64, 26, 9, 56, 9, 88, 78, 37, 88, 11, 89, 14, 26, 49, 50, 26, 36, 93, 56, 63, 97, 44, 37, 44, 64, 1, 26, 58, 62, 19, 68, 30, 66, 42, 9, 96, 45, 94, 9, 2, 17, 46, 12, 51, 3, 83, 43, 44, 14, 40, 30, 9, 27, 94, 90, 19, 87, 64, 91, 8, 61, 20, 74, 69, 42, 59, 47, 82, 40, 52, 80, 41, 83, 54, 45, 50, 31, 85, 41, 80, 56, 80, 44, 22, 88, 58, 3, 70, 51, 88, 8, 80, 2, 1, 39, 96, 71, 42, 8, 43, 35, 59, 4, 60, 59, 88, 25, 72, 48, 39, 86, 1, 23, 11, 50, 79, 74, 52, 79, 83, 56, 75, 31, 50, 43, 0, 38, 82, 14, 48, 78, 88, 77, 97, 44, 96, 76, 83, 61, 0, 32, 30, 22, 12, 1, 7, 56, 90, 49, 58, 21, 18, 62, 23, 85, 58, 28, 52, 16, 58, 49, 42, 57, 98, 59, 97, 23, 25, 65, 53, 3, 90, 89, 79, 50, 25, 53, 18, 49, 36, 42, 47, 33, 54, 27, 59 >; const int countIterations = 200000; //////////////////////////////////////////// SearchLooping searchLoop = new SearchLooping(); DateTime start = DateTime.Now; int count = 0; for (int it = 0; it < countIterations; it++) count = searchLoop.Search(a, b); TimeSpan span = DateTime.Now - start; Console.WriteLine("Search with looping. Count = , Elapsed msec= ", count, span.TotalMilliseconds); /////////////////////////////////////////// SearchFlat searchFlat = new SearchFlat(); DateTime start2 = DateTime.Now; int count2 = 0; for (int it = 0; it < countIterations; it++) count2 = searchFlat.Search(a, b); TimeSpan span2 = DateTime.Now - start2; Console.WriteLine("Search with switch. Count = , Elapsed msec= ", count2, span2.TotalMilliseconds); Console.ReadLine(); > >>

Вот результат, говорящий сам за себя.

В заключение хочу рассказать вам о ещё одном классе задач, где применение динамического программирования может дать существенный выигрыш в эффективности.

Это задачи с гибким (многовариантным) нижним уровнем. (Название я придумал сам, так что наверняка есть более правильное.) Что я имею в виду под словами «гибкий нижний уровень»?

Примерно следующее. Представьте себе, что вы разрабатываете библиотеку для обработки некоторых данных. При этом все ваши алгоритмы оперируют данными с помощью некоторых унифицированных методов доступа. Эти методы доступа скрывают от ваших алгоритмов всё разнообразие типов данных и способов доступа к ним, скрывают их разнообразные параметры и настройки. Методы доступа универсальны (гибки), а, значит, вряд ли обладают достаточной эффективностью (универсальность и эффективность редко сочетаются). Вы могли бы реализовать частные методы доступа, но разнообразие типов и параметров данных так велико, что задача становится невыполнимой. Из-за этого вам приходится мириться с недостаточной эффективностью кода.

Тут на помощь приходит динамическое программирование. Частные методы доступа можно сгенерировать «на лету», в тот момент, когда типы и параметры данных вам уже известны, что позволит создать максимально эффективный код. В этом случае нет нужды обеспечивать универсальность, ведь сгенерированный код будет использован только для того типа данных, с которым вы работаете сейчас.

Другими словами, вы откладываете реализацию нижнего уровня до момента обработки конкретных данных, прописывая настройки прямо в коде (перенося данные в код, учитывая настройки непосредственно при генерации кода, выражая данные в виде кода) и получаете за это максимальную эффективность.

Примером может служить реализация класса RegExp в демонстрационной версии CLR – Rotor. Класс RegExp позволяет производить поиск и замену в тексте на основе регулярных выражений. В данном случае регулярное выражение играет роль того самого гибкого метода доступа (фильтра). Динамическое генерирование метода проверки соответствия регулярному выражению, позволяет в несколько раз повысить скорость поиска и замены текста. Подробности реализации класса RegExp вы можете изучить по исходникам Rotor’а [7].

Мне же на этом пора заканчивать. Надеюсь, мне удалось вызвать у вас интерес к обсуждаемой теме и помочь сделать первые шаги в столь увлекательной и перспективной области, как программирование с использованием метаданных. Удачи!

Источник

Dynamic в C#: рецепты использования

Это заключительная часть цикла про Dynamic Language Runtime. Предыдущие статьи:

1. Подробно о dynamic: подковерные игры компилятора, утечка памяти, нюансы производительности. В этой статье подробно рассматривается кэш DLR и важные для разработчика моменты, с ним связанные.
2. Грокаем DLR. Общий обзор технологии, препарирование DynamicMetaObject и небольшая инструкция о том, как создать собственный динамический класс.

Когда без dynamic не обойтись

Таких случаев нет. Всегда можно написать аналогичный по функционалу код в статическом стиле, разница лишь в удобстве чтения и объеме кода. Например, при работе с COM-объектами вместо dynamic можно использовать рефлексию.

Когда dynamic полезен

Работа с COM-объектами

В первую очередь это, конечно же, работа с COM-объектами, ради которой всё это и затевалось. Сравните код, получившийся при помощи dynamic и при помощи рефлексии:

dynamic instance = Activator.CreateInstance(type); instance.Run("Notepad.exe");

var instance = Activator.CreateInstance(type); type.InvokeMember("Run", BindingFlags.InvokeMethod, null, instance, new[] < "Notepad.exe" >);

Как правило, для работы с COM-объектами через рефлексию приходится создавать развесистые классы с обертками под каждый метод/свойство. Есть и менее очевидные плюшки типа возможности не заполнять ненужные вам параметры (обязательные с точки зрения COM-объекта) при вызове метода через dynamic.

Работа с конфигами

Ещё один хрестоматийный пример — работа с конфигами, например с XML. Без dynamic:

XElement person = XElement.Parse(xml); Console.WriteLine( $" " );

dynamic person = DynamicXml.Parse(xml); Console.WriteLine( $" " );

Разумеется, для этого нужно реализовать свой динамический класс. В качестве альтернативы первому листингу можно написать класс, который будет работать примерно так:

var person = StaticXml.Parse(xml); Console.WriteLine( $" " ); 

Но, согласитесь, это выглядит гораздо менее изящно, чем через dynamic.

Работа с внешними ресурсами

Предыдущий пункт можно обобщить на любые действия с внешними ресурсами. У нас всегда есть две альтернативы: использование dynamic для получения кода в нативном C# стиле либо статическая типизация с «магическими строками». Давайте рассмотрим пример с REST API запросом. С dynamic можно написать так:

dynamic dynamicRestApiClient = new DynamicRestApiClient("http://localhost:18457/api"); dynamic catsList = dynamicRestApiClient.CatsList;

Где наш динамический класс по запросу свойства отправит запрос вида

[GET] http://localhost:18457/api/catslist

Затем десериализует его и вернем нам уже готовый к целевому использованию массив кошек. Без dynamic это будет выглядеть примерно так:

var restApiClient = new RestApiClient("http://localhost:18457/api"); var catsListJson = restApiClient.Get("catsList"); var deserializedCatsList = JsonConvert.DeserializeObject(catsListJson); 

Замена рефлексии

В предыдущем примере у вас мог возникнуть вопрос: почему в одном случае мы десериализуем возвращаемое значение к конкретному типу, а в другом — нет? Дело в том, что в статической типизации нам нужно явно привести объекты к типу Cat для работы с ними. В случае же dynamic, достаточно десериализовать JSON в массив объектов внутри нашего динамического класса и вернуть из него object[], поскольку dynamic берёт на себя работу с рефлексией. Приведу два примера того, как это работает:

dynamic deserialized = JsonConvert.DeserializeObject(serialized); var name = deserialized.Name; var lastName = deserialized.LastName;

Attribute[] attributes = type.GetCustomAttributes(false).OfType(); dynamic attribute = attributes.Single(x => x.GetType().Name == "DescriptionAttribute"); var description = attribute.Description;

Тот же самый принцип, что и при работе с COM-объектами.

Visitor

С помощью dynamic можно очень элегантно реализовать этот паттерн. Вместо тысячи слов:

public static void DoSomeWork(Item item) < InternalDoSomeWork((dynamic) item); >private static void InternalDoSomeWork(Item item) < throw new Exception("Couldn't find handler for " + item.GetType()); >private static void InternalDoSomeWork(Sword item) < //do some work with sword >private static void InternalDoSomeWork(Shield item) < //do some work with shield >public class Item < >public class Sword : Item <> public class Shield : Item <>

Теперь при передаче объекта типа Sword в метод DoSomeWork будет вызван метод InternalDoSomeWork(Sword item).

Выводы

Плюсы использования dynamic:

• Можно использовать для быстрого прототипирования: в большинстве случаев уменьшается количество бойлерплейт кода
• Как правило улучшает читаемость и эстетичность (за счет перехода от «магических строк» к нативному стилю языка) кода
• Несмотря на распространенное мнение, благодаря механизмам кэширования существенного оверхеда по производительности в общем случае не возникает

• Есть неочевидные нюансы, связанные с памятью и производительностью
• При поддержке и чтении таких динамических классов нужно хорошо понимать, что вообще происходит
• Программист лишается проверки типов и всех гарантий работоспособности, предоставляемых компилятором

Заключение

На мой взгляд, наибольший профит от использования dynamic разработчик получит в следующих ситуациях:

• При прототипировании
• В небольших/домашних проектах, где цена ошибки невысока
• В небольших по объему кода утилитах, не подразумевающих длительное время работы. Если ваша утилита исполняется в худшем случае несколько секунд, задумываться об утечках памяти и снижении производительности обычно нет нужды

Если вы работаете с COM-объектами или доменами в сервисах/продуктах, подразумевающих длительное непрерывное время работы — лучше dynamic не использовать, несмотря на то, что именно для таких случаев он и создавался. Даже если вы досконально знаете что и как делать и никогда не допускаете ошибок, рано или поздно может прийти новый разработчик, который этого не знает. Итогом, скорее всего, будет трудновычислимая утечка памяти.

Источник