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. Основно търсене
Три-често използваните методи за търсене масив са като Списък, а Set, или с една линия , която разглежда всяка държава, докато намери мач.
Нека започнем с три метода, които реализират всеки алгоритъм:
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 да изведе средното време в микросекунди и да изпълним пет итерации за загряване, за да гарантираме надеждността на нашите тестове:
@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 Цикличното търсене е по-ефективно от другите. Но това е поне отчасти поради начина, по който използваме колекции.
Създаваме нов екземпляр на List с всяко повикване към searchList () и нов Списък и нов HashSet с всяко обаждане към searchSet () . Създаването на тези обекти създава допълнителни разходи, които при цикъла през масива няма.
4. По-ефективно търсене
Какво се случва, когато създадем единични екземпляри от List and Set и след това ги използваме повторно за всяко търсене?
Нека опитаме:
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 Докато търсенето в Списъка е малко по-бързо от преди, 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.