论坛首页 Java企业应用论坛

PageRank算法的原理和源代码实现(java)

浏览 10341 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2008-07-30   最后修改:2009-03-24
OO

参考文章:

理论:竹笋炒肉:Google的PageRank算法学习 http://hedong.3322.org/archives/000199.html

算法: PageRank算法的原理和源代码实现(C++)http://renxijun.blog.sohu.com/60220486.html

模仿上面这个算法实现了java版的计算,我写的这个性能不好,3496987篇网页迭代1次居然需要3分钟左右,贴出来希望高手帮我指点改正。

package pagerank;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Hashtable;
/*
linkmaptest.txt内容为
d00000-0 d00000-0 d00000-1 d00000-2
d00000-1 d00000-2 d00000-1
d00000-2 d00000-0
d00000-3 
*/
public class PageRank {

	public static void main(String[] args) throws Exception {

		String[] linesarr;
		Hashtable<String, Integer> docIDandNum = new Hashtable<String, Integer>();
		int total = 0;
		int father, son;
		int outdegree = 0;

		// 读取文件,得到docid,计算链接总数total,outdegree在迭代的时候计算
		File linkfile = new File("E:/larbin/linkmaptest.txt");
		BufferedReader linkinput = new BufferedReader(new FileReader(linkfile));
		String line = linkinput.readLine();
		while (line != null) {
			++total;
			linesarr = line.split(" ");
			if (linesarr.length > 0) {
				// outdegree = linesarr.length - 1;
				// for(int j = 1; j <= linesarr.length - 1; ++j) {
				// if(linesarr[j].equals(linesarr[0]))
				// outdegree--;
				// }
				if (linesarr[0] != null) {
					docIDandNum.put(linesarr[0], total);
					// System.out.println("链接" + linesarr[0] + "的出度为" + outdegree);
				}
			}
			linesarr = null;
			line = linkinput.readLine();
		}
		linkinput.close();
		// System.out.println("链接总数为:" + total);

		if (total > 0) {
			// pageRank[]存放PR值
			float[] pageRank = new float[total + 1]; 

			// 链入页面的计算总和
			float[] prTmp = new float[total + 1]; 

			 // 设置pageRank[]初始值为1.0f
			for (int i = 1; i <= total; ++i) {
				pageRank[i] = 1.0f;
				prTmp[i] = 0.0f;
			}

			 // 当前页面的PR值
			float fatherRank = 1f;

			// 阻尼系数d或称为alpha
			float alpha = 0.85f; 

			// 进行10次迭代
			for (int iterator = 0; iterator < 10; iterator++) { 
				long startTime = System.currentTimeMillis();

				linkinput = new BufferedReader(new FileReader(linkfile));
				line = linkinput.readLine();
				// 读出docid和outdegree和sons
				while (line != null) { 
					linesarr = line.split(" ");
					if (linesarr.length > 0) {
						outdegree = linesarr.length - 1;
						for (int j = 1; j <= linesarr.length - 1; ++j) {
							 // 指向自身的链接无效,不计算在内
							if (linesarr[j].equals(linesarr[0]))
								outdegree--;
						}
					}
					if (outdegree > 0) {
						father = (int) docIDandNum.get(linesarr[0]);
						 // 对应公式中的pr(Ti)/c(Ti),Ti为指向father的页面
						fatherRank = pageRank[father] / outdegree;
						for (int k = 1; k <= linesarr.length - 1; ++k) {
							if (linesarr[k].equals(linesarr[0])) {
								continue;
							}
							son = docIDandNum.get(linesarr[k]);
							if (total >= son && son >= 0) {
								prTmp[son] += fatherRank;
							}
						}
					}
					linesarr = null;
					line = linkinput.readLine();
				}

				// 准备下次迭代的初始值
				for (int i = 1; i <= total; ++i) 	{
					// PR公式1
					// prTmp[i] = 0.15f + alpha * prTmp[i];
					
					// PR公式2
					prTmp[i] = 0.15f / total + alpha * prTmp[i]; 

					// 每次迭代后的真正pr值
					pageRank[i] = prTmp[i]; 

					prTmp[i] = 0.0f;
				}
				// 打印出每次迭代值,此操作耗费时间和内存
				// for (int i = 1; i <= total; ++i)
				// System.out.print(pageRank[i] + " \t ");
				// System.out.println(" ");
				linkinput.close();

				long endTime = System.currentTimeMillis();
				System.out.println("第" + iterator + "次迭代耗时" + (endTime - startTime) + "ms");
			}

			//最终PR值输出至文件
			BufferedWriter newlink = new BufferedWriter(new FileWriter(
					new File("E:/larbin/pageranktest.txt")));
			for (int i = 1; i <= total; ++i) {
				// System.out.println(docIDandNum.toString());
				newlink.write(String.valueOf(pageRank[i]));
				newlink.newLine();
			}
			newlink.flush();
			newlink.close();
			pageRank = null;
			prTmp = null;
		}
	}
}

 

 学java有段时间了,但是总感觉自己不着道,第一次在论坛发帖,也希望大家指出我的很多不规范的地方,给我些改正的建议,分享些经验给新手们,(比如有什么好的书适合我,在编程习惯技巧等方面我应该如何去改正以便更加规范些),谢谢。

   发表时间:2008-07-30  
做个profiling看看瓶颈在哪里,实在不行就先用NIO替换一下吧。
0 请登录后投票
   发表时间:2008-07-30  
这个速度很正常
0 请登录后投票
   发表时间:2008-10-31  
这个好像写得很不错啊,不过我还是没能看太明白,想问一下linkmaptest.txt文件里面的内容是什么意思呢?
0 请登录后投票
   发表时间:2008-11-01  
编码风格不是很好,面向对象的一些原则还没有搞清楚
建议回归基础
0 请登录后投票
   发表时间:2008-11-20  
frenchmay 写道

编码风格不是很好,面向对象的一些原则还没有搞清楚建议回归基础

嗯,谢谢建议
0 请登录后投票
   发表时间:2008-11-20  
phz50 写道

这个好像写得很不错啊,不过我还是没能看太明白,想问一下linkmaptest.txt文件里面的内容是什么意思呢?

就是页面之间的链接关系啊
0 请登录后投票
   发表时间:2008-11-20  
对, 怎么全堆到main里了
0 请登录后投票
   发表时间:2008-12-02  
这么晦涩的代码也给你翻译过来了,呵呵
你这性能有比较大的问题
检查IO,有没有反复读?
检查一些反复调用的计算

原始代码中BuildIndex很有用的,你再瞅瞅
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics