以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 软件工程论坛 』 (http://bbs.xml.org.cn/list.asp?boardid=48) ---- 空间换时间,Memoization,单件模式,备忘录模式,之间的关系。[原创] (http://bbs.xml.org.cn/dispbbs.asp?boardid=48&rootid=&id=42017) |
-- 作者:pennyliang -- 发布时间:1/6/2007 5:07:00 PM -- 空间换时间,Memoization,单件模式,备忘录模式,之间的关系。[原创] 在设计模式中,名字的命名一般都和具体应用有关,这里我们从单件模式,和备忘录模式挖掘一些深层次的东西。 首先来看单件模式,本质上,它是构造一次,每次要用到的时候不需要重复构造,直接取出即可,我们不妨把构造变成计算,那么就是,计算一次,然后存储,不在重复计算。 在看备忘录模式,每个对象都含有内部状态,但是对象的状态都在不断变化,如何保留这些变化,备忘录模式协助我们保留用户的状态,那么本质上也是,计算一次,然后存储,下次需要的时候直接取出。不需要redo前面的计算。比如一个对象这样变迁 object[state1] - event1->object[state2]- event2->.......object[statei] 如果我们要得到object 在状态i是的数据,那么有两个办法,一个是记录全部的event,然后从object[state1]开始redo,另一个办法就是存储全部的state,以备查询。 从上可知,都存在以下抽象的操作 1)compute 2)save 3)if (saved) get else compute then save 这种在算法中称作Memoization algorithm, 在动态规划中应用为重叠子结构。方法与之类似,不再多讲,那么他们 的本质是什么呢?这样做的好处是什么能,存储计算的好处是什么呢? 这来自于一个很朴素的原理,就是时间和空间的问题,这个所有学习计算机的人都知道,如果一种计算被经常执行 那么这种计算结果被存储的结果,就把计算的时间变为了查表的时间,拿单件来说,如果一个对象,我们经常需要 它,而且不希望每次需要的时候构造他,用完了就析构他,希望保留一份实例,那么就是空间换时间的经典例子, 可能有人会说我故意遗漏了唯一性的这个属性,单件的唯一性就是集合的唯一性,一个计算如果被保留了,那么就 不需要再次被计算了,计算仅唯一的计算一次,空间中也仅保留唯一的计算结果。 最后,我不禁得到这样一个结论,一切皆有联系,最终的原理其实都是朴实无华的. 原创于: |
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
31.250ms |