Multiple Representations

Copyright © 1997 Kenneth J. Goldman

In the next several lectures, we'll be thinking about multiple representations, different ways to implement the same abstraction. We've already seen different ways to implement some ADT's. For example, we discussed the implementation of stacks and queues in terms of ordinary linked lists, and then saw how to implement the same abstraction in terms of circular lists.

Part of the software design process is choosing an appropriate representation for an ADT once the interface has been defined. Factors influencing this decision include:

• time efficiency (how will this representation choice impact the time required to execute the various methods in the ADT interface?)
• space efficiency (how much memory is required by this representation?)
• implementation efficiency (how long will it take to implement the ADT using this representation, and how easy will it be to debug and maintain the code?)

The answers are not always easy. There are space-time tradeoffs, meaning that one implementation may use little time but require a lot of space, while another implementation may use little space but require a lot of time. Also, there may be tradeoffs between methods of the ADT. For example, one implementation of a relation may support fast insertion but provide slow lookup, while another implementation may do exactly the reverse. The choice, then, might depend on whether one expects to do a lot of inserts and few lookups, or the other way around.

public class BaseNumber {
    int base;
    Digit list;
    public BaseNumber(int value) {
        base = 10;
        list = listInBase(10, value);
    }
    BaseNumber(int base, Digit list) {
        this.base = base;
        this.list = list;
    }
    Digit listInBase(int base, int n) {
        if (n == 0)
            return new Digit(0,null);
        else {
            Digit ls = null;
            while (n != 0) {
                ls = new Digit(n % base, ls);
                n /= base;
            }
            return ls;
        }
    }
    

    public int toInt() {  // uses Horner's method
        Digit ls = list;
        int result = 0;
        while (ls != null) {
            result = (result * base) + ls.number;
            ls = ls.next;
        }
        return result;
    }
    

    public BaseNumber toBase(int b) { // 2 <= b <= 10 
        return new BaseNumber(b, listInBase(b, toInt()));
    }
    public BaseNumber plus(BaseNumber x) {
        return new BaseNumber(toInt() + x.toInt());
    }
    public BaseNumber times(BaseNumber x) {
        return new BaseNumber(toInt() * x.toInt());
    }
    public String toString() {
        return ("" + list + " base " + base);
    }
    

}

class Digit {
    int number;
    Digit next;
    Digit(int n, Digit next) {
        number = n;
        this.next = next;
    }
    public String toString() {
        if (next == null)
            return "" + number;
        else
            return "" + number + next;
    }
}
    

As we have seen, one of the important benefits of data abstraction is encapsulation, hiding the internal representation of the data behind an abstraction barrier consisting of public methods. This encapsulation allows us to change the internal representation without changing the semantic behavior of the object. One motivation for changing the internal representation is to improve performance (efficiency).

In the next example, we'll consider three different internal representations of a set ADT, and we'll consider the impact of each representation on the performance. In particular, we'll look at time requirements for executing the various methods with each choice of representation.

First, let's define the interface for the set ADT:

Recall: A set does not contain duplicate items. (A multiset is like a set, but may contain duplicate items.)

Since our concern is choice of representation, we want to explore various possible representations and make comparisons. To do these comparisons, it is not necessary to do a complete implementation. Instead, we will:

1. identify the methods for which we are most concerned about performance
2. write algorithms in "pseudocode" for those methods for each representation
3. analyze the algorithms to determine their relative efficiency

Pseudocode is an informal notation with code-like structure. It is used to get the essentials of an algorithm on paper without taking the time to deal with the language-specific details. Often. people explain algorithms to each other because it's easier to read and is not dependent on knowledge of a particular language. You can think of pseudocode as an abstraction of an algorithm implementation.

Let's suppose that the methods for which we really care most about efficiency are: insert, delete, and intersection. In general, one would care most about the methods that we expect to be used more often.

We can create a table in which to make comparisons of the relative efficiency of the best algorithms we can find for each of three representations.

In each square of the table, we will fill in the time required to perform the given method using the best algorithm we can think of for the given representation.

As we do our analysis, we will make the following assumptions:

• each set contains n elements when the method is invoked
• the items in the set are integers with a uniform probability distribution over some range
• the insert operation is performed for an item not already in the set (the code should handle either case, but in the analysis we'll be interested in only one case)
• the delete operation is performed for an item in the set (again, the code must handle both cases)
• for intersection, we'll measure the cost of the case where the intersection is empty
• our cost measure will be the number of times we examine elements

We are already familiar with linked lists of numbers, so let's first consider how we might implement the insert, delete, and intersection methods using linked lists. We'll use the ListOfInts ADT we implemented earlier as our internal representation. Pseudocode will be used to describe the algorithms.

For insert, we'll walk to the end of the list looking for the given number. If it's not there, we'll put it at the end.

ls.reset();
while (!ls.atEnd() and (ls.getItem() != x))

ls.next();

if (ls.atEnd())

ls.append(x);

Notice that if the element isn't already in the set, we must examine all of the elements. Since our analysis is to be done for the case of inserting a new item into a set of n elements, we can write "n" in the table.

For delete, we'll use a similar strategy, but this time if we find the number, we'll take it out.

ls.reset();
while (!atEnd() and (ls.getItem() != x))

ls.next();

if (!ls.atEnd())

ls.delete();

For delete, we're interested in the cost of deleting an existing set element. Assuming deletion of a random element, we can expect to go about half way down the list, on average. So we can write n/2 in the table.

For intersection, we want to delete all elements of our set that aren't also elements of the given set.

ls.reset();
while (!ls.atEnd())

if t.hasElement(ls.getItem())

ls.next();

else

ls.delete();

For each item in the list, we check to see if the item is in the other list. We haven't written the hasElement method, but we know that this check requires looking through the whole list if the item isn't there. Since we're measuring the case where the intersection is empty, we need to examine n² items.

Let's see if we can improve performance by keeping the list in sorted order, least to greatest.

For insert, we'll do it like before, but we can stop "early," as soon as we see an element greater that (or equal to) the one we're inserting.

ls.reset();
while (!ls.atEnd() and (ls.getItem() < x))

ls.next();

if (ls.atEnd() or (ls.getItem() != x))

ls.insert(x);

On average, we'll go halfway down the list, even inserting a new element, so n/2 goes in the table.

For delete, a similar strategy:

ls.reset();
while (!ls.atEnd() and (ls.getItem() < x))

ls.next();

if (!ls.atEnd() and (ls.getItem() == x))

ls.delete();

Again, we expect to go halfway down the list, even if the element isn't in the set.

For intersection, how can we best exploit the fact that the two lists are in sorted order? If we call hasElement for each item to see if it's in the other set, then we have to look through the other set n times. However, knowing that the lists are sorted, we can walk down both lists simultaneously, saving the elements in common and discarding the others. That is, we'll use a "two finger" approach, where one finger points to an element in each list.

If the element in S is smaller, we delete it since it's not in T. If the element in T is smaller, we skip over it. If the elements are equal, we move forward in both lists.

ours = ls;
theirs = t.ls;
while (!ours.atEnd())

if (theirs.atEnd()) // no more items in intersection

ours.delete();

else if (ours.getItem() < theirs.getItem()) // ours isn't in their list

ours.delete();

else if (ours.getItem() > theirs.getItem()) // theirs isn't in our list

theirs.next();

else

ours.next();
theirs.next();

The methods insert, delete, and hasElement all depend on being able to find the presence (or absence) of a given element, and other elements may be implemented in terms of these. Therefore, let's think about the way we've been finding elements by looking through the list. In the unordered list, we had to look all the way through the list. In the unordered list representation, we had some improvement, on average looking at only half the list.

But when you look for a name in the telephone book, do you start at the first name in the book and read each name until you get to the one you want? Of course not. More likely, you start somewhere in the middle and move forward or back in smaller and smaller chunks until you find the right page.

So what we'd like is a data structure that lets us start somewhere in the "middle" and then move left or right in large chunks, narrowing the search as we go. One data structure that offers this kind of capability is known as a binary search tree.

Let's use this structure for our set of numbers. Each item (node) of our binary search tree contains three things:

• the element (a number)
• a reference to the left subtree (another binary search tree)
• a reference to the right subtree

For each node, all elements in the left subtree are smaller and all elements in the right subtree are greater.

The first value inserted goes in the top node, called the root. Nodes without children are called leaves.

class TreeNode {
   int number;
   TreeNode left;
   TreeNode right;
   TreeNode(int n, TreeNode l, TreeNode r) {
      number = n;
      left = l;
      right = r;
   }
}
    

To insert, we go down the tree, moving left or right at each level until we either find the number or reach the bottom and insert a new node.

if tree is empty

root = new TreeNode(x, null, null)

else

ptr = root
while (ptr.number != x)

if (x < ptr.number)

if (ptr.left == null)

ptr.left = new TreeNode(x, null, null)

ptr = ptr.left

else

if (ptr.right == null)

ptr.right = new TreeNode(x, null, null)

ptr = ptr.right

Alternatively, we can do this recursively:

root = insertValue(x, root)

if (ptr == null)

return new TreeNode(x, null, null)

else

if (x < ptr.number)

ptr.left = insertValue(x, ptr.left)
// Let left subtree be result of inserting x into left subtree

else if (x > ptr.number)

ptr.right = insertValue(x, ptr.right)

return ptr

If we assume the tree is balanced (as "bushy" as possible), then the nth level contains 2ⁿ nodes, so a tree with n nodes contains approximately log₂n levels (the power of 2 to get n).

Delete is tricky. We can't just pluck a node out of the middle of a tree because it may have two children. Where would they go?

For example, suppose we want to delete 3 from

If we just removed the 3, we'd have to do something with the 1 and the 5. But 7 only has room for one left child. We could just re-insert all descendants of 3, but there could, in general, be a lot of them, so that could take too much time.

What if we replace the 3 by some other value further down in the tree? We must maintain the invariant that:

For each node, all values in the left subtree are smaller, and all values in the right subtree are greater.

So we want a value greater than all the values in the left subtree and less than all values in the right subtree. Well, we know that all values in the left subtree are less than all values in the right subtree, so the greatest value in the left subtree will work, as will the least value in the right subtree.

Suppose we decide to use the greatest value in the left subtree. What happens if there isn't a left subtree? Then we can just replace the deleted node by the right subtree.

Now what if x has no children? Then we can just delete x.

The only remaining question: How do we find the largest element in the left subtree? Kepp moving right in that subtree as far as possible.

root = deleteFromSubtree(x, root)

if (ptr == null)

return null

else if (ptr.number == x) // found it!
return deleteRoot(ptr) // take it out

else

if (x < ptr.number)

ptr.left = deleteFromSubtree(x, ptr.left)

else

ptr.right = deleteFromSubtree(x, ptr.right)

return ptr

if (root.left == null)

return root.right

else if (root.right == null)

return root.left

else

int largest = rightMost(root.left)
return new TreeNode(largest, deleteFromSubtree(largest, root.left), root.right)

while(ptr.right != null)

ptr = ptr.right

return ptr.number

Alternatively, we could delete the rightmost node when we find it, but we must be sure to return the value for use higher in the tree.

We'll implement intersection recursively. At each node, if it's not in the other set, we remove it and recurse. Otherwise, we recurse on the left and right subtrees, intersecting each with the given set.

root = intersectSubtree(root, T)

if (ptr == null)

return null

else if ! T.hasElement(ptr.number)

return intersectSubtree(deleteRoot(ptr), T)

else

ptr.left = intersectSubtree(ptr.left, T)
ptr.right = intersectSubtree(ptr.right, T)
return ptr

Assuming balanced trees, hasElement takes log₂n time. Since intersection calls hasElement for each node. So far we have n·log₂n. However, each deletion takes up to 2 log₂n time, one log₂n factor to find the largest node in the left subtree and one log₂n factor to delete it from the subtree. So, all together we have 3n log₂n time.

Let's go back and look at the comparison table.

Clearly, the ordered list beats the unordered list. But what about the other two? Really, it depends on how many of each type of operation you expect.

Another thought: Could we use the binary search tree but convert to ordered lists for taking intersections? This would give us a hybrid implementation.

First, let's think about how much it would help. We'd have to

1. convert to an ordered list -- this would cost at least n since we'd have to touch all the elements
2. do the intersection -- costs 2n
3. convert the result to a tree -- assuming n elements, if we do n insertions, we have n·log₂n.

So, all together, we'd have n·(log₂n + 3). For n=32 and n=1024, the costs would be 256 and 13312, some improvement. Of course, we'd have to be careful about our assumption of balanced trees.

How can we convert a binary search tree to an ordered list? We can create an empty list, and insert the elements in order. We'll do this recursively, starting at the root. Each node will make a recursive call to insert all the elments less than itself (the left side), then it will insert itself, and finally it will make another recursive call to insert all the elements larger than itself (the right side). This is known as an in-order traversal.

ListOfInts list = new ListOfInts(); // create empty list
treeToList(root, list); // insert the items in order
return list;

if (ptr != null)

treeToList(ptr.left, ls);
ls.append(ptr.number);
treeToList(ptr.right, ls);