使用二分法Arrays.binarySearch()与list.contains()进行元素比较的效率分析

 有这样一个简单的场景，需要把Excel存储的以下格式的物料数据上传到系统里，但是系统的数据库已经存在大量的记录，例如几十万条记录。而业务 上的约束条件是对于同一个PLANT下，不允许存在重复的Material，数据库的设计也是将PLANT和MATERIAL_NO作为联合主键，如果从 Excel导入的数据对于数据库中已经存在的数据重复，那么也会抛出主键唯一约束异常。

 

Excel数据格式：

 

PLANT	MATERIAL_NO	MTYPE	MATERIAL_DES
P603	0101-002876	ROH	MATE_DES
P603	0101-002877	ROH	MATE_DES
P604	0101-002878	ROH	MATE_DES
P604	0101-002879	ROH	MATE_DES

 

 

数据库表结构(SqlServer2008)

TB_WASTER_MATE

Column Name	Type	Primary Key	Foreign Key	Not Null
PLANT	varchar(10)	1	0	1
MATE_NO	varchar(20)	1	0	1
MTYPE	varchar(4)	0	0	1
MATE_DES	varchar(40)	0	0	0
CREATEUSERID	varchar(50)	0	0	0
CREATEUSERNAME	nvarchar(50)	0	0	0
CREATETIME	datetime	0	0	0
UPDATEUSERID	varchar(50)	0	0	0
UPDATEUSERNAME	nvarchar(50)	0	0	0
UPDATETIME	datetime	0	0	0

 

对于这种需求，如果不考虑性能和效率，在数据较少的情况下，我们常见的的解决方案是读取所有的Excel数据构成一个Material List,

循环此List，取List中每个Material，根据Material对象的PLANT和MATE_NO属性去查询数据中是否存在这样的记录，如果存在，跳过，如果不存在，插入这条数据到数据库，返回给用户操作结果。

那么在大数据量的情况下，这样做的弊端是显而易见的，主要就是数据库的访问太频繁，每插入一条记录就得做一次select操作。

那如何减少数据库访问次数呢？显然将数据库表中数据一次性查询全部取出组成一个Material对象List，然后调用List对象的 contains()方法判断此List是否包含了待插入的Material可能是比较好的一个方法。但是这样做也存在一些问题，1.一次性全部取出并组 装成Material对象，对内存的开销比较大，如果是比较大的对象，而且内存有限，有可能导致内存溢出；2.首先Material类需要重写 equals()方法，对于每条待插入的数据都需要调用contains()方法，调用contains方法时，默认是将contains方法的参数和 List中的数据遍历比较，对于Material对象，需要不断的调用equals()方法来比较这个对象和List中的元素对象是否相等。假设数据库查 出来的Material记录有10000条，最坏的情况，需要插入的数据和第10000条数据重复或和10000条都不重复，那么equals()方法需 要被调用10000次。

更好的解决方案是查询出PLANT和MATE_NO的连接字符串，并且排好序

SELECT (PLANT+MATE_NO) as MATEINFO FROM TB_WASTER_MATE ORDER BY MATEINFO

得到诸如：

P6030101-002876

P6030101-002877

P6040101-002878

P6040101-002879     

形式的数据

 

将查出的所有数据组合成字符串数组，调用数组的二分查找方法Arrays.binarySearch()来判断待插入的数据是否在数据库中已存在， 二分法查找需要被查找的数组已经是排好序的，而sql查询时已经将顺序排好，所以数组可以直接使用，这样不仅将数据库查询减少到仅有一次，而且每次将查找 范围缩小一半，元素比较的效率大大提高。

 

 

 下面来比较测试一下两种方法的效率差异：

 

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

/**
 * ClassName:EffCompare.java
 * Author: Jack0511
 * CreateTime: Feb 28, 2011 2:50:23 PM
 * Description:
 **/

public class EffCompare {

  /**
   * @param args
   */
  public static void main(String[] args) {
    List list = new ArrayList(10000);
     for(int i=0;i<100000;i++){
       list.add("jack"+i);
     }
     String[] array = list.toArray(new String[10000]);
     Arrays.sort(array);
     long begin = System.currentTimeMillis();
     for(int k=60000;k<70000;k++){  //1
       int index = Arrays.binarySearch(array, "jack"+k);
       //System.out.println(Arrays.binarySearch(array, "jack"+k));
     }
     long end = System.currentTimeMillis();
     System.out.println("二分法查找10000个item消耗："+(end-begin)+"毫秒");

     begin = System.currentTimeMillis();
     for(int n=60000;n<70000;n++){  //2
       boolean i***ist = list.contains("jack"+n);
       //System.out.println(list.contains("jack"+n));
     }
     end = System.currentTimeMillis();
     System.out.println("contains查找10000个item消耗："+(end-begin)+"毫秒");
  }

}

 

结果：

二分法查找10000个item消耗：0毫秒
contains查找10000个item消耗：12453毫秒

 

测试的时候可以将 1,2 处的代码改为for(int n=0;n<10000;n++){  ，

for(int n=90000;n<100000;n++){ 

可以发现，起始值越往后，二分法的耗时基本不变，而用contains()比较的耗时越来越大，原因当然是contains方法进行了越来越多的equals()调用。