Mengapa push_back dalam vektor C ++ konstan diamortisasi?

Saya belajar C ++ dan memperhatikan bahwa waktu berjalan untuk fungsi push_back untuk vektor adalah konstan "diamortisasi." Dokumentasi lebih lanjut mencatat bahwa "Jika realokasi terjadi, realokasi itu sendiri hingga linier di seluruh ukuran."

Bukankah ini berarti fungsi push_back adalah , di mana adalah panjang vektor? Bagaimanapun, kami tertarik pada analisis kasus terburuk, bukan?$O(n)$$n$

Saya kira, yang terpenting, saya tidak mengerti bagaimana kata sifat "diamortisasi" mengubah waktu berjalan.

Kata penting di sini adalah "diamortisasi". Analisis diamortisasi adalah teknik analisis yang meneliti urutan operasi . Jika seluruh urutan berjalan dalam waktu T ( n ) , maka setiap operasi dalam urutan berjalan dalam T ( n ) / n . Idenya adalah bahwa sementara beberapa operasi dalam urutan mungkin mahal, mereka tidak dapat terjadi cukup sering untuk membebani program. Penting untuk dicatat bahwa ini berbeda dari analisis kasus rata-rata pada beberapa distribusi input atau analisis acak. Analisis diamortisasi merupakan kasus terburuk$n$$T(n)$$T(n)/n$terikat untuk kinerja suatu algoritma terlepas dari input. Ini paling umum digunakan untuk menganalisis struktur data, yang memiliki status persisten di seluruh program.

Salah satu contoh paling umum yang diberikan adalah analisis stack dengan operasi multipop yang muncul elemen . Analisis naif dari multipop akan mengatakan bahwa dalam kasus terburuk multipop harus memakan waktu O ( n ) karena mungkin harus menghilangkan semua elemen stack. Namun, jika Anda melihat urutan operasi, Anda akan melihat bahwa jumlah muncul tidak dapat melebihi jumlah dorongan. Jadi pada urutan n operasi apa pun, jumlah pops tidak dapat melebihi O ( n ) , sehingga multipop berjalan dalam O ( 1 ) waktu diamortisasi meskipun kadang-kadang satu panggilan mungkin membutuhkan lebih banyak waktu.$k$$O(n)$$n$$O(n)$$O(1)$

Sekarang bagaimana hubungannya dengan vektor C ++? Vektor diimplementasikan dengan array sehingga untuk meningkatkan ukuran vektor Anda harus merealokasi memori dan menyalin seluruh array. Jelas kami tidak ingin sering melakukannya. Jadi jika Anda melakukan operasi push_back dan vektor perlu mengalokasikan lebih banyak ruang, itu akan menambah ukuran dengan faktor . Sekarang ini membutuhkan lebih banyak memori, yang mungkin tidak Anda gunakan secara penuh, tetapi beberapa operasi push_back berikutnya semuanya berjalan dalam waktu yang konstan.$m$

Sekarang jika kita melakukan analisis diamortisasi dari operasi push_back (yang saya temukan di sini ) kita akan menemukan bahwa itu berjalan dalam waktu diamortisasi konstan. Misalkan Anda memiliki item dan faktor multiplikasi Anda adalah m . Maka jumlah relokasi kira-kira log m ( n ) . The i realokasi th akan dikenakan biaya sebanding dengan m i , tentang ukuran array saat ini. Jadi total waktu untuk n push back adalah β log m ( n ) i = 1 m i ≈ n $n$$m$$\log_m(n)$$i$$m^i$$n$ , karena ini adalah deret geometri. Bagilah ini denganoperasindan kami mendapatkan bahwa setiap operasi membutuhkan$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$ , sebuah konstanta. Terakhir Anda harus berhati-hati dalam memilih faktor Andam. Jika terlalu dekat dengan1maka konstanta ini menjadi terlalu besar untuk aplikasi praktis, tetapi jikamterlalu besar, katakanlah 2, maka Anda mulai membuang banyak memori. Tingkat pertumbuhan yang ideal bervariasi berdasarkan aplikasi, tetapi saya pikir beberapa implementasi menggunakan1,5.$\frac{m}{m-1}$$m$$1$$m$$1.5$

Meskipun @Marc telah memberikan (apa yang saya pikir) analisis yang sangat baik, beberapa orang mungkin lebih suka mempertimbangkan hal-hal dari sudut yang sedikit berbeda.

Pertama adalah mempertimbangkan cara yang sedikit berbeda dalam melakukan realokasi. Alih-alih segera menyalin semua elemen dari penyimpanan lama ke penyimpanan baru, pertimbangkan untuk menyalin hanya satu elemen pada satu waktu - yaitu, setiap kali Anda melakukan push_back, itu menambahkan elemen baru ke ruang baru, dan menyalin tepat satu yang sudah ada elemen dari ruang lama ke ruang baru. Dengan asumsi faktor pertumbuhan 2, cukup jelas bahwa ketika ruang baru penuh, kita akan selesai menyalin semua elemen dari ruang lama ke ruang baru, dan setiap push_back adalah waktu yang persis konstan. Pada saat itu, kami akan membuang ruang lama, mengalokasikan blok memori baru yang dua kali lebih besar, dan mengulangi prosesnya.

Cukup jelas, kita dapat melanjutkan ini tanpa batas waktu (atau selama masih ada memori tersedia) dan setiap push_back akan melibatkan penambahan satu elemen baru dan menyalin satu elemen lama.

Implementasi yang khas masih memiliki jumlah salinan yang persis sama - tetapi alih-alih melakukan salinan satu per satu, ia menyalin semua elemen yang ada sekaligus. Di satu sisi, Anda benar: itu berarti bahwa jika Anda melihat setiap doa push_back, beberapa di antaranya akan jauh lebih lambat daripada yang lain. Namun, jika kita melihat rata-rata jangka panjang, jumlah penyalinan yang dilakukan per permintaan push_back tetap konstan, terlepas dari ukuran vektor.

Meskipun tidak relevan dengan kompleksitas komputasi, saya pikir ada baiknya menunjukkan mengapa menguntungkan untuk melakukan hal-hal seperti yang mereka lakukan, daripada menyalin satu elemen per push_back, sehingga waktu per push_back tetap konstan. Setidaknya ada tiga alasan untuk dipertimbangkan.

Yang pertama adalah ketersediaan memori. Memori lama dapat dibebaskan untuk penggunaan lain hanya setelah penyalinan selesai. Jika Anda hanya menyalin satu item pada suatu waktu, blok memori lama akan tetap dialokasikan lebih lama. Bahkan, Anda akan memiliki satu blok lama dan satu blok baru yang pada dasarnya dialokasikan setiap saat. Jika Anda memutuskan faktor pertumbuhan yang lebih kecil dari dua (yang biasanya Anda inginkan), Anda akan membutuhkan lebih banyak memori yang dialokasikan setiap saat.

Kedua, jika Anda hanya menyalin satu elemen lama pada satu waktu, pengindeksan ke dalam array akan sedikit lebih rumit - setiap operasi pengindeksan perlu mencari tahu apakah elemen pada indeks yang diberikan saat ini berada di blok memori lama atau baru. Itu tidak terlalu rumit dengan cara apa pun, tetapi untuk operasi dasar seperti pengindeksan ke dalam array, hampir semua pelambatan bisa menjadi signifikan.

Ketiga, dengan menyalin sekaligus, Anda memanfaatkan caching dengan lebih baik. Menyalin sekaligus, Anda dapat mengharapkan sumber dan tujuan berada di cache dalam banyak kasus, sehingga biaya dari cache yang ketinggalan diamortisasi selama jumlah elemen yang sesuai dengan garis cache. Jika Anda menyalin satu elemen pada satu waktu, Anda mungkin dengan mudah kehilangan cache untuk setiap elemen yang Anda salin. Itu hanya mengubah faktor konstan, bukan kompleksitas, tetapi masih bisa cukup signifikan - untuk mesin biasa, Anda dapat dengan mudah mengharapkan faktor 10 hingga 20.

Mungkin juga patut mempertimbangkan arah lain sejenak: jika Anda mendesain sistem dengan persyaratan waktu nyata, mungkin lebih baik untuk menyalin hanya satu elemen pada satu waktu alih-alih sekaligus. Meskipun kecepatan keseluruhan mungkin (atau mungkin tidak) lebih rendah, Anda masih memiliki batas atas yang sulit pada waktu yang dibutuhkan untuk satu eksekusi push_back - anggap Anda memiliki pengalokasi waktu nyata (meskipun tentu saja, banyak waktu nyata sistem hanya melarang alokasi memori dinamis sama sekali, setidaknya sebagian dengan persyaratan waktu nyata).