Category: 性能

翻译:High Performance Web Sites(5)-Chapter 3

《High Performance Web Sites》 :Chapter 3

法则3:增加Expires Header  Add an Expires Header 

在您设计网页时,快速的响应时间不应该是你唯一要考虑的,如果仅仅是这样,那我们采用法则1,把我们的页面设计成一个极端的网页:没有任何图片,script,样式表。我们都明白,图片、script、样式表这些组件可以增强用户体验,虽然它们会给页面带来较长的载入时间。你幸运了,在这一章介绍的法则3,我就要向你介绍如何最大限度地利用浏览器的缓存来使这些页面组件更高效的为我们的页面服务。

现在的网页所包含的组件越来越丰富,java applet去了,Flash来了,script也不可缺少,随着div的大潮,css样式表也少不了…… 所以用户若第一次访问您的网页,则可能会产生多个HTTP请求;但如果您在请求返回中使用Expires头信息,则可以缓存这些组件,避免在随后的访问中产生不必要的HTTP请求,Expires头信息最常用于图片,其实它适合应用在所有的组件中,如scripts,样式表和Flash。但大多数当今的热门网站目前并没有这样做。在这一章节中我会提及如何让这些网站可以更快。在使用Header头信息时,也可能会有一定的额外开销,这点会在 “改变文件名”段落中再详谈.

Expires Header

浏览器使用缓存来减少HTTP请求数和减少HTTP的响应数据量,以达到更快的加载页面。web服务器通过Expries header来告诉web客户端(John:主要是浏览器)当前返回的组件在我指定的时间以前都是可用的,你(浏览器)可以留着下次备用(John:有点像我们在超市买牛奶时,随包装袋上返回的过期日期)。Expries header 在HTTP规范中描述为 “the date/time after which the response is considered stale.”,它附带在HTTP的响应中返回给客户端。

如上图,这是一个典型的expries header ,它告诉浏览器,直到2010年4月15日这个请示的返回都不会变化。如果这个头信息是随着一个图片返回的,那浏览器就会缓存这个图片,以为其后的页面浏览直接使用,以减少一个HTTP请示。 

Max-Age and mod_expires

在我解释缓存是如何更好的提升性能之前,有必要介绍一下与Expries header相关的几个头信息。Cache-Control header是在HTTP/1.1中被引入以弥补Expries header的不足。因为Expries header使用的是一个具体的日期,它就要求服务器与客户端之间要有严格的时钟检查,并且当过期日期到来之后,服务器端还必须配置一个新日期。

相反,Cache-Control 使用max-age来指定一个时间段来标识一个组件能使用多长时间。这个max-age是以秒为单位来描述的(John:有点保质期的概念)。如果在这个保质期内,这个组件再被请求,浏览器就直接使用缓存里的就行了。下面就是一个返回10年保质期的头信息。

使用Cache-Control虽然弥补了Expires的不足,但我们仍然还是得使用 Expires header以兼容那些不支持HTTP/1.1的浏览器(尽管这些流量可能还不到1%)。所以我们一般同时使用Expires和Cache-Control max-age,按HTTP规范这时会以max-age的时间为优先考虑,所以我们还是避免不了服务器与客户端之间的时钟检查和服务器端的新日期配置。幸运的是我们有Apache的 mod_expires模块,能让我们像设置max-age那样来配置Expires header,它使用ExpiresDefault来设置一个时间段,如下,为图片,scripts和样式表设置10年的有效期: 

<FilesMatch “\.(gif|jpg|js|css)$”>
ExpiresDefault “access plus 10 years”
</FilesMatch>
这个时间可以是年,月,周,天,小时,分钟甚至是秒。使用了这个模块,所有的响应返回中就会同时带着 Expires header 和 Cache-Control max-age 头信息:
其中Expires header所携带的过期时间具体是多少,则依赖于每个客户端什么时间发出的请求,在上面的例子中,始终是10年。这样就避免了我们每次在到期后都要重新设置服务器,mod_expires会搞定一切。图3-1是对10大网站使用这些headr的一个调查。有7家使用了这些header,其中有5家同时使用了
Expires 和 Cache-Control max-age(John:推荐)。各有2家分别只使用 Expires 或Cache-Control max-age。很遗憾有3家什么也没使用。 

 

Empty Cache vs. Primed Cache

使用Expires  header只会影响已经访问过的页面和组件,当用户第一次访问您的页面时无法避免的会有比较多的HTTP请求数,因为这时浏览器的缓存里是空的。所以如果您的网站能吸引用户访问更多的页面, 并经常在此停留,我们所做的缓存工作才有效果。

不仅仅是图片 More Than Just Images

一般Expires header常用于图片,其实这并不是最佳实践。Expires header应该应用于所有那些不经常变动的组件,script,样式表或Flash组件。

在理想情况下,所有组件都在一个页面内,并且都有一个未过期的Expries header,而随后浏览的页面只一个对HTML源文件的HTTP请求,其余的组件都在浏览器的缓存中直接提供,这时的响应时间会提高50%甚至更多。

我调查了美国的10大网站,并记录了其中有多少图片,script和样式表是设置了至少30天有效期的Expires 或是 Cache-Control max-age header,如表3-2所示,情况并不是太好,图中所列的是被缓存至少30天的组件数,分母是该网站上的所有的该类型组件数,分子是被加了过期header的组件数。
• 有5家网站把大多数图片的缓存有效期设为30天以上.
• 有4家网站把大多数样式表的缓存有效期设为30天以上.
• 有2家网站把大多数script的缓存有效期设为30天以上.

从上图的百分比中俺发现有74.7%的组件没有被缓存或是有效期低于30天。一种解释就是这些组件因为业务关系而不应该被缓存,如新闻网站CNN.com就是个例子,138张图片中没有一张被缓存,这是因为很多新闻照片要被不断更新而不必缓存在用户端,所以这时更适合用Last-Modified heade,来通过组件的最后修改时间判断是否要读取新数据。 

表3-2的最后一项,显示了未被缓存的组件的最后修改时间的中分线,就CNN.com来说有一半的未缓存组件的最后修改时间是在227天前了,很显然这些组件是应该被缓存的。

这种情况也曾发生在Yahoo!,在过去,Yahoo!并没有缓存script,样式表和一些图片,是因为我们认为这样是经常变化的,用户有必要每次访问时都去请求一次以获取最新的。可问题是,在实际应用中,这些组件并不是我们想像中的那样要经常变化更新,我意识到应该把它们缓存来提升用户体验。后来,Yahoo!选择了去缓存它们,哪怕会带来一些额外的开发花销,这就是我马上要谈到的Revving Filenames。

改变文件名 Revving Filenames

如果我们已经为组件设置了缓存,可当这些组件又需要更新时,用户如何才到得到最新的组件呢?由我们前面介绍的Expires 或是 Cache-Control max-age header 都会让浏览器不检查任何改变,直接从本地硬盘中读取缓存,除非是过了有效期。所以我们能做的,就是在HTML页面中改变这个组件的文件名。在Mark Nottingham的文章”Caching Tutorial for Web Authors and Webmasters“谈到这个问题:

最优的方案还是改变它们的链接;只有这样,用户才能从服务器上获取更新。(The most effective solution is to change any links to them; that way, completely new representations will be loaded fresh from the origin server.)

说白了,还是要改变文件名。在已有的页面中改变文件名可能是件头疼的烦事,但是,不得不这样,如果您使用的是PHP,Perl等动态的页面,不妨利用一个变量为所有的组件命名,这样换起文件名来比较省事。在Yahoo!,我们是在组件名后面跟上版本号(如,yahoo_2.0.6.js),把这个版本号做为一个变量写在程序中,真的很省事。


举例 Examples

下面的两个链接,包包含有相同的组件:6个图片,3个script和1个样式表。第一个链接没有任何Expires header,而第二个链接,全有。
No Expires
http://stevesouders.com/hpws/expiresoff.php
Far Future Expires
http://stevesouders.com/hpws/expireson.php
我在900Kbps的DSL下测试,加了过期头设置的链接页面访问时间会减少600~260毫秒,能提升57%,如果页面的组件再多一点,这个百分比还会更高。

要说明一点,并不是说没有加过期头的组件就不会被浏览器缓存,它们也会被缓存,还记得我在Chapter B中介绍的有条件的GET请求吗,只不过,会多一个HTTP请求到服务器端以询问这个组件是否有效,如果这个组件的最后修改时间和以前一下,则直接使用缓存中的版本,HTTP返回中将不带这个组件的具体数据了。

为您页面上的组件贴上保质期吧,再加有有条件的GET请求,带来的会是减少近一半的HTTP请求数还有不必要的数据传输。

 

翻译:High Performance Web Sites(4)-Chapter 2

《High Performance Web Sites》 :Chapter 2

法则 2: 使用CDN 内容分发网络  Use a Content Delivery Network

用户的网络带宽在逐年增加,但用户访问您web服务器的快慢仍受着地域的限制(John:最典型的例子就是我们大陆的南北电信互通问题)。Web创业者往往都会在某一地域的机房放置自己的服务器,但一旦他们渡过艰难的初创阶段,开始要面对涌入的大量用户时,他们都要面对这样的现实:即一个地域机房里的那一台服务器已经不足于应付这种大访问了,是时候在多个分散地域(城市结点)上部署更多的内容服务器。

如何迈出第一步呢?要实施地理上的内容分布,切勿急着尝试以分布式的系统构架去重新设计您的web应用。如果依赖于应用系统的分布,那您的重构工作可能会是十分艰巨,如要处理会话状态的同步和在多个地域的数据库之间处理数据一致性等复杂问题(John:如果您进行的是类似银行级的用户应用,则不在此讨论之列)。您应该优先考虑缩短用户与您web内容之间的地域距离。

还记得我们在前面的Chapter A中讨论的性能黄金法则吗:
只有10-20%的最终用户响应时间是花在了下载HTML源文件上。其它的80-90%是花在了下载页面中的所有组件上。

如果您的web应用服务器离用户足够近,那么在Chapter A 中讨论的那个第一个HTTP请求的响应时间就可以更快;再或者您的web组件服务器也离用户足够近,那在页面中请求这些组件的响应时间也会缩短,这可比您重新设计一个分布式的系统的复杂度要小的多了,这就要用到内容分发网络:CDN(content delivery networks)。

Content Delivery Networks

内容分发网络 CDN 是一个分布在多个地域间用于为用户提供更高效的内容访问服务的网络服务器集群。这种高效不仅体现在性能上,也体现在成本的节省上,因为CDN会选择离请求用户物理结点最近的一台服务器为用户提供内容访问服务,以在到提高响应时间。

一些大型的互联网公司都拥有自己的CDN,但使用专业CDN服务提供商的服务则更能节约成本。如Akamai科技公司于2005年收购了Speedera网络公司,成为北美CDN市场的领军者,还有Mirror Image网络公司,Limelight 网络公司,SAVVIS 公司等。

如下图2-1是十大美国网站使用CDN的情况:

 

我们能看到:
• 有五家网站使用了Akamai
• 有三家分别选择了 Mirror Image,Limelight,SAVVIS
• 其他的五家要么没有使用CDN,要么就是有自己的CDN解决方案

规模较小或是非商业网站未必能负担得起CDN服务器的高额费用,但有一些免费的CDN服务机构可以选择。如部署在阿姆斯特丹自由大学的基于Apache模块的Globule(http://www.globule.org),建在普林斯顿大学的CoDeeN (http://codeen.cs.princeton.edu)等等。(John:老实说,这些免费的CDN对我们没有什么用)
CDN除了能提升响应时间,还有一个好处。CDN还可以用于备份数据,扩充存储容量甚至是做缓存;它还可以帮助我们解决流量高峰的问题,如,一个提供实时性较强的天气预报或财经新闻的服务,或是发布某种体育娱乐新闻时,这种瞬间的访问高流量也可以被CDN所分流。

说到这,该说说CDN的缺点了,除了费用高,您的服务响应时间则会依赖于CDN服务商的硬件和同时在使用这家CDN的其它网站,甚至是有可能会受您竞争者的影响,如果您的竞争者也在使用与您相同的CDN服务商。因为CDN服务商一般都是在他所有的分发服务器之间为客户共享这些资源(John:这和大家在机房使用共享的虚拟主机是一个道理)。CDN的另一个不足是您可能会无法直接控制这些内容服务器,假如您要修改所有该CDN中的组件的HTTP响应头,这可能必须通过CDN服务商而不是您自己的技术人员。如果CDN本身出了问题,也会直接影响用户对您的web的访问。在上图2-1中,eBay和MySpace都使用了两家CDN服务商,这可是个明智之举,减少一定的风险,前提是您有足够的业务需求和金钱的支撑。

CDN是用来分发静态内容的,如图片,scripts,样式表或Flash。而要提供动态的HTML页面则要一定的服务器端要求:数据库连接,状态管理,权限认证,硬件和操作系统优化等,这些复杂的东西都超出了CDN的服务器范围(John:CND不是虚拟主机提供商)。由于CDN只提供静态文件的访问,从另一方面看,也使得它更有针对性,它只针对于提供静态文件较多的网站使用。

时间,节省

使用CDN到底能带来多少速度的提升。下面的两个链接页面,都包含相同的页面元素:5个script,1个样式表,8个图片。第一个链接页面是放在Akamai公司的CDN上,另一个是放置在一台单独的web服务器上:
CDN
http://stevesouders.com/hpws/ex-cdn.php
No CDN
http://stevesouders.com/hpws/ex-nocdn.php

由于这是放在美国的服务器,我们在国内访问可能还没那么快,但从测试的时间上来看,用 CDN的页面比放在单独服务器上的要快近18%,当然了,这一结果要取决于您的带宽接入速率和所在的地域。(John:目前的几大门户网站,新华网,人民网等以新闻资讯为主的网站都使用了CDN,在我前面介绍的Youtube构架中,也提到了他们的CDN策略。)

相关章节:

 

What is scalability ?

什么是scalablity? scalablity译成中文是:可扩展性,伸缩性。

很多人都在谈论系统性能,系统可用性,但我觉得scalablity(可扩展性)并不是这些,虽然我们仍然需要关注速度,性能,高可用性,程序平台,网络等等,但这些并不是scalablity的全部。
scalablity,简单的说,就是关于您如何把事情做的更大。扩展(scaling)一个web应用就是指怎么做才能使您的系统允许更多的人去访问或使用您的应用。
在目前的业内实践中,有两种扩展WEB应用的方法:

  • 垂直扩展Vertical Scalability” – 通过增加资源来增强系统的处理能力。如:给现有的系统升级CPU,或是为RAID/SAN扩充更多的硬盘。
  • 横向扩展Horizontal Scalability” – 增加多个应用处理单元的机器。一般是集群,分布式文件系统,负载均衡的形式来横向扩展系统。

 

每一个组件,无论是CPU,服务器,存储系统或是负载均衡,都还是会有一些运营上的开销。当您尝试扩展您的系统时,您一定要清楚到底哪些升级或扩展是对您系统影响比例最大的,这要经过一些测量。我们把比这些测量的结果叫做”可扩展性因子“。比如:您每为系统增加一个CPU,但因为一些开销要耗掉这个CPU 5%的性能,实际上您的可扩展性因子是0.95,也就意味着您只能使用到这个CPU 95%的资源。

  • 如果可扩展性因子是一个常量(=1),我们就称之为 “线性扩展linear scalability“.
  • 但实际上有很多组件的扩展性并不太好,如上面介绍的增加CPU时的有非功能性开销的例子. 如果扩展性因子小于 1.0,我们就称之为 “子线性扩展性-sub-linear scalability“.
  • 有一种情况比较少见,就是通过增加组件而获得性能(扩展性因子>1)的大幅度提升(如把在多个磁盘上的I/O操作移到一个RAID上),这种情况我们称之为 “超线性扩展supra-linear scalability“.
  • 还有一些设计的不好的应用,根本不适合扩展,扩展的努力只会让系统更糟 ,我们就称之为”负可扩展性 negative scalability“.

如果您需要扩展系统,垂直扩展是最简单的方式(只要您银行存款足够,这事就成了)。一般在不做代码优化的情况下,您可以把您的系统程序迁移到一个超级的,也更贵的64位CPU的服务器上;也可以把存储系统换成EMC,日立或Netapp的产品。但是垂直扩展只会让您的花费越来越大。

横向扩展,则不一定要相当数量的昂贵服务器。因为它可以通过普通的机器和存储硬件以达到规模效应来解决问题,像早期的Yahoo!,Google都是这样。横向扩展不仅仅是便宜,它是把应用程序构建在多个服务器组成的一个大server的基础上,这样就会随之有两个常见的问题: “Split brain“(功能,数据分割) 和 “hardware failure“(硬件故障,毕竟机器太多了)。

无限的线性横向扩展是很难实现的,无限的垂直扩展则更不可能了(硬件的性能都有极限)。如果您正在建设中的系统事先无法确定用户的数量,那么用垂直扩展比较明智。但如果您正在建立一个给百万网友使用的WEB应用,那垂直扩展是一个错误,它实在太昂贵了。

可扩展性不仅仅是关于CPU(处理能力)的,一个成功的可扩展的WEB应用,它的所有层都应该能够方便的扩展,如:存储层(文件集群系统),数据层(数据分区,数据联合),应用层(memcached,scaleout,terracota,tomcat集群等),WEB层,负载均衡层,防火墙。举个例子,如果您对您未来的WEB应用网络负载没有考虑负载均衡,那么花再多的钱在WEB层的横向扩展上都是浪费,因为您的WEB访问的将会被瓶颈限制,而这时只有负载均衡能解决问题。

选择一个正确的可扩展性方案取决于您的系统应用规模和您的银行帐户情况。如果有人说他有一个能解决所有问题的方案,那人肯定是个骗子或是外行。如果您再参加某人的”可扩展性”讨论,您一定要先问问他:What is scalability ?

More to say:

  • Always try to identify the worst case scenarios.
  • Always build for the worst case scenarios.
  • Always test the known worst case scenarios.

And , always have a back-up plan!

更多资料:http://www.royans.net/arch/

 

译:High Performance Web Sites(3)-Chapter 1

《High Performance Web Sites》 :Chapter 1

法则 1: 尽可能减少HTTP请求数 Make Fewer HTTP Requests

在Chapter A中介绍的性能黄金法则,揭示了一个现象:只有10~20%的用户响应时间是花在请求html源文件上,剩下的80~90%的时间则是在请求页面中的各个组件(图片,script,样式表,flash等)。因此,我们的第一个提速的方法就是尽可能的减少这些组件的数量,我们的目的就是要减少HTTP请求的数量。

减少页面组件的建议,通常会让人在性能和产品设计上产生冲突。毕竟我们的页面现在所蕴含的元素越来越多,更多的小图片,不同的样式表,script等,这一章节,我会介绍一些技术方法来帮助我们平衡性能与产品设计上的冲突。这些将要出场的技术包括:image maps, CSS sprites,inline images以及尽量使用独立的js和样式表文件。使用这些技术方法在我们的案例中能减少50%的响应时间。

Image Maps
将一个页面中所要引用的图片整合成一个单一的图片文件,按顺序排好,再分切出里面的链接区域。这样对整个图片群的需求样式没有变,但减少了对图片的http请求数。
图1-1显示的是一个有五个图片组成的导航栏,每个图片对应一个独立的超链接。我们常规的做法,当然就是做五个图片,然后为每个图片做一个链接;但为了更高效,我们把五张独立的图片做成一张image map,这样从五个HTTP请求,就变成了一个HTTP请求,相应的响应时间也就会变的更快了。

您可以试一下下面的两个链接,自己体会一下Image maps所带来的速度上的不同。

No Image Map
http://stevesouders.com/hpws/imagemap-no.php
Image Map
http://stevesouders.com/hpws/imagemap.php

如果使用IE6在DSL(~900Kbps)的网络环境下,用image map的方法组成的导航栏要比用单独图片文件的所组成的导航栏要快56%(354ms 比 799ms).这是因为image map会减少四个HTTP请求。

Image Map最常用的实现方式是使用HTML的map标签,把大图片分成一个一个的小块,并设置其不同的链接。如下:

<img usemap=”#map1″ border=0 src=”http://7career.org/images/imagemap.gif”>
<map name=”map1″>
<area shape=”rect” coords=”0,0,31,31″ href=”http://7career.org/home.html” title=”Home”>
<area shape=”rect” coords=”36,0,66,31″ href=”http://7career.org/gifts.html” title=”Gifts”>
<area shape=”rect” coords=”71,0,101,31″ href=”http://7career.org/cart.html” title=”Cart”>
<area shape=”rect” coords=”106,0,136,31″ href=”http://7career.org/settings.html” title=”Settings”>
<area shape=”rect” coords=”141,0,171,31″ href=”http://7career.org/help.html” title=”Help”>
</map>
但是它所带来的缺点就是你得手动确定图片的坐标,这会比较乏味和容易出错,并且它只适合把图片都组合在一个长方形的区域里。

CSS Sprites (您可以参考YouTube和iGoogle的首页,它们就是采用的这种优化方式)
与image maps类似,CSS Sprites也是把若干小图片合成一个大图片,但是CSS Sprites方式更灵活。为了实现CSS Sprites,是把各个小图片像组成一个棋盘一样地合成一个图片。如下图:

 

然后通过HTML中任何能支持背景图片的元素,如<span>或<div>,再通过CSS中的background-position属性来定位要显示的大图片中的某个小图片的位置。如下,就是要在上面给出的在图片中使用”My”这个图标来充当下面这个div的背景:
<div style=”background-image: url(’a_lot_of_sprites.gif’);
background-position: -260px -90px;
width: 26px; height: 24px;”>
</div>

我把前面我介绍image map的例子转成CSS Sprites的形式:把导航栏的五个链接都放到一个名为navbar的DIV中。每个链接都有一个SPAN元素,在#navbar的样式中为SPAN元素定义了背景图片spritebg.gif,但每个SPAN都有一个不同的class以指明其具体显示的背景图片的偏移位置,正是利用了CSS中的background-position属性。

<style>
#navbar span {
width:31px;
height:31px;
display:inline;
float:left;
background-image:url(/images/spritebg.gif);
}
.home { background-position:0 0; margin-right:4px; margin-left: 4px;}
.gifts { background-position:-32px 0; margin-right:4px;}
.cart { background-position:-64px 0; margin-right:4px;}
.settings { background-position:-96px 0; margin-right:4px;}
.help { background-position:-128px 0; margin-right:0px;}
</style>

<div id=”navbar” style=”background-color: #F4F5EB; border: 2px ridge #333;
width:180px; height: 32px; padding: 4px 0 4px 0;”>
<a href=”javascript:alert(’Home’)”><span></span></a>
<a href=”javascript:alert(’Gifts’)”><span></span></a>
<a href=”javascript:alert(’Cart’)”><span></span></a>
<a href=”javascript:alert(’Settings’)”><span></span></a>
<a href=”javascript:alert(’Help’)”><span></span></a>
</div>

这比image map的方式的例子要更快:342ms VS 354ms,但是他们之间的实现方式只有很小的不同。但重要的是,这可比用单独的五个图片的例子要快57%了。
CSS Sprites
http://stevesouders.com/hpws/sprites.php

我们看到,image map的方式要求所有的图片是连续的组合在一起的,而CSS Sprites没有这个限制。关于CSS Sprites的优缺点在Dave Shea的权威文章“CSS Sprites: Image Slicing’s Kiss of Death“中已经有详细的介绍,但我已经从CSS Sprites中体会到它的优点:减少了HTTP请求,比image maps灵活。另一个让我没想到的优点是它减少了下载的数据量。大多数人可能会认为一个拼合成的大图片肯定要比这此小图片的总量要大,因为它会有一些小图片的间隔区域。实际上正相反,大图片减少了图片中的color tables和格式信息等,而使得大图片比一堆小图片实际size要小一些。

如果你的网站中有很多背景图片,按钮图片,导航栏图片,那么你应该用CSS Sprites方式来优化你的页面了。(您可以参考YouTube和iGoogle的首页,它们就是采用的这种优化方式)

Inline images(注:IE暂不支持,您可以跳过这一部分;但说不定什么时候IE就支持了)
我们上面所做的都是为了减少HTTP请求,现在有一个更绝的方式,把所有的图片都以base64编码以源代码的形式写在HTML源码里:data:[<mediatype>][;base64],<data> 所有对图片的HTTP请求,都化在了对HTML源文件的第一次请求里。

我们在HTML中肯定都用过ftp:,file:,mailto:这样的标签,实际上像这样的标签还有很多,只是我们平常不太使用,像:smtp:,pop:,dns:,whois:,finger:,daytime:,news:,urn:等等.

data:URL标签是在1995年第一次提出,按RFC2397规范的描述:它是”allows inclusion of small data items as ‘immediate’ data.(允许在页面中包含一些小的即时数据)”。如一个内嵌的小红星的图片可以这样引用:(在firefox下可以出来)

<IMG ALT=”Red Star”
SRC=”data:image/gif;base64,R0lGODlhDAAMALMLAPN8ffBiYvWW
lvrKy/FvcPewsO9VVfajo+w6O/zl5estLv/8/AAAAAAAAAAAAAAAACH5BAEA
AAsALAAAAAAMAAwAAAQzcElZyryTEHyTUgknHd9xGV+qKsYirKkwDYiKDBia
tt2H1KBLQRFIJAIKywRgmhwAIlEEADs=”>
这样是挺方便吧,但它的不足之处也很明显:目前IE不支持;再就是FireFox1.5所能处理的line image有大小限制,不能超过100K;base64的编码会增加HTML的容量,总体下载量会增多。
Inline Images:http://stevesouders.com/hpws/inline-images.php

data:URL是内嵌在页面中的,所以它不会在页面之间缓存。所以您别用这种方法存储您公司的logo,因为它会增加您每个页面的容量。要解决这个问题,您可以把inline image写在CSS中,尽管date:URL不会被缓存,但CSS是可以被缓存的,Inline CSS Images:http://stevesouders.com/hpws/inline-css-images.php

下面就是接上面的例子,为每个SPAN加上inline image:

.home { background-image: url(data:image/gif;base64,R0lGODlhHwAfAPcAAAAAAIxKA…);}
.gift { background-image: url(data:image/gif;base64,R0lGODlhHwAfAPcAAAAAAABCp…);}
.cart { background-image: url(data:image/gif;base64,R0lGODlhHwAfAPcAAAAAADlCr…);}
.settings { background-image: url(data:image/gif;base64,R0lGODlhHwAfAPcAAAAAA…);}
.help { background-image: url(data:image/gif;base64,R0lGODlhHwAfAPcAAAAAALW1t…);}
PHP的file_get_content函数可以很轻松的实现inline image的那串base64的图片编码。我上面的例子就是用的这个函数:
.home { background-image: url(data:image/gif;base64,
<?php echo base64_encode(file_get_contents(”../images/home.gif”)) ?>);}
.gift { background-image: url(data:image/gif;base64,
<?php echo base64_encode(file_get_contents(”../images/gift.gif”)) ?>);}
Combined Scripts and Stylesheets | 15
.cart { background-image: url(data:image/gif;base64,
<?php echo base64_encode(file_get_contents(”../images/cart.gif”)) ?>);}
.settings { background-image: url(data:image/gif;base64,
<?php echo base64_encode(file_get_contents(”../images/settings.gif”)) ?>);}
.help { background-image: url(data:image/gif;base64,
<?php echo base64_encode(file_get_contents(”../images/help.gif”)) ?>);}
我们比较一下上面的几个例子,image maps与CSS Sprites的响应时间基本上相同,但比使用各自独立图片的方式要快50%以上。用inline image与CSS组合的方式虽然增加一个HTTP请求,但是它可以以样式表的形式被缓存。

Combined Scripts and Stylesheets
尽量使用独立的js和样式表文件

现在的前端开发少不了JavaScript和CSS,但我们还是建议:使用外部的js和css文件引用的方式,因为这要比直接写在页面中性能要更好一点(细节会在Chapter 8中讨论)。但是如果你滥用这条规则,把你的代码切割成了很多个小文件,那只会增加更多的HTTP请求而影响性能。
表1-1是10大网站首页中js和样式表的数量表,它们的样式表都不多,但js显然还有优化的余地。

下面的例子中,你会发现用独立的一个js比用多个js文件组成的页面载入要快38%.
Separate Scripts
http://stevesouders.com/hpws/combo-none.php
Combined Scripts
http://stevesouders.com/hpws/combo.php

有的人可能会习惯于按功能或模块来把js分成各种不同的文件,但以我的经验,如果一个网站的页面引用大量的js文件,那应该要分析一下这些分类是否真的便于管理。

结论
这一章节介绍了我们在Yahoo!用到的以减少HTTP请求数量的技术方法。也是对访问网站很重要的一条法则。它会提高用户第一次访问您网站时的体验速度。而更快的访问速度将会使用户更愿意常回头访问您杰作。

相关章节:


 

翻译:High Performance Web Sites(2)-Chapter B

《High Performance Web Sites》 :Chapter B

HTTP Overview

在开始介绍具体的优化法则之前,您务必要理解超文本传输协议:HyperText Transfer Protocol(HTTP)对性能的影响。HTTP是浏览器与服务器之间通过Internet通信的方式。HTTP的规范是由万维网联盟:W3C(World Wide Web Consortium)和互联网工程任务组:IETF(Internet Engineering Task Force)共同制定,而最终形成的RFC 2616规范。HTTP/1.1是目前流行通用的版本了,但还是有一些浏览器只支持HTTP/1.0。

HTTP就是描述请求request和响应response的c/s模型协议。一个浏览器发送HTTP请求(request)到一个指定的URL,这个URL所指定的服务器接到请求后返回一个HTTP响应(response)给浏览器,就这么简单。与很多互联网服务一样,这个协议用的是简单的明文格式。请求的种类有:GET,POST,HEAD,PUT,DELETE,OPTIONS和TRACE。下面我只重点介绍GET请求,这一最常用的。

一个GET请求把所请求的URL组装在头信息(headers)中,然后发送到这个指定的URL。服务器接收到请求后,经过响应处理,返回一个包含状态码,头信息(headers)和具体明文文本(一般是Html源码)所组装的数据包。如下图,就是请求yahoo_2.0.0-b2.js时的HTTP头信息(headers)的内容示例。

压缩
如果浏览器和服务器都支持,可以通过压缩来减少响应返回时的数据量。浏览器通过头信息中的Accept-Encoding元素来告诉服务器是否可以接受压缩数据,以及何种压缩方式。而服务器则通过头信息中的Content-Encoding元素来告诉浏览器,我目前支持哪种压缩方式。如下图

 

注意上图中返回的数据是已经被压缩的数据。Chapter 4会专门介绍HTTP压缩,以及在代理缓存下产生的一些问题,当然还会讨论一些其它的头信息(headers)。

有条件的GET请求  Conditional GET Request
如果浏览器已经缓存了一个组件,但是浏览器该怎么知道这个组件是否还有效呢,于是就产生了有条件的GET请求。如果缓存里的组件是有效的,浏览器就继续使用这个组件来加载页面,以减少响应的数据量从而加速了用户体验。

一般来说,判断缓存的组件是否有效是检查它的最后修时间。浏览器通过response响应数据中名为Last-Modified的头信息来获取这个时间值。再次有相同组件的GET请求时,浏览器会将名为If-Modified-Since头信息随GET请求一起发送到服务器,带着这一条件信息给远程的服务器,这就好像是浏览器对服务器呐喊:”我已经有一个版本的组件了,这里它的最后修改时间,这次我还可以继续使用它吗?”(只要网络不断,服务器总是会听见这呐喊声的)

 

如果这个组件在这个Last-Modified描述的时间之后没有被修改过,服务器就不会返回这个组件的具体数据了,而返回一个”304 Not Modified”状态码,这样可不就提高了响应速度了。在HTTP/1.1里,名为ETag和If-None-Match的头信息也可以起到类似的作用,这两个都会在Chapter 13中有讨论。

过期 Expires

有条件的GET请求和返回304状态码能让页面载入的更快,但它还是需要在客户端和服务器端进行一个往返的验证过程,HTTP请求仍然存在。而名为Expires的头信息会则会避免这种验证过程。

 

一旦浏览器发现响应返回的头信息中有Expires属性,它就会把这个属性所描述的日期与组件保存到浏览器缓存中,只要再次访问这个组件时的日期没有超过Expires属性里描述的日期,就会一直被浏览器使用而不会再次发送HTTP请求。Chapter 3会有关于Expires和Cache-Control头信息的更多介绍。

Keep-Alive

HTTP是建立在TCP协议的上层的实现,在早期的HTTP实现中,每个HTTP请求都会打开一个新的socket连接。实际上效率很低,因为大多数的HTTP请求都是针对同一个服务器发出的(想像一下我们浏览一个页面的情形,是不是该页面的组件大多数都是在这个页面所host的服务器上)。于是,长连接(persistent connections)的概念被引入了HTTP,以解决这种同一个服务器不停地打开关闭socket连接的情况。它能够让浏览器的多个请求只通过一个连接完成。浏览器和服务器就是通过相互传递Keep-Alive头信息来判断是否支持这一特性。

 

浏览器或服务器可以通过发送一个close头信息来关闭连接。从规范来说,keep-alive并不包含在HTTP/1.1中,但是绝大多数浏览器和服务器还是支持这一特性的。

Pipelining, 定义在HTTP/1.1中,它允许在一个socket连接中发送多个请求而不用等待响应返回。Pipelining比长连接(persistent connections)有着更好的性能。但是很不幸,IE不支持(IE7已经支持了),FireFox 2以后的版本虽然支持,但默认是关闭的。所以在Pipelining还没能普及以前,我们就还只能用Keep-Alive的方式来优化浏览器与服务器之间通过socket的通信。这个特性对于HTTPS很重要,因为HTTPS的连接都是长时间的连接.

更多

这个章节只是大致的介绍了HTTP,并把重点放在介绍影响性能的方面。如果要了解更多,您可以参考HTTP规范(http://www.w3.org/Protocols/rfc2616/rfc2616.html和由David Gourley 与 Brian Totty编写的《HTTP: The Definitive Guide》(O’Reilly; http://www.oreilly.com/catalog/httptdg)。上面所例举的资料将会您理解我们后台的章节有很大的帮助。

 

翻译:High Performance Web Sites(1)-Chapter A

前端性能的重要性The Importance of Frontend Performance

我的大部分web生涯都是在扮演后台开发工程师的角色。所以,我很自然的把每个性能作业都作为是一个后台的优化练习罢了,像什么编译器参数,数据库索引,内存管理什么的。而且也有很多关于后台性能优化的书籍和资料让大家从中找到想要的东西。但实际上,对于绝大多数的web页面,只有不到10-20%的最终用户响应时间是花在了从服务器下载HTML源文件到用户浏览器上。如果你想达到不可思议般的用户快速浏览体验,那当然就应该去关注一下那其它的80-90%的用户体验时间花在哪儿呢?又该怎么去减少这个时间呢?后面的章节就会向您讲解与目前web优化所相关的一些基础知识,并提供14条优化性能的法则。

来关注一下web页面的性能

为了知道怎么去提高性能,我们应该先了解最终用户们都把等待的时间花在哪儿了?图A-1是在IE上访问Yahoo!的首页(http://www.yahoo.com)的HTTP响应时间图(John注:我们可以用HttpWatch(IE),Firebug(ff)工具来生成类似的图)。每一个横条都是一个HTTP请求。第一个横条,标识为html的那个,是HTML文档的初始请求(指请求HTML源文件)。然后浏览器解析这个HTML文档,并且开始下载这个页面的所有组件(John注:这里的组件是指页面所引用的图片,flash等非html文档的东西)。在我们的测试环境下,浏览器的缓存是空的,所以所有的组件都会被下载。在图上,我们可以看到,HTML源文件的下载只占整个响应时间的5%,最终用户花了近95%的时间用在等待下载组件上.还有一小部分是花在HTML,script和样式表(stylesheets)的解析上,在图中我们用每个下载时间条间的空白间隔来表示这些解析时间.

图A-2显示的是我们第二次用IE浏览这个网页时的情况.HTML文档的下载占到了整个响应时间的12%.大部分的组件都不用再下载了,因为它们已经被浏览器缓存了。

图A-1 在Internet Explorer上访问http://www.yahoo.com,空缓存

图A-2在Internet Explorer上访问http://www.yahoo.com,预先已有缓存

Ok,我们来看一下,有五个组件在第二次浏览页面时仍被下载了:

一个重定向(redirect)

这里的重定向虽然已在第一次访问被处理过了,但是浏览器还是再次请求了一次。因为它的HTTP响应状态码是302(表示”Found” 或 “move temporarily”),在响应header中没有缓存信息,所以浏览器不会去缓存它。关于这方面我们会在Chapter B中讨论HTTP时提到。

三个没有缓存的图片
接着的三个request请求是在上一次浏览时没有下载的三个图片。这些是经常变动的新闻图片和广告图片.

一个被缓存的图片
最后一个HTTP request请求是一个有条件的GET请求.这个图片是上次被缓存的,但是因为HTTP的响应头(response headers)的设置,浏览器要确认一下这个图片是不是最新的.有条件的GET请求我们也会在Chaptet B中讨论它.

 

时间都去哪儿了?

再回过来看看HTTP时间响应图,我们看到至少80%的最终用户响应时间是花在了下载页面里的组件上,如果我们来仔细分析一下这个图表的内容,我们会发现浏览器与HTTP之间的交互开始有点变的复杂了。除了上面我提到了HTTP的状态码和header会响应浏览器的缓存,另外,我们还能得到下面一些观察结果:

l 凡是被缓存的组件(图A-2)大多都不会有下载动作。相反,你看到的是紧跟在Html请求后的一个没有下载的空白时间间隔,这表示这段时间是在解析HTML,JavaScript和CSS,以及从缓存中获取相关的组件。

l 在同一时间里的HTTP请求数变化了。图A-2在同一个时间切面上最多只有三个HTTP请求,而图A-1却同时有多达六到七个HTTP请求。这是因为使用了多个不同的主机名(hostname),而无论它们是使用HTTP/1.0还是HTTP/1.1。Chapter 6将会解释这种多个同时下载的”平行下载(Parallel Downloads)”。(John注:是指同时下载)

l 这种平行下载不会发生在下载script上,因为在大多数情况下,浏览器会阻止其它下载script的HTTP请求。Chapter 6会解释为什么会这样,同时也会教你如何应用这个知识去优化你的页面载入时间。

要完完整整地指出时间都去哪儿了真是一个挑战。但至少还是很容易地能看到哪儿没花时间?它没有全花在下载HTML文档上,也没全花在后台的处理上。(几乎都花在了前端下载组件上)这就是为什么前端性能如此重要了。

 

性能黄金法则

像Yahoo!主页这样只有10%-20%的响应时间花在下载HTML源文件的现象并不是一个特例。据我分析,几乎所有与Yahoo!类似的网站都是这样(这可不包括Yahoo!Search,因为它的页面上组件的数量实在是太少了)。甚至可以进一步说,绝大多数的网站都是这样的情况。表A-1展示了由http://www.alexa.com所统计出的当今美国前10大网站。说明一下,下面提到的网站只有AOL不在前10,因为Craigslist.org本是排在前10,但是它的页面风格没有什么图片,script和样式表,不适合这里做为研究例子,所以我挑选了AOL。

图A-1 访问10大网站时的下载HTML源文件所占的时间比

所有的网站都只花了不到20%的总响应时间在获取HTML源文件上(John注:这一部分时间更多地取决于各网站的后端性能)。但只有Google在已有缓存的情况下是个例外。因为http://www.google.com只有6个组件,其中有5个被配置成被浏览器缓存。再次访问时,所有的组件被缓存,只有一个请求HTML源文件的HTTP请求和一个图片请求。

在做完所有的后台优化努力的情况下,你已经很难再有大的突破了。很显然,是时候关注前端的性能了。

首先,关注前端性能所能带来的整个性能提升到底有多少。如果我们能把后台的响应时间再优化,再砍掉一半响应时间,最终用户的响应时间也只是相应减少5% ~10%(John注:因为后台的性能只能是减少那个20%的响应HTML源文件请求)。相反的,如果我们把前端的性能提高一倍,我们可以把整个响应时间减少40~45%。

再说了,前端的改进一般不需要太多的时间和资源。而优化后台的性能时间基本上都得深入应用的构架和代码,找出优化的关健代码路径,增加或者改进硬件,分布化数据库等等,这些工作动辄就要以周和月为时间单位。在接下来的章节中介绍的前端性能优化法则都来自于最佳实践,比如修改web服务器的配置文件(Chapters3,4);将script和样式表放置到页面中相应的地方(Chapters 5 ,6);将图片,script,样式表组合到一起(Chapters 1)。这些实践只需要以小时和天为工作单位–远比提高后台性能需要的时间成本要低。

第三点,前端性能的这些实践都是经过实际考验的。在Yahoo!中有超过50个小组用这些实践减少了25%甚至更多的最终用户响应时间。在一些案例中,我们分析了运用这些要点的网站,一般都能达到25%或更多的性能提升。

在开始每个新的性能提升项目时,我都会画一张类似图A-1的图表来阐释一下性能的黄金法则:

只有10-20%的最终用户响应时间是花在了下载HTML源文件上。其它的80-90%是花在了下载页面中的所有组件上。

俺把这句浓缩一下,就是:80-90%的用户等待时间是来自于前端的页面加载。

这本书后面的部分将会提供详细的指导法则去减少这80-90%的最终用户响应时间。为了说明这些法则,我会陆续提到很多相关的技术:HTTP headers,JavaScript,CSS,Apache等等。

因为一些HTTP的基本概念对理解这本书非常有必要,所以我会在Chapter B中重点简介。

在这之后就是分章节的14条优化法则。我把这些法则按优先级列出。每条法则都有自己的适应范围。举个例子,法则2更适合商业网站而不适合个人站点。如果您应用所有适合您网站的的优化法则,您可以将页面速度提升25-50%从而增强用户体验。这本书的最后章节会告诉您如何以性能的眼光去分析美国的10大网站。

High Performance Web Sites

大概两个月前就在网上down下了这部书,并一口气读完。正值blog迁移,故现在才浓重推荐。此书是对于web前端的性能优化不可多得的一部好书,其可实践性极强,作者是原Yahoo!的首席性能官(Chief Performance Officer):Steve Souders,现已经跳至google。
在Yahoo,有一支性能小组,叫:Yahoo!’s Exceptional Performance team,翻译成中文就是是特别性能小组,他们主要是致力于以最佳的实践来提高Web性能。好像前段时间他们来过中国参加了CSDN的开发者大会,可惜俺未能参加,要是早知这一出演讲讨论,肯定要前往倾听了。Steve Souders就是这支小组的team leader。
书中,Steve Souders提出了一个performance golden rule,与其说是黄金法则,到不如说这是一个目前各网站所常见的一个表象:80-90 %的用户等待时间是来自于前端的网页加载
而《High Performance Web Sites》就是介绍如何去减少这80~90%的等待时间的一部优化手册。此书即适合前台开发者(html,js,css),也适合后台开发者。此书在yahoo的开发者网站有Html版本,具体可查阅http://developer.yahoo.com/performance/rules.html
如果您对后台的构架或性能更感兴趣,那在我前面介绍Flickr构架时,所提到的《Building Scalable Web Sites》就更值得一看了。
该书的中文版已经出来了,我就不翻译了,推荐大家买书学习。

排序研究二

五.归并排序
归并排序比前面讲到的排序方法要有效的多.冒泡排序,插入排序和选择排序要用O(N^2)时间,而归并只要O(N*logN).如果N是10000,那么N^2就是100000000,而N*logN只是40000,如果为这么多数据项排序用并归排序的话需要40秒,那么用插入排序则需要将近28个小时.
但归并排序有个最大的缺点,就是它需要在内存能装下一个大小等于被排序的数据项数目的数组.

在研究归并排序前,先要说说什么是归并.
假设有两个有序数组,数组A有4个数据,数组B有6个数据,它们要归并到数组C中,那么我们就要为C初始10个空的存储空间.

然后,对A的第一个数据,和B的第一个数据进行比较,把较小的数据项被复制到数组C中.再把未复制的数据与另一个数组的第二个数据进行比较,再把比较小的数据复制到C中,依次类推.

                                  // 把数组A和B归并到数组C
     public static void merge( int[] arrayA, int sizeA,
                               int[] arrayB, int sizeB,
                               int[] arrayC )
      {
      int aDex=0, bDex=0, cDex=0;

      while(aDex < sizeA && bDex < sizeB)  // 两个数组均不为空时
         if( arrayA[aDex] < arrayB[bDex] )
            arrayC[cDex++] = arrayA[aDex++];
         else
            arrayC[cDex++] = arrayB[bDex++];

      while(aDex < sizeA)                  // 数组B空了,
         arrayC[cDex++] = arrayA[aDex++];  // 数组A还没空

      while(bDex < sizeB)                  // 数组A空了,
         arrayC[cDex++] = arrayB[bDex++];  // 数组B还没空
      }  // end merge()

现在来看看归并排序的思想,是把一个数组分成两半,排序每一半,然后用上面的归并思想把数组的两半归并成一个有序的数组.但如何对每一部分排序呢,就要用到递归了,把每一半都分成两个1/4,对每个1/4部分排序,然后把它们归并成一个有序的一半,再以此类推不停的分解问题,直到得到了基值条件:只有一个数据项的数组是有序的.

public void mergeSort()          // 归并排序组程序,theArray是待排序数组,nElems是其长度
{                              // 建一个存放有序结果的初始数组
      long[] workSpace = new long[nElems];
      recMergeSort(workSpace, 0, nElems-1);
      }

 private void recMergeSort(long[] workSpace, int lowerBound,
                                               int upperBound)
      {
      if(lowerBound == upperBound)            // 如果就一个了,没
         return;                              // 必要排序了
      else
         {                                    // 找到中间点
         int mid = (lowerBound+upperBound) / 2;
                                              // 对左边的一半排序
         recMergeSort(workSpace, lowerBound, mid);
                                              // 对右边的一半排序
         recMergeSort(workSpace, mid+1, upperBound);
                                             // 合并两个排好序的一半
         merge(workSpace, lowerBound, mid+1, upperBound);
         }
      }  

 //-----------------------------------------------------------
   private void merge(long[] workSpace, int lowPtr,     //lowPtr:前半部分的子数组的开始;
                           int highPtr, int upperBound) //highPtr:后半部分子数组的开始位置;
      {                                                 //upperBound:后半部分子数组的上界
      int j = 0;
      int lowerBound = lowPtr;
      int mid = highPtr-1;
      int n = upperBound-lowerBound+1; 

      while(lowPtr <= mid && highPtr <= upperBound) //把theArray数组中前半部分和后半部分
         if( theArray[lowPtr] < theArray[highPtr] ) //中小的数据复制到workSpace中
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <= mid)
         workSpace[j++] = theArray[lowPtr++];

      while(highPtr <= upperBound)
         workSpace[j++] = theArray[highPtr++];

      for(j=0; j<n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()
   //-----------------------------------------------------------

workspace数组的创建在mergeSort()中实现,是因为如果在recMergeSort()中创建数组会在每一次递归调用中都创建新数组,这是没有效率的.

但是一个算法作为一个递归的方法通常从概念上很容易理解,但是,在实际的运用中证明递归算法的效率不太高,有时可以用一个基于栈的方法来替代它,有兴趣的朋友可以继续研究.

六,希尔排序
希尔排序不像快速排序和其他时间复杂度为O(N*logN)的排序算法那么快,因此对非常大的文件排序,它不是最优的.但是希尔排序比选择排序和插入排序这种时间复杂度为O(N^2)的排序算法还是要快得多.另外 ,希尔排序算法的代码既短又简单.
我们先看看插入排序带来的问题.假设一个很小的数据项在很靠近右端的位置上,这里本来应该是值比较大的数据项所在的位置.把这个小数据项移动到在左边的正确位置上,所有的中间数据都必须向右移一位.这个步骤对每一个数据项都执行了将近N次的复制.

希尔排序是通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项能大跨度地移动.
进行希尔排序时数据项之间的间隔被称为增量,并且习惯上用字母h来表示.
如对包含10个数据项的数组进行排序,我们设h=4,我们则先对0,4,8位置上的元素排序,然后再对1,5,9号数据项进行排序.这个排序过程持续进行,直到所有的数据项都已经完成了4增量排序,也就是说所有间隔为4的数据项之间都已经有序.
然后我们就可以进行普通的插入排序,即1-增量排序.
在完成以h为增量的希尔排序后,所有元素离它在最终有序序列中的位置都比较近,这就是数据"基本有序"的含义.这也正是希尔排序的奥秘所在.
接着上面的例子4-增量排序和1-增量排序结合起来应用,比前面只用普通的插入排序要快得多.
那对于希尔排序中的h间隔如何取呢,一般我们选用Knuth序列:h初值为1,然后应用h=h*3+1生成序列:1,4,13,40,121,364,…当间隔大于数组大小时,这个过程停止.

 public void shellSort(int []a)
      {
      int inner, outer;
      long temp;

      int h = 1;                     // 间隔h的初始值是1
      while(h <= a.length/3)
         h = h*3 + 1;                // (1, 4, 13, 40, 121, 等等)

      while(h>0)                     // h递减,直到h=1
         {
                                     // h-增量排序
         for(outer=h; outer<a.length; outer++)  //即插入排序
            {
            temp = a[outer];
            inner = outer;
            while(inner > h-1 && a[inner-h] >=  temp)
               {
               a[inner] = a[inner-h];
               inner -= h;
               }
            a[inner] = temp;
            }  // end for
         h = (h-1) / 3;              // h递减
         }  // end while(h>0)
      }  // end shellSort()

迄今为止,除了在一些特殊情况下,还没有人能够从理论上分析希尔排序的效率,有各种各样基于试验的评估,估计它的时间级从O(N^3/2)到O(N^7/6).

七,快速排序
讲快速排序,就要先说一下划分,因为划分是快速排序的根本机制.
划分就是把数组分为两组,使所有关键字大于特定值的数据项在一组,使所有关键字小于特定值的数据项在另一组.
完成划分,数据还不能称为有序,也只是比没有划分前更接近有序了.同时划分也是不稳定的,因为它往往会颠倒数组中一些数据的顺序.

 public int partitionIt(int left, int right, long pivot)
       {
       int leftPtr = left - 1;           // 左边
       int rightPtr = right + 1;         // 右边
       while(true)
          {
          while(leftPtr < right &&       // 找出左边比pivot大的元素时停止
                theArray[++leftPtr] < pivot)
             ;  // (nop)

          while(rightPtr > left &&       // 找出右边比pivot小的元素时停止
                theArray[--rightPtr] > pivot)
             ;  // (nop)
          if(leftPtr >= rightPtr)        // 左右相逢
             break;                      // 划分结束
          else                           // 左右未逢
             swap(leftPtr, rightPtr);    // 交换元素
          }  // end while(true)
	  swap(leftPtr, rightPtr);        //将pivot放到正确点
       return leftPtr;                   //返回相逢点
       }

划分算法主要是两个指针,分别指向数组的两头.在左边的指针,leftPtr向右移动,而在右边的rightPtr则向左移动.实际上,leftPtr初始化时是在第一数据的左边一位,rightPtr是在最后一个数据项的右边一位,这是因为它们在执行前都要分别的加一和减一.
当leftPtr遇到比待比较数据小的数据项时,它继续右移,但遇到比待比较数大时,它就停止.类似的,当rightPtr遇到大于待比较数的数据项时,它继续左移,但是当遇到比待比较数小时,也停止.两个内层while循环,第一个用于leftPtr,第二个用于rightPtr,控制左右两部分的扫描过程.
当这两个循环都退出之后,也就是leftPtr与rightPtr都指向左右两边位置不对的数据项上,所以交换这两个数据.交换结束之后,继续移动两个指针,再停止,再交换.这一切都包含在一个外部循环中.

快速排序是最流行的算法,在大多数情况下,快速排序都是最快的,执行时间为O(N*logN)级.这也只是对内部排序而言,对于在磁盘文件中的数据进行排序,其他的排序算法可能更好.
快速排序算法本质上是通过把一个数组划分为两个子数组,然后递归地调用自身为每一个子数组进行快速排序.

 public void recQuickSort(int left, int right)
      {
      if(right-left <= 0)              // if size <= 1,
          return;                      //    already sorted
      else                             // size is 2 or larger
         {
         long pivot = theArray[right];      // 选择最右端的元素为待比较数
                                            // 划分
         int partition = partitionIt(left, right, pivot);
         recQuickSort(left, partition-1);   // 排序左边
         recQuickSort(partition+1, right);  // 排序右边
         }
      }  // end recQuickSort()

排序研究一

排序是数据结构中重要的一个部分,也是在实际开发中最易遇到的问题之一,当然了,你也可以不考虑这些排序的算法,直接把要排序的数据insert到数据库中,用数据库的order by 再select一下,也能产生排序结果,不过,开发一个好的系统,性能同样很重要。

在一堆数据中,是比较的执行耗时多,还是复制交换的执行耗时比较多,大量数据比较时,是否会有内存限制等等,在综合这些因素后,我们选择适当的排序算法,常常会让系统性能提升数倍,当然了,如果你的系统中没有任何需要数据排序的,那就不考虑了。

所有的排序算法,都是在大数据量时才会显示出其运行差别,所以,在下面的讨论中,大家了解各特性,按需选用。(如果你觉得往数据库里插入数据,再带着order by 去select执行耗时最小,那就使用我提的这个方法吧)

注:以下的排序,均以int或long型来比较,其实,比较的元素可以是除这以外的任何对象,要对象实现比较功能,可参考jdk的compareable接口,这个后面再讨论。

所有的问题,都会有一个简单的解决方法,但它往往并不是最佳的方法。

一,冒泡排序

public void bubbleSort(int[] array) {
  int temp;
  for(int i=0;i<array.length-1;i++){
   for(int j=i+1;j<array.length;j++){
    if (array[i]>array[j]){
     temp=array[i];
     array[i]=array[j];
     array[j]=temp;
    }
   }
  }

这个是最简单,最易理解的排序算法。从队列的最左边开始,比较0号位置和1号位置的元素,如果左边的元素(0号)大,就让两个元素交换;如果右边的元素大,就什么也不做。然后右移一个位置比较1号位置和2号位置;沿着这个队列照这样比较下去,一直比较到队列的最右端,虽然没有把所有元素排好充,但是最大的那个元素已经在最右边了,也就像是在水底下冒泡一样,冒上来了。然后再从左边的1号开始,再循环前面的操作。。。。

可以看出,冒泡排序运行需要O(N^2)时间级别,其速度是很慢的,比较次数:N*(N-1)/2,交换次数最坏的情况也是:N*(N-1)/2。

2,选择排序

选择排序与冒泡排序有点相似,但是,选择排序对冒泡排序做了些许优化:减少元素交换的次数。
从下面的代码中,我们可以看出,通过每一次循环,标识出当前最小的元素,再做交换。

选择排序和冒泡排序执行了相同的比较次数:N*(N-1)/2,对于100个数据项就是要4950次比较,但选择排序只进行了不到100次交换。当N值很大时,比较的次数是主要的。所以,当N比较小,特别是如果交换的性能消耗比比较的性能消耗大得多时,用选择排序是相当快的。

public void selectionSort(int[] array)
      {
      int out, in, min,nElems=array.length;

      for(out=0; out<nElems-1; out++)   // 外层循环
         {
         min = out;                     // 最小值
         for(in=out+1; in<nElems; in++) // 内层循环
            if(a[in] < a[min] )         // 如果有比最小值还小的
                min = in;               // 得到新最小值
         swap(out, min);                // 交换
         }  // end for(out)
      }  // end selectionSort()

 private void swap(int one, int two)
      {
      long temp = a[one];
      a[one] = a[two];
      a[two] = temp;
      }

三,插入排序

插入排序的特点是局部有序,通过循环,在(局部)有序组中的适当位置插入元素进行排序。然而要做到这一点,就需要把部分已排序的队员右移以让出空间。当把最后一个要比较的元素移位之后,这个移动的过程就结束了。

public void insertionSort(int a[]){
      int in, out,nElems=a.length;

      for(out=1; out<nElems; out++) {    // 外层循环
          long temp = a[out];            // 先把要插入有序队列中的元素取出
         in = out;                      // 要从这个元素的左边开始依次比较了
         while(in>0 && a[in-1] >= temp){ // 比较条件,
            a[in] = a[in-1];            // 比temp大的元素,就要右移了
            --in;                       // 再比较左边的
            }
         a[in] = temp;                  // 找到合适的位置了
         }  // end for
      }  // end insertionSort()

在外层的for循环中,out变量从1开始,向右移动。它标记了未排序部分的最左端的数据。而在内层的while循环中,in变量从out变量开始,向左移动,直到temp变量小于in所指的数组数据项,或者它已经不能再往左移动了。while循环的每一趟都向右移动了一个已排序的数据项。

这个算法需要多少次比较和复制呢?在第一趟排序中,它最多比较一次,在第二趟中最多比较两次,依此类推了,最后一趟最多,N-1次.所以:

1+2+3+……+N-1=N*(N-1)/2

然而,在每一趟排序发现插入点之前,平均只有全体数据项的一半真的进行了比较,所以实际上大约是N*(N-1)/4 次 (这个值不是精确值,只是一个概率的估算值,学过数理统计的朋友就不要太过计较了)

复制的次数大致等于比较的次数,由于一次复制与一次交换的时间耗费不同,所以相对于随机数据,这个算法比冒泡排序快一倍,比选择排序略快。

如果数据基本有序,插入排序几乎只需要O(N)的时间;然后对于逆序排列的数据,每次比较和移动都会执行,所以这时插入排序并不比冒泡快。

大家在选择算法时,要注意了,在事先估算待排序数据的状况下,再选择相应的算法。

四,有序链表排序

这里存储数据的方式就不是前面讨论的用数组来存储了,而是用链表这一个数据结构。

有序链表排序是一种高效的排序机制。所设有一个无序数组,如果从这个数组中取出数据,然后一个一个地插入有序链表,它们自动地按序排列,把它们从链表中删除重新放入数组,那么数组就会排好序了。

建立链表类Link.java:

class Link
   {
   public long dData;                  

   public Link next;
   public Link(long dd)
      { dData = dd; }
   }

建立有序链表SortedList.java

class SortedList
   {
   private Link first;
   public SortedList()
      { first = null; }
   public SortedList(Link[] linkArr)  

      {                               

      first = null;
      for(int j=0; j<linkArr.length; j++)
         insert( linkArr[j] );             

      }
   public void insert(Link k)     

      {
      Link previous = null;
      Link current = first;

      while(current != null && k.dData > current.dData)
         {                             

         previous = current;
         current = current.next;
         }
      if(previous==null)
         first = k;                    

      else
         previous.next = k;            

      k.next = current;
      }  // end insert()
   public Link remove()           

      {
      Link temp = first;             

      first = first.next;             

      return temp;                     

      }
   }

测试类ListInsertionSortApp.java:

class ListInsertionSortApp
   {
   public static void main(String[] args)
      {
      int size = 10;
                                 // 建立一个随机数组
      Link[] linkArray = new Link[size];

      for(int j=0; j<size; j++)  

         {
         int n = (int)(java.lang.Math.random()*99);
         Link newLink = new Link(n);  // 建立链表

         linkArray[j] = newLink;      

         }

      System.out.print("Unsorted array: ");
      for(int j=0; j<size; j++)
         System.out.print( linkArray[j].dData + " " );
      System.out.println("");

      SortedList theSortedList = new SortedList(linkArray);

      for(int j=0; j<size; j++)
         linkArray[j] = theSortedList.remove();

      System.out.print("Sorted Array:   ");
      for(int j=0; j<size; j++)
         System.out.print(linkArray[j].dData + " ");
      System.out.println("");
      } 

   }

这种排序方式总体上比在数组中用常用的插入排序效率更高一些,因为这种方式进行的复制次数少一些,但它仍然是一个时间级为O(N^2)的过程,因为在有序链表中每插入一个新的链结点,平均要与一半已存在数据进行比较。如果插入N个新数据,就进行了N*N/4次比较。每一个链结点只进行两次复制:一次从数组到链表,一次从链表到数组。在数组中进行插入排序需要N*N次移动,相比之下,2*N次移动更好。

注:以上提供的算法出自《Data Structures & Algorithms in Java》by Robert Lafore Sams © 1998