漫谈设计模式 —— 创建行为的封装

在经典的24个设计模式中,有一部分是关于对创建行为的封装的,他们分别是原型模式、单例模式、生成器模式、简单工厂模式、工厂方法模式、抽象工厂模式。他们都是致力于把实例化对象的职责解耦出来,通过不同的形式封装达到不同的效果。我们从最简单的例子开始入手看看这几种模式的相似与不同。

通常,我们实例化一个对象最简单的就是通过new操作符直接创建,但如果该对象比较复杂,在创建的同时要进行许多初始化工作,例如游戏中创建一个NPC对象,在new一个NPC后,要把他添加到相应的场景中,还有要对他设置许多属性,还要根据他身上的装备来绑定各种部件。通常我们会写一个NPCFactory类,提供一个NPCFactory::CreateNPC()接口把这一连串创建NPC相关的流程封装起来。在设计模式中把这样的做法叫做简单工厂(Simple Factory)模式简单工厂严格来说不算是一个完整的设计模式,但很多人却误以为这就是所谓的工厂模式。

还有一个与上面说的很相似的是生成器(Builder)模式,不同点在于生成器模式把创建过程分开几个步骤封装到类中。就像这样:

NPCFactory.Init(szResourcePath);
NPCFactory.AddToScene(nSceneID);
NPCFactory.SetProperty();
NPCFactory.Equit();
NPC* pNpcA = NPCFactory.GetObject();

生成器模式的最大特点是分步骤,他把创建的过程封装成好几个步骤并交由使用者控制,使用者可以更灵活的控制创建,但相对应他的问题也是使用者必须熟悉创建流程与规则,要知道先Init、再设置、最后调GetObject才真正得到对象。

在介绍完简单工厂与生成器模式后,我们接着来看看另外两个很相似的工厂模式。工厂方法(Factory Method)模式抽象工厂(Abstract Factory)模式

Continue reading

漫谈设计模式

最近有空又重新看了一遍《Head First 设计模式》,孔子曰“温故而知新”,诚不欺我也。虽然在大学时已经看过这本书,但工作两三年后重新看回来还是获益良多。不仅弄明白了很多以前一知半解的东西,而且对于很多模式都能够在项目工程中找到实例,了解了其设计意图以及优缺点,很有拨云见日的感觉。

现有的设计模式很多,最经典的有24个,他们有的很相似,有的南辕北辙,各有各的优缺点,各有各的适用范围。通过三篇文章来把他们归类、梳理并逐一介绍:

(一)漫谈设计模式 —— 创建行为的封装

(二)漫谈设计模式 —— 结构的封装

(三)漫谈设计模式 —— 职责的封装

通过以上的文章我们看了那么多的模式,我们肯定会有所思考。设计模式到底是什么?设计模式用来干什么的?

Continue reading

布隆过滤器

布隆过滤器是Burton Bloom 在1970年提出的,用于解决打标记的问题。对于每个字符串,利用k种不同的字符串hash算法,生成k个哈希值,然后把这k个值打入大小为m个bit的槽中,用以标记这个字符串已经出现。举个简单的例子,对于字符串”blog.vvbin.com”,利用k=4种不同的字符串哈希算法,产生4个哈希值:4216,3054,1017,2222。然后采用求模的方式打入m=31的bit槽中,结果如下图:

bloom-bit

在查询时,只要查看对应的k个bit位是否为1,就可以知道当前字符串是否已经存在。

布隆过滤器通常只需传统哈希表1/8的存储空间,就可达到很好的哈希效果。假设我们有10万个字符串,鉴于hash表的存储效率大约是50%,这样我们需要20万个槽,每个槽是一个32位(8字节)的DWORD,这样我们需要160万字节空间来存储。而如果采用布隆过滤器,对于10万个字符串,我们采用160万个槽来存储,每个槽是一个bit,那么我们总共只需160万bit,也就是20万字节,即可达到比较理想的哈希效果。

Continue reading

侯捷老师《C++及标准库》课程培训 记录

这周一至周三(2013.07.22-2013.07.24)三天时间,有幸参加到侯捷老师的《C++及标准库》课程培训,不仅加深了对C++的理解,了解了STL的许多细节,而且重温了大学课堂的生活,十分高兴。感谢公司给予这样宝贵的机会,感谢侯捷老师的精彩课程,更加感谢他创作,翻译了这么多优秀书籍,为广大国内程序员指点迷津,授业解惑。

这次课程面向的是初级程序员,所以有些知识点在大学中已经接触到,但温故而知新也不失为一件乐事。以下是我对于这三天课程的一些知识点总结。

Continue reading

为什么求模运算要用素数(质数)—— 哈希表设计

在设计用除法来散射的哈希表时,我们都会用数值模哈希表大小,得到的余数来作为ID存入哈希表对应格子中。所有文章都表明要用一个较大的素数来作为哈希表的大小,也就是要模一个较大的素数。但为什么就是要用素数呢?简单分析一下可以看出玄机。

先看看如果用一个合数8作为哈希表大小,0-30在哈希表中的散射情况:

(表1)

mod8

再来看看用质数7作为哈希表大小,0-30在哈希表中的散射情况:

(表2)

mod7

Continue reading