Berapa banyak salinan yang dibutuhkan untuk memperbesar array?

Saya membaca analisis tentang array dinamis (dari manual algoritma Skiena).
Yaitu ketika kita memiliki struktur array dan setiap kali kita kehabisan ruang, kita mengalokasikan array baru dua kali lipat ukuran aslinya.

Ini menjelaskan pemborosan yang terjadi ketika array harus diubah ukurannya.
Dikatakan bahwa (n / 2) +1 hingga n akan dipindahkan paling banyak satu kali atau tidak sama sekali. Ini jelas.
Kemudian dengan menjelaskan bahwa separuh elemen bergerak satu kali, seperempat elemen dua kali, dan seterusnya, jumlah total gerakan M diberikan oleh:

Bagi saya ini menambah lebih banyak salinan daripada yang sebenarnya terjadi.

Misalnya

jika kita memiliki yang berikut ini:

array of 1 element
+--+
|a |
+--+

double the array (2 elements)  
+--++--+  
|a ||b |  
+--++--+  

double the array (4 elements)  
+--++--++--++--+  
|a ||b ||c ||c |  
+--++--++--++--+  

double the array (8 elements)  
+--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x |  
+--++--++--++--++--++--++--++--+    

double the array (16 elements)  
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x ||  ||  ||  ||  ||  ||  ||  ||  |   
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+   

Kami memiliki elemen x disalin 4 kali, elemen c disalin 4 kali, elemen b disalin 4 kali dan elemen disalin 5 kali sehingga totalnya adalah 4 + 4 + 4 + 5 = 17 salinan / gerakan.

Tetapi menurut rumus kita harus memiliki 1 * (16/2) + 2 * (16/4) + 3 * (16/8) + 4 * (16/16) = 8 + 8 + 6 + 4 = 26 salinan dari elemen untuk pembesaran array menjadi 16 elemen.

Apakah ini beberapa kesalahan atau tujuan dari formula ini adalah untuk memberikan perkiraan batas atas kasar? Atau apakah saya salah memahami sesuatu di sini?

Pertama, b dipindahkan 3 kali dan a dipindahkan 4 kali, yang memberikan total 4 + 4 + 3 + 4 = 15 salinan.

Saya pikir rumus harus diisi dengan n = 8: 1 * (8/2) (x disalin sekali) + 2 * (8/4) (c disalin dua kali) + 3 * (8/8) (b disalin tiga kali) = 11. Dengan kata lain, rumus tampaknya tidak memiliki istilah "+ log ₂ n +1" selain jumlah itu sendiri.

Apa yang menurut saya merupakan cara yang lebih alami untuk menghitung jumlah gerakan adalah dengan menghitung jumlah elemen yang dipindahkan per salinan:

jumlah dari i = 1 ke i = langit-langit (log ₂ n): 2 ^i-1

Dalam kasus Anda, n = 16, jadi langit-langit (log ₂ 16) = 4 dan jumlah di atas adalah: 2 ⁰ +2 ¹ +2 ² +2 ³ = 1 + 2 + 4 + 8 = 15.

Saya akan melihat apakah saya dapat menemukan manual algoritma Skiena ini untuk melihat apakah saya sudah benar.

Pembaruan: Saya menemukan bagian dalam manual algoritma Skiena. Sepertinya ada istilah yang hilang dalam jumlah yang dia gunakan di sana. Namun, kesimpulannya benar:

M = jumlah dari i = 1 ke i = langit-langit (log ₂ n): 2 ^i-1 = jumlah dari i = 0 sampai i = langit-langit (log ₂ n) - 1: 2 ⁱ = 2 ^{langit-langit (log ₂ n) - 1 + 1} <= (2 ^{log ₂ n + 1 - 1 + 1} ) = 2 * n

(Saya berharap saya bisa memformat formula ini dengan cara yang lebih baik untuk Anda)

Poin utama dari paragraf ini tampaknya adalah untuk memberikan contoh analisis diamortisasi . Metode seperti metode potensial akan membuat argumen yang lebih baik (kurang ad hoc) mengapa array dinamis berkinerja sangat baik, tetapi metode ini agak maju.

Jika Anda yakin ada kesalahan dalam buku ini, Anda dapat mempertimbangkan untuk menghubungi penulis tentang hal ini (tentu saja dengan cara yang konstruktif - buku ini memiliki banyak halaman, dan sulit untuk menyelesaikan semua hal terakhir dengan benar, dan selalu ada kemungkinan buku itu benar dan kami berdua salah). Saya belum menemukan yang satu ini di errata.

Pada level penghitungan blok bawah, tidak mungkin terjadi alokasi memori. Manajer memori menangani blok memori dan secara rutin mengalokasikan blok memori yang lebih besar daripada permintaan alokasi yang diminta.

Demikian juga, implementasi kelas array kemungkinan untuk mengumpulkan alokasi untuk memungkinkan beberapa elemen tambahan.

EDIT:

Pada refleksi lebih lanjut, salinan yang sebenarnya tidak akan terjadi saat Anda menggambarkannya juga. Prosesor biasanya memiliki perintah salin blok dan akan menggunakan instruksi assmbler tunggal untuk menyalin data array sebagai blok memori tunggal ke alamat baru.

Saya percaya formula yang diberikan dalam buku itu tidak benar. The imultiplier harus turun dari rumus untuk memperbaikinya.

Mari kita ambil contoh si penanya dan memanggil larik 1 elemen larik-1, larik 2 elemen - array-2, larik 4 elemen - array-4, dan seterusnya.

Jadi, sesuai dengan buku, untuk contoh khusus ini jumlah salinan diatur oleh rumus berikut:

M = 1⋅8 + 2⋅4 + 3⋅2 + 4⋅1

Istilah pertama dari jumlah tersebut 1⋅8adalah untuk menyalin array-8'sitem ke dalam array-16.

Kami menyalin array-4'sitem (a, b, c, c)dua kali. Sekali dari array-4ke array-8. Dan ketika menyalin array-8'sitem ke array-16kita menyalin (a, b, c, c)item untuk kedua kalinya. Sesuai dengan buku, maka istilah yang kedua: 2⋅4.

Tetapi sekarang perhatikan bahwa 1⋅8istilah tersebut sudah memperhitungkan penyalinan (a, b, c, c)barang dari array-8ke array-16. Karenanya 2⋅4istilah tersebut tidak boleh menyertakan 2pengganda.

Logika yang sama berlaku untuk semua istilah lainnya. Dan mengalikan dengan imerupakan kesalahan.