Нэш Трей - C# 2010. Ускоренный курс для профессионалов (2010) (1160865), страница 139
Текст из файла (страница 139)
В методе Ма1п он используется для производства составного выражения. Делегат, который получается после вызова Спагп<>, эквивалентен делегату, который получается при преобразовании следующего лямбда-выражения в делегат: х .=> (х * 3) з 3.1415 Метод вроде этого, который способен связывать в цепочки произвольные выражения, действительно полезен, но давайте рассмотрим другие способы создания производных функций, Представим операцию, которая требует действительно длительного времени на вычисление.
Примерами могут служить операции вычисления факториала или операции вычисления и-го числа Фибоначчи. Рассмотрим пример вычисления обратной константы Фибоначчи согласно формуле: — = 3.35988566... Здесь й' — число Фибоначчи'. Для вычисления этой константы сначала понадобится написать операцию вычисления п-го числа Фибоначчи: ия1пс Яуясев! ия1пс) Яуясев.а1пЧ! риЬ11с с1эзз Ргоог ( ясас1с зогб Мвгп() ( типс<1пе, гпе> Т1Ь = пи111 Тгв (х) > х > 1 2 ТТЬ(х-1) + Т1Ь(х-2) с х; Гог( 1пг 1 = 30! г < 40! +41 ) ( Сопяо1е.нг1пе11пе( 11Ь(г) ); см, статью эрика Ввйсштейна ((()е!яя1е1п, епс цс) "Вес1ргоса) Р!ьопасс( сопя(зп1" на сайте Ма(ЬУ(сог1с)по адресу ьггрсс'с'вясьзаг1е.яо11гяв.совсаесгргоаа1ГТЬопассгСопясзпс.псв1.
Лякбда-аыражения 519 Первое, что бросается в глаза при взгляде на этот код — формирование процедуры Фибоначчи, т.е, делегата 11Ь. Он формирует замыкание на самом себе! Это определенно форма рекурсии с необходимым поведением. Запустив этот пример, вы заметите, насколько медленно он работает, всего лишь вычисляя числа Фибоначчи с 30-го по 39-е. В таком случае даже не стоит надеяться продемонстрировать вычисление обратной константы Фибоначчи. Медлительность кода обусловлена тем, что каждое вычисляемое число Фибоначчи требует чуть больше работы. чем вычисление двух предыдущих, и в результате затрачиваемое время растет лавинообразно.
Проблему можно решить, пожертвовав пространством в пользу времени — за счет кэширования чисел Фибоначчи в памяти. Но вместо модификации исходного выражения давайте посмотрим, как создать метод, принимающий первоначальный делегат в качестве параметра и возвращающий новый делегат, который заменяет оригинал. Конечная цель — получить возможность заменять первый делегат производным делегатом, не затрагивая код, который его использует. Один из таких приемов называется мемоизацией (п1епю)за(1оп; также называемая "запоминанием")'.
В соответствие с этим приемом, функция кэширования возвращает значения, и каждое возвращенное значение ассоциируется с входными параметрами. Прием работает только в случае, если функция не обладает энтропией — в том смысле, что для одних и тех же входных параметров она всегда возвращает один и тот же результат. Тогда перед вызовом действительной функции сначала проводится проверка, не был ли вычислен результат для данного параметра ранее, и если да, то он возвращается вместо вызова функции. Для очень сложных функций такая техника требует немного больше пространства памяти, но дает существенный выигрыш в скорости.
Рассмотрим пример. ияасч эуягеп; оягсд Яуягеп.щсс; сяасз Буясеп.Со11есь]оья.песет]с; риЬ1(с ясяшс с1аяя Мепогяегя ! риь11с ясасас Випс<т,в> маповзе<т,В>( еьзя аипс<т,в> тиас ) ( изс сасье = иеи пасевоиаху<т,к>(); хесиси (х] => ( В хези1С йееаи1С(В] 1 ТЕ( сасье.Тзуцееуа1ии(к, оие хеяи1С) ) ( сеьихи хаэи1С; ) сияи1С = Тиас (х): сасье [х] хеяи1С1 хееиги хеяи1С; )1 ) ! РиЫТс с1аяя Ггоо( зсяьгс ясгб Мазо() ! Еисс<гсг, Тсг> ГТЬ = пи11; Г Ь = (х] => х > 1 2 Г Ь( -1] + Г!Ь( -г): х; ТТЬ = Т'Ь.Маковки(); Гог( Тсс 1 = 301 1 < 40; яеа ) Сосяс1е.нгзье11се ( 11Ь (1) ) 1 ) мемоизация хорошо описана з блоге Веса Дайера (%(!ея ]]уег) по адресу ьььр: Оысо я . пяпа.
соп!неяйуег/агсщяе/2007/01/20/(иссь1ос-пепе(яаь1оп.аярх. 520 Глава (5 Прежде всего, обратите внимание, что в Мабп добавился только один дополнительный оператор, в котором к делегату применяется метод Мепо1хе<>, чтобы произвести новый делегат. Все прочее осталось без изменений, так что прозрачная взаимозаменяемость обеспечена. Метод Метобхе<> помещает исходный делегат, который передан в аргументе Еппс.
в оболочку другого замыкания, включающего экземпляр Оесс1опагу<> для хранения кэшированных значений данного делегата Ештс. В процессе Мепобхе<> взятие одного делегата и возврат другого реализует кэш, который значительно повышает эффективность. Всякий раз, когда вызывается делегат, он сначала проверяет, нет ли в каше ранее вычисленного значения. Внимание! Естественно, мемоизация работает только с функциями, которые детерминировано повторяемы — в том смысле, что для одних и тех же параметров гарантируется получение одного и того же результата. Например, истинный генератор случайных чисел подвергнуть мемоизации невозможно. Запустите предыдущий пример и увидите поразительную разницу в скорости выполнения. Теперь вполне можно приступить к вычислению обратной константы Фибоначчи, модифицирован метод ма).п следующим образом: ятая1с чобб Ма1п() ( Гппс<п1опд, п1опс> Е1Ь = пп11; ЕРЬ = (х) => х > 1 2 ЕРЬ(х-1) + ЕЕЪ (х-2) : х; Е1Ь = 11Ь.Мепо1хе(); Гппо<п1опд, бесмва1> е1ьсопвеапс пп11 г ЕЕЬСопввапс = (х) => ( 1Е(х=-1) ( кеепкп 1 / ( (беозиа1) ЕЕЬ(х) ) г ) е1ае ( кеешп 1 / ((бесзиа1) ЕхЬ(х) ) + Е1ЬСопэсапв(х-Ц ) )г ЕЕЬСОПВСаве в Е1ЬСОПаеаПС.МЕИОЕВЕ() ) Сопяо1е.нг1теьзпе( "тп(0)тг(1)11(2)тс(З)тп", "Номер", "Фибоначчи".Раба19ЬС(24), "1/Фибоначчи ".Рзбятспг(24), "Константа Фибаначчн".Рабябспя(24) Рог( п1опч 1 = 1; 1 <= 93г ++1 ) ( Сопяо1е.нт1теь1пе( "(О:05)тс(1:024)1с(2:Г24)11(з:Г24)", 1, ЕЕЬ (1), (1/ ( бес1па1) Е>Ь (1) ), ЕРЬСопягапт(1) Вьщеленный полужирным код соответствует делегату, созданному для вычисления и-й обратной константы Фибоначчи.
Вызывая этот делегат с все большим и большим значением х, несложно заметить, что результат становится все ближе и ближе к обратной константе Фибоначчи. Обратите внимание на внедрение мемоизации в делегат Ебьсопясапс. Если этого не сделать, то по мере вызова ЕЕЬСопябапя с все большими и большими значениями х может возникнуть переполнение стека из-за рекурсии.
Легко убедиться, что мемоизация также экономит пространство стека за счет пространства кучи. В каждой строке вывода для информации выдается промежуточное значение, но самое интересное Лямбдв.выражения 521 значение находится в крайней правой колонне. Обратите внимание, что вычисление прекращается на итерации номер 93. Причина в том, что и1опд на 94-м числе Фибоначчи переполнится. Проблему можно решить, воспользовавшись типом В191пгедег из пространства имен Яувсегв.))ипсег1с. Однако это не обязательно, поскольку 93-я итерация уже дает достаточно близкое значение обратной константы Фибоначчи. 3.359885ббб243177553039387 Значимые разряды выделены полужирными. Как видите, прием мемоизации чрезвычайно полезен.
В отношении методов, принимающих функции и производящих другие функции, можно предпринять много других полезных вещей, что будет продемонстрировано в следующем разделе. Каррироаание В предыдущем разделе, посвященном замыканиям, было показано, как создать метод, который принимает функцию, переданную в виде делегата, и производит новую функцию. Это очень мощная концепция. и мемоизация, продемонстрированная в предыдутцем разделе, является примером удачного ее применения. В этом разделе рассматривается техника, называемая каррироеанием [сшту(пй)'~. По сути, под каррированием понимается создание операции (обычно — метода), которая принимает функцию с несколькими параметрами (обычно — делегат) и производит функцию с только одним параметром.
На заметку! Программисты на С++, знакомые с библиотекой ВТЬ, несомненно, применяли операцию каррирования, когда имели дело с любой из привязок параметров, таких квк Взпс1вс и В1пс)2пс). Пусть имеется лямбда-выражение, которое выглядит следующим образом: (х, у) => х + у Предположим. что есть список вещественных чисел двойной точности. и требуется применить это лямбда-выражение для добавления константного значения к каждому элементу списка, в результате чего получается новый список.
Было бы здорово создать новый делегат на базе исходного лямбда-выражения. в котором одна из переменных стала бы статическим значением. Это понятие называется привязкой парамептров, и те, кто использовал БТ). в С++, наверняка хорошо знакомы с ним. Ниже показан пример демонстрации привязки параметров, в котором к элементам в экземпляре 11вг<с)оиЬ1е> добавляется константа 3. 2: ивгпз Бувгепн ивгпд Бувгеи.11пс)г ивгпд Бувсеи.Со11есг1опв.оепег1с) риЫ1с зсвсгс с1ввв СиггуЕхсепв(опв ( риь1хс веаз1с Рипс<тАгд1, ткеви1е> Взж)2пб<тдхд1, тдгд2, ткеви1е>( ЕЬ1з 3'ипс<ТАгд1, Тдгд2, Ткеви1Е> Еипс, ТАгд2 сспвсэпс ) ( хекихп (к) => Еипс( к, сопэсапс ) г Дополнительные разряды обратной константы Фибоначчи можно посмотреть по адресу Ьсср://ннн.гевеэгсь.всс.сои/-п)ав/вес)иепсев/А079586.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
