Aiur

zellux 的博客

CLRS Problem 11.1-4

Permalink

简单来说就是给定一个未初始化的巨大的数组,然后通过它实现一个字典。所谓未初始化是指一开始里面元素的值都是随机的,巨大是指可以假设数组长度范围很大,对这个数组做初始化工作(例如清零)的代价自然也是很大。现在的问题是,利用这个数组设计出来的字典,要求初始化、查找、插入、删除操作都能在O(1)时间内完成。

Intructor’s Manual 上的解答设计了一个很巧妙的验证策略。假设T为那个巨大的数组,S为辅助栈,那么对于一个键k,如果k存在于这个字典中,则T[k]保存的是 k在S中的位置j,而S[j]则保存了k值。即1 ≤ T[k] ≤ top[S], S[ T[k] ] = k, T [ S[j] ] = j,我们称这个条件为“验证环”。这个设计的关键在于T和S能够互相验证,从而排除了未初始化位置上随机值的干扰。

还有一个问题就是,键k对应的值v应该怎么保存呢?其实只要维护另外一个和T或者S平行的数组就行了,既然S的元素个数远小于T,选择和S平行即可。

根据这个验证策略,我们就能设计出词典的基本操作了: 初始化:建立一个大小为0的栈 查找:给定键k,检查 1 ≤ T [k] ≤ top[S] && S[ T[k] ] = k,如果满足则返回对应值,否则返回NULL 插入:如果键已经存在则直接替换;否则将新的键值入栈,并且维护T[k] ← top[S] 删除:要确保两件事,一是验证环要被破坏,二是栈S的空洞要被填补。通过把栈顶的元素移动到要删除的元素位置,我们能同时确保这两点:

1
2
3
4
5
S[ T[k] ] ← S[ top[S] ]
S[ T[k] ] ← S [ top[S] ]
T[ S[ T[k] ] ] ← T [k]
T[k] ← 0
top[S] ← top[S] − 1

所有操作都能在O(1)时间内完成

原题:We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time. (Hint: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)

评论