极客教程Java List中的二分查找和contains()方法的性能对比
Java提供了两个方法来查找List中的元素，分别为Collections.binarySearch()和contains()。在底层，contains()方法使用indexOf()方法来搜索元素。 indexOf() 方法通过线性循环遍历List，并将每个元素与关键字进行比较，直到找到关键字并返回true，否则返回false，表示未找到。因此，contains()的时间复杂度为O(n)。而Collections.binarySearch()的时间复杂度为O(log2(n))。但是，如果要使用这个方法，则列表必须是已排序的。如果列表未排序，我们需要在使用Collections.binarySearch()之前对其进行排序，这需要O(nlog(n))的时间。
如何选择：
- 如果要查找的元素靠近列表的开头，则contains()方法的性能更好，因为contains()从列表的开头开始线性搜索元素。
- 如果元素已排序且元素数量相对较大，则Collections.binarySearch()更快，因为它只需要O(log2(n))的时间。
- 如果列表中的元素未排序，则contains()方法的性能更好，因为它只需要O(n)的时间，但如果查询的数量很大，则Collections.binarySearch()方法的整体性能更好，因为我们仅在第一次搜索期间对列表进行排序，这需要O(nlog(n))时间，并且在此之后，每个搜索操作只需要O(log(n))的时间。
- 对于包含相对较少元素的列表，contains()更快。
- 如果我们使用的是未实现RandomAccess接口的LinkedList，因此无法提供O(1)时间来访问元素，则应优先选择contains()而不是Collections.binarySearch()，因为Collections.binarySearch()需要花费O(n)的时间执行链接遍历，然后需要O(log(n))的时间来执行比较。
现在我们将讨论三种不同情况的测试，对比二分查找和contains()方法：
- 已排序的小列表
- 已排序的大列表
- 未排序的列表
情况1： 对于一个已排序的小列表
在下面的代码中，我们以从0到99的100个元素的已排序列表为例，搜索40。正如我们上面看到的那样，在小列表中，contains()的速度要优于Collections.binarySearch()。
例子：
// 比较 contains() 和 Collections.binarySearch() 方法性能的 Java 程序
// 对于小列表（案例 1）
// 从 java.util 包中导入 ArrayList 和 Collections 类
import java.util.ArrayList;
import java.util.Collections;
// 主类
class GFG {
// 主方法
public static void main(String[] args)
{
// 创建 ArrayList 对象
// 声明整数类型的对象
ArrayList<Integer> arr = new ArrayList<>();
// 使用 for 循环遍历对象
for (int i = 0; i < 100; i++) {
arr.add(i);
}
// 计算并打印寻找 40 所需的时间
// 使用 contains() 方法
long start = System.nanoTime();
arr.contains(40);
long end = System.nanoTime();
// 打印语句
System.out.println(
"Time taken to find 40 inside arr using contains() = "
+ (end - start) + " nano seconds");
// 计算并打印寻找 40 所需的时间
// 使用 Collections.binarySearch() 方法
start = System.nanoTime();
Collections.binarySearch(arr, 40);
end = System.nanoTime();
// 打印语句
System.out.println(
"Time taken to find 40 inside arr using binarySearch() = "
+ (end - start) + " nano seconds");
}
}
输出结果
Time taken to find 40 inside arr using contains() = 16286 nano seconds
Time taken to find 40 inside arr using binarySearch() = 87957 nano seconds
案例 2: 对于一个大的排序列表
在下面的例子中，我们创建了一个包含 100000 个元素从 0 到 99999 的排序过的 ArrayList，然后使用 contains() 和 Collections.sort() 方法寻找其中元素 40000。由于列表是排序的并且具有相对较多的元素，Collections.sort() 方法的性能优于 contains() 方法。
例子
// 寻找和比较 contains() 和 Collections.sort() 方法性能的 Java 程序
// 对于大的排序 ArrayList（案例 2）
// 从 java.util 包中导入 ArrayList 和 Collections 类
import java.util.ArrayList;
import java.util.Collections;
// 主类
public class GFG {
// 主方法
public static void main(String[] args)
{
// 创建 ArrayList 类对象
// 声明整数类型的对象
ArrayList<Integer> arr = new ArrayList<>();
// 遍历对象
for (int i = 0; i < 100000; i++) {
// 使用 add() 方法添加元素
arr.add(i);
}
// 计算并打印寻找 40000 所需的时间
// 使用 contains() 方法
long start = System.nanoTime();
arr.contains(40000);
long end = System.nanoTime();
// 打印语句
System.out.println(
"Time taken to find 40000 inside arr "
+ "using contains() = " + (end - start)
+ " nano seconds");
// 计算并打印寻找 40000 所需的时间
// 使用 Collections.binarySearch() 方法
start = System.nanoTime();
Collections.binarySearch(arr, 40000);
end = System.nanoTime();
// 打印语句
System.out.println(
"Time taken to find 40000 inside arr "
+ "using binarySearch() = " + (end - start)
+ " nano seconds");
}
}
输出结果
使用contains() 从 arr 中查找40000所需的时间= 6651276纳秒
使用binarySearch() 从 arr 中查找40000所需的时间= 85231纳秒
第三种情况： 对于未排序的列表
在下面的代码中，我们通过在其中存储介于0和100000之间的随机数字来创建了一个未排序的ArrayList。由于列表未排序，因此contains() 方法的性能更好，因为它只需要O(n)的时间，而对于使用 _Collections.sort() 方法 _ 我们首先必须对列表进行排序，这需要额外的O(nlog(n))时间，然后需要O(log2(n))的时间来搜索元素。
例子
// Java程序，比较contains() 方法和Collections.sort()
// 方法对未排序ArrayList（第三种情况）的性能
// 从java.util包导入ArrayList和Collections类
import java.util.ArrayList;
import java.util.Collections;
// 主类
class GFG {
// 主方法
public static void main(String[] args)
{
// 创建ArrayList类的对象
ArrayList<Integer> arr = new ArrayList<>();
// 遍历0到100000之间的数字
for (int i = 0; i < 100000; i++) {
//使用random()函数生成随机数
int rand = (int)(Math.random() * 100000);
// 然后把它们存储在我们的列表中
arr.add(rand);
}
// 把要查找的关键字设置为未排序列表中索引30000处的元素
int key = arr.get(30000);
// 计算并打印使用contains()方法查找关键字所需的时间
long start = System.nanoTime();
arr.contains(key);
long end = System.nanoTime();
// 打印语句
System.out.println(
"使用contains()方法从 arr 中查找" + key
+ "所需的时间为"
+ (end - start) + "纳秒");
// 计算并打印使用Collections.sort()方法对列表进行排序，然后使用Collections.binarySearch()
// 方法查找关键字所需的时间
start = System.nanoTime();
Collections.sort(arr);
Collections.binarySearch(arr, key);
end = System.nanoTime();
// 打印语句
System.out.println(
"使用binarySearch()方法从 arr 中查找 " + key
+ "所需的时间为"
+ (end - start) + "纳秒");
}
}
输出
使用contains()方法从 arr 中查找66181所需的时间=8331486纳秒
使用binarySearch()方法从 arr 中查找66181所需的时间=140322701纳秒