1
2
3
public
static
boolean
useList(String[] arr, String targetValue) {
return
Arrays.asList(arr).contains(targetValue);
}
使用Set
1
2
3
4
public
static
boolean
useSet(String[] arr, String targetValue) {
Set<String>
set = new
HashSet<String>(Arrays.asList(arr));
return
set.contains(targetValue);
}
使用循環判斷
1
2
3
4
5
6
7
public
static
boolean
useLoop(String[] arr, String targetValue) {
for(String
s: arr){
if(s.equals(targetValue))
return
true;
}
return
false;
}
使用Arrays.binarySearch()
Arrays.binarySearch()方法只能用於有序數組!!!如果數組無序的話得到的結果就會很奇怪。
查找有序數組中是否包含某個值的用法如下:
1
2
3
4
5
6
7
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。這種方法得到的結果可能並不精確,但是是最簡單清晰的方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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);
}
運行結果:
1
2
3
4
useList:
13
useSet:
72
useLoop:
5
useArraysBinarySearch:
9
使用壹個長度為1k的數組
1
2
3
4
5
6
String[]
arr = new
String[1000];
Random
s = new
Random();
for(int
i=0;
i< 1000;
i++){
arr[i]
= String.valueOf(s.nextInt());
}
結果:
1
2
3
4
useList:
112
useSet:
2055
useLoop:
99
useArrayBinary:
12
使用壹個長度為10k的數組
1
2
3
4
5
6
String[]
arr = new
String[10000];
Random
s = new
Random();
for(int
i=0;
i< 10000;
i++){
arr[i]
= String.valueOf(s.nextInt());
}
結果:
1
2
3
4
useList:
1590
useSet:
23819
useLoop:
1526
useArrayBinary:
12
總結
顯然,使用壹個簡單的循環方法比使用任何集合都更加高效。許多開發人員為了方便,都使用第壹種方法,但是他的效率也相對較低。因為將數組壓入Collection類型中,首先要將數組元素遍歷壹遍,然後再使用集合類做其他操作。
如果使用Arrays.binarySearch()方法,數組必須是已排序的。由於上面的數組並沒有進行排序,所以該方法不可使用。
實際上,如果妳需要借助數組或者集合類高效地檢查數組中是否包含特定值,壹個已排序的列表或樹可以做到時間復雜度為O(log(n)),hashset可以達到O(1)。
(英文原文結束,以下是譯者註)
使用ArrayUtils
除了以上幾種以外,Apache Commons類庫中還提供了壹個ArrayUtils類,可以使用其contains方法判斷數組和值的關系。
1
2
3
4
import
org.apache.commons.lang3.ArrayUtils;
public
static
boolean
useArrayUtils(String[] arr, String targetValue) {
return
ArrayUtils.contains(arr,targetValue);
}
同樣使用以上幾種長度的數組進行測試,得出的結果是該方法的效率介於使用集合和使用循環判斷之間(有的時候結果甚至比使用循環要理想)。
1
2
3
4
5
6
7
8
9
10
11
useList:
323
useSet:
3028
useLoop:
141
useArrayBinary:
12
useArrayUtils:
181
-------
useList:
3703
useSet:
35183
useLoop:
3218
useArrayBinary:
14
useArrayUtils:
3125
其實,如果查看ArrayUtils.contains的源碼可以發現,他判斷壹個元素是否包含在數組中其實也是使用循環判斷的方式。
部分代碼如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if(array
== null)
{
return
-1;
}
else
{
if(startIndex
< 0)
{
startIndex
= 0;
}
int
i;
if(objectToFind
== null)
{
for(i
= startIndex; i < array.length; ++i) {
if(array[i]
== null)
{
return
i;
}
}
}
else
if(array.getClass().getComponentType().isInstance(objectToFind))
{
for(i
= startIndex; i < array.length; ++i) {
if(objectToFind.equals(array[i]))
{
return
i;
}
}
}
return
-1;
}
所以,相比較之下,我更傾向於使用ArrayUtils工具類來進行壹些合數祖相關的操作。畢竟他可以讓我少寫很多代碼(因為自己寫代碼難免有Bug,畢竟apache提供的開源工具類庫都是經過無數開發者考驗過的),而且,效率上也並不低太多。