论坛首页 → Java企业应用论坛 →

集合比较算法（Java）

浏览 6859 次
锁定老帖子 主题：集合比较算法（Java）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (15) :: 隐藏帖 (0)
作者 正文
  • dongliwei122
  • 等级: 初级会员
  • 性别:
  • 文章: 25
  • 积分: 70
  • 来自: 北京
   发表时间：2009-03-28   最后修改：2009-03-28
最近做了一个小测试，对两个集合的比较，目的是想删除出两个集合相同的数据。
分别用List、Map、和Set进行测试
利用List比较
10000用户的数据（6000相同的用户,4000不同的用户），完成比较的时间共耗时1531毫秒
100000用户的数据（60000相同的用户,40000不同的用户），完成比较的时间共耗时143735毫秒
利用Map比较
10000用户的数据（60000相同的用户,40000不同的用户），完成比较的时间共耗时172毫秒
100000用户的数据（60000相同的用户,40000不同的用户），完成比较的时间共耗时359毫秒
利用Set比较
10000用户的数据（60000相同的用户,40000不同的用户），完成比较的时间共耗时78毫秒
100000用户的数据（60000相同的用户,40000不同的用户），完成比较的时间共耗时156毫秒 
package com.test;

/**
 * 进行比较的基础数据对象
 * <br>
 *文件名：User.java<br>
 *@author 董利伟<br>
 *版本:<br>
 *描述：<br>
 *创建时间:Mar 25, 2009 9:06:26 PM<br>
 *文件描述：<br>
 *修改者：<br>
 *修改日期：<br>
 *修改描述：<br>
 */
public class User {

	private String name = "";
	private String id = "";
	
	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public String getId() {
		return id;
	}

	public void setId(String id) {
		this.id = id;
	}

	public String getKey(){
		return this.name + "&" + this.id;
	}
	
	public int hashCode(){
		int hash = 1;
		hash += this.id.hashCode();
		hash += this.name.hashCode();
		return hash;
	}
}


package com.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 * 主要用于初始化集合(其中List的数据是从Map中获取是因为数据在Map中是无序的)
 * <br>
 *文件名：CreateUser2.java<br>
 *@author 董利伟<br>
 *版本:<br>
 *描述：<br>
 *创建时间:Mar 25, 2009 9:33:17 PM<br>
 *文件描述：<br>
 *修改者：<br>
 *修改日期：<br>
 *修改描述：<br>
 */
public class CreateUser2 {

	public static Map UserMapA = new HashMap();
	public static Map UserMapB = new HashMap();
	
	
	public static HashSet UserSetA = new HashSet();
	public static HashSet UserSetB = new HashSet();
	
	public static List UserListA = new ArrayList();
	public static List UserListB = new ArrayList();
	
	public static int aa = 60000;//相同的用户数
	public static int bb = 40000;//不相同的用户数
	
	public static void CreateUserList(){
		
		String name = "张三";
		int count = 0;
		//制作600个相同的用户
		for(int i = 0 ; i < aa ;i++){
	        User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserListA.add(user);
	        UserListB.add(user);
	        count++;
		}
		//制作400个不相同的用户
		int test = count;
		for(int i = test ; i < bb +test ;i++){
			User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserListA.add(user);
	        count++;
		}
		test = count;
		for(int i = test ; i < bb +test ;i++){
			User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserListB.add(user);
	        count++;
		}
	}
	
	public static void CreateUserMap(){
		
		String name = "张三";
		int count = 0;
		//制作600个相同的用户
		for(int i = 0 ; i < aa ;i++){
	        User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserMapA.put(user.getKey(), user);
	        UserMapB.put(user.getKey(), user);
	        count++;
		}
		//制作400个不相同的用户
		int test = count;
		for(int i = test ; i < bb +test ;i++){
			User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserMapA.put(user.getKey(), user);
	        count++;
		}
		test = count;
		for(int i = test ; i < bb +test ;i++){
			User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserMapB.put(user.getKey(), user);
	        count++;
		}
	}
	
	public static void CreateUserSet(){
		
		String name = "张三";
		int count = 0;
		//制作600个相同的用户
		for(int i = 0 ; i < aa ;i++){
	        User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserSetA.add(user);
	        UserSetB.add(user);
	        count++;
		}
		//制作400个不相同的用户
		int test = count;
		for(int i = test ; i < bb +test ;i++){
			User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserS[b][/b]etA.add(user);
	        count++;
		}
		test = count;
		for(int i = test ; i < bb +test ;i++){
			User user = new User();
	        user.setId(i+"");
	        user.setName(name+i);
	        UserSetB.add(user);
	        count++;
		}
	}
}


package com.test;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;

/**
 * 对List测试
 * <br>
 *文件名：Test.java<br>
 *@author 董利伟<br>
 *版本:<br>
 *描述：<br>
 *创建时间:Mar 25, 2009 8:16:21 PM<br>
 *文件描述：<br>
 *修改者：<br>
 *修改日期：<br>
 *修改描述：<br>
 */
public class TestList {

	public static void execute(){
		
		List test = new ArrayList();
		for(int  i = 0 ; i < CreateUser2.UserListA.size();i++){
			test.add(CreateUser2.UserListA.get(i));
		}
		CreateUser2.UserListA.removeAll(CreateUser2.UserListB);
		CreateUser2.UserListB.removeAll(test);
	}
	
	public static void main(String[] args) {
		long begin = new Date().getTime();
		CreateUser2.CreateUserList();
		long end = new Date().getTime();
		System.out.println("形成模拟数据共耗时" + (end - begin) + "毫秒");
		System.out.println("运算前");
		System.out.println("CreateUser2.UserListA.size()=" + CreateUser2.UserListA.size());
		System.out.println("CreateUser2.UserListB.size()=" + CreateUser2.UserListB.size());
		begin = new Date().getTime();
		execute();
		end = new Date().getTime();
		System.out.println("比较用户共耗时" + (end - begin) + "毫秒");
		System.out.println("运算后");
		System.out.println("CreateUser2.UserListA.size()=" + CreateUser2.UserListA.size());
		System.out.println("CreateUser2.UserListB.size()=" + CreateUser2.UserListB.size());
	}

}


package com.test;

import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import com.test.CreateUser2;

/**
 * 对Map测试<br>
 *文件名：Test.java<br>
 *@author 董利伟<br>
 *版本:<br>
 *描述：<br>
 *创建时间:Mar 25, 2009 8:16:21 PM<br>
 *文件描述：<br>
 *修改者：<br>
 *修改日期：<br>
 *修改描述：<br>
 */
public class TestMap {

	public static void execute(){
		
		
		//备份用户组b
		Map m = new HashMap();
		Iterator itt = CreateUser2.UserMapB.entrySet().iterator();
        while (itt.hasNext()) {
            Map.Entry entry = (Map.Entry) itt.next();
            Object key = entry.getKey(); 
            Object value = entry.getValue(); 
            m.put(key, value);
        }
        
        Iterator it = CreateUser2.UserMapA.entrySet().iterator();
		int count = 0;
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            Object key = entry.getKey(); 
            if(CreateUser2.UserMapB.get(key)!= null){
            	count++;
            	CreateUser2.UserMapB.remove(key);
            }
        }
        Iterator itm = m.entrySet().iterator();
        while (itm.hasNext()) {
            Map.Entry entry = (Map.Entry) itm.next();
            Object key = entry.getKey(); 
            if(CreateUser2.UserMapA.get(key)!= null){
            	count++;
            	CreateUser2.UserMapA.remove(key);
            }
        }
        System.out.println(count);
	}

	public static void main(String[] args) {
		long begin = new Date().getTime();
		CreateUser2.CreateUserMap();
		long end = new Date().getTime();
		System.out.println("形成模拟数据共耗时" + (end - begin) + "毫秒");
		System.out.println("运算前");
		System.out.println("CreateUser2.UserMapA.size()=" + CreateUser2.UserMapA.size());
		System.out.println("CreateUser2.UserMapA.size()=" + CreateUser2.UserMapB.size());
		begin = new Date().getTime();
		execute();
		end = new Date().getTime();
		System.out.println("比较用户共耗时" + (end - begin) + "毫秒");
		System.out.println("运算后");
		System.out.println("CreateUser2.UserMapA.size()=" + CreateUser2.UserMapA.size());
		System.out.println("CreateUser2.UserMapB.size()=" + CreateUser2.UserMapB.size());
	}

}


package com.test;

import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * 对Set测试<br>
 *文件名：TestSet.java<br>
 *@author 董利伟<br>
 *版本:<br>
 *描述：<br>
 *创建时间:Mar 25, 2009 9:40:40 PM<br>
 *文件描述：<br>
 *修改者：<br>
 *修改日期：<br>
 *修改描述：<br>
 */
public class TestSet {

	public static void execute(){
		
		
		//备份用户组b
		Set m = new HashSet();
		Iterator itt = CreateUser2.UserSetA.iterator();
        while (itt.hasNext()) {
        	User user = (User) itt.next();
            m.add(user);
        }
        CreateUser2.UserSetA.removeAll(CreateUser2.UserSetB);
        CreateUser2.UserSetB.removeAll(m);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long begin = new Date().getTime();
		CreateUser2.CreateUserSet();
		long end = new Date().getTime();
		System.out.println("形成模拟数据共耗时" + (end - begin) + "毫秒");
		System.out.println("运算前");
		System.out.println("CreateUser2.UserSetA.size()=" + CreateUser2.UserSetA.size());
		System.out.println("CreateUser2.UserSetB.size()=" + CreateUser2.UserSetB.size());
		begin = new Date().getTime();
		execute();
		end = new Date().getTime();
		System.out.println("比较用户共耗时" + (end - begin) + "毫秒");
		System.out.println("运算后");
		System.out.println("CreateUser2.UserSetA.size()=" + CreateUser2.UserSetA.size());
		System.out.println("CreateUser2.UserSetB.size()=" + CreateUser2.UserSetB.size());
	}

}
返回顶楼
         
  • duooluu
  • 等级: 初级会员
  • 性别:
  • 文章: 262
  • 积分: 78
  • 来自: 杭州
   发表时间：2009-03-28  
ArrayList内部是一个数组，删除后还要将后面的元素向前移动
HashSet内部也是一个HashMap，你后面两个测试相差一倍，TestMap应该还能优化
返回顶楼
          回帖地址
0 请登录后投票
  • mewleo
  • 等级: 一星会员
  • 性别:
  • 文章: 119
  • 积分: 164
  • 来自: 济南
   发表时间：2009-03-28  
避免比较对象，还是比数字好。
返回顶楼
          回帖地址
0 请登录后投票
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2009-03-30  
引用
#     public int hashCode(){ 
#         int hash = 1; 
#         hash += this.id.hashCode(); 
#         hash += this.name.hashCode(); 
#         return hash; 
#     }

这个hashcode很强大~~
返回顶楼
          回帖地址
0 请登录后投票
  • allenny
  • 等级: 初级会员
  • 性别:
  • 文章: 90
  • 积分: 60
  • 来自: 苏州
   发表时间：2009-03-31  
我还以为是DNA的算法呢
返回顶楼
          回帖地址
0 请登录后投票
  • aninfeel
  • 等级: 初级会员
  • 性别:
  • 文章: 207
  • 积分: 10
  • 来自: 广州
   发表时间：2009-04-01  
无序或单向肯定比不上有序多向的，真要比的话应该把添加的时间也计算在内。
返回顶楼
          回帖地址
0 请登录后投票
  • myworkfirst
  • 等级: 初级会员
  • 文章: 305
  • 积分: 67
   发表时间：2009-07-07  
   是否真正都删除了相同的数据，有待怀疑。

认真检查下User类
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → Java企业应用版

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