題目：

9. One problem with trading more space to use less time is that initializing the space can itself take a great deal of time. Show how to circumvent this problem by designing a technique to initialize an entry of a vector to zero the first time it is accessed. Your scheme should use constant time for initialization and for each vector access, and use extra space proportional to the size of the vector.

Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is dear and the vector is sparse.

提供的參考答案：

The effect of initializing the vector data[0..n-1] can be accomplished with a signature contained in two additional n-element vectors, from and to, and an integer, top. If the element data[i] has been initialized, then from [i] < top and to[from[i]] = i. Thus from is a simple signature ,and to and top together make sure that from is not accidentally signed by the random contents of memory.

Blank entries of data are uninitialized in this picture:

        data :  ｜  ｜3 ｜  ｜2  ｜   ｜ 8 ｜   ｜   ｜

        from：｜  ｜0｜   ｜2 ｜   ｜ 1 ｜   ｜  ｜

        to：     ｜1｜5｜3｜    ｜   ｜    ｜    ｜   ｜

The variable top is initially zero; the array element i is first accessed by the code

        from[i] = top

        to[top]  = i

        data[i]  = 0

        top++

This problem and solution are form Exercise 2.12 of Aho, Hopcroft and Ullman's Design and Analysis of Computer Algorithms. It combines key indexing and a wily signature scheme. It can be used for matrices as well as vectors.

首先，我們需要明確問(wèn)題是什么。

       在這里，我們有一個(gè)稀疏的數(shù)組需要訪問(wèn)，并且在第一次訪問(wèn)的時(shí)候?qū)⑵涑跏蓟癁?. 因?yàn)閿?shù)組很大，并且需要訪問(wèn)的數(shù)組元素很稀疏，而程序要求的時(shí)間很寶貴。

       所以，我們不能直接將data數(shù)組的各個(gè)元素都初始化為0.

       我們需要做的是在第一次數(shù)組data中的某個(gè)元素的時(shí)候，將其初始化為0. 如果之后再次訪問(wèn)到該元素，應(yīng)該能夠判斷其是否已經(jīng)被初始化過(guò)，避免多次初始化從而覆蓋數(shù)據(jù)。

       在提供的解決方案中，就使用了from，to兩個(gè)向量和top變量來(lái)保存哪些變量已經(jīng)被初始化了。

       當(dāng)我們?cè)L問(wèn)索引為i的data元素時(shí)，我們通過(guò)判斷form［i]是否小于top，并且to［from［i]]是否等于i來(lái)判斷元素樹(shù)否被初始化過(guò)。

       需要注意的是我們使用to向量的原因是為了防止from中的未經(jīng)初始化的數(shù)據(jù)剛好因?yàn)樾∮趖op而導(dǎo)致出現(xiàn)錯(cuò)誤判斷。也就是說(shuō)，我們是不對(duì)from和to向量進(jìn)行初始化的（因?yàn)槲覀冞B對(duì)data進(jìn)行初始化的成本都不肯），所以無(wú)法判斷from中的數(shù)據(jù)哪些是我們寫(xiě)入的，哪些是原來(lái)就有的。于是，我們就通過(guò)增加一個(gè)to數(shù)組，并且增加一個(gè)判斷條件來(lái)保證我們的判斷是正確的。

       當(dāng)然，這樣的保證也并不是絕對(duì)正確的。只是小概率事件，直接忽略了吧？？？

綜上：

       我們?cè)谠L問(wèn)data中索引為i的元素時(shí)，通過(guò)條件from［i]<top和to［from［i]]=i來(lái)判斷該數(shù)據(jù)是否被初始化過(guò)。

       如果已被初始化過(guò)，就直接訪問(wèn)該數(shù)據(jù)；

       否則，使用如下的語(yǔ)句對(duì)其進(jìn)行初始化，并且在from，to和top中保存該數(shù)據(jù)已被初始化過(guò)這個(gè)信息：

       from[i]=top;

       to[top]=i

      data[i] = 0