以文本方式查看主题

-  计算机科学论坛  (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, 在动态规划中应用为重叠子结构。方法与之类似,不再多讲,那么他们

的本质是什么呢?这样做的好处是什么能,存储计算的好处是什么呢?

这来自于一个很朴素的原理,就是时间和空间的问题,这个所有学习计算机的人都知道,如果一种计算被经常执行

那么这种计算结果被存储的结果,就把计算的时间变为了查表的时间,拿单件来说,如果一个对象,我们经常需要

它,而且不希望每次需要的时候构造他,用完了就析构他,希望保留一份实例,那么就是空间换时间的经典例子,

可能有人会说我故意遗漏了唯一性的这个属性,单件的唯一性就是集合的唯一性,一个计算如果被保留了,那么就

不需要再次被计算了,计算仅唯一的计算一次,空间中也仅保留唯一的计算结果。

   最后,我不禁得到这样一个结论,一切皆有联系,最终的原理其实都是朴实无华的.

原创于:
http://blog.csdn.net/pennyliang/archive/2007/01/06/1475741.aspx


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
31.250ms