Java 배열에 값이 포함되어 있는지 확인

1. 개요

이 기사에서는 배열에서 지정된 값을 검색하는 다양한 방법을 살펴 보겠습니다.

또한 JMH (Java Microbenchmark Harness)를 사용하여 이들의 성능을 비교하여 어떤 방법이 가장 잘 작동하는지 확인합니다.

2. 설정

예제에서는 각 테스트에 대해 무작위로 생성 된 문자열 을 포함하는 배열을 사용합니다 .

String[] seedArray(int length) { String[] strings = new String[length]; Random value = new Random(); for (int i = 0; i < length; i++) { strings[i] = String.valueOf(value.nextInt()); } return strings; }

각 벤치 마크에서 배열을 재사용하기 위해 JMH에 대한 범위를 선언 할 수 있도록 배열과 개수를 저장할 내부 클래스를 선언합니다.

@State(Scope.Benchmark) public static class SearchData { static int count = 1000; static String[] strings = seedArray(1000); } 

3. 기본 검색

배열을 검색하기위한 일반적으로 사용되는 세 가지 방법은 같다 목록 집합, 또는 루프 가 매치를 찾을 때까지 각각의 부재를 검사한다.

각 알고리즘을 구현하는 세 가지 방법으로 시작하겠습니다.

boolean searchList(String[] strings, String searchString) { return Arrays.asList(SearchData.strings) .contains(searchString); } boolean searchSet(String[] strings, String searchString) { Set stringSet = new HashSet(Arrays.asList(SearchData.strings)); return stringSet.contains(searchString); } boolean searchLoop(String[] strings, String searchString) { for (String string : SearchData.strings) { if (string.equals(searchString)) return true; } return false; }

이러한 클래스 주석을 사용하여 JMH에 평균 시간 (마이크로 초)을 출력하고 5 회의 워밍업 반복을 실행하여 테스트의 신뢰성을 보장합니다.

@BenchmarkMode(Mode.AverageTime) @Warmup(iterations = 5) @OutputTimeUnit(TimeUnit.MICROSECONDS) 

그리고 루프에서 각 테스트를 실행합니다.

@Benchmark public void searchArrayLoop() { for (int i = 0; i < SearchData.count; i++) { searchLoop(SearchData.strings, "T"); } } @Benchmark public void searchArrayAllocNewList() { for (int i = 0; i < SearchData.count; i++) { searchList(SearchData.strings, "T"); } } @Benchmark public void searchArrayAllocNewSet() { for (int i = 0; i < SearchData.count; i++) { searchSet(SearchData.strings, "S"); } } 

각 방법에 대해 1000 번의 검색을 실행하면 결과는 다음과 같습니다.

SearchArrayTest.searchArrayAllocNewList avgt 20 937.851 ± 14.226 us/op SearchArrayTest.searchArrayAllocNewSet avgt 20 14309.122 ± 193.844 us/op SearchArrayTest.searchArrayLoop avgt 20 758.060 ± 9.433 us/op 

루프 검색은 다른 것보다 효율적입니다. 그러나 이것은 적어도 부분적으로 우리가 컬렉션을 사용하는 방식 때문입니다.

searchList ()를 호출 할 때마다 새 List 인스턴스를 만들고 searchSet ()를 호출 할 때마다 새 List 및 새 HashSet 을 만듭니다 . 이러한 객체를 생성하면 배열을 반복 할 때 발생하지 않는 추가 비용이 발생합니다.

4.보다 효율적인 검색

ListSet 의 단일 인스턴스를 만든 다음 각 검색에 재사용하면 어떻게됩니까?

시도해 보겠습니다.

public void searchArrayReuseList() { List asList = Arrays.asList(SearchData.strings); for (int i = 0; i < SearchData.count; i++) { asList.contains("T"); } } public void searchArrayReuseSet() { Set asSet = new HashSet(Arrays.asList(SearchData.strings)); for (int i = 0; i < SearchData.count; i++) { asSet.contains("T"); } } 

위와 동일한 JMH 주석으로 이러한 메서드를 실행하고 비교를 위해 간단한 루프에 대한 결과를 포함합니다.

우리는 매우 다른 결과를 봅니다.

SearchArrayTest.searchArrayLoop avgt 20 758.060 ± 9.433 us/op SearchArrayTest.searchArrayReuseList avgt 20 837.265 ± 11.283 us/op SearchArrayTest.searchArrayReuseSet avgt 20 14.030 ± 0.197 us/op 

List 검색은 이전보다 약간 빠르지 만 Set 는 루프에 필요한 시간의 1 % 미만으로 떨어집니다!

이제 각 검색에서 새 컬렉션을 만드는 데 필요한 시간을 제거 했으므로 이러한 결과는 의미가 있습니다.

HashSet의 기본 구조 인 해시 테이블 검색은 시간 복잡성이 0 (1)이고 ArrayList의 기본이되는 배열 은 0 (n)입니다.

5. 이진 검색

배열을 검색하는 또 다른 방법은 이진 검색입니다. 이진 검색은 매우 효율적이지만 사전에 배열을 정렬해야합니다.

배열을 정렬하고 이진 검색을 시도해 보겠습니다.

@Benchmark public void searchArrayBinarySearch() { Arrays.sort(SearchData.strings); for (int i = 0; i < SearchData.count; i++) { Arrays.binarySearch(SearchData.strings, "T"); } } 
SearchArrayTest.searchArrayBinarySearch avgt 20 26.527 ± 0.376 us/op 

이진 검색은 HashSet 보다 덜 효율적이지만 매우 빠릅니다. 이진 검색 의 최악의 경우 성능은 0 (log n)으로 배열 검색과 해시 테이블의 성능 사이에 배치됩니다.

6. 결론

배열을 검색하는 몇 가지 방법을 보았습니다.

결과에 따라 HashSet 은 값 목록을 검색하는 데 가장 적합합니다. 그러나 미리 생성하여 세트에 저장해야합니다 .

항상 그렇듯이 예제의 전체 소스 코드는 GitHub에서 사용할 수 있습니다.