Hi all, I don’t really understand the solution to this problem. Why go through this complicated setup of pointers? Why can’t we simply use an array with a special value to indicate whether that element is initialized in the original array? For example when we write to A[i] we set P[i] to a known value. I don’t understand the solution that the authors have proposed. Could someone please explain why my scheme wont work and why did the authors choose such a complex solution?
Problem 6.2 - Lazy Initialization
Hey,
It is an old problem that we eventually deprecated. Basic idea is that we don’t want to pay O(n) time to initialize an array since we won’t use all of them so we want to only initialize those until we actually use those entries. This is actually very tricky since many people falsely thought that declaring an array with initial value is O(1) time; in fact, it is O(n) time. If you are interested in that, please take more look at https://en.wikipedia.org/wiki/Lazy_initialization where many discussions are there.
0 Likes
learner
#3
Thanks for your response. I understand the motivation. However what I did not get is reasoning behind using other arrays P and S. This hasn’t been explained well. Could you expand on the reasoning behind using these two arrays?
0 Likes
There is a detailed post about this at http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time
0 Likes