`
deepinmind
  • 浏览: 451557 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
1dc14e59-7bdf-33ab-841a-02d087aed982
Java函数式编程
浏览量:41631
社区版块
存档分类
最新评论

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
英文原文链接
3
1
分享到:
评论
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  
二分查找必须是有序的数组,太苛刻了

相关推荐

    在Java中如何高效的判断数组中是否包含某个元素Java开

    `Arrays.binarySearch()`方法可以实现这一点,但这需要确保数组已排序,否则结果可能不正确。 6. **使用Objects.equals()** - 当处理对象数组时,推荐使用`Objects.equals()`代替`==`,以处理可能的`null`值。例如...

    Java中高效的判断数组中某个元素是否存在详解

    `Arrays.binarySearch()`方法适用于有序数组,它使用二分查找算法,时间复杂度为O(log n)。但注意,对于无序数组,这种方法可能无法正确返回结果,甚至可能导致错误。 为了评估这些方法的性能,通常会进行基准测试...

    common.search

    Java的`Collections`类提供了多种搜索方法,如`binarySearch()`进行二分查找,以及`indexOfSubList()`在子列表中查找元素。 3. **排序算法**:为了提高搜索效率,数据通常需要先进行排序。Java中的`Arrays.sort()`...

    Data Structures Succinctly Part 1

    本章涵盖了节点类(The Node Class)和二叉搜索树类(The Binary Search Tree Class)的定义,包括添加(Add)、删除(Remove)、查找(Contains)、计数(Count)以及遍历操作(Traversals),例如前序遍历...

    北京师范大学数据结构教学资料第6章——集合与字典.ppt

    常见的字典实现包括哈希表(Hash Table)和二叉查找树(Binary Search Tree)等。跳表是一种用于加速查找的字典实现,它通过多层链表构建,每一层都是上一层的一个子集,通过跳跃可以在较短时间内找到目标元素。 在...

    java _Tree.rar

    二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,其中每个节点的左子树只包含比该节点小的元素,右子树包含比该节点大的元素。 2. **红黑树**:在Java集合框架中,`TreeSet`和`TreeMap`是基于红黑树实现...

    10个Java经典的List面试题!.zip

    此外,Collections还有其他实用方法,如binarySearch()、reverse()等。 这些面试题涉及了Java集合框架的基础和高级用法,熟练掌握这些知识点将有助于你在面试中展现出扎实的Java基础和问题解决能力。在实际开发中,...

    对象数组便历及查找.zip

    这样做后,我们就可以使用Java的`Collections`类提供的方法,如`contains()`或`binarySearch()`进行查找。 总结来说,理解和熟练掌握对象数组的遍历和查找对于JavaSE开发者至关重要,因为它们是构建复杂数据结构和...

    Oracle Spatial用户指南

    为了提高空间查询的性能,Oracle Spatial提供了空间索引,如R-Tree和GIST(Generalized Indexed Search Tree)。这些索引能快速定位和比较空间对象,加速查询过程。 四、空间查询与分析 Oracle Spatial提供了丰富的...

    集合框架的使用,可以很好的教你使用集合的框架!

    Person类的例子中,我们可以使用Collections的`sort()`方法对列表进行排序,`equals()`方法用于判断元素是否相等,`binarySearch()`则在排序后的列表中查找元素。 7. Collections工具类:Collections提供了许多对...

    20_集合_第3天(Map、可变参数、Collections)_讲义

    `reverse(List&lt;T&gt; list)`反转List,`copy(List&lt;? super T&gt; dest, List&lt;? extends T&gt; src)`将一个List的内容复制到另一个List,`fill(List&lt;T&gt; list, T obj)`用指定对象填充整个List,`binarySearch(List...

    c#可变数组 快来下

    除了基本的添加、删除和访问元素,`List&lt;T&gt;`还提供了一些额外的有用方法,如`Clear`清空列表,`Count`获取元素数量,`Sort`对列表进行排序,`BinarySearch`进行二分查找,`Contains`检查元素是否存在,以及`ToArray`...

    large_num_polygon

    标题“large_num_polygon”暗示了我们正在讨论一个与大数据量多边形图层相关的主题,尤其是在DB2数据库环境中的操作。这个图层可能包含了海量的地理空间数据,每一行记录都可能代表一个复杂的几何对象,比如城市边界...

    TStringList.pdf

    - `BinarySearch`: 在排序的列表中搜索特定元素,返回元素的索引位置。 - `Clear`: 移除列表中的所有元素。 - `Contains`: 检查列表中是否包含特定元素。 - `ConvertAll&lt;TOutput&gt;`: 将列表中的元素转换为另一种类型...

    Algorithm-HackerRankSolutions.zip

    二分查找尤其适用于已排序的数据,Swift的`binarySearch(_:)`函数可以实现这一操作。 3. **图论算法**:如Dijkstra算法、Floyd-Warshall算法,用于解决最短路径问题。这些算法在网络路由、交通规划等领域有广泛应用...

    Java常用类别用法和进阶代码

    - **Collections类**是集合操作的工具类,提供了一组静态方法来操作集合,如`sort()`, `reverse()`, `binarySearch()`等。 - **Set接口实现类**,如`HashSet`提供无序且不重复的元素集合,`TreeSet`则通过红黑树...

    Collection、Map、List、Set、Iterator

    - `binarySearch(T[] a, T key)`:在已排序的数组中查找指定元素的位置。 - `copyOf(T[] original, int newLength)`:创建一个新的数组,其长度为 `newLength`,并将原数组的元素复制到新数组中。 - `copyOfRange...

    java判定数组或集合是否存在某个元素的实例

    - **方法1-1**: 使用`Arrays.sort()`和`Arrays.binarySearch()`。首先对数组进行排序,然后使用二分查找法来确定元素是否存在。这种方法适用于可排序的元素,效率较高,时间复杂度为O(log n)。 - **方法1-2**: ...

    笔记11-数据结构之MAP和SET

    二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树,它的每个节点都包含一个键值对,左子树的键值都小于根节点的键值,右子树的键值都大于根节点的键值。二叉搜索树的主要操作包括查找、插入和删除。 查找...

Global site tag (gtag.js) - Google Analytics