PageRank算法的原理和源代码实现（java）

参考文章：

理论：竹笋炒肉: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有段时间了，但是总感觉自己不着道，第一次在论坛发帖，也希望大家指出我的很多不规范的地方，给我些改正的建议，分享些经验给新手们，（比如有什么好的书适合我，在编程习惯技巧等方面我应该如何去改正以便更加规范些），谢谢。

评论

9 楼 opencvImage 2012-05-06  

你好！请问能不能把你Lucene结合ＰＲ进行排序优化的代码贴出来分享呢？不知道怎么把两者结合……谢谢啦！

8 楼 plantegg 2008-12-02  

这么晦涩的代码也给你翻译过来了，呵呵
你这性能有比较大的问题
检查IO，有没有反复读？
检查一些反复调用的计算

原始代码中BuildIndex很有用的，你再瞅瞅

7 楼 mayday85 2008-11-20  

对， 怎么全堆到main里了

6 楼 chencang 2008-11-20  

phz50 写道

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

就是页面之间的链接关系啊

5 楼 chencang 2008-11-20  

frenchmay 写道

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

嗯，谢谢建议

4 楼 frenchmay 2008-11-01  

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

3 楼 phz50 2008-10-31  

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

2 楼 shellkk 2008-07-30  

这个速度很正常

1 楼 yining 2008-07-30  

做个profiling看看瓶颈在哪里，实在不行就先用NIO替换一下吧。