Masalah dan Senario Penggunaan
Menggunakan fixed array, laksanakan dynamic array dengan get(index), set(index, value) dan append(value). Lakukan resize apabila penuh, terangkan dasar pertumbuhan, tingkah laku sempadan, masa append kes terburuk dan terpelunasan, serta bandingkan pertumbuhan linear dengan geometri.
Andaikan rujukan atau nilai bersaiz tetap, indeks berasaskan sifar, pengecualian untuk capaian luar julat, dan append pada tatasusunan kosong. Bank temu duga awam menghubungkan pelaksanaan dynamic array/vektor dengan Microsoft, pengurusan memori dan analisis terpelunasan; MIT 6.006 menyenaraikan append dynamic array sebagai terpelunasan Θ(1).
Perkara yang Dinilai oleh Penemu Duga
- Sama ada anda memisahkan
sizedaripadacapacitydan mengekalkan invarian bahawa item yang sah menduduki slotsizepertama. - Sama ada anda memilih pertumbuhan geometri dan bukannya menambah satu slot pada satu masa.
- Sama ada anda boleh membuktikan batas terpelunasan dengan analisis agregat, perakaunan atau potensi dan bukannya sekadar mendakwa O(1).
- Sama ada anda merangkumi kapasiti sifar, limpahan integer (overflow), kegagalan peruntukan, pengecutan (shrinking) dan sisipan di tengah.
Soalan Penjelasan Sebelum Menjawab
- Adakah hanya tail append diperlukan, atau adakah insert di tengah, delete dan pop juga diperlukan? Ini mengubah analisis kerumitan.
- Adakah nilai bersaiz tetap? Adakah semantik rujukan, ketidaksahan lelaran (iterator invalidation), atau keselamatan bebenang (thread safety) diperlukan?
- Adakah matlamatnya kurang salinan, overhed memori yang lebih rendah, atau had latensi yang ketat?
- Adakah pengecutan diperlukan? Jika ya, patutkah ambang pengecutannya diasingkan daripada ambang pertumbuhan untuk mengelakkan thrashing?
Rangka Jawapan 30 Saat
Saya akan menyimpan backing array, size dan capacity. Append menulis secara terus apabila slot kosong tersedia. Apabila penuh, ia memperuntukkan tatasusunan yang lebih besar, menyalin elemen size pertama, dan menulis nilai baharu. Pertumbuhan geometri seperti penggandaan adalah kunci: jumlah keseluruhan elemen yang disalin sepanjang n append ialah siri geometri di bawah 2n, jadi jumlah kerja ialah O(n) dan append adalah terpelunasan O(1). Panggilan resize itu sendiri masih O(n), jadi ini bukan jaminan O(1) kes terburuk bagi setiap panggilan.
Analisis Mendalam Langkah Demi Langkah
Keadaan dan Invarian
Kekalkan tiga medan: backing array data, bilangan elemen sah size, dan slot diperuntukkan capacity. Sentiasa pastikan saiz sekurang-kurangnya sifar dan tidak lebih besar daripada kapasiti; elemen yang sah menduduki [0, size). Append menulis pada data[size] dan meningkatkan saiz. get dan set hanya menerima [0, size), tidak sekali-kali slot kapasiti yang belum dimulakan.
Dasar Pertumbuhan Geometri
Apabila size == capacity, peruntukkan sekurang-kurangnya max(1, capacity * 2), salin elemen lama, dan gantikan rujukan backing. Kapasiti sifar memerlukan kes khas, jika tidak pendaraban tetap menghasilkan sifar. Penggandaan menghasilkan siri append murah yang setanding dengan saiz semasa; faktor yang lebih besar menyalin dengan lebih jarang tetapi meninggalkan lebih banyak ruang yang tidak digunakan.
~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;
public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }
public int size() { return size; }
public Object get(int index) { check(index); return data[index]; }
public void set(int index, Object value) { check(index); data[index] = value; }
private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~
Object[] ialah cara biasa untuk menggambarkan pelaksanaan di bawah generic type erasure; kod pengeluaran masih memerlukan dasar eksplisit untuk null, kegagalan peruntukan dan kekompaunan (concurrency). Invarian dan kerumitan tidak bergantung pada Java.
Bukti Terpelunasan
Andaikan kapasiti bermula pada 1 dan berganda. Sepanjang n append, penulisan biasa mengambil kos pemalar n; salinan resize berlaku pada kapasiti 1, 2, 4, 8 dan seterusnya, dengan jumlah keseluruhan di bawah 2n. Oleh itu, jumlah kerja adalah di bawah 3n ditambah pemulaan, memberikan kos terpelunasan O(1) bagi setiap operasi.
Ini adalah jaminan ke atas jujukan kes terburuk, bukan purata ke atas input rawak. Append yang mencetuskan resize masih menyalin elemen Θ(n), jadi satu panggilan mempunyai masa kes terburuk O(n). get dan set adalah O(1) kes terburuk, dan storan backing adalah O(n).
Pertumbuhan Linear dan Pengecutan
Menambah hanya c slot pada satu masa menjadikan kos penyalinan kira-kira c + 2c + ...; memasukkan n elemen menelan kos Θ(n²), jadi append merosot kepada terpelunasan Θ(n). Pertumbuhan geometri biasanya merupakan pertukaran (trade-off) yang lebih baik, walaupun faktor yang lebih besar meningkatkan ruang puncak yang tidak digunakan.
Jika pop disokong, kecilkan tatasusunan di bawah paras minimum penggunaan. Jarakkan ambang pertumbuhan dan pengecutan—contohnya, gandakan apabila penuh dan kurangkan separuh apabila di bawah satu perempat—untuk mengelakkan pemindahan berulang apabila append dan pop bersilih ganti. Pengecutan mengekalkan operasi tail terpelunasan O(1) tetapi menambah jeda pelepasan dan penyalinan.
Sempadan yang Boleh Diuji
Uji append pertama pada tatasusunan kosong, append pada kapasiti tepat, pertumbuhan berulang, rujukan pendua, indeks negatif, index == size, kapasiti besar, overflow, dan kegagalan peruntukan. Pembilang salinan terkawal boleh mengesahkan bahawa n append melakukan jumlah salinan Θ(n); hanya memeriksa kandungan akhir akan membiarkan pelaksanaan pertumbuhan linear kuadratik lulus.
Contoh Jawapan Berkualiti Tinggi
Saya akan memisahkan backing array, size dan capacity, dengan elemen yang sah sentiasa berada pada kedudukan size pertama. Append menulis ke dalam kapasiti kosong; apabila penuh, ia memperuntukkan dua kali ganda kapasiti, menyalin elemen lama, dan kemudian menulis nilai tersebut. Kapasiti awal sifar mendapat kes khas satu slot.
Bukti penggandaan adalah bahagian penting: sepanjang n append, salinan resize kekal di bawah 2n; menambah n penulisan malar menghasilkan jumlah kerja O(n) dan append terpelunasan O(1). Panggilan resize itu sendiri kekal O(n), jadi kos terpelunasan bukanlah had siling latensi bagi setiap panggilan. Pertumbuhan linear menelan kos Θ(n²) dalam jumlah salinan. Jika pengecutan diperlukan, saya akan menggunakan histeresis dan menguji input kosong, sempadan, overflow dan kegagalan peruntukan.
Kesilapan Lazim
- Tambah satu slot setiap kali penuh → jumlah penyalinan menjadi kuadratik → gunakan pertumbuhan geometri dan tunjukkan sirinya.
- Menyatakan append ialah kes terburuk O(1) → mengabaikan salinan resize → bezakan O(n) bagi satu panggilan daripada O(1) terpelunasan untuk jujukan.
- Mengesahkan
getterhadap kapasiti → mengembalikan slot yang belum dimulakan → wajibkan indeks sekurang-kurangnya sifar dan di bawah saiz. - Menggandakan kapasiti sifar → tatasusunan tidak pernah berkembang → gunakan kapasiti minimum satu.
- Mengecutkan serta-merta pada penggunaan rendah → append/pop berselang-seli menyebabkan pergerakan data berulang kali → asingkan ambang pertumbuhan dan pengecutan.
Soalan Susulan dan Jawapan
Bagaimana jika setiap append mesti mempunyai masa kes terburuk O(1)?
Resize tatasusunan bersebelahan (contiguous array) melakukan migrasi O(n), jadi ia tidak boleh menjanjikan had ketat itu seperti yang ditulis. Tatasusunan bersegmen, migrasi bertahap (incremental), atau pra-peruntukan batas atas yang diketahui boleh mengubah pertukaran ini, dengan mengorbankan lokaliti, pemalar pengindeksan, atau ruang. Mula-mula sahkan sama ada keperluannya benar-benar kes terburuk.
Apakah yang berubah jika faktor pertumbuhan ialah 1.25 dan bukannya 2?
Sebarang faktor yang lebih besar daripada 1 masih memberikan append tail terpelunasan O(1), tetapi penyalinan berlaku lebih kerap dan ruang ganti lebih rendah. Apabila faktor menghampiri 1, pemalar meningkat; pilih berdasarkan belanjawan memori, tingkah laku peruntuk memori, dan matlamat latensi dan bukannya Big-O semata-mata.
Bagaimana anda membuktikan pertumbuhan linear ialah O(n²)?
Jika setiap resize menambah c slot, resize ke-j menyalin kira-kira jc elemen. n elemen pertama mencetuskan kira-kira n/c resize, jadi jumlahnya ialah c + 2c + ... + (n/c)c = Θ(n²). Oleh itu, append terpelunasan ialah Θ(n).
Bagaimanakah sisipan di tengah mengubah kerumitan?
Walaupun dengan kapasiti ganti, sisipan di tengah menganjakkan akhiran (suffix) dan merupakan kes terburuk O(n). Menyalin semasa resize adalah kerja tambahan; dynamic array dioptimumkan untuk capaian rawak dan operasi tail, bukan setiap jenis sisipan.
Bagaimanakah concurrent append berfungsi?
Gunakan kunci (lock), pemilikan bebenang tunggal, atau protokol indeks atomik dengan resize yang diselaraskan. Menjadikan size atomik sahaja tidak melindungi keseluruhan jujukan semak kapasiti, peruntukkan, salin dan terbitkan. Jika konkurensi tidak diperlukan, nyatakan sempadan bebenang tunggal secara eksplisit.