Of Stack

Java effectively determines whether an element in an array has a detail

  • 2020-05-17 05:25:14
  • OfStack

1. A method to check if an array contains a value

Using List 


public static boolean useList(String[] arr, String targetValue) {
  return Arrays.asList(arr).contains(targetValue);
}

Using Set 


public static boolean useSet(String[] arr, String targetValue) {
  Set<String> set = new HashSet<String>(Arrays.asList(arr));
  return set.contains(targetValue);
}

Using circular judgment 


public static boolean useLoop(String[] arr, String targetValue) {
  for(String s: arr){
    if(s.equals(targetValue))
      return true;
  }
  return false;
}

Using Arrays. binarySearch ()

Arrays.binarySearch() Method can only be used with ordered arrays!! If you have an unordered array you get a very strange result.

To find out whether an ordered array contains a value is as follows: 


public static boolean useArraysBinarySearch(String[] arr, String targetValue) { 
  int a = Arrays.binarySearch(arr, targetValue);
  if(a > 0)
    return true;
  else
    return false;
}

Time complexity

The following code gives you a rough idea of the time cost of each method. The basic idea is to look up a value from an array of sizes 5, 1k, and 10k. This method may not be accurate, but it is the easiest and clearest way to get results. 


public static void main(String[] args) {
  String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB"};

  //use list
  long startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useList(arr, "A");
  }
  long endTime = System.nanoTime();
  long duration = endTime - startTime;
  System.out.println("useList: " + duration / 1000000);

  //use set
  startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useSet(arr, "A");
  }
  endTime = System.nanoTime();
  duration = endTime - startTime;
  System.out.println("useSet: " + duration / 1000000);

  //use loop
  startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useLoop(arr, "A");
  }
  endTime = System.nanoTime();
  duration = endTime - startTime;
  System.out.println("useLoop: " + duration / 1000000);

  //use Arrays.binarySearch()
  startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useArraysBinarySearch(arr, "A");
  }
  endTime = System.nanoTime();
  duration = endTime - startTime;
  System.out.println("useArrayBinary: " + duration / 1000000);
}

Operation results: 


useList: 13
useSet: 72
useLoop: 5
useArraysBinarySearch: 9

Use an array of length 1k 


String[] arr = new String[1000];

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

Results: 


useList: 112
useSet: 2055
useLoop: 99
useArrayBinary: 12

Use an array of length 10k 


String[] arr = new String[10000];

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

Results: 


useList: 1590
useSet: 23819
useLoop: 1526
useArrayBinary: 12

summary

Obviously, using a simple looping method is more efficient than using any collection. Many developers use the first method for convenience, but it is also relatively inefficient. Because pressing an array into an Collection type, you first have to walk the array elements once before you do anything else with the collection class.

If you are using Arrays.binarySearch() Method, the array must be sorted. This method is not available because the array above is not sorted.

In fact, if you need an array or collection class to efficiently check whether an array contains a particular value, a sorted list or tree can be O(log(n)) and hashset can be O(1).

Using ArrayUtils

In addition to the above, the Apache Commons library also provides an ArrayUtils class that can be used to determine the relationship between an array and a value using its contains method. 


public static boolean useSet(String[] arr, String targetValue) {
  Set<String> set = new HashSet<String>(Arrays.asList(arr));
  return set.contains(targetValue);
}
0

Again, using arrays of the same length, the result is that the efficiency of this method is somewhere between using collections and using loop judgments (sometimes even better than using loops). 


public static boolean useSet(String[] arr, String targetValue) {
  Set<String> set = new HashSet<String>(Arrays.asList(arr));
  return set.contains(targetValue);
}
1

In fact, if you look at the source code of ArrayUtils.contains, you can see that it also USES a loop to determine whether an element is included in an array.

Part of the code is as follows: 


public static boolean useSet(String[] arr, String targetValue) {
  Set<String> set = new HashSet<String>(Arrays.asList(arr));
  return set.contains(targetValue);
}
2

Therefore, in comparison, I prefer to use the ArrayUtils tool class to perform some composite progenitor related operations. After all, he could have gotten me to write a lot less code (because there's Bug in writing my own code, since apache's open source tool library has been tested by countless developers), and it wouldn't have been much less efficient.

conclusion

All right, that's the whole content of this article, I hope the content of this article can help you to learn or use Java. If you have any questions, you can leave a message to communicate.

Related articles: