极客教程Java List二分查找与contains性能对比
Java 提供了两个方法，即 Collections.binarySearch() 和 contains() 来寻找一个列表中的元素。在引擎盖下，contains()方法使用indexOf()方法来搜索元素。indexOf()方法在列表中线性循环，将每个元素与键进行比较，直到找到键为止，并返回真，否则当没有找到元素时返回假。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()会产生更好的速度。
- 如果我们使用的LinkedList没有实现RandomAccess接口，因此无法提供O(1)时间来访问一个元素，那么我们应该选择contains()而不是Collections.binarySearch()，因为Collections.binary search()需要O(n)来进行链接遍历，然后需要O(log(n))时间来进行比较。
现在我们将讨论两种变体，即排序后的列表是
1.分类的小名单
2.分类的大名单
3.未分类列表
案例1：对于一个小型的排序列表
在下面提到的代码中，我们以一个只包含0到99的100个元素的排序列表为例，我们搜索了40个元素，正如我们在上面看到的，在小列表中，contains()在速度上比Collections.binarySearch有优势。
示例
// Java program to compare the performance
// of contains() and Collections.binarySearch()
// For a Small List (Case 1)
// Importing ArrayList and Collections classes
// from java.util package
import java.util.ArrayList;
import java.util.Collections;
// Main class
class GFG {
// Main driver method
public static void main(String[] args)
{
// Creating an object of ArrayList
// Declaring object of integer type
ArrayList<Integer> arr = new ArrayList<>();
// Iterating over object using for loop
for (int i = 0; i < 100; i++) {
arr.add(i);
}
// Calculating and printing the time taken
// where we are finding 40
// Using contains() method
long start = System.nanoTime();
arr.contains(40);
long end = System.nanoTime();
// Print statement
System.out.println(
"Time taken to find 40 inside arr using contains() = "
+ (end - start) + " nano seconds");
// Calculating and printing the time taken
// to find 40
// Using Collections.binarySearch() method
start = System.nanoTime();
Collections.binarySearch(arr, 40);
end = System.nanoTime();
// Print statement
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：对于一个大的排序的列表
在下面提到的例子中，我们创建了一个排序的ArrayList，其中包含100000个从0到99999的元素，我们使用contains()和Collections.sort()方法在其中找到40000个元素。由于该列表是排序的，并且有相对较多的元素，Collections.sort()的性能比contains()方法更好。
示例
// Java program to Find and Compare the Performance
// of contains() and Collections.sort() Methods
// For Large Sorted ArrayList (Case 2)
// Importing ArrayList and Collections classes
// from java.util package
import java.util.ArrayList;
import java.util.Collections;
// Main class
public class GFG {
// Main driver method
public static void main(String[] args)
{
// Creating an object of ArrayList class
// Declaring object of Integer type
ArrayList<Integer> arr = new ArrayList<>();
// Iterating over the object
for (int i = 0; i < 100000; i++) {
// Adding elements using add() method
arr.add(i);
}
// Calculating and printing the time taken
// to find 40000 using contains()
long start = System.nanoTime();
arr.contains(40000);
long end = System.nanoTime();
// Print statement
System.out.println(
"Time taken to find 40000 inside arr "
+ "using contains() = " + (end - start)
+ " nano seconds");
// Calculating and printing the time taken
// to find 40000 using Collections.binarySearch()
start = System.nanoTime();
Collections.binarySearch(arr, 40000);
end = System.nanoTime();
// Print statement
System.out.println(
"Time taken to find 40000 inside arr "
+ "using binarySearch() = " + (end - start)
+ " nano seconds");
}
}
输出
Time taken to find 40000 inside arr using contains() = 6651276 nano seconds
Time taken to find 40000 inside arr using binarySearch() = 85231 nano seconds
案例3：对于一个未排序的列表
在下面提到的代码中，我们创建了一个未排序的ArrayList，在其中存储了0到100000之间的随机数字。由于该列表是未排序的，所以contains()方法的性能更好，因为它只需要O(n)时间，而使用Collections.sort()方法我们首先要对列表进行排序，这需要额外的O(nlog(n))时间，然后需要O(log2(n))时间来搜索该元素。
示例
// Java program to compare the performance
// of contains() and Collections.sort() method
// on an unsorted ArrayList (Case3)
// Importing ArrayList and Collections class
// from java.util package
import java.util.ArrayList;
import java.util.Collections;
// Main class
class GFG {
// Main driver method
public static void main(String[] args)
{
// Creating an object of ArrayList class
ArrayList<Integer> arr = new ArrayList<>();
// Iterating between 0 to 100000 numbers
for (int i = 0; i < 100000; i++) {
// Generating random numbers as iterated
// using random() function
int rand = (int)(Math.random() * 100000);
// Later storing them inside our list
arr.add(rand);
}
// Setting the key to be found as the element
// at index 30000 inside of unsorted list
int key = arr.get(30000);
// Calculating and printing the time taken
// to find the key using contains()
long start = System.nanoTime();
arr.contains(key);
long end = System.nanoTime();
// Print statement
System.out.println(
"Time takes to find " + key
+ " inside arr using contains() = "
+ (end - start) + " nano seconds");
// Calculating and printing the time taken to
// find the key using Collections.binarySearch()
// after sorting the list using Collections.sort()
// method
start = System.nanoTime();
Collections.sort(arr);
Collections.binarySearch(arr, key);
end = System.nanoTime();
// Print statement
System.out.println(
"Time takes to find " + key
+ " inside arr using binarySearch() = "
+ (end - start) + " nano seconds");
}
}
输出
Time takes to find 66181 inside arr using contains() = 8331486 nano seconds
Time takes to find 66181 inside arr using binarySearch() = 140322701 nano seconds