X hits on this document

99 views

0 shares

0 downloads

0 comments

15 / 25

北京大学学士学位论文

该页面长度所在的范围的计数器加1。

该文件所属的编码类型的计数器加1。

将该页面的网址、标题、引用次数写入一个文件。

主机统计程序中,每从数据库中读取一个信息,都要进行如下处理:

主机数计数器加1。

找到该主机所在的域,并将该域的计数器加1。

§4.3 引用次数排行表

将所有页面的引用次数都记录在一个文件中后,要对该文件进行处理,从中找出引用次数最高的100项。

因为数据库中有一百多万个页面,所以该文件的数据量很大,必须采用高效的算法。又因为最终只要产生前100项就可以了,所以不必将文件中的数据全部排序。

经过比较,我采用了下面的算法:

1.

将中间文件中的前100项用插入排序法加入双链表。

2.

读中间文件后面的项,如果某一项的引用次数小于当前双链表中的最后一项,直接将它略去;否则,将它插入双链表,并将最后一项除去,保证双链表中只有100项。

算法效率评估:

该算法只需要一遍扫描文件,刚开始时,双链表的内容变换比较频繁,但处理过一些数据之后,双链表中的100项的引用次数就会高于文件中的大多数项。这时,很多项都不需要插入双链表。

在100项的双链表中插入一项的平均比较次数是50次,在双链表中插入和删除一项时,并不需要移动别的项。

如果文件中有N项,该算法所需的比较次数远小于50N次。所以,该算法的时间复杂度为 O(N),效率较高。

该算法所占用的空间仅为100项的双链表所需的空间,空间代价也较低。

15

Document info
Document views99
Page views99
Page last viewedSat Dec 03 14:24:50 UTC 2016
Pages25
Paragraphs544
Words834

Comments