最近需要用PageRank算法实现无向带权图节点的ranking，具体的PageRank算法介绍可以参考维基百科http://en.wikipedia.org/wiki/Pagerank

最初的PageRank算法是针对有向图的，迭代方程为：，其中是顶点的PageRank值，是顶点的出度。

在无向带权图中，改进迭代方程： 其中是边的权重，是顶点的度数。

在实际迭代计算式，选择好的数据结构很重要，上面迭代公式中主要的计算就是边的权重与顶点的度数。使用Map<String, ArrayList<MapEntry>> 来表示边(node1, <node2, weight>)，这样计算权重与度数是都很方便。

实现代码与测试数据可在github上下载:https://github.com/jia1546/PageRank

设计页面时加上了Exit按钮，希望点击之后浏览器页面可以自动关闭。用JavaScript写了下面的脚本：

<script language="javascript" type="text/javascript"> 
function winClose()
{  
	window.close(); 
} 
</script> 

但是发现在Firefox,跟Chrome浏览器中，这段脚本不起作用，上网查了之后发现这段介绍：

Ref:http://hi.baidu.com/suen_%CB%EF/blog/item/bedca57f8932480d28388a49.html

最近用MyEclipse遇到很多诡异的问题，但也都是有迹可循的，比如java类无法自动编译的问题，折腾了一个晚上，算是解决了。这篇博客对这个问题总结得很好：

http://xinkong1010.iteye.com/blog/852162

PS：在JSP文件中调用java类，如果java类不放在package中，调用<<%page import="example">>会显示example can't be resolved.但是把example.java放在包hanle中，调用<<%page import="handle.example">>表不会出错了。

正在做一个交互式网站，需要记住用户的IP来生成user profile，使用JSP的response.getRemoteAddr()可以做到，但是在网上查资料后发现这种方法解决不了客户端使用代理软件来访问网站的问题，这篇文章给出了很好的解决办法：

http://blog.csdn.net/maxracer/article/details/6118460

但是使用上述方法，会出现记录的IP地址为 0:0:0:0:0:1,出现会误以为是IPv6的地址，其实是客户端与服务器使用同一机器的原因，将主机名localhost改为真实IP地址就不会出现这个问题了。这篇文章给出了详细的分析

http://java161.iteye.com/blog/1189279

使用图片作为按钮，点击按钮后都跳转到同一页面，

此时如何判断用户点击的是哪个图片呢？

隐藏标签可以帮上忙了，下面代码中可以使用id来传递value值“next”.在跳转之后的页面中可以使用request.getParameter("id")来获取所要传递的参数值。

<form name="tonext" action="factAssess.jsp" method="post">
	<input type="hidden" name="id" value="next"/>
  	<input type="image" src="next.png" name="nextButton"></input>
</form>

可是要传递的是一个java类型的变量怎么办？自然是：

<% out.print("<td><input type=\"hidden\" name=\"factId\" value='"+factId+"'</input></td>");%>

在这里忘了变量factId需要加上引号'"+factId+"',在跳转后的页面中factId的String值可以正确获取，而使用Integer.parseInt(request.getParameter("factId"))来获取factId的int值总是会出现“Integer parseint NumberFormatException”，花了很长时间才找到错误所在。

Problem Description: Given an array A[1...n] consisting of integers and an integer m. Find three elements in A, so that sum of the three integers in A equals to m. 

for i from 1 to n-2
    do for j from i+1 to n-1
        do for k from j+1 to n
            do if A[i] + A[j] + A[k] = m
                   then print A[i], A[j], A[k]

sort array A
for i from 1 to n-2
    do for j from i+1 to n-1
        do binary_search(A[j+1...n], m-A[i]-[j])

数据结构的编程作业，使用哈希函数实现字典，并且支持插入，删除，查找功能。没有复杂的算法，但是写的过程中还是遇到一些问题。

1. 段错误

程序定义结构体：

struct hashTableEntry
{
    char key[LEN];
    char value[LEN];
};

然后在main()函数中定义 struct hashTableEntry hashTable[12255], 出现段错误，开始怀疑是不是C语言对数组所占的内存空间有限制，后来把hashTable变为全局变量，就没有问题。问超哥才知道堆空间和栈空间的区别，开始忏悔编译原理跟OS怎么学的……下面引用C语言教材关于C程序内存映像的介绍：

一个完成编译的C程序取得并使用4块在逻辑上不同且用于不同目的的内存区域。如上图所示，第一块区域存放程序代码，相邻的一块内存区域是存放全局变量和静态变量的静态存储区。相邻两块分别是“堆”和“栈”。栈用于保存程序的许多运行信息，如函数调用的返回地址，函数的形参，局部变量以及CPU的当前状态。堆是一个自由存储区，程序可以使用C的动态内存分配函数来使用它。

C程序中变量的内存分配方式有以下3种：

1. 从静态存储区分配。程序的全局变量和静态变量都是在静态存储区上分配，且在程序编译时就已经分配好了，在程序运行期间是存在的。只有在程序终止之前被操作系统回收。
2. 在栈上创建。在执行函数调用时，函数内的局部变量及形参都是在栈上创建的，该函数执行结束时，这些内存自动被释放掉。栈内存分配运算置于处理器的指令集中，效率很高，但是容量有限。
3. 从堆上分配。在程序运行期间，用动态内存分配函数来申请的内存都是从堆上分配的。动态内存的生存周期由程序员自己来决定，使用非常灵活，但也容易出现问题。有一点需要程序员时刻牢记：自己要负责在不使用这些内存的时候用free()将其释放，归还系统，以便以后利用，这时防止内存泄漏的必要手段。

2. sscanf() 的使用

以前只用过sprintf()，与printf()的使用方法相同，只是将打印的内容保存到字符串中。sscanf()与scnaf()同理，只是从字符串中按格式读取输入，而不是从终端中读取。基本用法见:http://baike.baidu.com/view/1364018.htm

C代码下载链接：https://github.com/jia1546/dictionary

通常关于矩阵的算法，时间复杂度都是，但是下面两个问题可以有的解法

1.这个问题是数据结构课的 story time 老师让思考的一个问题：

给定一个n*n的矩阵，矩阵中的每个元素都比它左边和上边所有的元素大，利用二分查找的思想判断矩阵中是否存在值K

大家很快说出从对角线上的元素开始判断，可是这样二分判断后，如果值不相等，得到一个L型的子矩阵，递归的过程无法继续，于是老师讲了下面这段话并说出答案：In designing a recursive algorithm, make sure you can repeat the strategy after the base case. 答案是从右上方的元素开始判断，伪代码如下：

Input: a matrix M with n rows and n columns, where M[i][k] < M[i][j], k < j and 
       M[k][j] < M[i][j], k < i. A given number K

Output: "yes", if number K is in the matrix; otherwise, "no"

binary_search_in_Matrix(int row, int column, int K)

if row > n or column < 0 then

return "no"

if K > M[i][j] then

binary_search_in_Matrix(row+1, column, K)

else if K < M[i][j] then

binary_search_in_Matrix(row, column-1, K)

else

return "yes"

最多2*n次基本操作，所以时间复杂度O(n)

2. 另一个相似的问题是《算法导论》上的作业，题目如下：

When an adjacency-matrix representation is used, most graph algorithms require time , but there are some exceptions. Show that determining whether a directed graph G contains a "universal sink" - a vertex with in-degree |V| -1 and out-degree 0 - can be determined in time , given an adjacency matrix of G.

算法伪代码如下：

Input: an adjacency matrix M of graph G

       an array named flag to remember whether a vertx is universal sink

Output: "yes", if G contains an "universal sink"; otherwise, return "no"

while i < n and j < n

do if M[i][j] == 1 then// i can't be universal sink

     i++

     flag[i] <-- false

     else // j can't be universal sink

     j++

     flag[j] <-- false

时间复杂度分析与上面的问题相似，为O(n)

script table 主要用于检测软件的行为是否正确，比如模拟用户登录过程，堆栈操作过程等等。

script table 的格式是：

第一行关键字Script + 测试类的名字 表明这是一个script table

以后的每一行都对应类中的一个行为，并且可以加上关键字check, ensure, reject, show, start 等等来检测行为是否正确执行。这些关键字的含义见：http://fitnesse.org/FitNesse.UserGuide.SliM.ScriptTable 这里主要用到check, check关键字位于第一列，后面是带有返回值的函数，最后是期望输出的值。如果两者相等则此列标识为绿色，否则为红色。

这次的作业是检测 Java 1.7中双端队列(Double Ended Queue)中栈的实现是否正确，所谓双端队列就是可以从队列两端进行元素的插入和删除，如果从一端插入，从另一端删除，则是队列，从同一端删除则是栈。用script table 来检测栈的四种行为：instantiate, push(e), pop(), peek(),同时检查栈是否是LIFO的

用于生成script table的代码为：

!define TEST_SYSTEM {slim}
 
!path /home/jia1546/workspace/Test/bin

!define COLLAPSE_SETUP {true}
!define COLLAPSE_TEARDOWN {true}
 
|import|
|c0403 |

!|Script    |StackMethodTests |
|instantiateMyStack           |
|pushMyStack|1                |
|check      |countOfElements|1|
|check      |peekMyStack    |1|
|check      |peekMyStack    |1|
|check      |popMyStack     |1|
|check      |countOfElements|0|

!|Script    |StackMethodTests|
|instantiateMyStack          |
|pushMyStack|1               |
|pushMyStack|2               |
|pushMyStack|3               |
|check      |popMyStack  |3  |
|check      |popMyStack  |2  |
|check      |popMyStack  |1  |

生成的script table为:

对应测试类的代码为：

package c0403;
import java.util.ArrayDeque;
import java.util.Deque;
import java.math.*;

public class StackMethodTests {
	private int num;
	private Deque<Integer> theStack;
	final int SCALE = 1000;		//define the range of the random integer
	final int TIMES = 100;		//define the times used in Different-But-Equivalent technique
	
	public void instantiateMyStack(){
		//theStack = StaticStack.myStack;
		theStack = new ArrayDeque<Integer>();
	}
	
	public void pushMyStack(int num){
		theStack.addFirst(num);
	}
	
	public int popMyStack(){
		return theStack.removeFirst();
	}
	
	public int peekMyStack(){
		return theStack.peekFirst(); 
	}
	
	public int countOfElements(){
		return theStack.size();
	}
	
	/*
	 * push 100 elements and then pop those 100 elements
	 */
	public void pushThenPop(){
		for(int i=0; i<TIMES; i++){
			int n = (int)(Math.random() * SCALE);
			this.pushMyStack(n);
		}
		for(int i=0; i<TIMES; i++){
				this.popMyStack();
		}
	}
	
	/*
	 * push and pop a random element 100 times
	 */
	public void pushAndPop(){
		for(int i=0; i<TIMES; i++){
			int n = (int)(Math.random() * SCALE);
			this.pushMyStack(n);
			this.popMyStack();
		}
	}
}

测试结果为:

PS: 最近的deadline太多了，接下来是有关performance test的测试工具JMemter的话题。

FitNesse是一个开源测试框架，主要用于接受测试，也就是比对开发软件实际输出与期望输出是否相同。FitNesse最大的特点在于本身是一个简单的web sever, 在项目初设计测试用例时，可以通过编写网页的形式来展示，这样极大方便非编程人员的测试工作。

下面通过一个最简单的例子---Decision Table Test来验证除法运算正确性，讲述FitNesse的使用方法及工作原理

1. 下载及安装FitNesse可参考：http://fitnesse.org/FitNesse.UserGuide.DownloadingAndInstallingFitNesse

2. 编写web page, 设计测试用例

这里测试用例采用判定表的形式，前面几列对应输入，也就是对应测试类中的Set方法，最后一列对应输出，对应需要测试类中的计算。网页中编写代码为：

!define TEST_SYSTEM {slim}

!path /home/jia1546/workspace/Test/bin

!|c0403.Division                |
|numerator|denominator|quotient?|
|10       |2          |5.0      |
|12.6     |3          |4.2      |
|100      |4          |25.0     |

第一行：使用FitNesse的slim模块，也就是使用网页的形式描述测试用例

第二行：测试类**.class所在的路径

表名：测试类的名称，c0403 package下的Division这个类

表头：numerator, denominator 对应类中的setNumerator(), setDeniminator()这两个方法，quotient对应double quotient()这个方法，注意quotient后面有个问号，说明这个方法是有返回值的。

保存后对应的网页：

下面是测试类的代码

package c0403;
import fit.ColumnFixture;

public class Division extends ColumnFixture{
	private double numerator;
	private double denominator;
	
	public void setNumerator(double numerator) {
		this.numerator = numerator;
	}
	public void setDenominator(double denominator) {
		this.denominator = denominator;
	}
	
	public double quotient(){
		return numerator / denominator;
	}
}

点Test按钮则开始测试，测试结果如下：

测试用例中的绿色显示结果正确。

到这里你也许猜出了这个测试工具的工作原理了吧，Slim根据网页中的classpath去调用测试类，将测试用例的输入给测试类中对应的set方法，然后slim将程序中对应方法的实际输出跟测试用例的期望输出相比较，如果相同，则测试用例通过。那如何将HTML中表单的值正确解析并输入到程序中呢，注意到程序中的import跟extend，这就告诉测试类该如何处理获得的表单数据。