你的位置:首页 > Java教程

[Java教程]【Simple Java】怎样高效判断数组中是否包含某个特定值

怎样判断一个无序数组是否包含某个特定值?这在JAVA中是一个非常实用的操作,在Stack Overflow问答网站中也同样是一个热门问题;

要完成这个判断,可以通过若干种不同的方式实现,每种实现方式对应的时间复杂读会有很大的不同;

接下来我将展示不同实现方式的时间开销。

四种不同方式检查数组是否包含某个值

使用List:

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

使用Set:

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

使用简单的循环语句:

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

使用Arrays.binarySearch()方法:

下面的代码是错误的,之所以列在下面是出于完整性考虑(四种判断方式),binarySearch()二分查找只能用于有序数组。

运行下面程序,你有可能会得到异常结果;

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

四种实现方式对应的时间开销

以下代码可计算出以上四种实现方式大致的时间消耗,基本策略是使用不同大小的数组(5,1k,10k)做测试,可能不是很精准,但这种方式很简单;

数组大小为5:

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);  }

运行结果:

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

数组大小为1000:

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

运行结果:

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

数组大小为10000:

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

运行结果:

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

结论

从测试结果可以看出,使用简单的循环语句比使用任何集合都高效,很大一部分开发人员选择使用第一种方法(List),但这种方法其实是相对低效的。在使用集合提供的API前,需要把一个数组放到集合里,这需要消耗一定的时间,特别是对于Set集合;(注:其实ArrayList集合的性能跟普通的循环语句差不多,因为对于ArrayList,转换成集合的时候,仅仅是改变了内部的数组索引,遍历判断的时候,跟普通的循环语句类似);

如果要使用Arrays.binarySearch()方法,前提是数组要有序,在这个测试demo中,很显然数组是无序的,因此不该被使用;

事实上,如果你确实需要高效的去检查数组或集合中是否包含某个值,一个有序列表或者有序树能把时间复杂度降低到O(log(n)),或者使用散列集合,时间复杂度为O(1);

 

译文链接:http://www.programcreek.com/2014/04/check-if-array-contains-a-value-java/