coolfiry

认认真真做人,兢兢业业做事!
posts - 39, comments - 17, trackbacks - 0, articles - 0

从LiveJournal后台发展看大规模网站性能优化方法

一、LiveJournal发展历程

LiveJournal是99年始于校园中的项目,几个人出于爱好做了这样一个应用,以实现以下功能:

  • 博客,论坛
  • 社会性网络,找到朋友
  • 聚合,把朋友的文章聚合在一起

LiveJournal采用了大量的开源软件,甚至它本身也是一个开源软件。

在上线后,LiveJournal实现了非常快速的增长:

  • 2004年4月份:280万注册用户。
  • 2005年4月份:680万注册用户。
  • 2005年8月份:790万注册用户。
  • 达到了每秒钟上千次的页面请求及处理。
  • 使用了大量MySQL服务器。
  • 使用了大量通用组件。

二、LiveJournal架构现状概况

livejournal_backend.png

三、从LiveJournal发展中学习

 

LiveJournal从1台服务器发展到100台服务器,这其中经历了无数的伤痛,但同时也摸索出了解决这些问题的方法,通过对LiveJournal的学习,可以让我们避免LJ曾经犯过的错误,并且从一开始就对系统进行良好的设计,以避免后期的痛苦。

下面我们一步一步看LJ发展的脚步。

1、一台服务器

一 台别人捐助的服务器,LJ最初就跑在上面,就像Google开始时候用的破服务器一样,值得我们尊敬。这个阶段,LJ的人以惊人的速度熟悉的Unix的操 作管理,服务器性能出现过问题,不过还好,可以通过一些小修小改应付过去。在这个阶段里LJ把CGI升级到了FastCGI。

最终问题出现了,网站越来越慢,已经无法通过优过化来解决的地步,需要更多的服务器,这时LJ开始提供付费服务,可能是想通过这些钱来购买新的服务器,以解决当时的困境。
毫无疑问,当时LJ存在巨大的单点问题,所有的东西都在那台服务器的铁皮盒子里装着。

LJ-backend-7.png

2、两台服务器

用付费服务赚来的钱LJ买了两台服务器:一台叫做Kenny的Dell 6U机器用于提供Web服务,一台叫做Cartman的Dell 6U服务器用于提供数据库服务。

LJ-backend-8.png

LJ有了更大的磁盘,更多的计算资源。但同时网络结构还是非常简单,每台机器两块网卡,Cartman通过内网为Kenny提供MySQL数据库服务。

暂时解决了负载的问题,新的问题又出现了:

  • 原来的一个单点变成了两个单点。
  • 没有冷备份或热备份。
  • 网站速度慢的问题又开始出现了,没办法,增长太快了。
  • Web服务器上CPU达到上限,需要更多的Web服务器。

3、四台服务器

又买了两台,Kyle和Stan,这次都是1U的,都用于提供Web服务。目前LJ一共有3台Web服务器和一台数据库服务器。这时需要在3台Web服务器上进行负载均横。

LJ-backend-9.png

LJ把Kenny用于外部的网关,使用mod_backhand进行负载均横。

然后问题又出现了:

  • 单点故障。数据库和用于做网关的Web服务器都是单点,一旦任何一台机器出现问题将导致所有服务不可用。虽然用于做网关的Web服务器可以通过保持心跳同步迅速切换,但还是无法解决数据库的单点,LJ当时也没做这个。
  • 网站又变慢了,这次是因为IO和数据库的问题,问题是怎么往应用里面添加数据库呢?

4、五台服务器

又买了一台数据库服务器。在两台数据库服务器上使用了数据库同步(Mysql支持的Master-Slave模式),写操作全部针对主数据库(通过Binlog,主服务器上的写操作可以迅速同步到从服务器上),读操作在两个数据库上同时进行(也算是负载均横的一种吧)。

LJ-backend-10.png

实现同步时要注意几个事项:

  • 读操作数据库选择算法处理,要选一个当前负载轻一点的数据库。
  • 在从数据库服务器上只能进行读操作
  • 准备好应对同步过程中的延迟,处理不好可能会导致数据库同步的中断。只需要对写操作进行判断即可,读操作不存在同步问题。

5、更多服务器

有钱了,当然要多买些服务器。部署后快了没多久,又开始慢了。这次有更多的Web服务器,更多的数据库服务器,存在 IO与CPU争用。于是采用了BIG-IP作为负载均衡解决方案。

LJ-backend-11.png

6、现在我们在哪里:

LJ-backend-1.png

现在服务器基本上够了,但性能还是有问题,原因出在架构上。

数据库的架构是最大的问题。由于增加的数据库都是以Slave模式添加到应用内,这样唯一的好处就是将读操作分布到了多台机器,但这样带来的后果就是写操作被大量分发,每台机器都要执行,服务器越多,浪费就越大,随着写操作的增加,用于服务读操作的资源越来越少。

LJ-backend-2.png

由一台分布到两台

LJ-backend-3.png

最终效果

现在我们发现,我们并不需要把这些数据在如此多的服务器上都保留一份。服务器上已经做了RAID,数据库也进行了备份,这么多的备份完全是对资源的浪费,属于冗余极端过度。那为什么不把数据分布存储呢?

问题发现了,开始考虑如何解决。现在要做的就是把不同用户的数据分布到不同的服务器上进行存储,以实现数据的分布式存储,让每台机器只为相对固定的用户服务,以实现平行的架构和良好的可扩展性。

为 了实现用户分组,我们需要为每一个用户分配一个组标记,用于标记此用户的数据存放在哪一组数据库服务器中。每组数据库由一个master及几个slave 组成,并且slave的数量在2-3台,以实现系统资源的最合理分配,既保证数据读操作分布,又避免数据过度冗余以及同步操作对系统资源的过度消耗。

LJ-backend-4.png

由一台(一组)中心服务器提供用户分组控制。所有用户的分组信息都存储在这台机器上,所有针对用户的操作需要先查询这台机器得到用户的组号,然后再到相应的数据库组中获取数据。

这样的用户架构与目前LJ的架构已经很相像了。

在具体的实现时需要注意几个问题:

  • 在数据库组内不要使用自增ID,以便于以后在数据库组之间迁移用户,以实现更合理的I/O,磁盘空间及负载分布。
  • 将userid,postid存储在全局服务器上,可以使用自增,数据库组中的相应值必须以全局服务器上的值为准。全局服务器上使用事务型数据库InnoDB。
  • 在数据库组之间迁移用户时要万分小心,当迁移时用户不能有写操作。

7、现在我们在哪里

LJ-backend-5.png

问题:

  • 一个全局主服务器,挂掉的话所有用户注册及写操作就挂掉。
  • 每个数据库组一个主服务器,挂掉的话这组用户的写操作就挂掉。
  • 数据库组从服务器挂掉的话会导致其它服务器负载过大。

对于Master-Slave模式的单点问题,LJ采取了Master-Master模式来解决。所谓Master-Master实际上是人工实现的,并不是由MySQL直接提供的,实际上也就是两台机器同时是Master,也同时是Slave,互相同步。

Master-Master实现时需要注意:

  • 一个Master出错后恢复同步,最好由服务器自动完成。
  • 数字分配,由于同时在两台机器上写,有些ID可能会冲突。

解决方案:

  • 奇偶数分配ID,一台机器上写奇数,一台机器上写偶数
  • 通过全局服务器进行分配(LJ采用的做法)。

 

Master-Master模式还有一种用法,这种方法与前一种相比,仍然保持两台机器的同步,但只有一台机器提供服务(读和写),在每天晚上的时候进行轮换,或者出现问题的时候进行切换。

8、现在我们在哪里

LJ-backend-6.png

现在插播一条广告,MyISAM VS InnoDB。

使用InnoDB:

  • 支持事务
  • 需要做更多的配置,不过值得,可以更安全的存储数据,以及得到更快的速度。

使用MyISAM:

  • 记录日志(LJ用它来记网络访问日志)
  • 存储只读静态数据,足够快。
  • 并发性很差,无法同时读写数据(添加数据可以)
  • MySQL非正常关闭或死机时会导致索引错误,需要使用myisamchk修复,而且当访问量大时出现非常频繁。

9、缓存

去年我写过一篇文章介绍memcached,它就是由LJ的团队开发的一款缓存工具,以key-value的方式将数据存储到分布的内存中。LJ缓存的数据:

  • 12台独立服务器(不是捐赠的)
  • 28个实例
  • 30GB总容量
  • 90-93%的命中率(用过squid的人可能知道,squid内存加磁盘的命中率大概在70-80%)

如何建立缓存策略?

想缓存所有的东西?那是不可能的,我们只需要缓存已经或者可能导致系统瓶颈的地方,最大程度的提交系统运行效率。通过对MySQL的日志的分析我们可以找到缓存的对象。

缓存的缺点?

  • 没有完美的事物,缓存也有缺点:
  • 增大开发量,需要针对缓存处理编写特殊的代码。
  • 管理难度增加,需要更多人参与系统维护。
  • 当然大内存也需要钱。

10、Web访问负载均衡

在数据包级别使用BIG-IP,但BIG-IP并不知道我们内部的处理机制,无法判断由哪台服务器对这些请求进行处理。反向代理并不能很好的起到作用,不是已经够快了,就是达不到我们想要的效果。

所以,LJ又开发了Perlbal。特点:

  • 快,小,可管理的http web 服务器/代理
  • 可以在内部进行转发
  • 使用Perl开发
  • 单线程,异步,基于事件,使用epoll , kqueue
  • 支持Console管理与http远程管理,支持动态配置加载
  • 多种模式:web服务器,反向代理,插件
  • 支持插件:GIF/PNG互换?

11、MogileFS

LJ使用开源的MogileFS作为分布式文件存储系统。MogileFS使用非常简单,它的主要设计思想是:

  • 文件属于类(类是最小的复制单位)
  • 跟踪文件存储位置
  • 在不同主机上存储
  • 使用MySQL集群统一存储分布信息
  • 大容易廉价磁盘

到目前为止就这么多了,更多文档可以在http://www.danga.com/words/找到。Danga.comLiveJournal.com的 同学们拿这个文档参加了两次MySQL Con,两次OS Con,以及众多的其它会议,无私的把他们的经验分享出来,值得我们学习。在web2.0时代快速开发得到大家越来越多的重视,但良好的设计仍是每一个应 用的基础,希望web2.0们在成长为Top500网站的路上,不要因为架构阻碍了网站的发展。

 http://blog.csdn.net/xmr_gxcfe/archive/2007/09/14/1785292.aspx

 

posted @ 2007-09-29 21:26 Coolfiry 阅读(544) | 评论 (0)编辑 收藏

posted @ 2007-09-25 14:30 Coolfiry 阅读(351) | 评论 (0)编辑 收藏

UML类图的各种标识法
关键字:   UML    
·------>虚线箭头表示依赖关系(dependency),一个类需要与另外一个类一起工作,是它一种最弱的关联关系,常见于各种工具类之间的关系
·——实线表示联合关系(association),一个类包含对另外一个类对象的引用,这个通常是使用属性来实现的,为了表明之间的包含关系,有时候会在实线的一端加上箭头(navigability arrow)来表示导航关系,如果关联的双方又都和第三个类有关联关系,那么可以在实线的中间加一个虚线和第三个类关联来表示这种association classes关系
·◇——空心菱形加实线表示聚合关系(aggregation),它是一种更强的关联关系,表示一个类可以拥有或者享有一个类的实例对象,在java代码表现上跟联合是一样的。
·◆——实心菱形加实线表示组合关系(composition),它的关联性比聚合更强,被组合的对象是组合对象的一部分,没法跟其他的对象共享,而且如果组合对象销毁的话,被组合的对象也会同时被销毁,其表现形式跟联合一样
·空心箭头加实线,表示泛化generalization(继承inheritance)关系,这个很简单
·在rose中要建立enumeration,只需要在建立的class中将其stereotype设置为enumeration即可。stereotype只是用来做一个标记,并不包含别的意义

posted @ 2007-06-10 18:03 Coolfiry 阅读(475) | 评论 (0)编辑 收藏

明天18号,要从沈阳回成都了

posted @ 2007-05-17 09:46 Coolfiry 阅读(209) | 评论 (0)编辑 收藏

PO BO VO DTO POJO DAO概念及其作用(附转换图)

   J2EE开发中大量的专业缩略语很是让人迷惑,尤其是跟一些高手讨论问题的时候,三分钟就被人家满口的专业术语喷晕了,PO VO BO DTO POJO DAO,一大堆的就来了(听过老罗对这种现象的批判的朋友会会心一笑)。

    首先声明偶也不是什么高手,以下总结都是自己的体会。不对之处请您多指教。

PO:
persistant object持久对象

最形象的理解就是一个PO就是数据库中的一条记录。
好处是可以把一条记录作为一个对象处理,可以方便的转为其它对象。

 



BO:
business object业务对象

主要作用是把业务逻辑封装为一个对象。这个对象可以包括一个或多个其它的对象。
比如一个简历,有教育经历、工作经历、社会关系等等。
我们可以把教育经历对应一个PO,工作经历对应一个PO,社会关系对应一个PO。
建立一个对应简历的BO对象处理简历,每个BO包含这些PO。
这样处理业务逻辑时,我们就可以针对BO去处理。

 



VO :
value object值对象
ViewObject表现层对象

主要对应界面显示的数据对象。对于一个WEB页面,或者SWT、SWING的一个界面,用一个VO对象对应整个界面的值。

 



DTO :
Data Transfer Object数据传输对象
主要用于远程调用等需要大量传输对象的地方。
比如我们一张表有100个字段,那么对应的PO就有100个属性。
但是我们界面上只要显示10个字段,
客户端用WEB service来获取数据,没有必要把整个PO对象传递到客户端,
这时我们就可以用只有这10个属性的DTO来传递结果到客户端,这样也不会暴露服务端表结构.到达客户端以后,如果用这个对象来对应界面显示,那此时它的身份就转为VO

 



POJO :
plain ordinary java object 简单java对象
个人感觉POJO是最常见最多变的对象,是一个中间对象,也是我们最常打交道的对象。

一个POJO持久化以后就是PO
直接用它传递、传递过程中就是DTO
直接用来对应表示层就是VO

 


DAO:
data access object数据访问对象
这个大家最熟悉,和上面几个O区别最大,基本没有互相转化的可能性和必要.
主要用来封装对数据库的访问。通过它可以把POJO持久化为PO,用PO组装出来VO、DTO


      总结下我认为一个对象究竟是什么O要看具体环境,在不同的层、不同的应用场合,对象的身份也不一样,而且对象身份的转化也是很自然的。就像你对老婆来说就是老公,对父母来说就是子女。设计这些概念的初衷不是为了唬人而是为了更好的理解和处理各种逻辑,让大家能更好的去用面向对象的方式处理问题.

      大家千万不要陷入过度设计,大可不必为了设计而设计一定要在代码中区分各个对象。一句话技术是为应用服务的。

欢迎指正。



画了个图,感觉没有完全表达出自己的意思。。。。。谁帮忙完善下,最好能体现各个O在MVC中的位置
snap20070108.jpg 


转自:http://www.blogjava.net/vip01/archive/2007/01/08/92430.html

posted @ 2007-05-17 09:44 Coolfiry 阅读(329) | 评论 (0)编辑 收藏

I love English from then on.I study English hard form then on.I love it.It is very lovely.

posted @ 2006-11-26 14:13 Coolfiry 阅读(266) | 评论 (0)编辑 收藏

一、引言

  随着Internet的飞速发展,人们越来越依靠网络来 查找他们所需要的信息,但是,由于网上的信息源多不胜数,也就是我们经常所说的"Rich Data, Poor Information"。所以如何有效的去发现我们所需要的信息,就成了一个很关键的问题。为了解决这个问题,搜索引擎就随之诞生。

   现在在网上的搜索引擎也已经有很多,比较著名的有AltaVista, Yahoo, InfoSeek, Metacrawler, SavvySearch等等。国内也建立了很多的搜索引擎,比如:搜狐、新浪、北极星等等,当然由于它们建立的时间不长,在信息搜索的取全率和取准率上都 有待于改进和提高。

  Alta Vista是一个速度很快的搜索引擎,由于它强大的硬件配置,使它能够做及其复杂的查询。它主要是基于关键字进行查询,它漫游的领域有Web和 Usenet。支持布尔查询的"AND","OR"和"NOT",同时还加上最相近定位"NEAR",允许通配符和"向后"搜索(比如:你可以查找链接到 某一页的所有Web站点)。你可以决定是否对搜索的短语加上权值,在文档的什么部位去查找它们。能够进行短语查询而不是简单的单词查询的优点是很明显的, 比如,我们想要查找一个短语"to be or not to be",如果只是把它们分解成单词的话,这些单词都是属于Stop Word,这样这个查询就不会有任何结果,但是把它当作一个整体来查询,就很容易返回一些结果,比如关于哈姆雷特或者是莎士比亚等等的信息。系统对查询结 果所得到的网页的打分是根据在网页中所包含的你的搜索短语的多少,它们在文档的什么位置以及搜索短语在文档内部之间的距离来决定的。同时可以把得到的搜索 结果翻译成其他的语言。

  Exite是称为具有"智能"的搜索引擎,因为它建立了一个基于概念的索引。当然,它所谓的"智能"是基 于对概率统计的灵活应用。它能够同时进行基于概念和关键字的索引。它能够索引Web,Usenet和分类的广告。支持"AND","OR","NOT"等 布尔操作,同时也可以使用符号"+"和"-"。缺点是在返回的查询结果中没有指定网页的尺寸和格式。

  InfoSeek是一个简单 但是功能强大的索引,它的一个优点是有一个面向主题搜索的可扩展的分类。你可以把你的搜索短语和相似的分类目录的主题短语相互参照,而那些主题短语会自动 加到你的查询中去。使你的搜索有更好的主题相关性。同时它也支持对图象的查询。它能够漫游Web,Usenet,Usenet FAQs等等。不支持布尔操作,但是可以使用符号"+"和"-"(相当于"AND"和"NOT")

  Yahoo实际上不能称为是一 个搜索引擎站点,但是它提供了一个分层的主题索引,使你能够从一个通常的主题进入到一个特定的主题,Yahoo对Web进行了有效的组织和分类。比如你想 要建立一个网页,但是你不知道如何操作,为了在Yahoo上找到关于建立网页的信息,你可以先在Yahoo上选择一个主题:计算机和Internet,然 后在这个主题下,你可以发现一些子主题,比如:Web网页制作,CGI编程,JAVA,HTML,网页设计等,选择一个和你要找的相关的子主题,最终你就 可以得到和该子主题相关的所有的网页的链接。也就是说,如果你对要查找的内容属于哪个主题十分清楚的话,通过目录查询的方法要比一般的使用搜索引擎有更好 的准确率。你可以搜索Yahoo的索引,但是事实上,你并没有在搜索整个Web。但是Yahoo提供了选项使你可以同时搜索其他的搜索引擎,比如: Alta Vista。但是要注意的是Yahoo实际上只是对Web的一小部分进行了分类和组织,而且它的实效性也不是很好。

  搜索引擎的基本原理是通过网络机器人定期在web网页上爬行,然后发现新的网页,把它们取回来放到本地的数据库中,用户的查询请求可以通过查询本地的数据库来得到。如yahoo每天会找到大约500万个新的网页。

   搜索引擎的实现机制一般有两种,一种是通过手工方式对网页进行索引,比如yahoo的网页是通过手工分类的方式实现的,它的缺点是Web的覆盖率比较 低,同时不能保证最新的信息。查询匹配是通过用户写入的关键字和网页的描述和标题来进行匹配,而不是通过全文的匹配进行的。第二种是对网页进行自动的索 引,象AltaVista则是完全通过自动索引实现的。这种能实现自动的文档分类,实际上采用了信息提取的技术。但是在分类准确性上可能不如手工分类。

  搜索引擎一般都有一个Robot定期的访问一些站点,来检查这些站点的变化,同时查找新的站点。一般站点有一个robot.txt文 件用来说明服务器不希望Robot访问的区域,Robot 都必须遵守这个规定。如果是自动索引的话,Robot在得到页面以后,需要对该页面根据其内容进行索引,根据它的关键字的情况把它归到某一类中。页面的信 息是通过元数据的形式保存的,典型的元数据包括标题、IP地址、一个该页面的简要的介绍,关键字或者是索引短语、文件的大小和最后的更新的日期。尽管元数 据有一定的标准,但是很多站点都采用自己的模板。文档提取机制和索引策略对Web搜索引擎的有效性有很大的关系。高级的搜索选项一般包括:布尔方法或者是 短语匹配和自然语言处理。一个查询所产生的结果按照提取机制被分成不同的等级提交给用户。最相关的放在最前面。每一个提取出来的文档的元数据被显示给用 户。同时包括该文档所在的URL地址。

  另外有一些关于某一个主题的专门的引擎,它们只对某一个主题的内容进行搜索和处理,这样信息的取全率和精度相对就比较高。

   同时,有一类搜索引擎,它本身不用Robot去定期的采集网页。象SavvySearch 和 MetaCrawler是通过向多个搜索引擎同时发出询问并对结果进行综合返回给用户实现搜索功能。当然实际上象SavvySearch能够对各个搜索引 擎的功能进行分析和比较,根据不同的用户查询提交给不同的搜索引擎进行处理,当然用户自己也可以指定利用哪一个搜索引擎。

  一个优秀的搜索引擎必须处理以下几个问题:1 网页的分类2 自然语言的处理3 搜索策略的调度和协作 4 面向特定用户的搜索。所以很多搜索引擎不同程度的使用了一些人工智能的技术来解决这些方面的问题。

  二、网络Spider的实现描述

   现在有很多文章对Web引擎做了大量的介绍和分析,但是很少有对它们的实现做一个详细的描述,这里我们主要来介绍一个具有基本功能的Web引擎的实现。 本文,我们以类C++语言的形式来描述Web引擎如何采集网页并存放到数据库中的过程。同时描述了如何根据用户输入的关键字查询数据库并得到相关网页的过 程。

  2.1数据库结构

  首先,我们要建立一个数据库表用来存放我们得到的网页。这里一般需要建立如下的表:

  1.字典表的建立,事实上这里是用文档中有意义的单词和它们的出现频率来代表一个文档。

  该表(WordDictionaryTbl)主要要包括三个字段,主要是用来存放和一个网页相关的单词的情况

    url_id    对每一个URL的唯一的ID号
    word      该URL中的经过stem的单词
    intag    该单词在该网页中的出现的次数

  2.存储每一个URL信息的表

  该表(URLTbl)中主要的关键字段有:

  rec_id        每一条记录的唯一的ID号
  status    得到该URL内容的状态,比如HTTP_STATUS_TIMEOUT表示
            下载网页的最大允许超时
  url        URL的字符串名称
  content_type      内容的类型
  last_modified    最新的更改时间
  title            该URL的标题
  docsize          该URL的文件的尺寸
  last_index_time  最近一次索引的时间
  next_index_time  下一次索引的时间
  tag    对于网页,用来表示它的类型,比如:是text,或者是html,
                    或者是图片等等
  hops              得到文件时候的曾经失败的次数
  keywords          对于网页,和该网页相关的关键字
  description      对于网页,指网页的内容的描述
  lang              文档所使用的语言

   3.因为网页中有很多单词是一些介词和语气助词或者是非常常用的常用词,它们本身没有多少意义。比如:英语中的about,in,at,we,this 等等。中文中的如"和","一起","关于"等等。我们统一的把它们称为停止词(stop word)。所以我们要建立一个表,来包括所有这些停止词。该表(StopWordTbl)主要有两个字段。
word char(32)    表示那些停止词
lang char(2)      表示所使用的语言

  4.我们要建立一个关于robot的表,我们在前面说过,所有的网站一般都有一个robot.txt文件用来表示网络上的robot可以访问的权限。该表(RobotTbl)主要有以下字段。
    hostinfo          Web站点主机的信息
    path              不允许robot访问的目录

  5.建立我们需要屏蔽的那些网页(比如一些内容不健康的或者没有必要去搜索的站点)的一张表(ForbiddenWWWTbl),主要的字段就是网页的URL。

   6.另外我们需要建立一个我们所要得到的文件类型的表(FileTypeTbl),比如,对于一个简单的Web搜索引擎,我们可能只需要得到后缀为. html,htm,.shtml和txt的类型文件。其他的我们只是简单的忽略它们。主要的字段就是文件的类型和说明。

  其中关于停止词的表的内容是我们要实现要根据各种语言的统计结果,把那些意义不大的单词放进去。关于文档单词、URL和Robot的表的内容都是在获取Web网页的时候动态增加记录的。

  2.2 具体网页获取算法描述

  具体的网页的获取步骤是这样的:

   我们可以设定我们的搜索程序最大可以开的线程的数目,然后这些线程可以同时在网上进行搜索,它们根据数据库中已有的关于网页的信息,找出那些需要更新的 网页(如何判断哪些网页需要更新是一个值得研究的过程,现在有很多启发式和智能的算法,基本上是基于统计规律进行建模。最简单的当然是设定一个时间范围, 在某个时间范围以前的网页被重新去搜索一遍),然后判断那些网页是否在屏蔽表中,如果是的话,就从关于URL的表中删除该条记录。否则,我们就到相应的 WWW站点去得到URL指定的文件(这里需要注意的是根据不同的URL的特点,需要使用不同的协议,比如对于FTP站点要采用FTP协议,对于HTTP站 点要采用HTTP协议,新闻站点要采用NNTP协议等等)事实上,我们先得到关于该网页的头信息,如果该网页的最新修改时间和我们最近提取的时间是一样的 话,表示该网页内容没有任何更新,则我们就不必去得到它的内容,只需要修改最近一次更新它的时间为当前的时间就可以了。如果该网页最近做了修改,我们就要 得到该网页,并对它的内容进行分析,主要要包括和它相关的链接,把它们加到相应的数据库中,同时判断网页所包含的各种其他的文件,如文本文件、图形文件、 声音文件和其他多媒体文件是否是我们所需要的文件,如果是的话,就把它加到我们响应的数据库中。同时要根据网页的内容提取所有的有意义的单词和它们的出现 的次数,放到相应的数据库中。为了更好的描述这个过程,我们来看跟这个过程相关的主要的几个对象和数据结构。对象主要是针对三个层次来讲的。第一层是针对 WWW服务器,第二层是针对每一个页面,第三层是针对每一个页面的全文的索引。

  2.3 和实现相关的主要类对象和功能描述下面的结构是针对一个站点来说的。

    Class  CServer {
    主要的属性有:
    char *url;            //WWW站点的URL名称
    char *proxy;          //使用的代理的名称
    char *basic_auth;      //进行基本的HTTP认证
    int  proxy_port;      //代理的端口号
    int  period;          //再次索引的周期
    int  net_errors;      //网络连接不通的次数
    int  max_net_errors;  //可以允许的最大的网络错误
    int  read_timeout;    //下载文件允许的最大的延迟
    int  maxhops;          //表示URL可以最大跳转的深度
    int  userobots;        //是否遵守robot.txt中的约定
    int  bodyweight;  // 在< body >....< /body >之间的单词的权重
    int  titleweight; // 在< title >....< /title >之间的单词的权重
    int  urlweight;  // 在文档的URL中的单词的权重
    int descweight;//在    < META
NAME="Description"        Content="..." >之间单词的权重
    int  keywordweight; //在< META NAME="Keywords" Content="..." >
  之间的单词的权重

  主要方法有:
FindServer();//用来查找该服务器是否存在并可以连接
FillDefaultAttribute() //用来针对所有的WWW服务器填写默认的属};

以上的对象中的成员变量是和一个站点相关的参数的设置,我们对所有的站点有一个默认的设置,但是可以对某些站点做一些特殊的设置。这些设置可以在配置文件中设定。
  下面是关于文档的结构的主要的数据成员:

Class CNetDocument
    主要属性有:
    int    url_id; //该URL的ID号
    int    status;  //获取该文档时候的状态
    int    size;  //文档的尺寸
int    tag;  //和该文档相关的标签,表示该文档是
HTML,TEXT或者是其他类型
    int    hops;    //URL跳转的次数
    char    *url; //和该文档相关的URL的名称
    char    *content_type;      //该内容的类型
    char    *last_modified;    //最近一次的更新时间
    char    *title;            //该文档的标题
    char    *last_index_time;  //上次索引的时间
    char    *next_index_time;  //下次索引的时间
    char    *keywords;          //该文档中的关键字
    char    *description;      //该文档的描述

  主要方法有:
  FillDocInfo(…) //根据数据库,得到该文档相关信息
  AddHerf(…)    //加入网页中存在的新的链接的网址
  DeleteURL(…)  //删除一个存在的网址
  CanGetThisURL(…) //根据配置决定是否去得到该网页
  //下面三个方法是根据不同的URL,用不同的协议去获得文档
  NNTPGet(…)     
  FTPGet(….)
  HTTPGet(….)
  ParseHead(…)  //如果是HTTP协议得到的话,分析头信息
  ParseMainBody(…)    //对获得的文档的主体进行分析
  ServerResponseType (….)  //得到服务器端的响应消息
  UpdateURLDB(….)  //更新的数据入库
} ;

  事实上,我们在要提取一个网页的时候,都要建立一个CNetDocument对象,然后再对这个网页进行分析的时候,把相关的内容放到这个CNetDocument的成员变量里面。下面是关于页面全文索引的结构的主要数据成员:
Class CIndexer {
主要属性有:
  char    *url;      //我们要处理的文档相关的URL的名称
  int mwords;      //  我们事先设定的一个网页的最大的单词数目
    int nwords;          // 实际的得到的单词的数目
    int swords;          // 我们已经排序的单词的数目
    WORD *Word;      //所有单词的内容
    char *buf;      //我们为文档所分配的空间
主要方法有:
  InitIndexer(…)    //进行初始设置和分配
  ParseGetFile(…)  //对得到的网页进行全文索引
  AddWord(…)    //把网页的可以索引的单词加到Word数组中去
  InToDB(….)    //关于网页全文索引的信息入库
};

  进行网页提取前,我们要建立一个CIndexer对象,它主要是用来对网页进行全文的索引。一般来说我们只对两种类型的URL进行全文索引,一个是text/html,另外一个是text/plain。其中WORD的数据结构如下:
        typedef struct word_struct {
    int count;  //该单词出现的次数
    int code;  //该单词的正常的形式,
比如单词可能为 encouraging,它的正常的形式应该为
encourage,这其实是一种对单词的stem。
即我们只取单词的主干部分。
    char *word;  //该单词的内容
} WORD;

  以下的结构是和网页中的一些链接的对象相关的一个数据结构
    typedef struct href_struct {
    char *href;    //该链接的名称
    int hops;      //发生的跳转次数
    int stored;    //是否已经存储到数据库中
} HREF;
 

  所有需要更新的和新产生的URL都被放到这个结构中,当它的数量超过一定的范围以后,被一次性的存入数据库。
  关于URL的一个数据结构如下:

typedef struct url {
char *schema; //表示该URL是通过什么协议得到的,比如HTTP,
              FTP,NNTP等。
char *specific;    //主机的名称加上路径
char *hostinfo;    //主机的名称加上相关的协议端口
char *hostname;    //主机的名称
char *path;        //在主机的具体的路径
char *filename;    //文件的名称
char *anchor;      //相关的anchor
int  port;        //协议相关的端口
} URL;

  这是针对URL的一些相关的属性的描述的一个数据结构。事实上在数据库中,我们存储的只是对网页的描述和对一些文本和HTML页面的关键词的索引信息。我们并不存储网页的实际的内容。

  三、用户查询实现描述

  关于对用户提交的查询请求的实现分析:

  用户想要查询某一方面的信息一般都是通过提供和该领域相关的几个关键字来进行的。

  我们来看一下关于用户查询的相关的数据结构和类:

  下面是一个关于单词和它的权值的基本结构:

  typedef struct word_weight_pair
    {
      char word[WORD_LEN];
      int weight;
    }word_weight_pair;
   

  下面的类主要是用来对用户的查询进行处理和分析:
    Class CUserQuery
    {
char m_UserQuery[MAX_QUERYLEN];  //用户的查询表达式
CPtrArray word_weight_col;
//是关于结构word_weight_pair的动态数组
int m_maxReturnSum;  //用户希望返回的最多的网页数
int search_mode;
CObArray m_returnDoc;  //是关于CNetDocument对象的一个动态数组
NormalizeWord(char* OneWord);  //对单词进行归整化,即Stem.
Find(char* odbcName);  //进行数据库查找和匹配
};

  系统实现的基本的步骤如下:

  1.对用户输入的查询表达式进行分析。事实上,我们在前面的Spider搜索过程中对文档的表示是通过关键字形式描述的,每一个文档可以表示为这样的一个集合

    其中 ::=< 单词或短语名称 >< 单词或短语的权值 >

  实际上就是采用矢量空间的表示方法来表示的文档。

   我们对用户输入的查询表达式也采用矢量空间的表示方法。我们认为用户输入的关键字的顺序代表了它的重要性的程度,所以对于位置靠前的单词有相对比较高的 优先级,同时我们对所有的内容以短语或者是单词为最小原子,进行Stem操作,即象前面所提到的:比如单词Encouraging就转化成 Encourage的格式。然后去掉那些Stop Word,比如is ,as等等的单词,这些单词存放在StopWordTbl表中。 然后把所有归整化后的内容放入动态数组word_weight_col中去。

  2.对于动态数组word_weight_col中 的每一个元素,即结构word_weight_pair(包括单词和该单词的权重),我们从表WordDictionaryTbl中可以找到和这些单词相 关的记录,这些记录应该是包括了所有的在word_weight_col中的单词。

  进行网页是否和查询相匹配的计算。匹配计算的 过程如下:首先我们对所有的记录按URL地址进行排序。因为可能好几条记录对应的是一个URL,然后对每一个网页进行打分,每一条记录的单词权值为 INITSCORE*WEIGHT+(TOTALTIMES-1)*WEIGHT* INCREMENT。其中INITSCORE为每一个单词的基准分数,TOTALTIMES为该单词在网页中的出现的次数,WEIGHT是该单词在不同的 内容段出现有不同的权值(比如在KEYWORD段,或者是标题段,或者是内容段等等)。INCREMENT是该单词每多出现一次所增加的分数。

  3.根据用户指定的m_maxReturnSum,显示匹配程度最高的前m_maxReturnSum页。

  四、结束语

   我们利用上面所讨论的机制,在WINDOWS NT操作系统下,用VC++和SQL SERVER实现了一个Web搜索引擎的网页搜集过程。在建立了一个基本的搜索引擎的框架以后,我们可以基于这个框架,实现一些我们自己设计的算法,比如 如何更好的进行Spider的调度,如何更好的进行文档的归类,如何更好的理解用户的查询,用来使Web搜索引擎具有更好的智能性和个性化的特点。

posted @ 2006-11-11 21:37 Coolfiry 阅读(462) | 评论 (0)编辑 收藏

     摘要: 1.   目标 使用 apache 和 tomcat 配置一个可以应用的 web 网站,要达到以下要求: 1、  Apache 做为 HttpServer ,后面连接多个 tomcat...  阅读全文

posted @ 2006-11-06 17:20 Coolfiry 阅读(717) | 评论 (0)编辑 收藏

JDBC学习笔记
2004-9-13     星期一     小雨

l. 连接到数据库的方法
答:1) ODBC(Open Database Connectivity)
       一个以C语言为基础访问SQL为基础数据库引擎的接口,它提供了一致的接口用于和数据库沟通以及访问数据。
    2) JDBC
       Java版本的ODBC

2. JDBC应用编程接口
答:JDBC应用编程接口是:
    1) 标准的数据访问接口,可以连到不同的数据库;
    2) JAVA编程语言的一组类和接口。
    JDBC应用编程接口能够:
    1) 连接到数据库;
    2) 发SQL查询字符串到数据库;
    3) 处理结果。
    JDBC应用编程接口有二个主要的部分:
    1) JAVA应用程序开发接口面向JAVA应用程序开发者;
    2) JDBC驱动程序开发接口
    
3. JDBC Driver
答:1) 一大堆实现了JDBC类和接口的类;
    2) 提供了一个实现java.sql.Driver接口的类。

4. JDBC Driver的四种类型
答:1) JDBC-ODBC桥
    由ODBC驱动提供JDBC访问
    2) 本地API
    部分Java driver把JDBC调用转化成本地的客户端API
    3) JDBC-net
    纯的Java driver,将JDBC调用转入DBMS,与网络协议无关。然后通过服务器将调用转为DBMS协议。
    4) 本地协议
    纯的java driver,将JDBC调用直接转为DBMS使用的网络协议

5. JDBC开发者接口
答:1) java.sql--java 2平台下JDBC的主要功能,标准版(J2SE)
    2) javax.sql--java 2平台下JDBC增强功能,企业版(J2EE)

6. 使用URL确认数据库
答:我们使用URL来确定一个数据库(正确的Driver,正确的主机,正确的协议,正确的协议,正确的用户名和密码);
    语法:protocol:subprotocol:subname
    范例:jdbc:db2:MyTest
          jdbc:db2://localhost:6789/MyTest

7. javax.sql包JDBC2.0的增强功能
答:1) 数据源接口;
    2) 连接池;
    3) 分布式交易;
    4) 行集;

8. 创建一个基本的JDBC应用
答:1) 步骤一:注册一个driver;
    2) 步骤二:建立一个到数据库的连接;
    3) 步骤三:创建一个statement;
    4) 步骤四:执行SQL语句;
    5) 步骤五:处理结果;
    6) 步骤六:关闭JDBC对象

9. 注册一个Driver(步骤一)
答:1) driver被用于连接到数据库;
    2) JDBC应用编程接口使用第一个能成功连接到给定URL的driver;
    3) 在同一时间可以装载多个driver

10.注册一个driver的方法:
答:1) 使用类loader(装载;实例化;注册入DriverManager)
       a. Class.forName("Com.ibm.db2.jdbc.app.DB2Driver");
       b. Class.forName("Com.ibm.db2.jdbc.net.DB2Driver");
       c. Class.forName("Com.microsoft.jdbc.sqlServer.SQLServerDriver);
       d. Class.forName("oracl.jdbc.driver.OracleDriver");
       e. Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");
    2) 实例化一个Driver
       a. Driver drv = new COM.cloudscape.core.RmiJdbcDriver();

2004-9-14     星期二     阴

1. 建立一个到数据库的连接(步骤二)
答:DriverManager调用getConnection(urlString)方法,实际上调用的是driver的connect(urlString)方法;
    1) 当一个driver肯定地对应到一个数据库URL,DriverManager建立一个连接;
    2) 当没有driver匹配,返回null然后下一个driver被检验;
    3) 假如没有建立连接,抛出一个SQLExcepiton异常

2. 经常使用的一些JDBC URL
答:1) JDBC-ODBC: jdbc:odbc:<DB>
    2) Oracle: jdbc:oracle:oci:@<sid> or jdbc:oracle:thin:@<SID>
    3) Weblogic MS-SQL: jdbc:weblogic:mssqlserver4:<DB>@<HOST>:<PORT>
    4) DB2: jdbc:db2:MyTest or jdbc.db2://localhost:6789/MyTest(需要用户名和密码)

3. Driver连接方法
答:1) 创建一个到指定Driver实例的直接调用;
    2) 避免一般访问的问题
       Driver drv = new COM.ibm.db2.jdbc.app.DB2Driver();
       Connection con = null;
       try {con = drv.connect("jdbc:db2:MyTest",new Properties())}
       catch(SQLException e){}

4. 创建一个Statement(步骤三)
答:1) Statement的三个接口:
       a. Statement;
       b. PreparedStatement(继承自Statement);
       c. CallableStatement(继承自PreparedStatement);
    2) 使用方法Connection.createStatement()得到一个Statement对象

5. PreparedStatement对象
答:1) 调用ProparedStatement比statement更为高效;
    2) 继承自Statement;
    3) 语法:PreparedStatement pstm = connection.prepareStatement(sqlString);

6. CallableStatement对象
答:1) 通过CallableStatement调用数据库中的存储过程;
    2) 继承自PreparedStatement;
    3) CallableStatement cstm = connection.prepareCall("{call return_student[?,?]}");
       cstm.setString(1,"8623034");
       cstm.registerOutparameter(2, Types.REAL);
       cstm.execute();
       float gpa = cstm.getFloat(2);

7. Statement接口的比较
答:             | Statement           | PreparedStatement         |  CallableStatement
    ------------------------------------------------------------------------------
    写代码位置   |   客户端            | 客户端                    |  服务器端
    ------------------------------------------------------------------------------
    写代码位置   |   客户端            | 服务器端                  |  服务器端
    ------------------------------------------------------------------------------
    编写代码技术 |Java,SQL操作        |Java,SQL操作              |  数据库的程序语言,如PL/SQL
    ------------------------------------------------------------------------------
    可配置性     |   高                |第一次高,以后低           |  低
    ------------------------------------------------------------------------------
    可移植性     |   高                |假设支持PreparedStatement的话高    
    ------------------------------------------------------------------------------
    传输效率     |   低                |第一次低,以后高           |  高

8. 执行SQL Statement(步骤四)
答:通过接口方法将SQL语句传输至?认的数据库连接,返回结果可能是一个数据表,可以通过java.sql.ResultSet访问。
    1) Statement的接口方法:
    a. executeQuery(sqlString): 执行给定的SQL声明,返回一个结果集(ResultSet)对象;
    b. executeUpdate(sqlString): 执行给定的SQL声明,可以是INSERT、UPDATE或DELETE声明,也可以是SQL DDL声明;
    c. execute(sqlString): 执行给定的SQL声明。

9. 处理结果(步骤五)
答:1) 使用结果集(ResultSet)对象的访问方法获取数据;
       a. next():下一个记录
       b. first():第一个记录
       c. last():最后一个记录
       d. previous():上一个记录
    2) 通过字段名或索引取得数据
    3) 结果集保持了一个指向了当前行的指针,初始化位置为第一个记录前。

10. 关闭JDBC对象(步骤六)
答:1) 首先关闭记录集;
    2) 其次关闭声明;
    3) 最后关闭连接对象。

11. 数据表和类对应的三种关系:
答:1) 一个表对应一个类;
    2) 一个表对应相关类;
    3) 一个表对应整个类关系层

12. 类间关系的几种表设计:
答:1) 多对一,
    2) 一对一: 
    3) 一对多:
    4) 多对多:

13. SQL数据类型及其相应的Java数据类型
答:SQL数据类型                     Java数据类型              说明
    ------------------------------------------------------------------
    INTEGER或者INT                  int                     通常是个32位整数
    SMALLINT                        short                   通常是个16位整数
    NUMBER(m,n) DECIMAL(m,n)        Java.sql.Numeric        合计位数是m的定点十进制数,小数后面有n位数
    DEC(m,n)                        Java.sql.Numeric        合计位数是m的定点十进制数,小数后面有n位数
    FLOAT(n)                        double                  运算精度为n位二进制数的浮点数
    REAL                            float                   通常是32位浮点数
    DOUBLE                          double                  通常是64位浮点数
    CHARACTER(n)或CHAR(n)           String                  长度为n的固定长度字符串
    VARCHAR(n)                      String                  最大长度为n的可变长度字符串
    BOOLEAN                         boolean                 布尔值
    DATE                            Java.sql.Date           根据具体设备而实现的日历日期
    TIME                            Java.sql.Time           根据具体设备而实现的时戳
    TIMESTAMP                       Java.sql.Timestamp      根据具体设备而实现的当日日期和时间
    BLOB                            Java.sql.Blob           二进制大型对象
    CLOB                            Java.sql.Clob           字符大型对象
    ARRAY                           Java.sql.Array
    

2004-9-15     星期三      阴

1. 元数据
答:关于数据的信息,例如类型或者容量。通过JDBC API可以访问:
    1) 数据库元数据;
       a. 使用connection.getMetadata方法返回DataMetaData引用
       b. 能够使用isReadOnly此类方法获取信息
    2) 结果集元数据;
       a. 使用ResultSet.getMetadata方法返回ResultSetMetaData引用
       b. 能够使用getColumnCount此类方法获取信息

2. 事务处理
答:1) 一系列的动作作为一个不可分的操作;
    2) JDBC API中使用事务处理步骤:
       a. 用false作为参数调用setAutoCommit方法;
       b. 执行一或多个关于数据库的操作;
       c. 调用commit方法完成改变;
       d. 恢复上次提交后的改变,调用rollback方法.

       try
       {
          con.setAutoCommit(false);
          Statement stm = con.createStatement();
          stm.executeUpdate("insert into student(name, age, gpa) values('gzhu', 30, 4.8)");
          stm.commit();
       }
       catch(SQLException e)
       {
          try
          {
             con.rollback();
          }
          catch(Exception e)
          {
          }
       }

3. 并发控制
答:1) 设置隔离级别方法:setTransactionIsolation
    2) 隔离级别静态变量
       a. TRANSACTION_NONE:只读的数据字典;
       b. TRANSACTION_READ_UNCOMMITTED:只读未提交数据;
       c. TRANSACTION_READ_COMMITTED:只读未提交数据;
       d. TRANSACTION_REPEATABLE_READ:重复读取数据;
       e. TRANSACTION_SERIALIZABLE:无论做什么操作都不许别人动。
    3) 示例:con.setTransactionIsolation(Connection.TRANSACTION_READ_UNCOMMITTED);

4. JDBC 2.0 应用程序编程接口增强功能
答:1) ResultSet增强:
       a. 可以回卷;
       b. 可以修改;
       设置示例:Statement stm = con.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
    2) Statement增强了批量修改能力(batch updates);
    3) 更高级的数据类型(例:Struct)。

5. JDBC 2.0标准扩展
答:1) JNDI(Java Naming and Directory Interface): 解决离散状态下Object的查找;
    2) 连接池:在内存中保存了一个数据库连接,不需要注册驱动器,提高性能的重要方法。

posted @ 2006-11-03 10:14 Coolfiry 阅读(230) | 评论 (0)编辑 收藏

问题引入:
在实习过程中发现了一个以前一直默认的错误,同样char *c = "abc"和char c[]="abc",前者改变其内

容程序是会崩溃的,而后者完全正确。
程序演示:
测试环境Devc++
代码
#include <iostream>
using namespace std;

main()
{
   char *c1 = "abc";
   char c2[] = "abc";
   char *c3 = ( char* )malloc(3);
   c3 = "abc";
   printf("%d %d %s\n",&c1,c1,c1);
   printf("%d %d %s\n",&c2,c2,c2);
   printf("%d %d %s\n",&c3,c3,c3);
   getchar();
}  
运行结果
2293628 4199056 abc
2293624 2293624 abc
2293620 4199056 abc

参考资料:
首先要搞清楚编译程序占用的内存的分区形式:
一、预备知识—程序的内存分配
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于

数据结构中的栈。
2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据

结构中的堆是两回事,分配方式倒是类似于链表,呵呵。
3、全局区(静态区)(static)—全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态

变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统

释放。
4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放。
5、程序代码区
这是一个前辈写的,非常详细
//main.cpp
  int a=0;    //全局初始化区
  char *p1;   //全局未初始化区
  main()
  {
   int b;栈
   char s[]="abc";   //栈
   char *p2;         //栈
   char *p3="123456";   //123456\0在常量区,p3在栈上。
   static int c=0;   //全局(静态)初始化区
   p1 = (char*)malloc(10);
   p2 = (char*)malloc(20);   //分配得来得10和20字节的区域就在堆区。
   strcpy(p1,"123456");   //123456\0放在常量区,编译器可能会将它与p3所向"123456"优化成一个

地方。
}
二、堆和栈的理论知识
2.1申请方式
stack:
由系统自动分配。例如,声明在函数中一个局部变量int b;系统自动在栈中为b开辟空间
heap:
需要程序员自己申请,并指明大小,在c中malloc函数
如p1=(char*)malloc(10);
在C++中用new运算符
如p2=(char*)malloc(10);
但是注意p1、p2本身是在栈中的。
2.2
申请后系统的响应
栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,
会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将

该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大

小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正

好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
2.3申请大小的限制
栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地

址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译

时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间

较小。
堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地

址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的

虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。
2.4申请效率的比较:
栈:由系统自动分配,速度较快。但程序员是无法控制的。
堆:是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.
另外,在WINDOWS下,最好的方式是用Virtual Alloc分配内存,他不是在堆,也不是在栈,而是直接在进

程的地址空间中保留一块内存,虽然用起来最不方便。但是速度快,也最灵活。
2.5堆和栈中的存储内容
栈:在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的

地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变

量。注意静态变量是不入栈的。
当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主

函数中的下一条指令,程序由该点继续运行。
堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。
2.6存取效率的比较
char s1[]="aaaaaaaaaaaaaaa";
char *s2="bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的;
而bbbbbbbbbbb是在编译时就确定的;
但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。
比如:
#include
voidmain()
{
char a=1;
char c[]="1234567890";
char *p="1234567890";
a = c[1];
a = p[1];
return;
}
对应的汇编代码
10:a=c[1];
004010678A4DF1movcl,byteptr[ebp-0Fh]
0040106A884DFCmovbyteptr[ebp-4],cl
11:a=p[1];
0040106D8B55ECmovedx,dwordptr[ebp-14h]
004010708A4201moval,byteptr[edx+1]
004010738845FCmovbyteptr[ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指针值读到edx中,在根据

edx读取字符,显然慢了。
2.7小结:
堆和栈的区别可以用如下的比喻来看出:
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会

切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。

自我总结:
char *c1 = "abc";实际上先是在文字常量区分配了一块内存放"abc",然后在栈上分配一地址给c1并指向

这块地址,然后改变常量"abc"自然会崩溃

然而char c2[] = "abc",实际上abc分配内存的地方和上者并不一样,可以从
4199056
2293624 看出,完全是两块地方,推断4199056处于常量区,而2293624处于栈区

2293628
2293624
2293620 这段输出看出三个指针分配的区域为栈区,而且是从高地址到低地址

2293620 4199056 abc 看出编译器将c3优化指向常量区的"abc"


继续思考:
代码:
#include <iostream>
using namespace std;

main()
{
   char *c1 = "abc";
   char c2[] = "abc";
   char *c3 = ( char* )malloc(3);
   //  *c3 = "abc" //error
   strcpy(c3,"abc");
   c3[0] = 'g';
   printf("%d %d %s\n",&c1,c1,c1);
   printf("%d %d %s\n",&c2,c2,c2);
   printf("%d %d %s\n",&c3,c3,c3);
   getchar();
}  
输出:
2293628 4199056 abc
2293624 2293624 abc
2293620 4012976 gbc
写成注释那样,后面改动就会崩溃
可见strcpy(c3,"abc");abc是另一块地方分配的,而且可以改变,和上面的参考文档说法有些不一定,

而且我不能断定4012976是哪个区的,可能要通过算区的长度,希望高人继续深入解释,谢谢
 

posted @ 2006-10-16 19:06 Coolfiry 阅读(1135) | 评论 (2)编辑 收藏

仅列出标题
共4页: 上一页 1 2 3 4 下一页