在本文中,您将学习如何使用回归式编程,它是什么,以及如何优化用于算法中的使用. 我们将使用JavaScript作为我们所选择的编程语言来理解回归的概念。
前提条件
我将使用Big O Notation来比较优化策略,您可以 在这里刷新。
什么是回归?
如果你曾经使用过 canvas 动画,那么你已经使用了回归,因为我们使用了一个动画函数,在重新启动之前更新我们的动画。
在下面的示例中,我们通过一个数字,将其翻倍,然后将该值再次传递给自己。理论上,这将持续永久,但由于计算机是有限的,我们通常不能有无限回归。
1const double = num => {
2 num = num + num;
3 console.log(num);
4
5 if (num > 100) return 'Exit'; // Try removing this
6 return double(num);
7};
8
9console.log(double(4));
你可能想,这很酷,但我不能只使用循环做任何回归可以做的事?好吧,但实际上不是。回归在处理各种搜索和排序算法或穿过比简单列表更复杂的数据结构时很有用。
记忆化
你不必玩回归很长时间才能意识到它很容易压倒你的计算机. 这是因为大多数回归函数都是O(n^2)或甚至是O(n!)! 由于JavaScript每次添加一个新的回归层时都会在调用堆栈上运行,所以必须使用大量的内存和处理能力来管理所有这些功能,尽管大多数都是多余的。
让我们尝试一些简单的东西,如生成一个菲波纳奇序列。一个菲波纳奇序列是每一个数字是前面的两个项目的总和,0、1、2、3、5、8、12...
1const fibonacci = num => {
2 if (num < 2) return num;
3
4 return fibonacci(num - 1) + fibonacci(num - 2);
5};
6
7for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 3 minutes before page crashed...
使用1000层相同信息的资源,即使对我的相对体面计算机来说也太多了。
相反,我们可以通过添加一个存储变量,或一个备忘录,这将包含我们的值,随着堆栈的进展. 每次我们的函数运行,它的值将被添加到相应的索引在备忘录中,下一层将参考它来计算我们的结果。
1const fibonacci = (num, memo) => {
2 memo = memo || {};
3
4 if (memo[num]) return memo[num];
5 if (num < 2) return num;
6
7 return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
8};
9
10for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 143 Milliseconds
问题
让我们尝试将此应用于另一个回归函数. 这需要一个数字并输出它的因子,所以3!应该返回6因为3x2x1=6。
1const factorial = n => {
2 let num = n;
3
4 if (n === 0) return 1;
5 for (let i = 0; i < n; i++) {
6 num = n * factorial(n - 1);
7 };
8
9 return num;
10};
11
12console.log(factorial(3)); // 7 Milliseconds
13console.log(factorial(6)); // 8 Milliseconds
14console.log(factorial(9)); // 15 Milliseconds
15console.log(factorial(12)); // 11,588 Milliseconds
对我来说,超过12的任何东西都会崩溃,因为这个函数具有O(n!)的复杂性,因为堆栈中的每个层都必须处理前面的复杂性。
相反,让我们试着记住它,看看差异。
1const factorial = (n, memo) => {
2 memo = memo || {};
3
4 if (memo[n]) return memo[n];
5 if (n === 0) return 1;
6 for (let i = 0; i < n; i++) {
7 memo[n] = n * factorial(n - 1, memo);
8 };
9
10 return memo[n];
11};
12
13console.log(factorial(12)); // 4 milliseconds
14console.log(factorial(120)); // 12 milliseconds
15console.log(factorial(1200)); // 24 milliseconds
16console.log(factorial(12000)); // 1408 milliseconds
我不知道你,但我认为这是一个令人难以置信的改进,它现在可以处理10万倍的计算在第八次。
关闭思想
回归是你需要非常舒适的事情之一,因为它将在你的编程生涯中反复返回,或困扰你,这将是学习穿越树木和列表并在未来分类各种数据集的必不可少的。