Menyimpan inisialisasi array

Saya baru-baru ini membaca bahwa dimungkinkan untuk memiliki array yang tidak perlu diinisialisasi, yaitu dimungkinkan untuk menggunakannya tanpa harus menghabiskan waktu mencoba mengatur setiap anggota ke nilai default. yaitu Anda dapat mulai menggunakan array seolah-olah telah diinisialisasi dengan nilai default tanpa harus menginisialisasi itu. (Maaf, saya tidak ingat di mana saya membaca ini).

Misalnya mengapa itu bisa mengejutkan:

Katakanlah Anda mencoba membuat model kasus terburuk hashtable (untuk setiap sisipan / hapus / cari) bilangan bulat dalam kisaran .$\mathcal{O}(1)$$[1, n^2]$

Anda dapat mengalokasikan array ukuran bit dan menggunakan bit individual untuk mewakili keberadaan integer dalam hashtable. Catatan: mengalokasikan memori dianggap sebagai waktu.O ( 1 $n^2$$\mathcal{O}(1)$

Sekarang, jika Anda tidak perlu menginisialisasi array ini sama sekali, urutan operasi say pada hashtable ini sekarang menjadi case terburuk .O ( n $n$$\mathcal{O}(n)$

Jadi sebenarnya, Anda memiliki implementasi hash "sempurna", yang untuk urutan operasi menggunakan ruang , tetapi berjalan dalam waktu !Θ ( n 2 ) O ( n $n$$\Theta(n^2)$$\mathcal{O}(n)$

Biasanya orang akan mengharapkan runtime Anda setidaknya seburuk penggunaan ruang Anda!

Catatan: Contoh di atas dapat digunakan untuk implementasi set jarang atau matriks jarang, jadi itu bukan hanya kepentingan teoritis, saya kira.

Jadi pertanyaannya adalah:

Bagaimana mungkin untuk memiliki array seperti struktur data yang memungkinkan kita untuk melewatkan langkah inisialisasi?

Ini adalah trik yang sangat umum, yang dapat digunakan untuk tujuan lain selain hashing. Di bawah ini saya berikan implementasi (dalam pseudo-code).

Mari tiga vektor diinisiasi , dan dari ukuran masing-masing. Kami akan menggunakan ini untuk melakukan operasi yang diminta oleh struktur data kami. Kami juga mempertahankan variabel . Operasi diimplementasikan sebagai berikut:P V n p o $A$$P$$V$$n$$pos$

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i) 
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i) 
  return A[i] 
else 
  return empty 

Array hanya menyimpan nilai-nilai yang dilewatkan melalui prosedur yang . Array dan berfungsi sebagai sertifikat yang dapat mengetahui apakah posisi yang diberikan dalam telah diinisialisasi.s e t V P $A$$set$$V$$P$$A$

Perhatikan bahwa setiap saat elemen dalam mulai dari hingga diinisialisasi. Oleh karena itu kita dapat dengan aman menggunakan nilai-nilai ini sebagai sertifikat untuk nilai-nilai diinisialisasi di . Untuk setiap posisi dalam yang diinisialisasi, ada elemen yang sesuai dalam vektor yang nilainya sama dengan . Ini ditunjukkan oleh . Oleh karena itu, jika kita melihat elemen yang sesuai, dan nilainya adalah , kita tahu bahwa telah diinisialisasi (sejak0 p o s - 1 A i A P I V [ i ] P [ V [ i ] ] i A [ i ] P A [ i ] V [ i ] P 0 .. p o s - 1 P [ j ] A P [ j ] ≠ i A [ i $P$$0$$pos-1$$A$$i$$A$$P$$i$$V[i]$$P[V[i]]$$i$$A[i]$$P$tidak pernah bohong, karena semua elemen yang kita pertimbangkan diinisialisasi). Demikian pula, jika tidak diinisialisasi, maka dapat menunjuk ke suatu posisi dalam di luar kisaran , ketika kita tahu pasti bahwa itu tidak diinisialisasi, atau dapat menunjuk ke suatu posisi dalam kisaran itu. Tetapi sesuai dengan posisi yang berbeda dalam , dan karenanya , jadi kita tahu bahwa belum diinisialisasi.$A[i]$$V[i]$$P$$0..pos-1$$P[j]$$A$$P[j] \neq i$$A[i]$

Sangat mudah untuk melihat bahwa semua operasi ini dilakukan dalam waktu yang konstan. Juga, ruang yang digunakan adalah untuk masing-masing vektor, dan untuk variabel , oleh karena itu secara total.O ( 1 ) p o s O ( n $O(n)$$O(1)$$pos$$O(n)$