Динамическое программирование на 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 (i){ case a[0]: case a[1]: … case a[b.Length - 1]: return true;}return false;

Разработчики компиляторов достигли больших успехов в оптимизации оператора 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 = {0}, Elapsed msec= {1}", 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 = {0}, Elapsed msec= {1}", count2, span2.TotalMilliseconds); Console.ReadLine(); } }}

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

Search with looping. Count = 84, Elapsed msec= 22482,328Search with switch. Count = 84, Elapsed msec= 5487,8912
СОВЕТ Пытливый читатель конечно заметит, что динамически созданный код соревновался с не совсем оптимально написанным поиском по массиву. Было бы гораздо оптимальнее предварительно отсортировать массив, с тем чтобы потом применить двоичный поиск. А вот в этом соревновании вряд ли будет выявлен явный лидер, т.к. сам реализация switch’а сама использует двоичный поиск. Ну что ж. Тогда можно считать, что предложенный способ это всего лишь автоматизация сортировки и двоичного поиска, переложенная на плечи компилятора. 8-)

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

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

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

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

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

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

Заключение

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