灵魂拷问:如何检查Java数组中是否包含某个值 ?(2)-阿里云开发者社区

开发者社区> 沉默王二> 正文

灵魂拷问:如何检查Java数组中是否包含某个值 ?(2)

简介: 灵魂拷问:如何检查Java数组中是否包含某个值 ?
+关注继续查看

假如把数组的长度增加到 1000,我们再来看一下统计结果。


String[] arr = new String[1000];
Random s = new Random();
for(int i=0; i< 1000; i++){
    arr[i] = String.valueOf(s.nextInt());
}



这时数组中是没有我们要找的元素的。为了做比较,我们顺便把二分查找也添加到统计项目中。


// 使用二分查找
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    useArraysBinarySearch(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useArraysBinarySearch:  " + duration / 1000000);



统计结果如下所示:


useList:  91

useSet:  1460

useLoop:  70

useArraysBinarySearch:  4



我们再把数组的长度调整到 10000。


String[] arr = new String[10000];


Random s = new Random();

for(int i=0; i< 10000; i++){

   arr[i] = String.valueOf(s.nextInt());

}



统计结果如下所示:


useList:  1137

useSet:  15711

useLoop:  1115

useArraysBinarySearch:  5



从上述的统计结果中可以很明显地得出这样一个结论:使用简单的 for 循环,效率要比使用 List 和 Set 高。这是因为把元素从数组中读出来再添加到集合中,就要花费一定的时间,而简单的 for 循环则省去了这部分时间。


在得出这个结论之前,说实话,我最喜欢的方式其实是第一种“使用 List”,因为只需要一行代码 Arrays.asList(arr).contains(targetValue) 就可以搞定。


虽然二分查找(Arrays.binarySearch())花费的时间明显要少得多,但这个结论是不可信的。因为二分查找明确要求数组是排序过的,否则查找出的结果是没有意义的。可以看一下官方的 Javadoc。


Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the natural ordering of its elements (as by the sort(Object []) method) prior to making this call. If it is not sorted, the results are undefined.

实际上,如果要在一个数组或者集合中有效地确定某个值是否存在,一个排序过的 List 的算法复杂度为 O(logn),而 HashSet 则为 O(1)。


我们再来发散一下思维:怎么理解 O(logn) 和 O(1) 呢?


O(logn) 的算法复杂度,比较典型的例子是二分查找。举个例子,假设现在一堆试卷,已经按照分数从高到底排列好了。现在要查找有没有 79 分的试卷,怎么办呢?可以先从中间找起,因为按照 100 分的卷子来看,79 分大差不差应该就在中间的位置(平均分如果低于 79 说明好学生就比较少了),如果中间这份卷子的分数是 83,那说明 79 分的卷子就在下面的一半,这时候可以把上面那半放在一边了。然后按照相同的方式,每次就从中间开始找,直到找到 79 分的卷子(当然也可能没有 79 分)。


假如有 56 份卷子,找一次,还剩 28 份,再找一次,还剩 14 份,再找一次,还剩 7 份,再找一次,还剩 2 或者 3 份。如果是 2 份,再找一次,就只剩下 1 份了;如果是 3 份,就还需要再找 2 次。


我们知道,log2(32) = 5,log2(64) = 6,而 56 就介于 32 和 64 之间。也就是说,二分查找大约需要 log2(n) 次才能“找到”或者“没找到”。而在算法复杂度里,经常忽略常数,所以不管是以 2 为底数,还是 3 为底数,统一写成 log(n) 的形式。


再来说说 O(1),比较典型的例子就是哈希表(HashSet 是由 HashMap 实现的)。哈希表是通过哈希函数来映射的,所以拿到一个关键字,通过哈希函数转换一下,就可以直接从表中取出对应的值——一次直达。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9913 0
Java Spring ClassPathXmlApplicationContext是如何判断容器内包含某个Bean的
Java Spring ClassPathXmlApplicationContext是如何判断容器内包含某个Bean的
4 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13649 0
JavaScript 检查一个 JSON 对象中是否对存指这下的 Key
JavaScript 检查一个 JSON 对象中是否对存指定的 Key 太阳火神的美丽人生 (http://blog.csdn.net/opengl_es) 本文遵循“署名-非商业用途-保持一致”创作公用协议 转载请保留此句:太阳火神的美丽人生 -  本博客专注于 敏捷开发及移动和物联设备研究:iOS、Android、Html5、Arduino、pcDuino,否则,出自本博客的文章拒绝转载或再转载,谢谢合作。
819 0
在JAVA中使用DCL双检查锁机制实现单例的多线程安全
元旦放假期间学代码,我都感动我自己啦。
1507 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7290 0
+关注
沉默王二
微信搜索「沉默王二」,回复关键字「00」获取硬核计算机基础资料。
1084
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载