Show how to implement a dictionary in external memory, using an unordered sequen
ID: 3813394 • Letter: S
Question
Show how to implement a dictionary in external memory, using an unordered sequence so that insertions require only O(1)transfers and searches require O(n/B) transfers in the worst case, where n is the number of elements and B is the number of list nodes that can fit into a disk block.
HINT: If the sequence representing a dictionary is implemented as an unsorted, doubly linked list, then insert and remove can be performed with O(1) transfers each, assuming we know which block holds an item to be removed. But, in this case, searching requires (n) transfers in the worst case, since each link hop we perform could access a different block. This search time can be improved to O(n/B) transfers. How do we improve it?
Explanation / Answer
Implement a dictionary in such a way that each block is full i.e. there are contagious elements in a dictionarry in each block .So each block will contain B elements of the dictionary. Whenever, we search for a word, at max O(N/B) transfers would be required.
This can be done as follows:
For inserting the first element, allocate an array which is O(B) blocks in size, so it will be contained in only one block. Now, keep filling these blocks unless there is space left.
When the space gets full, allocate another array which is O(B) blocks is size and keep filling that like before.
These arrays can be stored in a linked list fashion i.e. each linked list node contains an array which is O(B) blocks in size.
So, insertions taks O(1) as before. While searching, perform a linear search. At max, O(n/B) blocks would be transferred into main memory and that is the worst number of transfers required.