Kami terbiasa dengan fakta bahwa koleksi standar di JDK dibuat dengan cukup baik dan berperilaku intuitif. Tapi benarkah begitu? Kemarin Roman Elizarovelizarovdiposting di Twitter berita tentang kusen baru yang menarik.Pegang erat-erat: Set.removeAll(list)dalam kasus tertentu ini dapat bekerja untuk O (N²). Bagaimana?
Roman menemukan masalah ketika dia men-debug kode yang, karena alasan yang luar biasa, bekerja terlalu lambat. Dia meluncurkannya di profiler bawaan di IntelliJ IDEA dan langsung melihat pada grafik nyala bahwa dia menghabiskan semua waktu di dalam metode AbstractSet.removeAllpanggilan list.contains(tautan ke tempat yang tepat dalam kode ).Untuk memahami apa yang terjadi, pertimbangkan contoh yang sedikit berbeda. Sebelumnya, Jon Skeet menulis posting "Ada lubang di abstraksi saya, Liza sayang, Liza sayang" , di mana ia mempertimbangkan kasus menarik berikut.Katakanlah kita memiliki HashSet dari mana kita akan menghapus sesuatu. Misalkan kita menghapus elemen dari koleksi B lainnya dari satu koleksi A. Sering terjadi bahwa banyak elemen dari B tidak ada di A. Kami akan menganalisis kasus khusus ketika A dan B tidak berpotongan sama sekali - yaitu, tidak ada yang perlu dilakukan.Kami akan menulis program sederhana di mana ukuran koleksi kami diatur dari baris perintah. Agar himpunan ini tidak tepat berpotongan, salah satunya hanya akan diisi dengan angka positif, dan yang lainnya hanya dengan angka negatif. Lalu kami menghapus dari koleksi pertama semua elemen yang kedua dan mengukur waktu yang telah berlalu menggunakanSystem.currentTimeMillis(). Ini bukan cara terbaik di dunia untuk menghitung interval waktu, tetapi memungkinkan untuk menyalin-menempelkan kode secara langsung dari Habr ke Idea dan menyelamatkan kita dari keharusan membuat proyek Maven baru untuk JMH.import java.util.*;
public class Test {
public static void main(String[] args) {
int sourceSize = Integer.parseInt(args[0]);
int removalsSize = Integer.parseInt(args[1]);
Set<Integer> source = new HashSet<Integer>();
Collection<Integer> removals = new ArrayList<Integer>();
for (int i = 0; i < sourceSize; i++) {
source.add(i);
}
for (int i = 1; i <= removalsSize; i++) {
removals.add(-i);
}
long start = System.currentTimeMillis();
source.removeAll(removals);
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (end - start) + "ms");
}
}
Kode yang sangat sederhana yang dapat ditulis tanpa mendapatkan kembali kesadaran. Sekarang mari kita jalankan dengan parameter yang berbeda. Pertama, coba satu set 100 elemen dari mana Anda perlu membuang 100:$ java Test 100 100
Time taken: 1ms
Sejauh ini, semuanya cukup cepat, tetapi apa yang terjadi jika Anda menambah jumlahnya?java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
Bagaimana Anda suka ini: sekarang kita tunggu tiga menit. Tampaknya secara intuitif bahwa waktu pemrosesan koleksi yang lebih kecil (300.000 item dalam kasus kedua) harus kurang dari ketika memproses koleksi yang lebih besar (satu juta item dalam kasus pertama). Semuanya sebaliknya. Hidup tidak mempersiapkan ini, kan?Sekarang rahasia fokus.Bahkan, dijelaskan dalam teks yang jelas di JavaDoc yang sesuai :Kode implementasi menentukan apakah kurang: set atau koleksi. Ini dilakukan dengan menggunakan metode sizepada masing-masing. Jika ada lebih sedikit elemen dalam set, maka iterasi dilakukan pada set, dan pada setiap iterasi diperiksa apakah elemen saat ini ada dalam koleksi. Jika ya, maka elemen tersebut dihapus dari set menggunakan metode removeiterator. Jika ternyata koleksi lebih sedikit dalam jumlah elemen, maka akan perlu untuk memotong koleksi sudah, menghapus dari set semua elemen seperti menggunakan metode removedari set.
Dalam praktiknya, ini berarti bahwa ketika dipanggil source.removeAll(removals):- Jika koleksi adalah
removalslebih kecil dari source, maka metode ini disebut removedalam HashSet, dan itu cukup cepat; - Jika koleksinya
removalslebih besar atau berukuran sama dengan source, maka metode ini disebut removals.containsbekerja sangat lambat ArrayList.
Dalam JDK 8, sesuatu seperti ini bertanggung jawab atas bagian kode ini:public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
Tampaknya JDK telah memilih cara yang agak buruk untuk mengatasi tugas, tetapi karena sudah dijelaskan dalam JavaDoc, tidak ada jalan untuk kembali.Atau disana?Orang-orang bergegas ke tweet Roman Yelizarov, dan Zheka Kozlov menemukan bug yang sesuai yang diposting di JDK 15 dengan pemainnya, Stuart Marx.Dan setelah ini, Stuart Marx sendiri masuk ke dalam utas dan mengkonfirmasi bahwa dia benar-benar berurusan dengan masalah ini:Jadi ada cahaya di ujung terowongan. Jika Anda meningkatkan ke versi Java terbaru, tentu saja.temuan
Kesimpulan dari cerita ini adalah sebagai berikut: ada masalah yang perlu diketahui. Masalahnya sudah diperbaiki, tetapi diperbaiki hanya untuk pengguna Java segar yang bahagia, dan Anda seharusnya tidak benar-benar berharap untuk itu.Secara umum, ketika Anda mencoba untuk menyimpan banyak data dalam koleksi di Jawa, Anda mungkin mengalami berbagai masalah tidak intuitif yang perlu dipersiapkan.
Jadi, anak-anak, hari ini kami belajar sesuatu yang baru!Sebagai kelanjutan perjamuan, saya sarankan Anda melihat beberapa laporan Roman Elizarov, yang membantu membawa bug ini terungkap. Tentu saja, laporan ini tidak ada hubungannya dengan bug itu sendiri, tetapi ada banyak pelat timah yang berbeda:JPoint, , 2020 . , , , .