CS61B 2018 Lecture 6 ALists, Resizing, vs. SLists + proj1a

[poanc]

Summary

• Linked List Performance Puzzle

• The Naive Array Based List

  • removeLast
  • Naive Resizing Arrays
  • Analyzing the Naive Resizing Array
  • Geometric Resizing
  • Memory Performance(Usage Ratio)

• Generic ALists

• Loitering

• Conclusion

  1. Use Invariant to write your code
  2. always null out the reference we want to remove from the list, so that java can garabage collect this object item.

• Project 1A: Data Structures

  • Mistakes review
  • Conclusion

Linked List Performance Puzzle

上堂課介紹的DLList有個缺點，如果我們要取DLList中間的item，我們需要從頭或是從尾迭代，相較於getFirst()或是getLast()，花了很多時間。

The Naive Array Based List

Access Array內的element之所以是constant time，是因為array儲存element的方式，一定是contigous，想一想，可以去這篇Quora找到答案。

Invariants

1. The position of the next item to be inserted (using addLast) is always size.
2. The number of items in the AList is always size.
3. The position of the last item in the list is always size - 1.

/** Array based list.
 *  @author Josh Hug
 */

//         0 1  2 3 4 5 6 7
// items: [6 9 -1 2 0 0 0 0 ...]
// size: 5

/* Invariants:
 addLast: The next item we want to add, will go into position size
 getLast: The item we want to return is in position size - 1
 size: The number of items in the list should be size.
*/

public class AList {
    /** Creates an empty list. */

    private int[] item;
    private int size;

    public AList() {
        this.item = new int[100];
        this.size = 0;

    }

    /** Inserts X into the back of the list. */
    public void addLast(int x) {
        item[size] = x;
        size++;
    }

    /** Returns the item from the back of the list. */
    public int getLast() {
        return item[size];
    }
    /** Gets the ith item in the list (0 is the front). */
    public int get(int i) {
        return item[i];
    }

    /** Returns the number of items in the list. */
    public int size() {
        return size;
    }
    ...
}

removeLast

The list is the arbitrary idea user though, and the memory manipulating, such as get,item,item[i], is the concrete idea.

(The last operation we need to support is removeLast. Before we start, we make the following key observation: Any change to our list must be reflected in a change in one or more memory boxes in our implementation.

This might seem obvious, but there is some profundity to it. The list is an abstract idea, and the size, items, and items[i] memory boxes are the concrete representation of that idea. Any change the user tries to make to the list using the abstractions we provide (addLast, removeLast) must be reflected in some changes to these memory boxes in a way that matches the user's expectations. Our invariants provide us with a guide for what those changes should look like.)

    public int removeLast() {
        int x = getLast();
        size = size - 1;
        return x;
    }

Naive Resizing Arrays

The left side code is workable, however, the right side is better.
It will be better to break the code into little tiny piece. The piece of code can be test separately by testing code or java visualizer. In addition, breaking the code into piece is helpful for maintaining.

Analyzing the Naive Resizing Array

Exercise 2.5.5:
Suppose we have an array of size 100. If we call insertBack two times, how many total boxes will we need to create and fill throughout this entire process? How many total boxes will we have at any one time, assuming that garbage collection happens as soon as the last reference to an array is lost?

Exercise 2.5.5:
Suppose we have an array of size 100. If we call insertBack two times, how many total boxes will we need to create and fill throughout this entire process? How many total boxes will we have at any one time, assuming that garbage collection happens as soon as the last reference to an array is lost?

conclusion:
1. The SLList shows a straight line, which means for each add operation, the list takes the same additional amount of time. This means each single operation takes constant time! You can also think of it this way: the graph is linear, indicating that each operation takes constant time, since the integral of a constant is a line.
2. computer run in GHz, it means it can run a billion things per second. According to the right side image above, to insert 100000 elements into AList needs to create 5,000,000,000 memory box. 5 billion memory box divided by 1 GHz, it comes 5 sec.(Josh says his computer has a better CPU)

Geometric Resizing

Memory Performance(Usage Ratio)

In a typical implementation, we halve the size of the array when R falls to less than 0.25.

Generic ALists

To initiate the array based generic AList, the declaration is different from SLList。
That is, we cannot do this：

Glorp[] items = new Glorp[8];

Instead, we have to use the awkward syntax shown below：

Glorp[] items = (Glorp []) new Object[8];

Loitering

When we store the object item in the AList, assigning the item to null is a good practice. If we do not null out the last reference, garbage collector will not collect the object item.

(The other change we make is that we null out any items that we "delete". Whereas before, we had no reason to zero out elements that were deleted, with generic objects, we do want to null out references to the objects that we're storing. This is to avoid "loitering". Recall that Java only destroys objects when the last reference has been lost. If we fail to null out the reference, then Java will not garbage collect the objects that have been added to the list.)

Conclusion

1. Use Invariant to write your code
2. always null out the reference we want to remove from the list so that java can garbage collect this object item.

Project 1A: Data Structures

In this project, we have to implement several kinds of API method based on LinkedListDeque and ArrayDeque. Deque is one of the data structure, and the meaning defines in the course textbook:

Deque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).

In implementing LinkedListDeque, we use the 'circular sentinel topology' in this project.

public class LinkedListDeque<T>{
    public class StuffNode{

        public T item;
        public StuffNode next;
        public StuffNode prev;

        public StuffNode(T item, StuffNode next, StuffNode prev){
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }

    public StuffNode sentinel;
    public int size;

    public LinkedListDeque(){
        sentinel = new StuffNode(null, null, null);
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
        size = 0;
    }

    public LinkedListDeque(T item){
        sentinel = new StuffNode(null, null, null);
        StuffNode first = new StuffNode(item, sentinel.next, sentinel);
        sentinel.next = first;
        sentinel.prev = first;
        size = 1;
    }

    public void addFirst(T item){
        // sentinel.next = first item
        StuffNode first = new StuffNode(item, sentinel.next, sentinel);
        sentinel.next.prev = first;
        sentinel.next = first;
        size += 1;
    }

    public void addLast(T item){
        StuffNode last = new StuffNode(item, sentinel, sentinel.prev);
        sentinel.prev.next = last;
        sentinel.prev = last;
        size += 1;
    }

    public boolean isEmpty(){
        if(size == 0){
            return true;
        }
        return false;

    }

    public int size(){
        return size;
    }

    public void printDeque(){
        StuffNode sent = sentinel;
        sent = sent.next;
        while(sent != sentinel){
            System.out.print(sent.item + " ");
            sent = sent.next;
        }
        System.out.println();
    }

    public T removeFirst(){
        if(sentinel.next == null || sentinel.next == sentinel){
            return null;
        }
        StuffNode first = sentinel.next;
        sentinel.next = first.next;
        first.next.prev = sentinel;
        size -= 1;
        return first.item;
    }

    public T removeLast(){
        if(sentinel.prev == null || sentinel.next == sentinel){
            return null;
        }
        StuffNode last = sentinel.prev;
        sentinel.prev = last.prev;
        last.prev.next = sentinel;
        size -= 1;
        return last.item;
    }

    public T get(int index){
        int counter = 0;
        StuffNode L = sentinel.next;
        if(index > size - 1){
            return null;
        }
        while(counter < index){
            L = L.next;
            counter++;
        }
        return L.item;
    }

    public T getRecursive(int index){
        return getRecursive(sentinel.next, index);

    }

    private T getRecursive(StuffNode stuffnode, int index){
        if(index == 0){
            return stuffnode.item;
        }
        return getRecursive(stuffnode.next, (index - 1));
    }

    public static void main(String[] args){

        LinkedListDeque<String> L = new LinkedListDeque<>();
        
    }
}

It takes long time to complete ArrayDeque API function and I summarized some mistakes I made:

1. Always confirm the invariant before writing the code. I rushed in writing code and I don't realize the actual structure of ArrayDeque until I made lots of submitting. That is, the addFirst is to add the 'head' of the ArrayDeque, and addLast is to add the 'rear' of the ArrayDeque. Thus, the get(0) is to get the first item of ArrayDeque.
2. Tests is really a rool tool ! You can use unit test or integral test to run your API function, rather than calling the main() repeatedly.

Below is the sample code implementing ArrayDeque:

public class ArrayDeque<T> {

    private T[] items;
    private int size;
    private int nextFirst;
    private int nextLast;

    public ArrayDeque() {
        items = (T []) new Object[8];
        size = 0;
        nextFirst = 7;
        nextLast = 0;
    }

    private int elementNum() {
        return items.length;
    }

    /** Resize the A */
    private void resize(int capacity) {
        T[] newAList = (T []) new Object[capacity];
        /** copy the old items element to newAlist **/

        // index of newAList
        int j = 0;
        int i = plusOne(nextFirst);
        int counter = 0;
        while (counter < size()) {
            newAList[j] = items[i];
            j++;
            i = plusOne(i);
            counter++;
        }
        nextLast = j;
        nextFirst = capacity - 1;
        items = newAList;
    }


    public void addFirst(T item) {
        items[nextFirst] = item;
        size++;
        nextFirst = minusOne(nextFirst);
        if (size() == elementNum()) {
            resize(size() * 2);
            return;
        }
    }



    public void addLast(T item) {
        items[nextLast] = item;
        size++;
        nextLast = plusOne(nextLast);
        if (size() == elementNum()) {
            resize(size() * 2);
            return;
        }
    }


    public boolean isEmpty() {
        if (size == 0) {
            return true;
        }
        return false;
    }

    public int size() {
        return size;
    }

    public void printDeque() {
        for (T item : items) {
            System.out.print(item + " ");
        }
        System.out.println();
    }


    public T removeFirst() {
        if (size == 0) {
            return null;
        }
        if (nextFirst == elementNum() - 1) {
            nextFirst -= elementNum();
        }
        T first = items[nextFirst + 1];
        items[nextFirst + 1] = null;
        size--;
        nextFirst++;
        if (size() == 0) {
            nextFirst = elementNum() - 1;
            nextLast = 0;
        }
        if (elementNum() > 8 && (float) size() / elementNum() < 0.25) {
            resize(elementNum() / 2);
        }
        return first;
    }

    public T removeLast() {
        if (size() == 0) {
            return null;
        }
        if (nextLast == 0) {
            nextLast += 8;
        }
        T last = items[nextLast - 1];
        items[nextLast - 1] = null;
        size--;
        nextLast--;
        if (size() == 0) {
            nextFirst = elementNum() - 1;
            nextLast = 0;
        }
        if (elementNum() > 8 && (float) size() / elementNum() < 0.25) {
            resize(elementNum() / 2);
        }
        return last;
    }

    public T get(int index) {
        if (index >= size) {
            return null;
        }
        return items[Math.floorMod(nextFirst + 1 + index, elementNum())];
    }

    private int minusOne(int x) {
        return Math.floorMod(x - 1, elementNum());
    }

    private int plusOne(int x) {
        return Math.floorMod(x + 1, elementNum());
    }

    private static void main(String[] args) {
        ArrayDeque<Integer> A = new ArrayDeque<>();
        A.addFirst(4);
        System.out.println((float) (A.size() / 32));
    }
}

Conclusion

Before writing code:

1. write invariants
2. write some tests

During writing code:

1. write comments
2. debuged by the test, rather than run main() repeatedly