hapus detail implementasi

9

Saya punya pertanyaan detail implementasi kecil yang gagal saya pahami ArrayList::removeIf. Saya tidak berpikir saya bisa mengatakannya seperti itu tanpa prasyarat terlebih dahulu.

Seperti: pelaksanaan pada dasarnya adalah sebuah massal remove , tidak seperti ArrayList::remove. Sebuah contoh seharusnya membuat banyak hal lebih mudah untuk dipahami. Katakanlah saya memiliki daftar ini:

List<Integer> list = new ArrayList<>(); // 2, 4, 6, 5, 5
list.add(2);
list.add(4);
list.add(6);
list.add(5);
list.add(5);

Dan saya ingin menghapus setiap elemen yang genap. Saya bisa melakukan:

Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
    int elem = iter.next();
    if (elem % 2 == 0) {
         iter.remove();
    }
}

Atau :

list.removeIf(x -> x % 2 == 0);

Hasilnya akan sama, tetapi implementasinya sangat berbeda. Karena iteratorini adalah pandangan dari ArrayList, setiap kali saya menelepon remove, yang mendasarinya ArrayListharus dibawa ke keadaan "baik", yang berarti bahwa array batin sebenarnya akan berubah. Sekali lagi, pada setiap panggilan tunggal remove, akan ada panggilan System::arrayCopyinternal.

Sebaliknya removeIflebih pintar. Karena ia melakukan iterasi secara internal, itu dapat membuat hal-hal lebih optimal. Cara melakukan ini menarik.

Ini pertama menghitung indeks di mana elemen seharusnya dihapus. Ini dilakukan dengan terlebih dahulu menghitung kecil BitSet, array longnilai di mana pada setiap indeks, berada suatu 64 bitnilai (a long). Banyak 64 bitnilai membuat ini a BitSet. Untuk menetapkan nilai pada offset tertentu, pertama-tama Anda perlu mengetahui indeks dalam array dan kemudian mengatur bit yang sesuai. Ini tidak terlalu rumit. Katakanlah Anda ingin mengatur bit 65 dan 3. Pertama kita membutuhkan long [] l = new long[2](karena kita melampaui 64 bit, tetapi tidak lebih dari 128 bit):

|0...(60 more bits here)...000|0...(60 more bits here)...000|

Pertama-tama Anda menemukan indeks: 65 / 64(mereka benar-benar melakukannya 65 >> 6) dan kemudian dalam indeks itu ( 1) masukkan bit yang diperlukan:

1L << 65 // this will "jump" the first 64 bits, so this will actually become 00000...10.

Hal yang sama untuk 3. Dengan demikian array panjang itu akan menjadi:

|0...(60 more bits here)...010|0...(60 more bits here)...1000|

Dalam kode sumber, mereka menyebut BitSet ini - deathRow(nama yang bagus!).

Mari kita ambil evencontoh itu di sini, di manalist = 2, 4, 6, 5, 5

  • mereka iterate array dan menghitung ini deathRow(di mana Predicate::testadalah true).

deathRow = 7 (000 ... 111)

arti indeks = [0, 1, 2] harus dihapus

  • mereka sekarang mengganti elemen dalam array yang mendasari berdasarkan deathRow itu (tidak masuk ke detail bagaimana ini dilakukan)

array batin menjadi: [5, 5, 6, 5, 5]. Pada dasarnya mereka memindahkan elemen yang seharusnya tetap berada di depan array.

Saya akhirnya bisa mengajukan pertanyaan.

Pada titik ini, mereka tahu:

 w   ->  number of elements that have to remain in the list (2)
 es  ->  the array itself ([5, 5, 6, 5, 5])
 end ->  equal to size, never changed

Bagi saya, ada satu langkah yang harus dilakukan di sini:

void getRidOfElementsFromWToEnd() {
    for(int i=w; i<end; ++i){
       es[i] = null;
    }
    size = w;
}

Sebaliknya, ini terjadi:

private void shiftTailOverGap(Object[] es, int w, int end) {
    System.arraycopy(es, end, es, w, size - end);
    for (int to = size, i = (size -= end - w); i < to; i++)
        es[i] = null;
}

Saya telah mengganti nama variabel dengan sengaja di sini.

Apa gunanya menelepon:

 System.arraycopy(es, end, es, w, size - end);

Terutama size - end, karena end selalu size - tidak pernah berubah (jadi ini selalu zero). Ini pada dasarnya adalah NO-OP di sini. Kasus sudut apa yang saya lewatkan di sini?

java java-8 iterator Eugene
sumber
2
Saya hanya menghabiskan 1/2 hari untuk memahami detail ini, dan ini sangat jelas, metode ini juga digunakan di tempat lain . Saya seorang idiot: |
Eugene
Jujur, kamu membuatku bingung. Apakah pertanyaan Anda seputar penggunaan System.arraycopy(es, end, es, w, size - end)sebagai detail implementasi yang mendasarinya removeIf? Aku hampir merasa seperti, aku sedang membaca jawaban untuk beberapa pertanyaan lain di antaranya. (Membaca komentar di atas) Saya merasakannya berakhir pada pertanyaan sepele akhirnya. Apakah begitu?
Naman
@ Naman tepatnya, itu tentang itu ditakuti System.arrayCopy. Namun demikian itu adalah perjalanan yang menyenangkan melalui detail (yang ditetapkan bit internal ternyata memiliki ide yang sama seperti java.util.BitSet)
Eugene
@Naman jika mau, Anda dapat memberikan jawaban di mana itu bukan NOOP (petunjuk: range...) dan saya akan menerimanya.
Eugene
1
@Eugene di Java 8, itu digunakan java.util.BitSet. Bagi saya, implementasi ulang BitSetoperasi tidak terlihat jauh lebih baik daripada yang asli. Peluang untuk melewatkan seluruh kata telah terlewatkan.
Holger

Jawaban:

6

Anda melihat kasus khusus (umum) yang daftarnya Anda panggil removeIf, sama dengan ArrayList. Hanya dalam kasus ini, Anda dapat menganggap itu endselalu sama dengan size.

Contoh tandingannya adalah:

ArrayList<Integer> l = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7));
l.subList(2, 5).removeIf(i -> i%2 == 1);

Demikian juga, removeAllakan memanggil shiftTailOverGapdengan endargumen yang dapat berbeda dari sizeketika diterapkan ke subList.

Situasi serupa muncul ketika Anda menelepon clear(). Dalam hal ini, operasi aktual, dilakukan ketika memanggilnya ArrayListsendiri, sangat sepele sehingga bahkan tidak memanggil shiftTailOverGapmetode. Hanya ketika menggunakan sesuatu seperti l.subList(a, b).clear(), itu akan berakhir di removeRange(a, b)atas l, yang pada gilirannya akan, karena Anda sudah tahu sendiri, Invoke shiftTailOverGap(elementData, a, b)dengan byang bisa lebih kecil dari size.

Holger
sumber