contains与binarySearch的性能比较

查找List中的元素有两种方法，一个是使用contains()方法，还有一个是使用Collectoins.binarySearch()。binarySearch()方法有两种实现，一个版本是接受List和Comparator对象作为参数，另一个是接受List以及Comparable对象。这个方法使用二分查找算法来查询指定列表中的某个元素。在调用这个方法前，列表中的元素得按照它们的自然顺序进行升序排列。如果列表没有排序的话，方法调用的结果是不确定的。如果列表有多个元素与查找的元素一样，那么返回的具体是哪一个是不确定的。对于一个可”随机访问“的列表来说，算法的时间复杂度是O(log(n)。如果指定的列表没有实现RandomAccess接口并且列表长度很大的话，这个方法会基于迭代器来进行二分法的查找，它会执行O(n)次链接的遍历以及O(log n)次元素的比较。在方法的结尾，如果查找到了该元素，则返回对应元素在列表中的序号，否则返回的是(-(插入点序号)-1)。插入点的意思是这个元素应该在这个列表中的这个位置进行插入：第一个大于该查找元素的值所在的位置，如果所有元素都小于它的话则是list.size()。这意味着，当且仅当元素查找成功时，返回值才会大于等于0。List接口常见的实现比如ArrayList, Vector, CopyOnWriteArrayList和Stack都实现了RandomAccess接口，它们可以用来进行二分查找，不过还有些别的实现比如LinkedList，它没有实现RandomAccess接口，因此不适合使用二分查找。由于二分查找只能在排好序的列表中进行，因为在查找前你得先对列表排序，这可能会影响到性能，尤其是你的列表很大并且本来就无序的情况下。

下面是一段使用二分法来查找对象的程序。我们有一个包含1百万个整数的列表，这里同时使用contains()及binarySearch()方法进行搜索。

import java.util.ArrayList; 
import java.util.Collections;
import java.util.List; 
import org.slf4j.Logger; 
import org.slf4j.LoggerFactory; 
/** * Java program to perform binary search in Java collection e.g List, Set 
[*] @author Javin Paul 
[*]/ 
public class BinarySearchTest { 
      public static final Logger logger = LoggerFactory.getLogger(BinarySearchTest.class); 

      public static void main(String args[]) { 
            //creating List 
            List<Integer> numbers = new ArrayList<Integer>(1000000); //List of 1M records 

            //initializing List 
            for(int i =0; i<numbers.size(); i++){ 
                  numbers.add(new Integer(i)); 
            } 

               //performing contains search 
            long startTime = System.nanoTime(); 
            boolean isExist = numbers.contains(new Integer(1000000)); 
            long totalTime = System.nanoTime() - startTime; 
            logger.info("Time to search 1Mth Record using contains() is {} nano seconds", totalTime); 

               //performing binary search 
            startTime = System.nanoTime(); 
            Collections.sort(numbers);  // List needs to be sorted for Binary Search 
            Integer number = Collections.binarySearch(numbers, new Integer(1000000)); 
            totalTime = System.nanoTime() - startTime; 
            logger.info("Time to search 1Mth Record using binary search is {} nano seconds", totalTime); 
      } 
}

输出结果：

2013-06-04 23:23:17,834 0 [main] INFO test.BinarySearchTest - Time to search 1Mth Record using contains() is 51404 nano seconds 
2013-06-04 23:23:17,849 15 [main] INFO test.BinarySearchTest - Time to search 1Mth Record using binary search is 554261 nano seconds

从结果中可以看到，contains()方法比二分法要快了10倍，这说明使用contains()方法来搜索列表中的元素非常有效，尤其是当列表实现了RandomAccess接口的情况下。

译注：作者这么说似乎不太公平，如果列表原本就有序的话，二分查找还是相当快的，这里他是加上了排序的时间。如果排序后能进行重复利用，也还是比较划算的。

感谢网友风云无浪指出的问题，其实文中程序的列表是空的。不过修改完后该程序运行的结果仍然是相差大概10倍。当然了，这还是因为算上了排序的时间，毕竟单独从搜索的效率来说的话，二分法通常来说肯定是比顺序查找要快的。


原创文章转载请注明出处：http://it.deepinmind.com
英文原文链接

评论

5 楼 在世界的中心呼喚愛 2014-06-16  

算不算排序时间这个要根据具体情况来分析。。
不算排序时间，二分法快多了。。

4 楼 deepinmind 2014-05-11  

风云无浪 写道

这句写错了，你的list size是0，for(int i =0; i<numbers.size(); i++)
另外binarySearch里有这个限制，BINARYSEARCH_THRESHOLD是5000.所以你的1000000数据量已经和RandomAccess没有关系了
public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

感谢指出~的确是没有初始化。。。

3 楼 风云无浪 2014-05-11  

第二个看错了，是||的关系。那么即使不实现RandomAccess接口，list.size<5000的话有一点不一样。在Iterator时候会有点优化

ArrayList

size 10000
Time to search 1Mth Record using contains() is {} nano seconds 280244
Time to search 1Mth Record using binary search sort time is {} nano seconds 2723913
Time to search 1Mth Record using binary search is {} nano seconds 175538

size1000000
Time to search 1Mth Record using contains() is {} nano seconds 18922651
Time to search 1Mth Record using binary search sort time is {} nano seconds 237869938
Time to search 1Mth Record using binary search is {} nano seconds 200688

LinkedList

size 10000
Time to search 1Mth Record using contains() is {} nano seconds 1561874
Time to search 1Mth Record using binary search sort time is {} nano seconds 8926243
Time to search 1Mth Record using binary search is {} nano seconds 1159986

2 楼 风云无浪 2014-05-11  

这句写错了，你的list size是0，for(int i =0; i<numbers.size(); i++)
另外binarySearch里有这个限制，BINARYSEARCH_THRESHOLD是5000.所以你的1000000数据量已经和RandomAccess没有关系了
public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

1 楼 bitray 2014-05-11  

二分查找必须是有序的数组，太苛刻了