PascalABC.NET (версия 3.8.2, сборка 3074 от 07.02.2022)
Не могу загрузить изображение с результатами. попробуйте в коде убирать аттрибут [Cache] то у одной, то у другой, а также у обоих сразу функций. результат вас удивит. возможно, я что-то делаю не так, но я склоняюсь к мысли, что скорее всего дело не в моей программе. аттрибут [Cache] используется аналогично примеру с функцией фибоначчи из описания изменений к версии 3.8.1. Самое удивительное, что пример с функцией фибоначчи призапуске, действительно демонстрирует эффективность работы аттрибута [Cache] . но если это работает только с факториалом, то ценность этого аттрибута становится близкой к нулю.
Далее - вы сейчас замеряете скорость вывода на экран, кроме собственно вызова функции.
Вывод результата должен быть вне замера времени, потому что он всегда тратит разный объём времени, зависимо от многих внешних факторов.
И вы замеряете с помощью часов системы, вместо напрямую аппаратно поддерживаемого Stopwatch.
##
[Cache]
function f0(a,q:integer):integer:= if q=0 then 1 else f0(a*2,q-1)+f0(a*2+1,q-1);
function f1(a,q:integer):integer:= if q=0 then 1 else f1(a*2,q-1)+f1(a*2+1,q-1);
var sw := Stopwatch.StartNew;
var res := f0(1,22);
Writeln(sw.Elapsed);
res.Println;
sw.Restart;
res := f1(1,22);
Writeln(sw.Elapsed);
res.Println;
Readln;
P.S. А ещё надо запускать программу в режиме Shift+F9, отключив генерацию отладочной информации, иначе вы тестируете скорость фич IDE, а не вашего кода.
Далее, надо разобраться как именно работает [Cache], а не попробовать его во всего 2 случаях и из этого судить.
А он создаёт словарь Dictionary<System.Tuple<параметры>, результат>.
Он позволяет проверять существование значения со сложностью O(1).
И добавление значения обычно имеет ту же сложность, но когда объёма выделенной памяти не хватает и её надо пересоздать - сложность стоновится O(Dictionary.Count).
В вашем случае вы не читаете данные из кеша. Вы только заполняете его не нужным вам мусором. При чём в огромном кол-ве, так что требуется O(q) перевыделений.
[Cache] делает так чтобы второй вызов той же функции с теми же параметрами вычислялся со сложностью O(1), не зависимо от алгоритма его вычисления. Когда вы не используете фичу по назначению - это называется стрелять себе в ногу.
спасибо за подсказку, но десяток миллисекунд… если Вы запускали код, то Вы должны были обратить внимание на то, что сравниваемые цифры порядка 0,1 сек и 4 сек различаются в 40 раз. и те несколько миллисекунд, которые лишним грузом попадают в замеры времени, не имеют решающего значения.
спасибо за разъяснение, но оно не решает проблемы. мы имеем рекурсивную функцию, в которой аттрибут [Cache] не работает. с точки зрения конечного результата и предполагаемого ожидаемого эффекта от использования аттрибута, Ваше объяснение никак не решило существа имеющейся проблемы. прошу не обижаться, я понимаю о чем пишете Вы, но полумиллиону школьников вообще наплевать на то, как работает кеш, они не хотят разбираться в тонкостях .Net - потому что они всего лишь ученики школы. большая часть из них смутно представляет, что такое классы методы объекты наследование и т.п. я думаю, что дальнейшее обучение в ВУЗе поможет им разобраться в этих вещах , но здесь и сейчас им нужно, чтобы на ЕГЭ их программа работала быстро, и используя механизм кеширования они будут уверены, что ускоряют работу своей рекурсивной функции. я надеюсь Вы смогли понять основную мысль, которую я хочу донести касательно аттрибута [Cache]
У программиста есть множество способов для оптимизации кода. Кеширование это только один из них - будь то в RAM как [Cache], на диске как в случае браузеров и т.п.
Магического способа, оптимизирующего любой код, как бы он не был написан - не существует и не может существовать. Поэтому проблема тут только в ожидаемом результате.
И позволять школьникам ленивую точку зрения, что можно сначала научиться заставлять код кое-как работать с костылями - а нормально научатся как то потом - это всё равно что на всём серьёзе давать метод научного тыка, а обучение научному методу откладывать на 10 лет.
На сколько бы плохой школьная программа не была - исправлять эту точку зрения это задача учителя.
Разумеется и научный метод нельзя сразу целиком давать, но надо начинать с базы, чтоб изначальное направление роста было правильным. В случае метода программиста надо объяснить что первый шаг это всегда разобраться, что происходит и зачем.
возможно, у вас сложилось впечатление, что я преподаватель. нет я отец одного из таких учеников. я точно могу сказать, что преподаватель скорее всего даже не знает некоторых вещей, о которых мы тут с Вами дискутируем. как инженер-программист окончивший ВУЗ с отличием и 25 лет занимающийся программированием, я считаю что сыну моему тоже ни к чему сейчас углубляться в те вещи, которые мы с Вами обсуждаем - у него и так в голове сейчас такое нагромождение информации, что я удивляюсь тому как он справляется с этим объемом. даже с базовыми знаниями ООП ему не сразу стала понятна разница использования функций с параметрами и использования методов с объектами класса. пару занятий он путался где нужно вызывать функцию с параметром, а где нужно взывать метод с объектом. лично меня этому учили в ВУЗЕ. и племянник мой сейчас обучается на программиста и предмет “объектно ориентированное программирование” у него стоит в учебном плане ВУЗовской программы. если школа будет давать такие знания, которые предлагаете Вы, то после окончания школы ученикам сдавшим егэ по информатике на отлично можно сразу выдавать диплом бакалавра.
теперь о проблеме, которая никак не решается посредством подобных дискуссий.
код уже оптимизирован донельзя. никаких костылей тут и в помине не видно. функция чуть ли не сама обычная и примитивная.право, я даже не понимаю о чем вы тут разглагольствуете. необходимая база знаний и умений у школьника идущего на ЕГЭ по информатике есть и она достаточна, а то о чем рассказываете Вы - это уже не база. изучение архитектуры и иерархии классов .Net и уж тем более тонкости работы каждого класса .Net с памятью это никак не вписывается в рамки школьной программы. дискуссия ради дискуссии начинает меня утомлять. если вас не затруднит не пишите ничего в ответ, очень не хочется полемизировать в пустую о вопросах обучения и воспитания - это не решит некорректной работы механизма кеширования результатов вызовов рекурсивной функции. Проблема не решена!
Пожалуйста, прислушайтесь к словам, что Вы некорректно используете атрибут Cache.
Этот атрибут эффективен тогда, когда в процессе рекурсивных вызовов есть много вызовов с одинаковыми параметрами. У вас в коде это не так. То есть большинство вызовов - с новыми параметрами. В этом случае происходит не ускорение, а замедление работы потому что кешируется большое количество вызовов.
Вот когда атрибут Cache работает:
##
[cache]
function f0(a,q:integer): integer:= if q=0 then 1 else f0(a*2,q-1)+f0(a*2+1,q-1);
[cache]
function f1(a,q:integer): integer:= if q=0 then 1 else f1(a*2,q-1)+f1(a*2+1,q-1);
writeln(f0(1,22));
Println(MillisecondsDelta/1000);
writeln(f1(1,22));
Println(MillisecondsDelta/1000);
writeln(f0(1,22));
Println(MillisecondsDelta/1000);
writeln(f1(1,22));
Println(MillisecondsDelta/1000);
Треттий и четвертый вызовы мгновенны именно за счет того, что прошлый раз всё закешировалось
ну я сразу и написал, что практическая ценность этого атрибута практически нулевая, потому что от него польза будет только при вычислении факториала, ряда фибоначчи и подобных функций. ну хотя… а разве кто-то утверждал что задумка была более серьезной? наверное Вы правы, скорее всего разработчики закладывали именно тот смысл, о котором говорите Вы, а я просто выдал желаемое за… желаемое… на ЕГЭ пользы от этого аттрибута ноль целых ноль десятых, даже наоборот как мы видим… главное чтобы остальные, так же как и я, не выдали желаемое за желаемое… дело в том что в описании изменений к релизу 3.8.1 в качестве примера была взята рекурсивная функция вычисления чисел фибоначчи. это неудачный пример, который создал иллюзию того, что кеширование можно использовать как минимум для 3 задач из ЕГЭ. я сейчас понимаю что разработчики и не планировали реализовывать ничего сложного. просто вызов функции. если утрировать то присвоив переменной однажды вычисленное значении функции можно с таким же успехом вместо вызова использовать многократно значение переменной. я уверен вы поняли в чем сарказм. моя ошибка в том, что я предполагал, что разработчики хотели сделать нечто большее, и поэтому был уверен, что такое поведение кеша связано с неправильной реализацией задумки. но теперь все стало на свои места. Aequat causa effectum
Практическая ценность этого атрибута высокая для решения определённого набора задач.
Мы делали этот атрибут не для ЕГЭ как вы понимаете. PascalABC.NET - язык общего назначения, и использование кеширования весьма широко распространно в программировании. Так например, получение кода удалённой HTML-страницы первый раз делается десяток секунд, потом практически мгновенно.
Кеширование не работает когда результаты вызова функций с одинаковыми параметрами разные или когда в задаче нет одинаковых параметров.
Вы неправильно использовали данное средство, применив его к конкретной задаче.
Совершенно очевидно, что нет волшебного средства, облегчающего решение всех задач ЕГЭ. Преподаватель, который рискует учить школьников использованию Cache, должен аккуратно спроектировать объяснение - когда можно, когда нельзя. А использовать везде столь нетривиальное средство в надежде что оно всё ускорит, без понимания механизма его работы - точно большая ошибка. И в этом случае нужно точно проигнорировать его для задач ЕГЭ.
я имел в виду, что в отдельных случаях механизм использования кеша может вырождаться до эквивалента запоминания результата функции в отдельно созданном под этот результата объекте, с дальнейшим многократным использованием этого объекта вместо вызова функции. тут же можно начать копать в направлении того какой объем данных кешируем и каков размер кеша. и в широком смысле мы можем получить ситуацию когда объем кешируемых данных меньше размера кеша. ну… это уже тема для другой дискуссии.
В вашем случае это не поможет.
В вашей программе посчитаем количество вызовов с разными параметрами:
var s := new List<(integer,integer)>;
[cache]
function f0(a,q:integer): integer;
begin
s += (a,q);
if q=0 then
Result := 1
else
begin
var x := f0(a*2,q-1);
var y := f0(a*2+1,q-1);
Result := x + y;
end;
end;
begin
writeln(f0(1,22));
Println(MillisecondsDelta/1000);
Println(s.Count,s.Distinct.Count);
end.
Это значит, что ВСЕ вызовы - с разными параметрами. В этом случае кешировать любым - каким угодно - способом - не полезно, а вредно.
В ЕГЭ специально составляют мудрёные задания, которые нельзя как правило решить с использованием штатных возможностей. Этим они якобы борются с незаконным с их точки зрения использованием штатных возможностей. А на самом деле в любом промышленном проекте рекурсия, которую вы тут привели, очень маловероятна.
Это надо иметь в виду при подготовке школьников. Общая рекомендация - если не хотите рисковать, - не используйте эти возможности.
Есть однако ряд других задач ЕГЭ - мы про них рассказывали на конференции - где кеширование всё сильно упрощает. И это не числа Фибоначчи - это весьма сложные переборные задачи, связанные с деревом решений. Для них использование ручного решения без программирования лишь немного проще составления программы с Cache
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021