SICP Exercise 3.26 make-table generalized with ordered keys

Exercise 3.26.  To search a table as implemented above, one needs to scan through the list of records. This is basically the unordered list representation of section 2.3.3. For large tables, it may be more efficient to structure the table in a different manner. Describe a table implementation where the (key, value) records are organized using a binary tree, assuming that keys can be ordered in some way (e.g., numerically or alphabetically). (Compare exercise 2.66 of chapter 2.)

 SOLUTION

 The code and tests are here.
This took more time than I expected probably because of the number of interruptions I had to handle while working on this problem. My approach was to replace the list data structure from the previous exercise with a binary tree. This was not straightforward because in the previous (Exercise 3.25) implementation there is no clean separation between the procedure "make-table" and the list data structure that it uses. Operations such as 'get-first-key-value-pair' and 'get-remaining-key-value-pairs' do not make sense for a binary-tree. So I had to redo all of this. So it was a good opportunity to introduce a clean separation between the table object and the binary-tree structure that it uses to store its key-value pairs. This is exactly what I did. So the generic table level operations like lookup, insert!, find-key-value-pair etc. make no assumptions about the underlying data structure. Instead they use the message passing strategy to invoke operations on the binary-tree objects which exist in the generic table.

 For key ordering I have used string comparisons. However, the 'same', 'less-than' and 'greater-than' operations are passed in as parameters to the make-table procedure so make-table is agnostic to how the keys are ordered. 

I liked the idea of procedures with local state so I continued to use this technique to implement the binary-tree. I found the encapsulation that this technique gives, quite useful because it allowed me to think of the table and its contents as objects with operations within them.

I re-wrote the monolithic print procedure from the previous exercise and distributed the print work across the three objects: generic table, binary tree and key-value-pair. This made it a little clunky to handle the indentations while printing different levels in the generic table but overall, I think this is a huge improvement over the way I wrote the solution for Exercise 3.25.

I am a stickler for separation of concerns and clean interfaces. In this problem, the generic table contains binary trees which in turn contain key-value pairs. The key-value pair objects contain generic tables themselves in order to allow an arbitrary number of keys for any value. This circular relationship made the print procedure a little unclean as you can see where I call the procedure "print-generic-table"

As you can see in the tests below, my generic table implementation works pretty well. It allows values to be stored under an arbitrary number of keys, different values may be stored under different numbers of keys and since I use a binary tree to store the values, both the lookups and inserts have a time complexity of (Theta(log n)) where n is the number of elements at a given level in the multi-level table.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more