Algorithms 4th edition 3.1 25 3.1.25 Software caching. Since the default impleme

Question

Algorithms 4th edition 3.1 25

3.1.25 Software caching. Since the default implementation of containsO calls getO, the inner loop of FrequencyCounter if (!st.contains (word)) st.put (word, 1); else st.put (word, st.get (word)1); leads to two or three searches for the same key. To enable clear client code like this without sacrificing efficiency, we can use a technique known as software caching, where we save the location of the most recently accessed key in an instance variable. Modify SequentialSearchST and BinarySearchST to take advantage of this idea.

Explanation / Answer

Code is in java you will need to setup StdIn and StdOut dependency.

package chegg;

public
class Sequential_Search_ST<Key, Value> {
private
int n; // number of key-value pairs
private
our_Node first; // the linked list of key-value pairs

// a helper linked list data type
private
class our_Node {
private
Key key;
private
Value val;
private
our_Node next;

public
our_Node(Key key, Value val, our_Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}

public Sequential_Search_ST() {
}

public
int our_size() { return n; }

public
boolean is_Empty() { return our_size() == 0; }

public
boolean contains(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to contains() is null");
return get(key) != null;
}

public
Value get(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to get() is null");
for (our_Node x = first; x != null; x = x.next) {
if (key.equals(x.key))
return x.val;
}
return null;
}

public
void put(Key key, Value val) {
if (key == null)
throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete (key);
return;
}

for (our_Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
first = new our_Node(key, val, first);
n++;
}

public
void delete (Key key) {
if (key == null)
throw new IllegalArgumentException("argument to delete() is null");
first = delete (first, key);
}

private
our_Node delete (our_Node x, Key key) {
if (x == null)
return null;
if (key.equals(x.key)) {
n--;
return x.next;
}
x.next = delete (x.next, key);
return x;
}

public
Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (our_Node x = first; x != null; x = x.next)
queue.enqueue(x.key);
return queue;
}

public
static void main(String[] args) {
Sequential_Search_ST<String, Integer> st =
new Sequential_Search_ST<String, Integer>();
for (int i = 0; !StdIn.is_Empty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}

/**For some help refer to https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/SequentialSearchST.java

**/
}

package chegg;

import java.util.NoSuchElementException;

public class Binary_Search_ST<Key extends Comparable<Key>, Value> {
private static final int INIT_CAPACITY = 2;
private Key[] keys;
private Value[] vals;
private int n = 0;

public Binary_Search_ST() {
this(INIT_CAPACITY);
}

public Binary_Search_ST(int capacity) {
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}   

// resize the underlying arrays
private void resize_array(int capacity) {
assert capacity >= n;
Key[] tempk = (Key[]) new Comparable[capacity];
Value[] tempv = (Value[]) new Object[capacity];
for (int i = 0; i < n; i++) {
tempk[i] = keys[i];
tempv[i] = vals[i];
}
vals = tempv;
keys = tempk;
}

public int sizeofarray() {
return n;
}

public boolean isEmpty() {
return sizeofarray() == 0;
}

public boolean contains(Key key) {
if (key == null) throw new IllegalArgumentException("argument to contains() is null");
return get(key) != null;
}

public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
if (isEmpty()) return null;
int i = rank(key);
if (i < n && keys[i].compareTo(key) == 0) return vals[i];
return null;
}

public int rank(Key key) {
if (key == null) throw new IllegalArgumentException("argument to rank() is null");

int lo = 0, hiii = n-1;
while (lo <= hiii) {
int mid = lo + (hiii - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) hiii = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;
}

public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");

if (val == null) {
delete_key(key);
return;
}

int i = rank(key);

// key is already in table
if (i < n && keys[i].compareTo(key) == 0) {
vals[i] = val;
return;
}

// insert new key-value pair
if (n == keys.length) resize_array(2*keys.length);

for (int j = n; j > i; j--) {
keys[j] = keys[j-1];
vals[j] = vals[j-1];
}
keys[i] = key;
vals[i] = val;
n++;

assert check_array();
}

public void delete_key(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete is null");
if (isEmpty()) return;

// compute rank
int i = rank(key);

// key not in table
if (i == n || keys[i].compareTo(key) != 0) {
return;
}

for (int j = i; j < n-1; j++) {
keys[j] = keys[j+1];
vals[j] = vals[j+1];
}

n--;
keys[n] = null; // to avoid loitering
vals[n] = null;

// resize_array if 1/4 full
if (n > 0 && n == keys.length/4) resize_array(keys.length/2);

assert check_array();
}

public void delete_Min() {
if (isEmpty()) throw new NoSuchElementException("Symbol table underflow error");
delete_key(min());
}

public void delete_Max() {
if (isEmpty()) throw new NoSuchElementException("Symbol table underflow error");
delete_key(max());
}

public Key min() {
if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
return keys[0];
}
public Key max() {
if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
return keys[n-1];
}

public Key select(int k) {
if (k < 0 || k >= sizeofarray()) {
throw new IllegalArgumentException("called select() with invalid argument: " + k);
}
return keys[k];
}

public Key floor(Key key) {
if (key == null) throw new IllegalArgumentException("argument to floor() is null");
int i = rank(key);
if (i < n && key.compareTo(keys[i]) == 0) return keys[i];
if (i == 0) return null;
else return keys[i-1];
}

public Key ceiling(Key key) {
if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
int i = rank(key);
if (i == n) return null;
else return keys[i];
}

public int sizeofarray(Key lo, Key hiii) {
if (lo == null) throw new IllegalArgumentException("first argument to sizeofarray() is null");
if (hiii == null) throw new IllegalArgumentException("second argument to sizeofarray() is null");

if (lo.compareTo(hiii) > 0) return 0;
if (contains(hiii)) return rank(hiii) - rank(lo) + 1;
else return rank(hiii) - rank(lo);
}

public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hiii) {
if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
if (hiii == null) throw new IllegalArgumentException("second argument to keys() is null");

Queue<Key> queue = new Queue<Key>();
if (lo.compareTo(hiii) > 0) return queue;
for (int i = rank(lo); i < rank(hiii); i++)
queue.enqueue(keys[i]);
if (contains(hiii)) queue.enqueue(keys[rank(hiii)]);
return queue;
}

  
private boolean check_array() {
return isSorted_array() && rankCheck();
}

// are the items in the array in ascending order?
private boolean isSorted_array() {
for (int i = 1; i < sizeofarray(); i++)
if (keys[i].compareTo(keys[i-1]) < 0) return false;
return true;
}

// check_array that rank(select(i)) = i
private boolean rankCheck() {
for (int i = 0; i < sizeofarray(); i++)
if (i != rank(select(i))) return false;
for (int i = 0; i < sizeofarray(); i++)
if (keys[i].compareTo(select(rank(keys[i]))) != 0) return false;
return true;
}

public static void main(String[] args) {
Binary_Search_ST<String, Integer> st = new Binary_Search_ST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}

/** For some help goto https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BinarySearchST.java.html **/

}

Thank you, Comment if you need any help.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.