Periksa apakah Array Java Berisi Nilai

1. Ikhtisar

Dalam artikel ini, kita akan melihat berbagai cara untuk mencari array untuk nilai tertentu.

Kami juga akan membandingkan cara kerjanya menggunakan JMH (Java Microbenchmark Harness) untuk menentukan metode mana yang bekerja paling baik.

2. Penyiapan

Untuk contoh kami, kami akan menggunakan larik yang berisi String yang dibuat secara acak untuk setiap pengujian:

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

Untuk menggunakan kembali larik di setiap tolok ukur, kami akan mendeklarasikan kelas dalam untuk menampung larik dan jumlah sehingga kami dapat mendeklarasikan cakupannya untuk JMH:

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

3. Pencarian Dasar

Tiga metode yang umum digunakan untuk mencari sebuah array adalah sebagai Daftar, sebuah Set, atau dengan lingkaran yang meneliti setiap anggota sampai menemukan kecocokan.

Mari kita mulai dengan tiga metode yang mengimplementasikan setiap algoritma:

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

Kami akan menggunakan anotasi kelas ini untuk memberi tahu JMH untuk menghasilkan waktu rata-rata dalam mikrodetik dan menjalankan lima iterasi pemanasan untuk memastikan bahwa pengujian kami dapat diandalkan:

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

Dan jalankan setiap pengujian dalam satu putaran:

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

Saat kami menjalankan 1000 pencarian untuk setiap metode, hasil kami terlihat seperti ini:

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 

Pencarian loop lebih efisien daripada yang lain. Tetapi ini setidaknya sebagian karena cara kami menggunakan koleksi.

Kami membuat contoh Daftar baru dengan setiap panggilan ke searchList () dan Daftar baru dan HashSet baru dengan setiap panggilan ke searchSet () . Membuat objek-objek ini menciptakan biaya tambahan yang tidak dilakukan perulangan melalui array.

4. Pencarian Lebih Efisien

Apa yang terjadi jika kita membuat satu contoh List dan Set dan kemudian menggunakannya kembali untuk setiap pencarian?

Mari kita coba:

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

Kami akan menjalankan metode ini dengan anotasi JMH yang sama seperti di atas, dan menyertakan hasil untuk loop sederhana sebagai perbandingan.

Kami melihat hasil yang sangat berbeda:

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 

Saat mencari Daftar sedikit lebih cepat dari sebelumnya, Set turun menjadi kurang dari 1 persen dari waktu yang diperlukan untuk pengulangan!

Sekarang kami telah menghapus waktu yang diperlukan untuk membuat Koleksi baru dari setiap penelusuran, hasil ini masuk akal.

Pencarian tabel hash, struktur yang mendasari HashSet , memiliki kompleksitas waktu 0 (1), sedangkan array, yang mendasari ArrayList adalah 0 (n).

5. Pencarian Biner

Metode lain untuk mencari array adalah pencarian biner. Meskipun sangat efisien, pencarian biner mengharuskan array diurutkan terlebih dahulu.

Mari mengurutkan array dan mencoba pencarian biner:

@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 

Pencarian biner sangat cepat, meskipun kurang efisien dibandingkan HashSet: kinerja kasus terburuk untuk pencarian biner adalah 0 (log n), yang menempatkan performanya di antara pencarian array dan tabel hash.

6. Kesimpulan

Kami telah melihat beberapa metode pencarian melalui array.

Berdasarkan hasil kami, HashSet berfungsi paling baik untuk mencari melalui daftar nilai. Namun, kita perlu membuatnya terlebih dahulu dan menyimpannya di Set.

Seperti biasa, kode sumber lengkap dari contoh tersedia di GitHub.