Java proporciona dos métodos, a saber, Collections.binarySearch() y contains() para encontrar un elemento dentro de una lista. Debajo del capó, el método contains() usa el método indexOf() para buscar el elemento. El método indexOf() recorre linealmente la Lista y compara cada elemento con la clave hasta que se encuentra la clave y devuelve verdadero; de lo contrario, devuelve falso cuando no se encuentra el elemento. entonces, la complejidad temporal de contains() es O(n). La complejidad temporal de Collections.binarySearch() es O(log2(n)). Pero si queremos usar este método, la lista debe ordenarse. Si la lista no está ordenada, debemos ordenarla antes de usar Collections.binarySearch(), que toma tiempo O(nlog(n)).
Como escoger:
- Si el elemento que se va a encontrar está cerca del comienzo de la lista, entonces el rendimiento del método contains() es mejor ya que contains() comienza a buscar el elemento desde el comienzo de la lista de forma lineal.
- Si los elementos están ordenados y la cantidad de elementos es relativamente grande, Collections.binarySearch() es más rápido, ya que solo toma el tiempo O(log2(n)).
- Si los elementos de la lista no están ordenados, el rendimiento del método contains() es mejor, ya que solo requiere O(n) tiempo, pero si el número de consultas de búsqueda es alto, el rendimiento general del método Collections.binarySearch() es mejor. Ordenamos la lista solo una vez durante la primera búsqueda que toma el tiempo O(nlog(n)) y luego cada operación de búsqueda toma el tiempo O(log(n)).
- Para una lista que contiene una cantidad relativamente pequeña de elementos, contains() produce una mejor velocidad.
- Si estamos usando una LinkedList que no implementa la interfaz RandomAccess y, por lo tanto, no puede proporcionar O(1) tiempo para acceder a un elemento, entonces deberíamos preferir contains() sobre Collections.binarySearch() ya que Collections.binary search() toma O(n) para realizar cruces de enlaces, y luego toma tiempo O(log(n)) para realizar comparaciones.
Ahora discutiremos dos variantes donde una Lista ordenada es
- Lista pequeña ordenada
- Lista grande ordenada
- Lista desordenada
Caso 1: Para una pequeña lista ordenada
En el código mencionado a continuación, hemos tomado el ejemplo de una lista ordenada que contiene solo 100 elementos del 0 al 99 y buscamos 40 y, como hemos visto anteriormente, en las listas pequeñas contains() tiene una ventaja sobre Collections.binarySearch cuando se trata de velocidad.
Ejemplo
Java
// 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
Caso 2: Para una gran lista ordenada
En lo que se menciona a continuación, hemos creado una ArrayList ordenada que contiene 100000 elementos de 0 a 99999, y encontramos el elemento 40000 dentro de ella usando el método contains() y Collections.sort(). Como la lista está ordenada y tiene una cantidad relativamente grande de elementos, el rendimiento de Collections.sort() es mejor que el método contains().
Ejemplo
Java
// Java program to Find and Compare the Performance
// of conatins() 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
Caso 3: Para una Lista no ordenada
En el código que se menciona a continuación, hemos creado una ArrayList sin clasificar almacenando números aleatorios entre 0 y 100000 en su interior. Como la lista no está ordenada, el rendimiento del método contains() es mejor, ya que solo requiere tiempo O(n), mientras que para usar el método Collections.sort() primero tenemos que ordenar la lista, que requiere un O(nlog(n) adicional. ) tiempo y luego se toma el tiempo O(log2(n)) para buscar el elemento.\
Ejemplo
Java
// 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
Publicación traducida automáticamente
Artículo escrito por shivamsingh00141 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA