为什么用java实现时要比老师用C++实现时要快一个量级的时间呢？

Question

public class UnionFind {

	private int[] id;
	private int count;
	
	public UnionFind(int n){
		
		count = n;
		id = new int[n];
		for(int i = 0 ; i < n ; i++){
			id[i] = i;
		}
	}
	
	public int find( int p ){
		
		assert( p >= 0 && p < count);
		return id[p];
	}
	
	public boolean isConnected(int p, int q){
		
		return find(p) == find(q);
	}
	
	public void unionElements(int p, int q){
		
		int pId = find(p);
		int qId = find(q);
		if(pId == qId){
			return;
		}
		
		for(int i = 0 ; i < count ; i++){
			if(id[i] == pId){
				id[i] = qId;
			}
		}
	}
}

import java.util.Random;

public class Main {

	public static void main(String[] args){
		
		int n = 10000;
		UnionFind uf = new UnionFind(n);
		
		Random random = new Random(System.currentTimeMillis());
		
		long start = System.currentTimeMillis();
		for(int i = 0 ; i < n ; i++){
			int a = random.nextInt(n);
			int b = random.nextInt(n);
			
			uf.unionElements(a, b);
		}
		
		for(int i = 0 ; i < n ; i++){
			int a = random.nextInt(n);
			int b = random.nextInt(n);
			
			uf.isConnected(a, b);
		}
		
		long end = System.currentTimeMillis();
		
		System.out.println((double)(end-start)/1000);
	}
}

Answer 1

liuyubobobo 2017-04-07 13:26:17

有可能你的计算机比我的计算机快一个量级吧！：）我录课用的计算机很老啦，是一台2013年的macbook air：）

• 提问者 喜欢蹲门槛的猫 #1

  哦哦，谢谢老师哈，可是还有个问题哈，为什么我用uf2的方法实现比用uf1的方法实现在10万量级的时候要慢一点呢，而且量级越大慢的越多

• liuyubobobo 回复 提问者 喜欢蹲门槛的猫 #2

  那应该是uf2的实现有一些问题哦。不太应该哦。再查查看自己的代码实现有没有问题？尤其可以在代码内加入更多的时间测试，看看具体是那一部分操作拖慢了整体代码的执行速度？
  
  加油！

• 提问者 喜欢蹲门槛的猫 回复 liuyubobobo #3

  老师，我按照您的做法去设置了更多的时间设置，代码和视频对比了下，是完全一样的，最后检查出来UF2的并操作是远快于UF1的并操作的，但是随着量级的增加，特别是在6万以上时，UF2的总体时间就慢于UF1了，应该是UF2的查操作花了很多的时间，会不会是Find方法中的while循环的影响呀？还是其他的什么原因呢？不是很明白了/(ㄒoㄒ)/~~

点开查看后面2条评论