Apakah Waktu Konstan dan Waktu Konstan yang diamortisasi secara efektif dianggap setara?

Saya perlu menulis RandomQueue yang memungkinkan untuk menambahkan dan menghapus secara acak di Constant Time (O (1)).

Pikiran pertama saya adalah mendukungnya dengan semacam Array (saya memilih ArrayList), karena array memiliki akses konstan melalui indeks.

Melihat dokumentasi itu, saya menyadari bahwa penambahan ArrayLists dianggap Amortized Constant Time, karena penambahan mungkin memerlukan realokasi array yang mendasarinya, yaitu O (n).

Apakah Waktu Konstan diamortisasi dan Waktu Konstan efektif sama, atau apakah saya perlu melihat struktur yang tidak memerlukan realokasi penuh pada setiap penambahan?

Saya bertanya ini karena struktur berbasis array samping (yang sejauh yang saya tahu akan selalu memiliki penambahan Waktu Konstan yang Diamortisasi), saya tidak bisa memikirkan apa pun yang akan memenuhi persyaratan:

• Berbasis pohon apa pun akan memiliki akses O (log n) terbaik
• Daftar yang ditautkan berpotensi memiliki tambahan O (1) (jika referensi ke ekor disimpan), tetapi penghapusan acak harus terbaik O (n).

Inilah pertanyaan lengkapnya; kalau-kalau saya melihat beberapa detail penting:

Mendesain dan mengimplementasikan RandomQueue. Ini adalah implementasi dari antarmuka Antrian di mana operasi remove () menghapus elemen yang dipilih secara seragam di antara semua elemen yang ada dalam antrian. (Pikirkan RandomQueue sebagai tas di mana kita dapat menambahkan elemen atau menjangkau dan membabi buta menghapus beberapa elemen acak.) Operasi add (x) dan remove () dalam RandomQueue harus berjalan dalam waktu konstan per operasi.

Waktu Konstan yang diamortisasi hampir selalu dapat dianggap setara dengan Waktu Konstan, dan tanpa mengetahui spesifikasi aplikasi Anda dan jenis penggunaan yang Anda rencanakan untuk antrian ini, kemungkinan besar Anda akan ditanggung.

Daftar array memiliki konsep kapasitas , yang pada dasarnya sama dengan ukuran / panjang / jumlah item terbesar yang pernah diminta sejauh ini. Jadi, apa yang akan terjadi adalah bahwa pada awalnya daftar array akan terus merealokasi sendiri untuk meningkatkan kapasitasnya saat Anda terus menambahkan item ke dalamnya, tetapi pada titik tertentu jumlah rata-rata item yang ditambahkan per unit waktu pasti akan cocok dengan jumlah rata-rata item dihapus per satuan waktu, (jika tidak, Anda akhirnya akan kehabisan memori,) pada titik mana array akan berhenti mengalokasikan kembali dirinya sendiri, dan semua penambahan akan dipenuhi pada waktu konstan O (1).

Namun, perlu diingat bahwa secara default, penghapusan acak dari daftar array bukan O (1), itu adalah O (N), karena daftar array memindahkan semua item setelah item yang dihapus turun satu posisi ke bawah untuk menggantikan yang dihapus barang. Untuk mencapai O (1) Anda harus mengganti perilaku default untuk mengganti item yang dihapus dengan salinan item terakhir dari daftar array, dan kemudian menghapus item terakhir, sehingga tidak ada item yang akan dipindahkan. Tetapi kemudian, jika Anda melakukan itu, Anda tidak memiliki antrian lagi.

Pertanyaannya tampaknya secara khusus meminta waktu yang konstan, dan bukan diamortisasi waktu yang konstan . Jadi sehubungan dengan pertanyaan yang dikutip, tidak, mereka tidak efektif sama *. Namun apakah mereka dalam aplikasi dunia nyata?

Masalah umum dengan konstanta diamortisasi adalah bahwa kadang-kadang Anda harus membayar akumulasi hutang. Jadi, meskipun sisipan pada umumnya konstan, kadang-kadang Anda harus mengalami overhead memasukkan kembali semuanya ketika blok baru dialokasikan.

Di mana perbedaan antara waktu konstan dan waktu diamortisasi relevan untuk suatu aplikasi tergantung pada apakah kecepatan sangat lambat ini dapat diterima. Untuk sejumlah besar domain, ini biasanya tidak apa-apa. Terutama jika wadah memiliki ukuran maksimum yang efektif (seperti cache, temp buffer, wadah kerja) Anda dapat membayar biaya mereka hanya sekali selama eksekusi.

Sebagai tanggapan terhadap aplikasi penting, waktu ini mungkin tidak dapat diterima. Jika Anda harus memenuhi jaminan waktu penyelesaian yang singkat, Anda tidak dapat mengandalkan algoritme yang terkadang melebihi itu. Saya telah mengerjakan proyek-proyek seperti itu sebelumnya, tetapi mereka sangat jarang.

Ini juga tergantung pada seberapa tinggi biaya ini sebenarnya. Vektor cenderung berkinerja baik karena biaya realokasi relatif rendah. Namun, jika Anda membuka peta hash, realokasi bisa jauh lebih tinggi. Meskipun lagi, untuk sebagian besar aplikasi mungkin baik-baik saja, terutama server yang hidup lebih lama dengan batas atas pada item dalam wadah.

* Tapi ada sedikit masalah di sini. Untuk membuat wadah serba guna menjadi waktu yang konstan untuk penyisipan, salah satu dari dua hal harus disimpan:

• Wadah harus memiliki ukuran maksimum tetap; atau
• Anda dapat menganggap alokasi memori elemen individu adalah waktu yang konstan.

Tergantung - apakah Anda mengoptimalkan untuk throughput atau untuk latensi:

• Sistem yang sensitif terhadap latensi memerlukan kinerja yang konsisten. Untuk skenario seperti itu, kita harus menekankan perilaku terburuk dari sistem. Contohnya adalah sistem waktu nyata lunak seperti game yang ingin mencapai framerate yang konsisten, atau server web yang harus mengirim respons dalam jangka waktu ketat tertentu: membuang-buang siklus CPU lebih baik daripada terlambat.
• Sistem yang dioptimalkan untuk throughput tidak peduli dengan kios sesekali, selama jumlah maksimal data dapat diproses dalam jangka panjang. Di sini, kami terutama tertarik pada kinerja yang diamortisasi. Ini biasanya merupakan kasus untuk pekerjaan menghitung angka atau pekerjaan pemrosesan batch lainnya.

Perhatikan bahwa satu sistem dapat memiliki komponen yang berbeda yang harus dikategorikan berbeda. Misalnya prosesor teks modern akan memiliki utas UI latensi-sensitif, tetapi utas yang dioptimalkan untuk tugas-tugas lain seperti pemeriksaan ejaan atau ekspor PDF.

Juga, kompleksitas algoritmik seringkali tidak menjadi masalah sebanyak yang mungkin kita pikirkan: Ketika suatu masalah terbatas pada angka tertentu, maka karakteristik kinerja aktual dan terukur lebih penting daripada perilaku “untuk n yang sangat besar ”.

Jika Anda diminta untuk algoritma "waktu diamortisasi konstan", algoritma Anda kadang - kadang mungkin memakan waktu lama. Misalnya, jika Anda menggunakan std :: vector dalam C ++, vektor tersebut mungkin telah mengalokasikan ruang untuk 10 objek, dan ketika Anda mengalokasikan objek ke-11, ruang untuk 20 objek dialokasikan, 10 objek disalin, dan ke-11 ditambahkan, yang membutuhkan waktu yang cukup lama. Tetapi jika Anda menambahkan satu juta objek, Anda mungkin memiliki 999.980 operasi cepat dan 20 lambat, dengan waktu rata-rata menjadi cepat.

Jika Anda ditanya algoritma "waktu konstan", algoritme Anda harus selalu cepat, untuk setiap operasi. Itu akan penting untuk sistem waktu nyata di mana Anda mungkin memerlukan jaminan bahwa setiap operasi selalu cepat. "Waktu konstan" sangat sering tidak diperlukan, tetapi jelas tidak sama dengan "waktu konstan diamortisasi".