随笔-99  评论-224  文章-30  trackbacks-0
 
基本原理
   快速排序算法是一种分治排序算法,影响其性能的因素有划分元素的选择、小的子文件的处理、重复关键字等,本文论述针对重复关键字的改进实现。首先来回顾下一般的算法实现,其流程如下:
   a. 选择一个划分元素,这个元素在划分后将在最终的位置上,通常是选择最右端元素作为划分点。
   b. 从左端开始扫描,直到找到大于划分元素的元素;同时从右端开始扫描,直到找到小于划分元素的元素,再交换使扫描停止的这两个元素。
   c. 继续步骤b,直到左指针不小于右指针,最后再交换左指针元素和划分元素。
   d. 在左指针左侧和右侧区间(区间不包括左指针元素)重复以上过程,直至元素个数为0或1。
   在划分的过程中,位于左指针左侧的元素都比划分元素小,右侧的元素都比划分元素大,如下图所示
   由上述可见,一般的算法实现针对大量重复关键字的输入情况,其性能表现很差,例如如果一个文件完全由相等的值(只有一个值)组成,那么它就不需要再进行任何排序,但前面的算法依然划分直至得到小的子文件,无论文件有多大。针对这一情况,可以作实质性的改进,从而避免处理元素相同的子区间,提高效率。改进的算法实现主要问题在于如何处理与划分元素相等的情况,这里的基本思想是将区间划分为三个部分,左部分小于划分元素,中间部分等于划分元素,右部分大于划分元素,然后再在左右两部分进行子处理,具体的流程如下:
   a'. 选择左端元素、中间元素和右端元素的中值作为划分元素,也就是三者取中划分,这样能有效避免划分区间的最坏情况。
   b'. 从左端开始扫描,直到找到不小于划分元素的元素;同时从右端开始扫描,直到找到不大于划分元素的元素,再交换使扫描停止的这两个元素。如果左指针元素等于划分元素,那么与左端的元素交换,并递增左端位置(初始化为文件最左位置);如果右指针元素等于划分元素,那么与右端元素交换,并递减右端位置(初始化为文件最右位置)。
   c'. 继续步骤b',直到左指针不小于右指针。
   d'. 交换最左端区间和左指针左侧区间(不包括左指针元素),这一过程会递减左端位置;交换最右端区间和左指针右侧区间(包括左指针元素),这一过程会递增右端位置。
   e'. 在最左端和最右端区间重复以上过程,直至元素个数为0或1。
   在划分的过程中,与划分元素相等的元素分布在最左端和最右端,如下图所示
   在划分完成后处理子文件前,需要对调区间,如步骤d'所述,结果如下图所示

代码实现
   上面所有图中的v代表划分元素,最后列出代码清单,函数quick_sort有两个版本,一个是支持operator < 的默认实现,另一个是支持带谓词的自定义比较实现。在其中用到了实现三者取中值的__median函数,对应的也有两个版本实现,如下所示
 1template<class _RandIt>
 2void quick_sort(_RandIt _first,_RandIt _last)
 3{
 4    typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
 5    if (!(_first<_last-1)) return;
 6
 7    _RandIt i = _first,j = _last-1,p = i,q = j,k;
 8    _ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2));
 9
10    while(true)
11    {
12        while(*< pivot) ++i;
13        while(pivot < *j) --j;
14        if (!(i < j)) break;
15        std::iter_swap(i,j);
16        
17        if (!(*< pivot) && !(pivot < *i)) 
18            std::iter_swap(p++,i);
19        if (!(*< pivot) && !(pivot < *j))
20            std::iter_swap(q--,j);
21        ++i; --j;
22    }

23    
24    j = i - 1
25    for(k = _first;k<p;--j,++k) std::iter_swap(k,j);
26    for(k = _last-1;k>q;++i,--k) std::iter_swap(k,i);
27
28    quick_sort(_first,j+1);
29    quick_sort(i,_last);
30}

31
32template<class _RandIt,class _Compare>
33void quick_sort(_RandIt _first,_RandIt _last,_Compare _comp)
34{
35    typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
36    if (!(_first < _last - 1)) return;
37
38    _RandIt i = _first,j = _last-1,p = i, q = j, k;
39    _ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2),_comp);
40
41    while(true)
42    {
43        while(_comp(*i,pivot)) ++i;
44        while(_comp(pivot,*j)) --j; 
45        if (!(i < j)) break;
46        std::iter_swap(i,j);
47
48        if (!_comp(*i,pivot) && !_comp(pivot,*i)) 
49            std::iter_swap(p++,i);
50        if (!_comp(*j,pivot) && !_comp(pivot,*j))
51            std::iter_swap(q--,j);
52        ++i; --j;
53    }

54    j = i - 1;
55    for(k = _first;k < p;++k,--j)    
56        std::iter_swap(k,j);
57    for(k = _last - 1;k > q;--k,++i) 
58        std::iter_swap(k,i);
59
60    quick_sort(_first,j+1,_comp);
61    quick_sort(i,_last,_comp);
62}
   从上面实现可看出,与一般的实现相比,划分过程多了两个if及for循环,if测试用来将找到的重复元素放在左右两端;for循环用来交换区间,将重复元素再放在中间,这额外的工作量只与找到的重复关键字的个数成线性,因此,即使在没有重复关键字的情况下,它也运行得很好,平均时间复杂度为O(NlgN)。
posted @ 2012-05-19 14:48 春秋十二月 阅读(2184) | 评论 (1)编辑 收藏
     摘要: C与C++ API的比较    在c语言中,API体现为c函数,如操作系统提供的一系列API,在c++中,API体现为自由函数,这里的自由函数是指除普通成员函数、静态成员函数、友元函数外的能在某命名空间作用域或全局空间内直接访问的函数,而这更多地体现为函数模板,如stl提供的一系列算法swap、count和sort等。相对于c API,c++ API具有类型安全和封...  阅读全文
posted @ 2011-12-24 19:08 春秋十二月 阅读(2685) | 评论 (2)编辑 收藏
     摘要:    关于cstatic控件的自绘,网上也有很多的代码及文章,更有其界面画得很漂亮的、多种多样的功能。近来我自行封装实现了一个真彩色静态框类,目标初衷是从颜色、字体、光标入手,改变原始标准cstatic的色彩风格,使界面初步美化,具有好看的效果。同时作为一个基础简单的类来维护,为后续的功能增强及美化提供参考扩展,这个CColorStatic类的特点及功能如下:(1)文...  阅读全文
posted @ 2011-12-18 00:54 春秋十二月 阅读(3309) | 评论 (1)编辑 收藏
     摘要:    在《多标签视图类CTabView的设计实现》一文中,CTabView从CBasicSubClassWnd私有继承,重写其虚函数SubWindowProc,捕获WM_DRAWITEM和TTN_GETDISPINFO消息,从而实现了DrawItem和UpdateTooltipText虚函数回调机制,支持派生类的自定义处理,而CBasicSubClassWnd就是一个...  阅读全文
posted @ 2011-12-11 11:07 春秋十二月 阅读(1980) | 评论 (0)编辑 收藏
     摘要:    在MFC9(在vc2008和vc2010中,已经有了CTabView的现成类)以前的版本中,有CListView,CTreeView,CEditView,CRichEditView等控件视图类,但就是没有类似的CTabView类,因工作需要,最近在做一个简单的多标签IE浏览器,开发环境是vs2005,基本框架是sdi + chtmlview + ctabview...  阅读全文
posted @ 2011-12-11 00:47 春秋十二月 阅读(4269) | 评论 (3)编辑 收藏
     摘要:    关于系统托盘图标类,网上也有很多的代码,但都不太简洁灵活易用,为了这一目的,本人自行封装了一个API版本的实现类,这个类的设计思想来源于观察者模式,从而较好地解耦了托盘通知消息的发送、接收、处理这三者间的关系,使这三者可以是同一个对象,也可以是不同的对象,具体的情况可根据业务逻辑灵活选择控制,主要包括以下几方面的特点:1)对于托盘通知消息的接收处理,提供了一个默...  阅读全文
posted @ 2011-12-04 03:15 春秋十二月 阅读(1750) | 评论 (0)编辑 收藏
   在开发HTTP相关程序时,经常会碰到从网络链接URL中提取协议名、服务器、路径等目标对象,如果使用C/C++字符串操作函数,那么则显得有点麻烦且代码不易维护,其实关于文本内容的解析工作,都可优先考虑使用正则表达式库来解决处理,C++方面的正则库也有很多种,如atl、pcre、boost。下面就使用boost中的regex来解析URL提取协议名、服务器、路径为目标说明其用法。

协议名
   可有可无,如果有时则后面必跟着://,如果没有,则默认为使用http协议。通常还有其它的协议如https、ssl、ftp、mailto等。因此匹配协议名的正则表达式应该是(?:(mailto|ssh|ftp|https?)://)?,注意这个表达式本身捕获了协议名,但不包括://。
   
服务器
   或是域名,如www.csdn.net;或是IP地址,如192.168.1.1,可带端口号,如192.168.1.1:8080。匹配域名的正则表达式为(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z])),表达式"(?:com|net|edu|biz|gov|org|in(?:t|fo)"匹配了com、net、edu、biz、gov、org、int、info等常见的域名,而(?-i:[a-z][a-z])匹配了国家代码,而且只允许小写为合法的,如www.richcomm.com.cn。匹配IP要尽量精确,考虑到IP每部分应为数字且范围在0-255之间,因此表达式应为(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])。注意以上域名或IP的正则式本身不捕获它们,这是为了留在后面作为整体捕获。
   端口号的正则表达式为(?::(\d{1,5}))?,这里限制了端口号为1至5位的数字,更精确的匹配如要求在某范围如[1024,65535]间则可参考以上IP正则模式。综上所得,匹配服务器的正则表达式为((?:(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))|(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])))(?::(\d{1,5}))?,这个正则式作为整体捕获了域名或IP,及端口号(若有),如www.csdn.net,则得到www.csdn.net和空(没有端口,http默认为80,https默认为443)子串;192.168.1.1:8080则得到192.168.1.1和8080子串。
   
路径
   最简单的形式为(/.*)?,更精确的形式为/[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]*(?:[.!,?]+[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]+)*。
   
   以上所有正则表达式均为ascii字符集,对于unicode字符集则在其前加L即可。
   
   为方便使用,封装成了两个自由模板函数,如下所示
 1template<typename charT>
 2inline bool boost_match(const charT* pattern,const charT* text,unsigned int flags=boost::regex::normal,boost::match_results<const charT*>* result=NULL)
 3{
 4    boost::basic_regex<charT,boost::regex_traits<charT> > expression(pattern,flags); 
 5    if(NULL==result)
 6        return boost::regex_match(text,expression);
 7    return boost::regex_match(text,*result,expression);
 8}

 9
10template<typename charT>
11inline bool boost_search(const charT* pattern,const charT* text,unsigned int flags=boost::regex::normal,boost::match_results<const charT*>* result=NULL)
12{
13    boost::basic_regex<charT,boost::regex_traits<charT> > expression(pattern,flags); 
14    if(NULL==result)
15        return boost::regex_search(text,expression);
16    return boost::regex_search(text,*result,expression);
17}
   
   测试示例如下      
 1static const string protocol = "(?:(mailto|ssh|ftp|https?)://)?";
 2static const string hostname = "(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))";
 3static const string ip = "(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])";
 4static const string port = "(?::(\\d{1,5}))?";
 5static const string path = "(/.*)?";
 6static const string pattern = protocol + "((?:" + hostname + "|" + ip + "))" + port + path;
 7
 8int _tmain(int argc, _TCHAR* argv[])
 9{
10    using namespace boost;
11
12    //形式1: 带协议名,服务器为名称,不带端口号
13    bool ret;
14    string text = "http://www.cppblog.com/qinqing1984";
15    boost::cmatch what;
16    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
17    assert(ret);
18    assert(what[1].str()=="http");
19    assert(what[2].str()=="www.cppblog.com");
20    assert(what[3].str()=="");
21    assert(what[4].str()=="/qinqing1984");
22
23    //形式2: 不带协议名,服务器为名称,带端口号
24    text = "www.cppblog.com:80/qinqing1984";
25    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
26    assert(ret);
27    assert(what[1].str()=="");
28    assert(what[2].str()=="www.cppblog.com");
29    assert(what[3].str()=="80");
30    assert(what[4].str()=="/qinqing1984");
31
32    //形式3: 不带协议名,服务器为名称,不带路径
33    text = "www.cppblog.com:80";
34    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
35    assert(ret);
36    assert(what[1].str()=="");
37    assert(what[2].str()=="www.cppblog.com");
38    assert(what[3].str()=="80");
39    assert(what[4].str()=="");
40
41    //形式4: 协议为https,服务器为IP,带端口号
42    text = "https://192.168.1.1:443/index.html";
43    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
44    assert(ret);
45    assert(what[1].str()=="https");
46    assert(what[2].str()=="192.168.1.1");
47    assert(what[3].str()=="443");
48    assert(what[4].str()=="/index.html");
49
50    //形式5: 端口超过5位数
51    text = "ftp://192.168.1.1:888888";
52    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
53    assert(!ret);
54
55    //形式6: 没有协议名
56    text = "//192.168.1.1/index.html";
57    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
58    assert(!ret);
59
60    //形式7: 没有服务器
61    text = "http:///index.html";
62    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
63    assert(!ret);
64
65    //形式8: 不合法的服务器
66    text = "cppblog/index.html";
67    ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
68    assert(!ret);
69
70    return 0;
71}
   对URL的解析,因时间有限,本文所述不尽详细,只是略作分析,以点带面,更多的精确匹配则依赖于实际的应用需求。
posted @ 2011-11-27 17:22 春秋十二月 阅读(6800) | 评论 (5)编辑 收藏
     摘要:    在《基于stl序列容器实现的通用集合类》一文中,已经讲到了具体实现,近来因再次用到它又改进完善了,主要体现在以下几点:1)增加了查找操作方法,支持按值类型和谓词条件两种方式。2)增加重载了按值类型和谓词条件2种方式删除元素的方法。3)增加了2个模板参数以支持线程安全,一个是线程模型模板类,一个是互斥锁类,使用loki库来实现,因此所有方法现在都是线程安全的,当需...  阅读全文
posted @ 2011-10-21 18:43 春秋十二月 阅读(2847) | 评论 (1)编辑 收藏
     摘要:    本文讲述双端堆的5个公开泛型操作算法:make_dheap(原位构造双端堆)、push_dheap(插入元素)、pop_max_dheap(删除最大元素)、pop_min_dheap(删除最小元素),is_dheap(堆验证),每个算法都提供<小于运算符和仿函数比较2个版本,要注意的是比较必须是严格弱序的,即对于<版本存在a<b为真且b<...  阅读全文
posted @ 2011-10-05 13:24 春秋十二月 阅读(2364) | 评论 (1)编辑 收藏
     摘要:    在《基于双端堆实现的优先级队列(1):原理》一文中讲述了双端堆的相关原理,本文则详细讲述具体的内部实现,便于区分,内部函数名称都以双下划线作为前缀,在这里,有几个关键问题需要说明    1)怎么求一个结点的对称结点:如果完全二叉树根结点从索引1开始但不存储元素,那么最小堆根结点则在索引2,最大堆根结点则在索引3,4和5为2的左右孩...  阅读全文
posted @ 2011-10-03 17:54 春秋十二月 阅读(1883) | 评论 (1)编辑 收藏
仅列出标题
共10页: First 2 3 4 5 6 7 8 9 10