|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Ruby |
A very common paradigm in data processing involves storing information in a table and then later retrieving the information stored there. For example, consider a database of driver's license records. The database contains one record for each driver's license issued. Given a driver's license number, we can look up the information associated with that number.
Similar operations are done by the Ruby interpreter. The interpreter uses a symbol table to keep track of the user-defined symbols in a Ruby program. As it interprets a program, the interpreter inserts an entry in the symbol table every time a new symbol is introduced. In addition, every time a symbol is used, the interpreter looks up the type associated with that symbol in order to execute the methods associated with the type of the object to which the symbol refers.
Typically the database comprises a collection of key-and-value pairs. Information is retrieved from the database by searching for a given key. In the case of the driver's license database, the key is the driver's license number and in the case of the symbol table, the key is the name of the symbol.
In general, an application may perform a large number of insertion and/or look-up operations. Occasionally it is also necessary to remove items from the database. Because a large number of operations will be done we want to do them as quickly as possible.
Copyright © 2004 by Bruno R. Preiss, P.Eng. All rights reserved.