论坛首页 → Java版 → OO →

List数据对比筛选，如何才能达到最佳效率？

 
浏览 3483 次
主题：List数据对比筛选，如何才能达到最佳效率？
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • tomkoo
  • 等级: 三星会员
  • 用户头像
  • 性别:
  • 文章: 37
  • 积分: 333
  • 来自: 深圳
时间：2007-10-11
引用
在实际的开发中，经常会晕倒这样的问题，有两个List的数据，需要对这两个List的数据进行对比，然后筛选出需要的对象。

例如：财务中的对账,数据源一个是银行日记账（aList），一个是银行对帐单（bList），业务操作就是把两个List里面金额相同的记录筛选掉，剩下金额不相等的。

在实际开发中我目前知道有两个方式（假设两个List各有1000条数据）：

1、最简单的就是用双重循环进行比较，虽然简单，但是如果两个List的数据量都很大，那么运行时间将成数量级增长。循环次数为1000*1000

2、把一个List通过循环放入Map中，把需要比较的字段作为Map的Key，然后循环另外一个List，到Map里面去匹配。 

for(A a : aList){
   map.put(a.amount,a);
}

for(B b : bList){
   A a = map.get(b.amount);
   if(a==null){
      //a==null则说明没有同b匹配的项
   }else{
      //a!=null则说明匹配上了
   }
}


由于在Map中取数非常快，主要的耗时就在业务处理和循环上。循环次数为1000*2

但是第2种方法还是有不足的地方：

1、当比较的值有相同的时候，由于Key必须唯一，所以后面的值会覆盖掉前面的数据
2、当比较的内容比较复杂，或者是多项的时候，就比较难处理


我想在平时开发中大家应该都会遇到这样的问题吧，不知道大家有没有更好的方法来解决这个问题！！
返回顶楼
   
  • lovegiggs
  • 等级: 初级会员
  • 用户头像
  • 性别:
  • 文章: 3
  • 积分: 0
  • 来自: 上海
时间：2007-10-12
引用
可以考虑利用数据库资源来比较，写个存储过程来实现，通过内存来跑

对于存在差别的记录加上标记，然后就可一通过简单查询就可以得到

账单的平衡与否。
返回顶楼
   
0 请登录后投票
  • kidd3166
  • 等级: 初级会员
  • 用户头像
  • 性别:
  • 文章: 5
  • 积分: 0
  • 来自: 广州
时间：2007-10-12
引用
你这样属于自定义对象集合，我曾经用过比较器来比较2个集合
上网查找一个关于Comparable,Comparator 的资料吧
返回顶楼
   
0 请登录后投票
  • tomkoo
  • 等级: 三星会员
  • 用户头像
  • 性别:
  • 文章: 37
  • 积分: 333
  • 来自: 深圳
时间：2007-10-12
引用
Comparable实现排序，比较时还是需要循环啊
返回顶楼
   
0 请登录后投票
  • lighter
  • 等级: 二钻会员
  • 用户头像
  • 性别:
  • 文章: 626
  • 积分: 1205
  • 来自: 广州
时间：2007-10-13
引用
tomkoo 写道
Comparable实现排序，比较时还是需要循环啊

Commons 里面可能有你想要的答案,看一下CollectionUtils类吧 
String[] arrayA = new String[] { "1", "2", "3", "3", "4", "5" };
String[] arrayB = new String[] { "3", "4", "4", "5", "6", "7" };

List a = Arrays.asList( arrayA );
List b = Arrays.asList( arrayB );

Collection union = CollectionUtils.union( a, b );
Collection intersection = CollectionUtils.intersection( a, b );
Collection disjunction = CollectionUtils.disjunction( a, b );
Collection subtract = CollectionUtils.subtract( a, b );

Collections.sort( union );
Collections.sort( intersection );
Collections.sort( disjunction );
Collections.sort( subtract );


System.out.println( "A: " + ArrayUtils.toString( a.toArray( ) ) );
System.out.println( "B: " + ArrayUtils.toString( b.toArray( ) ) );
System.out.println( "Union: " + ArrayUtils.toString( union.toArray( ) ) );
System.out.println( "Intersection: " + 
                    ArrayUtils.toString( intersection.toArray( ) ) );
System.out.println( "Disjunction: " + 
                    ArrayUtils.toString( disjunction.toArray( ) ) );
System.out.println( "Subtract: " + ArrayUtils.toString( subtract.toArray( ) ) );


The previous example performs these four operations on two List objects, a and b, printing the results with ArrayUtils.toString( ): 

A: {1,2,2,2,3,3,4,5}
B: {3,4,4,5,6,7}
Union: {1,2,2,2,3,3,4,4,5,6,7}
Intersection: {3,4,5}
Disjunction: {1,2,2,2,3,4,6,7}
Subtract: {1,2,2,2,3}
返回顶楼
   
0 请登录后投票
  • tomkoo
  • 等级: 三星会员
  • 用户头像
  • 性别:
  • 文章: 37
  • 积分: 333
  • 来自: 深圳
时间：2007-10-13
引用
lighter 写道
tomkoo 写道
Comparable实现排序，比较时还是需要循环啊

Commons IO 里面可能有你想要的答案,看一下CollectionUtils类吧 
String[] arrayA = new String[] { "1", "2", "3", "3", "4", "5" };
String[] arrayB = new String[] { "3", "4", "4", "5", "6", "7" };

List a = Arrays.asList( arrayA );
List b = Arrays.asList( arrayB );

Collection union = CollectionUtils.union( a, b );
Collection intersection = CollectionUtils.intersection( a, b );
Collection disjunction = CollectionUtils.disjunction( a, b );
Collection subtract = CollectionUtils.subtract( a, b );

Collections.sort( union );
Collections.sort( intersection );
Collections.sort( disjunction );
Collections.sort( subtract );


System.out.println( "A: " + ArrayUtils.toString( a.toArray( ) ) );
System.out.println( "B: " + ArrayUtils.toString( b.toArray( ) ) );
System.out.println( "Union: " + ArrayUtils.toString( union.toArray( ) ) );
System.out.println( "Intersection: " + 
                    ArrayUtils.toString( intersection.toArray( ) ) );
System.out.println( "Disjunction: " + 
                    ArrayUtils.toString( disjunction.toArray( ) ) );
System.out.println( "Subtract: " + ArrayUtils.toString( subtract.toArray( ) ) );


The previous example performs these four operations on two List objects, a and b, printing the results with ArrayUtils.toString( ): 

A: {1,2,2,2,3,3,4,5}
B: {3,4,4,5,6,7}
Union: {1,2,2,2,3,3,4,4,5,6,7}
Intersection: {3,4,5}
Disjunction: {1,2,2,2,3,4,6,7}
Subtract: {1,2,2,2,3}



还真的没有好好使用过CollectionUtils，谢谢！这就看去！
返回顶楼
   
0 请登录后投票
  • tomkoo
  • 等级: 三星会员
  • 用户头像
  • 性别:
  • 文章: 37
  • 积分: 333
  • 来自: 深圳
时间：2007-10-13
引用
抽出时间看了一下ColletionUtils类的源代码，发现，union,intersection,disjunction,subtract等方法的实现方式都是我前面提到的第二种方式，利用Map来进行一系列的比较操作。不过用得可比我的例子灵活多了。看了有种豁然开朗的感觉。

谢谢楼上的！
返回顶楼
   
0 请登录后投票
  • phantomhu
  • 等级: 初级会员
  • 用户头像
  • 性别:
  • 文章: 15
  • 积分: 30
  • 来自: 北京
时间：2007-10-15
引用
lighter 写道
tomkoo 写道
Comparable实现排序，比较时还是需要循环啊

Commons 里面可能有你想要的答案,看一下CollectionUtils类吧 
String[] arrayA = new String[] { "1", "2", "3", "3", "4", "5" };
String[] arrayB = new String[] { "3", "4", "4", "5", "6", "7" };

List a = Arrays.asList( arrayA );
List b = Arrays.asList( arrayB );

Collection union = CollectionUtils.union( a, b );
Collection intersection = CollectionUtils.intersection( a, b );
Collection disjunction = CollectionUtils.disjunction( a, b );
Collection subtract = CollectionUtils.subtract( a, b );

Collections.sort( union );
Collections.sort( intersection );
Collections.sort( disjunction );
Collections.sort( subtract );


System.out.println( "A: " + ArrayUtils.toString( a.toArray( ) ) );
System.out.println( "B: " + ArrayUtils.toString( b.toArray( ) ) );
System.out.println( "Union: " + ArrayUtils.toString( union.toArray( ) ) );
System.out.println( "Intersection: " + 
                    ArrayUtils.toString( intersection.toArray( ) ) );
System.out.println( "Disjunction: " + 
                    ArrayUtils.toString( disjunction.toArray( ) ) );
System.out.println( "Subtract: " + ArrayUtils.toString( subtract.toArray( ) ) );


The previous example performs these four operations on two List objects, a and b, printing the results with ArrayUtils.toString( ): 

A: {1,2,2,2,3,3,4,5}
B: {3,4,4,5,6,7}
Union: {1,2,2,2,3,3,4,4,5,6,7}
Intersection: {3,4,5}
Disjunction: {1,2,2,2,3,4,6,7}
Subtract: {1,2,2,2,3}




Collections是那个包里面的 java.util.Collections的sort不能用在Collection对象上啊
返回顶楼
   
0 请登录后投票
  • lighter
  • 等级: 二钻会员
  • 用户头像
  • 性别:
  • 文章: 626
  • 积分: 1205
  • 来自: 广州
时间：2007-10-15
引用
phantomhu 写道

Collections是那个包里面的 java.util.Collections的sort不能用在Collection对象上啊

嗯,你说的对,可以强制转化一下,呵呵: 
Collections.sort((List)union);
Collections.sort((List)intersection);
Collections.sort((List)disjunction);
Collections.sort((List)subtract);
返回顶楼
   
0 请登录后投票
  • hamlet
  • 等级: 初级会员
  • 用户头像
  • 性别:
  • 文章: 15
  • 积分: 0
  • 来自: 上海
时间：2007-10-17
引用
CollectionUtils 好像不能满足lz的需求吧，
lz的意思是按照数据对象的某一属性进行比较，
而CollectionUtils中 则是按照对象在内存中的Id进行比较，
得到的结果很有可能会不同，除非重写数据对象的equal()方法。
看看CollectionUtils 的getCardinalityMap方法和getFreq()方法就知道了 
public static Map getCardinalityMap(final Collection col) {
        HashMap count = new HashMap();
        Iterator it = col.iterator();
        while(it.hasNext()) {
            Object obj = it.next();
            Integer c = (Integer)(count.get(obj));
            if(null == c) {
                count.put(obj,new Integer(1));
            } else {
                count.put(obj,new Integer(c.intValue() + 1));
            }
        }
        return count;
    }


private static final int getFreq(final Object obj, final Map freqMap) {
        try {
            return ((Integer)(freqMap.get(obj))).intValue();
        } catch(NullPointerException e) {
            // ignored
        } catch(NoSuchElementException e) {
            // ignored
        }
        return 0;
    }
返回顶楼
   
0 请登录后投票
 
论坛首页 → Java版 → OO

跳转论坛:
JavaEye推荐