Wolfram-Cloud/Mathematica, эффективная работа с рекурсивными функциями

В данный момент я работаю с полиномами Чебышёва, рекурсивно определенными полиномами. Для очень вероятного случая, когда вы никогда не видели их раньше:

f[0,x_]  := 1;
f[1,x_]  := x;
f[n_,x_] := 2 * x * f[n-1, x] - f[n-2, x];
Plot[{f[9, x],f[3, x]},{x, -1, 1}]

И я поймал себя на вопросе, так как я обычно работаю с python, есть ли способ построить массив функций в wolfram-cloud, чтобы упростить процесс.

Таким образом, я должен вычислять каждое f[n] только один раз, что позволяет мне немного улучшить время выполнения, а также позволяет мне расширить диапазон n.


recursion wolfram-mathematica wolfram-language
person Patrick Abraham    schedule 22.01.2017    source источник
comment
Типичным способом решения этой задачи в системе Mathematica является запоминание. reference.wolfram.com/language/tutorial/   -  person Szabolcs    schedule 22.01.2017
comment
Есть ли какая-то причина, по которой вы не используете встроенную функцию ChebyshevT? Мое наивное ожидание состоит в том, что использование этого немного улучшит время выполнения с очень небольшими усилиями с вашей стороны.   -  person High Performance Mark    schedule 22.01.2017
comment
@HighPerformanceMark Справедливо спросить, поэтому я хотел а) узнать кое-что о синтаксисе и б) на самом деле хотел сам поиграть с полиномом, чтобы лучше понять его.   -  person Patrick Abraham    schedule 22.01.2017
comment
@Szabolcs Это также справедливо для функций или это справедливо только для определенных значений. Также есть способ предварительно запустить какую-то его часть, чтобы он не истек. Итак, могу ли я разбить его на несколько вычислений?   -  person Patrick Abraham    schedule 22.01.2017
comment
@Szabolcs Я должен фальсифицировать себя. На самом деле это не так. Я попытался сделать рабочий образец и попытался рассчитать время выполнения без какого-либо вывода или упрощения полинома. Поэтому я подавил вывод полинома f[27,x] и попытался вычислить его один раз, а затем получить к нему доступ, не выводя его. Оба раза я проверял время до минус время после расчета. И каждый раз это занимало 3,1 секунды. Либо подразумевается, что поиск его занимает целую вечность и что он был предварительно рассчитан (в новой книге), либо что он фактически вычислил его оба раза.   -  person Patrick Abraham    schedule 22.01.2017
comment
Мемоизация сложнее, потому что мы не хотим запоминать здесь x, а только форму полинома. Я написал ответ.   -  person Szabolcs    schedule 22.01.2017
comment
Еще кое-что, что вы можете узнать о Mathematica и рекурсивных функциях: RSolve[{f[0,x]==1, f[1,x]==x, f[n,x]==2 xf[n-1,x ]-f[n-2,x]}, f[n,x], {n,x}] мгновенно обнаруживает, что f[n, x] == ((x-Sqrt[-1+x^2]) ^n+(x+Sqrt[-1+x^2])^n)/2. Это не всегда будет работать, но иногда это полезно.   -  person Bill    schedule 22.01.2017
comment
@Bill Думаю, это неплохо, но меня не интересовало ни решение, ни упрощение рекурсии. И Mathematica также должна уметь идентифицировать свою уже встроенную функцию ChebyshevT[n,x].   -  person Patrick Abraham    schedule 24.01.2017

Ответы (1)


arrow_upward
2
arrow_downward

Используйте запоминание.

В этом случае мемоизация сложнее, чем обычно, потому что мы работаем с функциями, а не со значениями функций.

Clear[cheb]
cheb[0] = 1 &;
cheb[1] = # &;
cheb[n_] := cheb[n] = Evaluate@Expand[2 # cheb[n - 1][#] - cheb[n - 2][#]] &

Evaluate гарантирует, что внутренности Function будут оценены еще до предоставления и аргумента.

person Szabolcs    schedule 22.01.2017
comment
Могу я спросить, почему вы используете &; вместо ;? - person Patrick Abraham; 24.01.2017
comment
И где на самом деле определяется #. Только что попробовал, и он выдал какую-то формулу # в качестве вывода. - person Patrick Abraham; 24.01.2017
comment
@PatrickAbraham Найдите Function и посмотрите reference.wolfram.com/language/tutorial/PureFunctions.html Вы можете ввести # или & в поле поиска документации, и вы попадете на соответствующую страницу. Изучая Mathematica, всегда сначала проверяйте документацию (перед гуглением и т. д.). Это лучше, чем у большинства других систем. - person Szabolcs; 24.01.2017
comment
Тем не менее код, который вы написали, не работает, по крайней мере, в облачной версии. И мне довольно трудно понять, как я могу заставить его работать. - person Patrick Abraham; 25.01.2017
comment
@PatrickAbraham Работает отлично. Если у вас с этим проблемы, покажите, что вы сделали, что получили в результате и чего ожидали. Помните, что cheb[10] — это функция, а не число. - person Szabolcs; 25.01.2017
comment
Я повторил то же самое, что и раньше, и это сработало. Может быть, мне просто нужно немного поспать ;) Спасибо, что нашли время и хорошего вечера - person Patrick Abraham; 25.01.2017
comment
PS: время обработки составляет несколько мс. 40+ не проблема, как было раньше. - person Patrick Abraham; 25.01.2017
comment
@PatrickAbraham Остерегайтесь кэширования слишком большого количества результатов. В этом случае это не будет проблемой, поскольку cheb[10000] вам, скорее всего, не понадобится. Но если имеется более одного аргумента, мемоизация усложняется и может пойти не так. Вы можете использовать ?cheb, чтобы проверить, что кешируется, и Clear[cheb], чтобы очистить все определения. Еще кое-что: рассмотрите вопрос на mathematica.stackexchange.com в следующий раз. - person Szabolcs; 25.01.2017