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

在实际的开发中，经常会晕倒这样的问题，有两个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、当比较的内容比较复杂，或者是多项的时候，就比较难处理


我想在平时开发中大家应该都会遇到这样的问题吧，不知道大家有没有更好的方法来解决这个问题！！

评论

12 楼 抛出异常的爱 2008-01-18  

要想对的快....要把list先排了序才可以...
用set treemap之类的东西存放数据
这样才不用每次遍历

11 楼 red008 2008-01-18  

把2个list都加到一个新的set中去，这个set里面就全是不重复的数据了。
代码只需要2行，看着也舒服。

10 楼 Godlikeme 2008-01-18  

tomkoo 写道

在实际的开发中，经常会晕倒这样的问题，有两个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、当比较的内容比较复杂，或者是多项的时候，就比较难处理


我想在平时开发中大家应该都会遇到这样的问题吧，不知道大家有没有更好的方法来解决这个问题！！

第一种方法, 两个列表金额为Key,List为Value往 HashMap里面放就可以了。O(2n)
这种问题自己思考下吧，不要总期望找现成的。

9 楼 hamlet 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 {
                [b]count.put(obj,new Integer(c.intValue() + 1))[/b];
            }
        }
        return count;
    }

private static final int getFreq(final Object obj, final Map freqMap) {
        try {
            return ((Integer)([b]freqMap.get(obj)[/b])).intValue();
        } catch(NullPointerException e) {
            // ignored
        } catch(NoSuchElementException e) {
            // ignored
        }
        return 0;
    }

8 楼 lighter 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);

7 楼 phantomhu 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对象上啊

6 楼 tomkoo 2007-10-13  

抽出时间看了一下ColletionUtils类的源代码，发现，union,intersection,disjunction,subtract等方法的实现方式都是我前面提到的第二种方式，利用Map来进行一系列的比较操作。不过用得可比我的例子灵活多了。看了有种豁然开朗的感觉。

谢谢楼上的！

5 楼 tomkoo 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，谢谢！这就看去！

4 楼 lighter 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}

3 楼 tomkoo 2007-10-12  

Comparable实现排序，比较时还是需要循环啊

2 楼 kidd3166 2007-10-12  

你这样属于自定义对象集合，我曾经用过比较器来比较2个集合
上网查找一个关于Comparable,Comparator 的资料吧

1 楼 lovegiggs 2007-10-12  

可以考虑利用数据库资源来比较，写个存储过程来实现，通过内存来跑

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

账单的平衡与否。