分享
 
 
 

泛型重构实践

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

重构的概念和编程一样古老,但长久以来,人们并未把它作为一项专门的技术提炼出来进行研究。随着Martin Fowler著作的面世,以及XP方法的广为传播,重构思想开始深入人心,相关的书籍和杂志文章也层出不穷,但焦点大多集中在OO代码上。而针对C++,也包括Java和C#中应用日益广泛的模板,却鲜有经验之谈。其实,泛型代码又何尝不需要重构?而且是更需要重构,因为它广泛存在于库中,需要不断提高整体质量。

笔者在此借用一个具体开发中的简单实例,根据需求的变化,对它不断进行重构,希望能够让大家有一些感性认识。同时,也期望抛砖引玉,引起大家对这个领域的重视,逐渐形成一些对泛型代码进行重构的固定手法。

问题描述:

本项目是一个企业级的网络访问控制软件,安装在局域网的出口处,可以控制局域网中的每台计算机能否访问某个特定的网页,能否聊天、打游戏,或者收发邮件等等,并把协议流量都记录下来以供分析。国际上的通用称谓是雇员Internet管理(EIM)软件,主要目的是减少员工在上班时间从事与工作无关的活动,提高工作效率。

其中,网页过滤是一个比较重要的模块,它需要把经网卡捕获到的每个URL请求,在一个存放着数百万条URL的数据库中查找,再决定是不是要切断连接。数据库如此庞大,大部分内容都只能存放在辅存中。如果每次都要访问硬盘查找,速度很难达到要求。但大家平时上网都能感觉到,一个网页中的链接大多数也都是指向同一个网站,如果能够将此前访问过的URL记住,以备后查,是个不错的主意。我们把这个玩意儿叫做Cache,是取其高速缓存之意。实际的URL数据库和Cache都采用字符串部分匹配,但为了简单起见,在这里只取主机名进行精确匹配。

对这个Cache,定几个的基本要求:

固定大小;

查找时间有上限;

使用最近最少使用(LRU)作为替换算法。之所以选择LRU算法,在教科书里都讲过,因为它是堆栈型算法,命中率会随容量单调增加。

第一步,根据具体需求,快速准确地完成目标

让我们根据前面定出的要求编写测试。为了简单起见,我并没有使用CppUnit或者Boost.Test等测试框架,而只使用了标准C++具备的断言。对这么个简单的东西,没有必要拿大炮打蚊子,而且,项目组也没有把测试框架作为代码库的一部分,如果我用了,别人拿过去,就没法编译。

这个东东需要具备哪些行为呢?无非就是增加和查找。对一个URL,将会在用户自定义数据库和系统数据库中依次查找,查找的结果,要么切断,要么通过。最初,我们定义了一个枚举类型来代表这种结果:

// representing the action we'll execute according to this url

enum UrlAction

{

ACTION_CUT, // can not access this page

ACTION_PASS, // allow

NOT_FOUND // haven't found in database or cache

};

第一次看到这个枚举时,我隐约觉得有点不安,也许这就是Martin Fowler所说的“臭味”吧,但又不知问题具体是什么。后面,我们就会发现它对重构过程所造成的障碍。

现在开始写测试:

首先,如果添加了一个条目,这个条目必须在里面:

void UrlCacheTest::testAddedItemMustExists()

{

UrlCache cache;

cache.add("www.163.com", ACTION_CUT);

assert(cache.check("www.163.com") == ACTION_CUT);

cache.add("www.google.com", ACTION_PASS);

assert(cache.check("www.google.com") == ACTION_PASS);

}

第二,如果Cache里没有某个条目,查找时当然就不能有。这个测试真是有点小儿科。但我就曾经犯过低级错误,在函数里返回一个固定值,然后就因为别的事,把这段代码给忘掉了。还是小心为上。考虑一个东西需不需要测试,是一个折衷的过程,如果你不像我这般粗心,就可以少写点代码。而我倾向于尽量多加一些防护措施。

void UrlCacheTest::testNonexistingItem()

{

UrlCache cache;

assert(cache.check("www.163.com") == NOT_FOUND);

}

第三,如果Cache的空间已经满了,再增加一条Url时,就会按LRU算法淘汰出一个候选者。这个淘汰算法对Cache的效率至关重要,而且也是比较复杂的部分,因此要重点测试。

乍一看不太好办,不深入其实现机制,如何能知道谁被淘汰了呢?不过此处可以用一点小技巧。如果我们让这个Cache只有两个元素的空间,在已经加过两条Url之后,再增加一条,必须会有一条被淘汰出来,我们可以通过check来判断淘汰的对象是不是我们所希望的。

同时,这也给我揭示了一个未曾想到的问题:UrlCache的大小虽然固定,但必须在建立时指定。因为我们需要依据命中率,调整应该使用的Cache大小。因此,写出测试代码如下:

void UrlCacheTest::testLRUWithNotEqualHits()

{

UrlCache<2> cache;

cache.add("www.163.com", ACTION_CUT);

cache.add("www.google.com", ACTION_PASS);

cache.check("www.163.com"); // 163.com现在两次命中

cache.add("www.sina.com", ACTION_PASS);

// cache中只有两个空间,必须替换掉一个

// google此时应该被替换掉,因为它比16少一次命中。

assert(cache.check("www.google.com") == NOT_FOUND);

}

UrlCache的大小为何用模板,而不在构造函数中传进去呢?主要考虑是这样实现起来最简单,可以用数组作为存储容器,很自然地就满足了固定大小的要求。当然,如果这个Cache需要动态调整大小,那就只能通过构造函数传了。

加了模板参数后,前两个测试的代码都得略微调整一下。

还有一个比较细节的问题:连续两次增加同一个URL,却使用不同的UrlAction,这个Cache应该是什么行为?是抛出异常、返回错误值、还是忽略?无论如何,都必须有确定的行为。最简单的办法就是只保留最后一次的结果。

void UrlCacheTest::testAddTwice()

{

UrlCache<2> cache;

cache.add("www.163.com", ACTION_CUT);

cache.add("www.163.com", ACTION_PASS);

// 只保留最后一次的结果

assert(cache.check("www.163.com") == ACTION_PASS);

}

现在,写一个do-nothing的UrlCache,让整个程序通过编译吧:

template<int SIZE>

class UrlCache

{

public:

UrlCache();

void add(const ::std::string& url, UrlAction action);

UrlAction check(const ::std::string& url) const;

private:

// not implemented

UrlCache(const UrlCache&);

UrlCache& operator=(const UrlCache&);

};

template<int SIZE>

UrlCache<SIZE>::UrlCache()

{

}

template<int SIZE>

void UrlCache<SIZE>::add(const ::std::string& url, UrlAction action)

{

}

template<int SIZE>

UrlAction UrlCache<SIZE>::check(const ::std::string& url) const

{

return NOT_FOUND;

}

最后,加上一个所有测试的驱动函数,以及整个测试程序的入口:

void UrlCacheTest::testAll()

{

testAddedItemMustExists();

testNonexistingItem();

testLRUWithNotEqualHits();

}

int main(int argc, char* argv[])

{

UrlCacheTest tester;

tester.testAll();

return 0;

}

编译,运行,不出所料,在第一个assert的地方就出错了。

剩下的任务,就是让测试通过。

用一个叫UrlItem的类来表示Cache中的一个元素:

class UrlItem

{

public:

UrlItem();

UrlItem(const ::std::string& url, UrlAction action);

const ::std::string& url() const;

UrlAction action() const;

private:

::std::string url_;

UrlAction action_;

};

我决定用一个固定的数组作为容器,用一个int型的值来代表该UrlItem当前命中的情况:

template<int SIZE>

class UrlCache

{

// …

private:

::std::pair<UrlItem, int> items_[SIZE];

};

然后,实现两个成员函数:

template<int SIZE>

void UrlCache<SIZE>::add(const std::string& url, UrlAction action)

{

int hits = items_[0].second;

int candidate = 0;

// loop begins from 1, because item 0 is the default value

for (int i = 1; i < SIZE; ++i)

{

if (items_[i].second < hits)

{

hits = items_[i].second;

candidate = i;

}

}

items_[candidate] = std::make_pair(UrlItem(url, action), 1);

}

template<int SIZE>

UrlAction UrlCache<SIZE>::check(const std::string& url)

{

for (int i = 0; i < SIZE; ++i)

{

if (items_[i].first.url() == url)

{

items_[i].second++;

return items_[i].first.action();

}

}

return NOT_FOUND;

}

在实现这两个成员函数的过程中,我查了查LRU(最近最少使用)算法和它的几个变种,仔细研读,因为此前我从来没有做过这样的东西。我选择了最简单的一种方法,而且还不敢保证我是否理解有误,或者实现上有问题。不过我还是比较有信心,因为我有安全网———单元测试。

大概花了10分钟时间,东调调,西整整,终于把编译和测试都通过了。这就是我们需要的功能,不多不少,刚好够用。眼睛有点酸,起身接了点水,一边喝着,一边眺望远方,顺便活动一下脸部神经。

这个Cache工作得很好。通过了单元测试,在命中率测试中也获得了高分。我有点自鸣得意,把代码和数据都提交到代码库中,然后带着愉快的心情,转而编写程序的其它部分。

过了不久,我又碰到另一部分代码,需要根据IP地址,反向查找对应的主机名。这个过程需要联络DNS服务器,这个过程受网络和DNS响应速度的影响很大,延迟和不确定性更胜过查找URL数据库,因而我需要将取得的IP/主机名对应关系也记住。这可以用一个map来实现,但我们的程序需要无人看守地不间断运行,如果任由这个map不断增大,物理内存到最后就会因为这个map而耗光。于是我又想到了曾经派上过用场的Cache。可原来的UrlCache完全是为UrlItem量身定制,要想重用,有点难度。我开始埋怨自己当初想得不够周全了。埋怨归埋怨,问题还得解决。我可不想再重新写一个Cache,重构的时机到了。

重构---将元素类型参数化

工作量不小,悠着点儿,一步一步来。

首先把UrlCache改为Cache,以符合其作为通用Cache的功能。同时,将头文件,实现文件、工程文件和Makefile都相应地更新。

然后,在测试程序中,把所有引用UrlCache的代码全部换成Cache。这一步倒是可以借助于文本替换工具。

编译,让编译器来帮我们查找没有发现的引用点。

下一步,考虑替换UrlItem。先思考一下:从更抽象的层次考虑,一个Cache,有哪几个重要的概念?

对应的值

是否命中。

在前一个版本中,我把后两个概念混在一起,在UrlAction中加了一个NOT_FOUND,原来这就是我觉得不对劲的地方。因为命中与否是Cache本身的概念,而键和值则随Cache元素类型而变化。但犯错误终归不可避免,现在就得纠正这个错误,把这两个概念分开。

因此,首先重构check成员函数,在UrlAction中去掉NOT_FOUND

enum UrlAction { ACTION_CUT, ACTION_PASS };

一鼓作气,让我们把check成员函数的声明改为:

bool check(const std::string& url, UrlAction& action);

如果Url在Cache中存在,则返回true,并将对应的值拷贝到输出参数action中,否则,返回false,不改变参数action的内容。

在测试程序中把所有对check的调用替换成新版本,然后,编译并运行。一切OK。

接口已经确定下来,现在就该大刀阔斧地修改实现代码了。这中间,没有遵循什么固定的章法,因为接口已经确定,函数体可以一个一个地改。最终的结果就是:类模板Cache具有三个模板参数:键类型、值类型和大小。最终的代码是这样:

#include <utility>

template<typename Key, typename Value>

class CacheItem

{

public:

typedef Key key_type;

typedef Value value_type;

CacheItem() {};

CacheItem(const Key& key, const Value& value);

const Key& key() const { return assoc_.first; }

const Value& value() const { return assoc_.second; }

int hits() const { return hits_; }

void incHits() { hits_++; }

private:

:: std::pair<Key, Value> assoc_;

int hits_;

};

template<typename Key, typename Value>

CacheItem<Key, Value>::CacheItem(const Key& key, const Value& value)

: assoc_(std::pair<Key, Value>(key, value)), hits_(0)

{

}

template<typename Key, typename Value, int SIZE>

class Cache

{

public:

Cache();

void add(const Key& key, const Value& value);

bool check(const Key& key, Value& value);

private:

// not implemented

Cache(const Cache&);

Cache& operator=(const Cache&);

CacheItem<Key, Value> items_[SIZE];

};

template<typename Key, typename Value, int SIZE>

Cache<Key, Value, SIZE>::Cache()

{

}

template<typename Key, typename Value, int SIZE>

void Cache<Key, Value, SIZE>::add(const Key& key, const Value& value)

{

int hits = items_[0].hits();

int candidate = 0;

for (int i = 0; i < SIZE; ++i)

{

if (items_[i].hits() < hits)

{

hits = items_[i].hits();

candidate = i;

}

}

items_[candidate] = CacheItem<Key, Value>(key, value);

}

template<typename Key, typename Value, int SIZE>

bool Cache<Key, Value, SIZE>::check(const Key& key, Value& value)

{

for (int i = 0; i < SIZE; ++i)

{

if (items_[i].key() == key)

{

items_[i].incHits();

value = items_[i].value();

return true;

}

}

return false;

}

因为增加了模板参数,所以原来的测试需要稍做修改。而且在网页过滤模块中已经用到了这个Cache,所以也得把对应的地方改过来,编译器可以在我们疏忽时提醒我们。

运行测试,有一个断言居然出错了。哦,原来是我图方便,在测试代码中直接拷贝、粘贴造成的。这让我又一次感激这些不起眼的测试代码。

既然这个Cache还要用于IP/主机名的缓存,那也为它增加一个测试吧。在实际中,IP地址是用一个类来表示的,不过这里,我们还是直接用点分十进制格式的字符串表示,别让那些无关紧要的东西污染了正题。这样,键和值都是标准string。

void testIPHostPairCache()

{

Cache<std::string, std::string, 2> cache;

std::string host;

cache.add("10.10.10.37", "RMY");

cache.add("10.10.10.31", "sunwang");

// 37现在两次命中

cache.check("10.10.10.37", host);

cache.add("10.10.10.38", "Xiaoqi");

// 31此时应该被替换掉,因为它比37少一次命中

assert(!cache.check("10.10.10.31", host));

}

好,我们的Cache又在另一个地方派上了用场,这让我觉得有点兴奋。兴许什么时候,还能够重用这段不起眼的代码呢?看来,该写个小小的Readme了。

我们的重构到此告一段落,但如果要挑刺,其实还有很多值得改进的地方,比如:

1. Cache对键和值都要求有默认构造函数和拷贝赋值运算符,这在某些情况下不现实。

2. 判断命中时,直接以键值是否相等作为标准,没有灵活性。假设为了避免拷贝,键值中存储的是指针,直接以指针进行比较显然是不对的,那就得对比较标准参数化,学习一下标准库,默认情况下,使用std::equal_to,同时又允许使用者提供自己的谓词。

3. 成员函数check,最多要执行SIZE次元素的大小比较,而add最多只需要SIZE次整数比较。但实际使用时,check调用的次数远远比add多。如果有办法让check只有O(logN)的复杂度,让add的运行时间长一点也是值得的。可以用堆排序(如标准库里的堆操作)做到这一点。

但现在的两个类型,我们都已经满足,而且要增加也非难事,对既有的使用者也没有影响。所以,还是留待以后需要此功能时,再加不迟,何苦现在就去加上那或许根本用不上的功能呢?把宝贵的时间用在更有意义的地方吧。我已略感困倦,火炬大厦的钟声已然敲响,该下班了。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有