Editing Lazy initialization (section)

== Theoretical computer science ==

In the field of [[theoretical computer science]], '''lazy initialization'''<ref>{{Cite book|last1=Moret|first1=B. M. E.|title=Algorithms from P to NP, Volume 1: Design & Efficiency|last2=Shapiro|first2=H. D.|publisher=Benjamin/Cummings Publishing Company|year=1991|isbn=0-8053-8008-6|pages=191–192}}</ref> (also called a '''lazy array''') is a technique to design [[data structure]]s that can work with memory that does not need to be initialized. Specifically, assume that we have access to a table ''T'' of ''n'' uninitialized memory cells (numbered from ''1'' to ''n''), and want to assign ''m'' cells of this array, e.g., we want to assign ''T''[''k<sub>i</sub>''] := ''v<sub>i</sub>'' for pairs (''k''<sub>1</sub>, ''v''<sub>1</sub>), ..., (''k<sub>m</sub>'', ''v<sub>m</sub>'') with all ''k<sub>i</sub>'' being different. The lazy initialization technique allows us to do this in just O(''m'') operations, rather than spending O(''m''+''n'') operations to first initialize all array cells. The technique is simply to allocate a table ''V'' storing the pairs (''k<sub>i</sub>'', ''v<sub>i</sub>'') in some arbitrary order, and to write for each ''i'' in the cell ''T''[''k<sub>i</sub>''] the position in ''V'' where key ''k<sub>i</sub>'' is stored, leaving the other cells of ''T'' uninitialized. This can be used to handle queries in the following fashion: when we look up cell ''T''[''k''] for some ''k'', we can check if ''T''[''k''] is in the range {1, ..., ''m''}: if it is not, then ''T''[''k''] is uninitialized. Otherwise, we check ''V''[''T''[''k'']], and verify that the first component of this pair is equal to ''k''. If it is not, then ''T''[''k''] is uninitialized (and just happened by accident to fall in the range {1, ..., ''m''}). Otherwise, we know that ''T''[''k''] is indeed one of the initialized cells, and the corresponding value is the second component of the pair.