|
后来因为程序运行的太快，又增加了皇后的数目，用9皇后来测试，这样需要输出352个解了，我仍然没有意识到输出对运行时间的影响。直到今天中午多放了一个皇后的时候，才意识到问题的严重性：java版运行10皇后如果不输出结果只需要30~40毫秒，而输出结果的情况下需要500毫秒左右，输出成了速度瓶颈。把前面的测试全部去掉结果输出部分重新测一遍吧： java版：   public class queens  { static int q=10; static int[] i=new int[q]; static int count=0;  public static void main(String[] args){ long t = System.currentTimeMillis(); scan(0); System.out.println("totle results:"+count); System.out.println("totle time:"+(System.currentTimeMillis()-t)); } private static void scan(int n){ if (n==q){// for (int k=0;k<q;k++) System.out.print(i[k]+(k==q-1?"\n":",")); count++; return; } i[n]=0; while(i[n]<q){ i[n] = i[n]+1; if (check(n)){ scan(n+1); } } } private static boolean check(int n){ for(int j=0;j<n;j++){ if (i[j]==i[n] || i[j]-i[n]==j-n || i[j]-i[n]==n-j ){ return false; } } return true; }}javascript（DHTML）版 <SCRIPT LANGUAGE="JavaScript"><!-- var q=10 var i=[] var count=0 var d = new Date(); scan(0) document.write("totle results:"+count+"<br>") document.write("time used:"+(new Date()-d)+"<br>") function scan(n){ if (n==q){ // document.write(i+"<br>") count++ return } i[n]=0 while(i[n]<q){ i[n] = i[n]+1 if (check(n)){ scan(n+1) } } } function check(n){ for (var j=0; j<n;j++) if (i[j]==i[n] || i[j]-i[n]==j-n || i[j]-i[n]==n-j ) return false return true } //--> </SCRIPT> groovy版 int q=10int[] i=new int[q]int count=0long t = System.currentTimeMillis();scan(0)println("totle results:"+count)println("totle time:"+(System.currentTimeMillis()-t));def scan(n){ if (n==q){// println(i.toList()) count++ return } i[n]=0 while(i[n]<q){ i[n] = i[n]+1 if (check(n)) scan(n+1) }}def check(n){ if (n>0) for (j in 0..<n) if (i[j]==i[n] || i[j]-i[n]==j-n || i[j]-i[n]==n-j ) return false return true}javascript（Rhino）版 var q=10var i=[] var count=0 var d = new Date(); scan(0) print("totle results:"+count) print("time used:"+(new Date()-d)) function scan(n){ if (n==q){ // print(i) count++ return } i[n]=0 while(i[n]<q){ i[n] = i[n]+1 if (check(n)){ scan(n+1) } } } function check(n){ for (var j=0; j<n;j++) if (i[j]==i[n] || i[j]-i[n]==j-n || i[j]-i[n]==n-j ) return false return true } 其中javascript版由于在IE上运行的时间刚好超过5秒，会收到一个警告，所以是在firefox上测的。 在我的笔记本上测试结果是： java 版: ---------- run ---------- totle results:724 totle time:40 Normal Termination 输出完成(耗时 0 秒)。 javascript（DHTML）版 totle results:724 time used:4977 groovy版 用groovy命令运行： ---------- run ---------- totle results:724 totle time:31095 Normal Termination 输出完成(耗时 32 秒)。 用groovyconsole运行或者编译成java class后用java命令运行的结果也差不多，都在30～36秒之间。 javascript（Rhino）版 ---------- run ---------- totle results:724 time used:3685 Normal Termination 输出完成(耗时 4 秒)。 结果是：Rhino运行javascript脚本比firefox快一点（而firefox似乎又比IE快一点），总的来说，在这个测试上javascript比java慢一个数量级，而groovy则比javascript慢一个数量级 。
再做一点点优化：
function check(n){ for (var j=0; j<n;j++) if (i[j]==i[n] || i[j]-i[n]==j-n || i[j]-i[n]==n-j ) return false return true } 改为 function check(n){ for (var j=0,c=i[n],b=n; j<n;j++,b--){ var d = i[j]; if (d==c) return false var a = d-c if (a==b||a==-b) return false } return true } 只是少访问几次数组，少做几次减法运算，好像差别不大。但是由于check函数处在循环的最里层，优化的结果是在Rhino下面算11皇后的时候快了一倍左右，在cscript下面没有那么突出，但也明显也快了不少。 作者Blog：http://blog.csdn.net/emu/
|
|
|
