首页
社区
课程
招聘
[原创]程序员的智慧-聊聊那些经典设计和经典算法
发表于: 2010-5-16 03:29 13129

[原创]程序员的智慧-聊聊那些经典设计和经典算法

2010-5-16 03:29
13129

大家说说印象比较深的设计和算法吧,我先来,算是抛砖引玉哈!

C++的虚函数
======================
C++使用虚函数实现了其对象的多态,C++对象的开始四个字节是指向虚函数表的指针,其初始化顺序是先基类后派生类,所以该虚函数表永远指向最后一个派生类,从而实现了相同函数在不同对象中的不同行为,使得对象既有共性,又有其个性。

内存池分配、回收之伙伴算法
=======================
伙伴算法是空闲链表法的一个增强算法,依次建立2^0\2^1\2^2\2^3...2^n大小的 内存块空闲链表,利用相邻内存块的伙伴性质,很容易将互为伙伴的内存块进行合并移到相应的空闲链表或将一块内存拆分成两块伙伴内存,一块分配出去,另一块挂入相应空闲链表,使得内存的分配和回收变得高效。

AVL树
=======================
AVL树是一个平衡二叉树,其中序遍历是从小到大排序的,该结构插入节点和检索非常高效,被广泛应用

快速排序
=======================
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。效率非常高

密码学之非对称加密协议(公钥、私钥加密协议)
======================
非对称加密算法需要两个密钥,用其中一个加密产生的密文,只能通过另外一个密钥解密,密钥持有者A可以将其中一个公开,称为公用密钥,另外一个秘密保存称为私钥,这样当某人B想给A传一封秘信时,只要将密信使用A的公钥加密后,就可以放心使用各种信道将迷信传给A了,因为该密信只有A可以解密,第三者截取因为无法解密而毫无意义。
该算法很好地解决了密钥的安全传递的问题,因为公钥和加密算法都是公开的,私钥不需要传输。

密码学之数字签名协议(身份鉴别、防抵赖)
======================
数字签名也是建立在非对称加密基础之上的,如果A君用它的私钥将文件加密后在发布,A君就无法抵赖该文件是其发布的,因为其他人能通过A君的公钥将文件解密就说明,如果算法可靠,该文件一定是A君用其私钥加密的。
由于非对称加密算法的加密和解密很慢,现在的数字签名并非是将其要发布的信息用其私钥加密,而是先用一个单项散列算法如(MD5)产生一个该信息的比较短的指纹(hash值),对其指纹用其私钥加密后和信息一并发布,同样达到了防抵赖的作用。

无回溯字符串模式匹配-kmp算法
======================
他是根据子串的特征,当匹配失败时,不需要回溯,而是直接将字串向后滑动若干个字节,继续匹配,极大提高了匹配速度。该算法被广泛使用。详细请参考数据结构教程。

最小路径选路-迪杰斯特拉算法、弗洛伊德算法
======================
学习数据结构的时候,印象最深的就要算kmp算法和最小路径算法了,因为理解他们比较费脑子,我是不可能发明这些算法了,发明他们的都是天才,呵呵。
使用最短路径的算法曾经帮人写过一个小东西,还是很有效的,记得是使用的弗洛伊德算法的一个变种,要详细了解的朋友可以查找相关资料,想将他们使用在你的项目中,代码直接从教科书上抄就可以了,不需要理解。

tcp协议之-nagle算法
======================
tcp、ip中令人叫绝的想法很多,印象最深的要算nagle算法了。
tcp出于效率和流量控制的考虑,发送端的数据不是产生多少就马上发送多少,一般是等到数据集聚到发送缓冲区长度的一半或者数据达到最大tcp数据包数据部分长度(好像是65515)才启动发送,而且还要看接受端可用缓冲区的大小,如果接受端产生一个回应报文通知发送端没有接受空间了,发送端哪怕缓冲区已经满了,也不会启动发送,直到接受端通告发送端其已经有了接受数据的空间了。
这样就有一个问题,假如发送端就是要发送一个小报文(比如10个字节),然后等待对方的回应。按照上面的方案,tcp会一直等数据收集到一定量才发送,于是矛盾就产生了。应用层不再发数据,tcp等不到足够的数据不会将10个字的数据发送到网卡,接收端应用层收不到数据就不会回应发送端。
你也可能说,可以让修改发送端发送条件,不一定要等到足够的数据再发送,为了效率考虑,可以考虑延时一定的时间,比如说1秒,如果上层还没有数据到来,就将发送缓冲中的数据发出去。当然这样也是可行的,尽管应用端白白等了1秒钟啥也没干,呵呵。
其实nagle算法很好解决了该问题,它的做发是链接建立后的第一次发送不用等待,直接将数据组装成tcp报文发送出去,以后要么等到数据量足够多、要么是等到接受方的确认报文,算法及其简单,而且很好解决了上面的矛盾。

socket之io模型设计
======================
windows下socket有两种工作方式:
1)同步方式
2)异步方式

同步socket又有两种工作模式:
1)阻塞模式
2)非阻塞模式

阻塞模式是最简单的工作模式,以tcp的发送数据为例,如果发送缓冲区没有空间,send调用就不会返回,一直要等到能够发出一点数据为止,哪怕是一个字节,但是send返回并不表示我要发送的数据已经全部提交给了tcp,所以send返回时要检查这次发送的数量,调整发送缓冲指针,继续发送,直到所有数据都提交给了系统。
由于其阻塞的特性,会阻塞发送线程,所以单线程的程序是不适合使用阻塞模式通信的,一般使用一个连接一个线程的方法,但是这种方式对于要维护多个连接的程序,是个不好的选择,线程越多,开销越大。

同步非阻塞模式的socket不会阻塞通信线程,如果发送缓冲区满,send调用也是立刻返回,接受缓冲区空,recv也不会阻塞,所以通信线程要反复调用send或recv尝试发送或接收数据,对cpu是很大的浪费。
针对非阻塞的尴尬,接口开发人员发明了三种io模型来解决该问题:
1)选择模型(select)
2)异步选择模型(AsyncSelect)
3)事件选择模型(EventSeselect)
其思想是根据io类型,预先查看1个或n个socket是否能读、写等。
其select本身来说,select是阻塞的,可以同时监视多个socket,只要所监视的其中一个socket可以读、写,secect调用才返回
异步选择模型其select是异步的(异步是不会阻塞的),是将监视任务委托给系统,系统在socket可读、写时通过消息通知应用程序。有一点需要说明,假如应用程序已经有很多数据需要发送,当收到可写通知时,一定要尽量多地发送数据,直到发送失败,lasterror提示“将要阻塞”,将来才可能有新的可写通知到来,否则永远也不会有。
事件选择模型也是将监视socket状态的工作委托给系统,系统在适当的时候通过事件通知应用程序socket可以的操作。

除了同步工作方式外,还有一种叫异步工作方式
异步工作方式是不会阻塞的,因为是将io操作本身委托给系统,系统在io操作完成后通过回调例程或事件或完成包通知应用程序
异步工作方式有两种io模型和其对应,其实这两种模型是window是异步io的实现:
1)重叠模型
2)完成端口

重叠模型通过事件或回调例程通知应用程序io已经完成
完成端口模型比较复杂,完成端口本身其实是一个io完成包队列。
应用程序一般创建若干个线程用来监视完成端口,这些线程试图从完成端口移除一个完成包,如果有,移除成功,应用程序处理该完成包,否则应用程序监视完成端口的线程被阻塞。

select模型是从UNIX上的Berkeley Software Distribution(BSD)版本的套接字就实现了的,其它四种io模型windows发明的,在windows中完成端口和异步选择模型是使用比较广泛的,一般分别用于服务端和客户端开发。
这五种io模型设计还是比较巧妙的:三种选择模型很好解决了“同步非阻塞”模式编程的不足;重叠模型和完成端口是windows异步io的经典实现,不局限于网络io,对文件io同样适用。

说点题外话,socket的send完成仅仅是将数据(可能是部分)提交给系统,而不是已经发送到了网卡上,更不是已经发送到了接收端。所以要知道你的数据已经发送到了对方的应用层的唯一方法是,让对方给你发送一个应对包。
发送数据要注意,对应tcp,要防止发送和接收的乱序,对于发送,一般应该为每一个链接建立一个发送队列,采用类似nagle的算法启动数据发送。
一次发送可能是你提交数据的一部分,一定要当心,否则出问题没处找去。

======================
欢迎大家不断补充


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 7
支持
分享
最新回复 (16)
雪    币: 184
活跃值: (41)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
2
记得stl中的红黑树就是avl的一个变种
socket的完成端口模型可以说是现在我发现的最完美的异步io模型解决方案

还有现在被广泛使用的“写时拷贝”的想法也挺绝的

怎么没有人对这个话题感兴趣么?大家可以聊聊你自己项目中最得意的地方,呵呵
2010-5-16 10:30
0
雪    币: 156
活跃值: (26)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
3
最短路径算法我就一直理解不能……
2010-5-16 21:40
0
雪    币: 184
活跃值: (41)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
4
最短路径的两个算法的确理解起来有点费脑子,但从教科书上抄过来用却不难,呵呵。
2010-5-16 22:23
0
雪    币: 184
活跃值: (41)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
5
看来大家对我的帖子并不待见,两天才一个回帖,杯具!

问题出在哪儿了????
2010-5-17 12:35
0
雪    币: 144
活跃值: (25)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
6
不错的文章,支持一下!呵呵!
2010-5-17 13:11
0
雪    币: 142
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
很好的文章
看的有点自卑了,别说发明强悍算法,叫我去理解这些现成的都很吃力
2010-5-20 17:03
0
雪    币: 213
活跃值: (15)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
把算法的代码贴一下啦,呵呵,弄成百科,给懒人专用
2010-5-28 01:23
0
雪    币: 247
活跃值: (187)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
版主是不是可以考虑对好的算法设一个主题呢?
那样应该可以集中更多的人去讨论,去了解,而不是到处搜索!
2010-5-28 09:00
0
雪    币: 234
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
自从看了这个帖子以后开始查找算法...找了很久都米找到..只有去借书了...
2010-6-18 16:55
0
雪    币: 132
活跃值: (30)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
11
闲聊贴~灌水~吸收ing
2010-12-7 17:36
0
雪    币: 233
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
我觉得lZ应该弄个系统点的,呵呵各个算法的文章,让我等菜鸟学习下!!
2010-12-9 02:39
0
雪    币: 232
活跃值: (25)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
13
等待大牛们发言
2010-12-13 12:49
0
雪    币: 239
活跃值: (25)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
14
最好每个算法都有详细的例子和应用
2010-12-13 13:03
0
雪    币: 89
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
算法确实是,程序的核心!但是我的造诣太低,不敢发什么评论!
2010-12-13 13:53
0
雪    币: 599
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
曲高而和寡,呵呵。
2010-12-15 08:49
0
雪    币: 35
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
IO完成端口不错,我用过,codeproject.com上也有源码
2010-12-27 10:07
0
游客
登录 | 注册 方可回帖
返回
//