动态规划之使用备忘录来改进Javascript函数

目录
  • 什么是备忘录?
  • 备忘录的概念
    • 1.引用透明
    • 2.查找表
  • 比较函数使用备忘录和不用备忘录
  • 解决方法是记录调用函数的返回结果
  • 备忘录的意义
  • 结论:什么是备忘录?

前言;

动态规划已出现了十多年。根据维基百科,它既是一种数学优化方法,也是一种计算机编程方法。一个问题要真正应用动态规划,必须具有两个关键属性:最优结构和重叠子结构。本文不会细讲动态规划,而是将关注重叠子结构如何成为动态规划的关键属性之一。由于这关系到接下来的存储解决方案问题,所以对它的讨论非常重要。

本文将介绍什么是备忘录,备忘录对Javascript开发人员来说具有哪些价值,以及如何使用它来改进Javascript函数,从而对备忘录本身以及备忘录对优化应用程序的意义有一个深入了解。

在本文中,我们将讨论以下几个主题:

  • 什么是备忘录
  • 备忘录的主要概念
  • 函数使用备忘录和不用备忘录的比较
  • 备忘录的意义

什么是备忘录?

备忘录是缓存的一种形式,是一种方便进入和后续使用的值存储方法。备忘录是将已解决问题的结果记录下来,这样下次需要再次执行相同操作时,就不必重新计算了。不过,一个函数要使用备忘录,需要满足一定条件:它必须是引用透明的,即只有在调用函数的效果与用函数的返回值替换函数调用的效果完全相同的情况下才可以使用。

在Ruby、C++、Python等大多数编程语言中都有备忘录,这些语言中甚至有很多库可以简化。在本文中,我们将重点关注Javascript。编程语言或许不同,但其中的概念和思想是一致的。

备忘录的概念

备忘录需要理解以下两个概念:

1.引用透明

如果一个表达式可以在不改变程序行为的情况下被其对应的值替换(反之亦然),那么它就被称为引用透明。这要求表达式必须是纯的,即对于相同的输入,表达式的值必须相同,并且它的求值必须没有副作用。非引用透明的表达式称为引用不透明。

有了上面的解释,我们可以很快地把它和备忘录的行为联系起来,这个概念让我们可以写出一个带备忘录的函数。

2.查找表

查找表(LUT)是一个数组,它用更为简单的数组索引操作取代运行时计算。该过程被称为“直接寻址”,LUT与哈希表的不同之处在于它检索的是一个值。

比较函数使用备忘录和不用备忘录

以经典的斐波那契数列定义为例:

function Fibo(n) {  
   if (n < 2) {  
       return n;  
   }  
   return Fibo(n - 1) + Fibo(n - 2);  
} 

你可能预料到了,一旦开始使用大于20的数字,这个过程就会变得非常缓慢。而当你处理35左右的数字时,计算机估计也撑不住了。

解决方法是记录调用函数的返回结果

var IterMemoFib = function() {  
    var cache = [1, 1];  
    var fib = function(n) {  
        if (n >= cache.length) {  
            for (var i = cache.length; i <= n; i++) {  
               cache[i] = cache[i - 2] + cache[i - 1];  
           }  
       }  
       return cache[n];  
   }  

  return fib;  
}(); 

这部分有点麻烦,也不完全可读,或者你也可以让计算机来协助完成:

Fib = Fib.memoize();  

由于技术(浏览器安全策略)限制,备忘录函数的参数只能是数组或标量值,不能是对象。

下面的代码扩展了Function对象以添加备忘录功能。如果函数是一个方法,则可以将对象传递给memoize()。

Function.prototype.memoize = function () {  
var pad = {};  
var self = this;  
 var obj = arguments.length > 0 ? arguments[i] : null;  
  
 var memoizedFn = function () {  
 // Copy the arguments object into an array: allows it to be used as  
   // a cache key.  
   var args = [];  
   for (var i = 0; i < arguments.length; i++) {  
     args[i] = arguments[i];  
  }  
  
   // Evaluate the memoized function if it hasn't been evaluated with  
   // these arguments before.  
   if (!(args in pad)) {  
     pad[args] = self.apply(obj, arguments);  
  }  
  
   return pad[args];  
};  
   
 memoizedFn.unmemoize = function () {  
   return self;  
 };  
  
 return memoizedFn;  
};  
   
Function.prototype.unmemoize = function () {  
 alert("Attempt to unmemoize an unmemoized function.");  
 return null;  
};  

备忘录的意义

  • “记住”与某组特定输入相对应的结果
  • 备忘录降低了函数的时间成本以换取空间成本
  • 备忘录更不依赖机器

结论:什么是备忘录?

在本文中,我们讨论了备忘录以及它的两个主要概念:引用透明和查找表。此外,我们还探讨了它对Javascript代码的重要性,同时比较了未使用备忘录的代码和使用备忘录的代码之间的区别,并对缓存值所用的技术进行了一定了解。

到此这篇关于动态规划之使用备忘录来改进Javascript函数的文章就介绍到这了,更多相关备忘录改进Javascript函数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • vue.js实现备忘录demo

    本文实例为大家分享了vue.js实现备忘录demo的具体代码,供大家参考,具体内容如下 代码: <!doctype html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale

  • vue.js实现备忘录功能的方法

    这个vue实现备忘录的功能demo是K在github上找到的,K觉得这是一个用来对vue.js入门的一个非常简单的demo,所以拿在这里共享一下. (尊重他人劳动成果,从小事做起~  demo原github地址:https://github.com/vuejs/vue) 一.实现效果 二.代码展示 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>备忘录&l

  • Vue.js实现备忘录功能

    本文实例为大家分享了Vue.js实现备忘录的具体代码,供大家参考,具体内容如下 效果展示: html代码: <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <!-- 移动设备设置 --> <meta name="viewport" content="width=device-width,initial-scale=1,minimum-

  • angularjs表格ng-table使用备忘录

    项目中用到angularjs的表格ng-table,功能相当强大,像搜索.排序.checkbox.分页.每页表格显示数目等都有.API,demo什么的也只能参考官网了.这里做个备忘,哪天肯定还会用到. HTML: <!DOCTYPE html> <html> <meta charset="utf-8"/> <head> <script data-require="angular.js@*" data-semver

  • javascript设计模式 – 备忘录模式原理与用法实例分析

    本文实例讲述了javascript设计模式 – 备忘录模式原理与用法.分享给大家供大家参考,具体如下: 介绍:在我们的开发中偶尔会遇到这样一种情况,需要对用户的行为进行撤销.要想实现撤销,首先需要保存软件系统的历史状态,当用户执行撤销时用之前的状态覆盖当前状态.本节介绍的备忘录模式提供了一种状态恢复的实现机制,使得用户可以方便的回到一个特定的历史步骤. 定义:在不破坏封装的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态,这样可以在以后将对象恢复到原先保存的状态,它是一种对象行为模式,

  • 动态规划之使用备忘录来改进Javascript函数

    目录 什么是备忘录? 备忘录的概念 1.引用透明 2.查找表 比较函数使用备忘录和不用备忘录 解决方法是记录调用函数的返回结果 备忘录的意义 结论:什么是备忘录? 前言; 动态规划已出现了十多年.根据维基百科,它既是一种数学优化方法,也是一种计算机编程方法.一个问题要真正应用动态规划,必须具有两个关键属性:最优结构和重叠子结构.本文不会细讲动态规划,而是将关注重叠子结构如何成为动态规划的关键属性之一.由于这关系到接下来的存储解决方案问题,所以对它的讨论非常重要. 本文将介绍什么是备忘录,备忘录对

  • 详解Javascript函数声明与递归调用

    Javascript的函数的声明方式和调用方式已经是令人厌倦的老生常谈了,但有些东西就是这样的,你来说一遍然后我再说一遍.每次看到书上或博客里写的Javascript函数有四种调用方式,我就会想起孔乙己:茴字有四种写法,你造吗? 尽管缺陷有一堆,但Javascript还是令人着迷的.Javascript众多优美的特性的核心,是作为顶级对象(first-class objects)的函数.函数就像其他普通对象一样被创建.被分配给变量.作为参数被传递.作为返回值以及持有属性和方法.函数作为顶级对象,

  • 轻松学习JavaScript函数中的 Rest 参数

    JavaScript函数可以使用任意数量的参数.与其他语言(如C#和Java)不同,你可以在调用JavaScript函数时传递任意数量的参数.JavaScript函数允许未知数量的函数参数.在ECMAScript 6之前,JavaScript有一个变量来访问这些未知或可变数目的参数,这是一个类似数组的对象,并非一个数组.细想以下代码来理解arguments变量: function add(){ var result = 0; for(let i=0;i<arguments.length;i++)

  • 改进 JavaScript 和 Rust 的互操作性并深入认识 wasm-bindgen 组件

    前言 最近我们已经见识了WebAssembly如何快速编译.加速JS库以及生成更小的二进制格式.我们甚至为Rust和JavaScript社区以及其他Web编程语言之间的更好的互操作性制定了高级规划.正如前面一篇文章中提到的,我想深入了解一个特定组件的细节,wasm-bindgen. 今天WebAssembly标准只定义了四种类型:两种整数类型和两种浮点类型.然而,大多数情况下,JS和Rust开发人员正在使用更丰富的类型! 例如,JS开发人员经常与互以添加或修改HTML节点相关的文档交互,而Rus

  • 测量JavaScript函数的性能各种方式对比

    概述 测量执行一个函数所需的时间总是一个很好的办法,证明某些实现比另一个实现的性能更好.这也是一个很好的方法,可以确保性能没有在某些改变后受到影响,也可以追踪瓶颈. 良好的性能有助于获得良好的用户体验,良好的用户体验会让用户回头客.一项研究显示,88%的在线消费者因为性能问题,在用户体验不佳后用户回来的可能性较小. 这就是为什么能够识别代码中的瓶颈并测量改进的原因.尤其是在为浏览器开发JavaScript时,要注意到你写的每一行JavaScript都有可能阻塞DOM,因为它是一种单线程语言. 在

  • JavaScript函数柯里化

    目录 1 什么是函数柯里化 2 柯里化的作用和特点 2.1 参数复用 2.2 提前返回 2.3 延迟执行 3 封装通用柯里化工具函数# 4 总结和补充 1 什么是函数柯里化 在计算机科学中,柯里化(Currying)是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数且返回结果的新函数的技术.这个技术以逻辑学家 Haskell Curry 命名的. 什么意思?简单来说,柯里化是一项技术,它用来改造多参数的函数. 比如: // 这是一个接受3个参数的函

  • 超链接怎么正确调用javascript函数

    点击超链接调用 JavaScript 函数,一般人都用: 复制代码 代码如下: <a href="javascript:function();"> 但这有个缺点,就是点击链接后,页面上的GIF动画将静止. 试看如下代码: 复制代码 代码如下: <script type="text/javascript"> <!-- function Foo() {     //do something } //--> </script>

  • 浅谈JavaScript函数节流

    浏览器中某些计算和处理要比其他的昂贵的多.例如,DOM操作比起非DOM交互需要更多的内存和CPU时间.连续尝试进行过多的DOM相关操作可能会导致 浏览器挂起,有时候甚至会崩溃.尤其在IE中使用onresize事件处理程序的时候容易发生,当调整浏览器大小的时候,该事件连续触发.在 onresize事件处理程序内部如果尝试进行DOM操作,其高频率的更改可能会让浏览器崩溃. 函数节流背后的基本思想是,某些代码不可以在没有间断的情况连续重复执行.第一次调用函数,创建一个定时器,在指定的时间间隔之后运行代

  • javascript函数命名的三种方式及区别介绍

    javascript函数命名的三种方式及区别介绍 第一 复制代码 代码如下: function fn(val1,val2) { alert(val1+val2); } fn(1,2); 第二 复制代码 代码如下: var fn=function() { alert(val1+val2); } fn(1,2); 第三 复制代码 代码如下: var fn=new Function("alert(val1+val2)"); fn(1,2); 上面三种方式逻辑上是等价的,但是还是有点小区别:区

  • JavaScript函数表达式详解及实例

    JavaScript函数表达式 一.序 定义函数的方式有两种:一种是函数声明,另一种就是函数表达式: 1.1 函数声明 function functionName(arg){ //函数体 } 关于函数声明,它有一个重要特征就是函数声明提升,意思就是在执行代码之前会先读取函数声明.这就意味着可以把函数放在调用它的语句后面.如下所示: helloworld(); //在代码执行之前会先读取函数声明 function helloworld(){ console.log("hello world&quo

随机推荐