LRU-2执行

Question

我试图用的PriorityQueue实现一个LRU-2缓存。在我看来，我可以在poll()和add()中完成O(LogN)时间，但是对于缓存中的搜索，需要花费O(N)时间。对于如何在LRU-2缓存中使用poll()、add()和search()在O(LogN)时间内实现有什么建议吗？还是根本不可能做到？

Answer 1

经过一点挣扎，我得到了一个MaxHeap和HashMap的LRU-2，操作最多需要O(log )时间。以下是Java中LRU-2的代码。代码也在我的GitHub上。

Node.java，这是HashMap和MaxHeap中的值。

package me.york;

class Node<K, V extends Comparable<V>> implements Comparable<Node<K, V>> {
private K key;
private V value;
private int index;
private long lastTime;
private long lastSecondTime;
public static long INIT = -1;

Node(K key, V value) {
    this.key = key;
    this.value = value;
    lastTime = INIT;
    lastSecondTime = INIT;
}

@Override
public int compareTo(Node<K, V> o) {
    return (int)(lastSecondTime-o.getLastSecondTime());
}

K getKey() {
    return key;
}

V getValue() {
    return value;
}

int getIndex() {
    return index;
}

void setIndex(int index) {
    this.index = index;
}

long getLastTime() {
    return lastTime;
}

void setLastTime(long lastTime) {
    this.lastTime = lastTime;
}

long getLastSecondTime() {
    return lastSecondTime;
}

void setLastSecondTime(long lastSecondTime) {
    this.lastSecondTime = lastSecondTime;
}
}

MaxHeap.java，LRU-2算法的主要逻辑就在这一类中.

package me.york;

class MaxHeap<K, V extends Comparable<V>> {
private Node<K, V>[] heap;
private int currentSize;
private long count;

MaxHeap(int size) {
    count = 0;
    currentSize = 1;
    heap = new Node[size + 1];
}

boolean isFull() {
    return currentSize >= heap.length;
}

Node<K, V> add(Node<K, V> value) {
    Node<K, V> previous = value;
    if (currentSize >= heap.length) {
        previous = removeMax();
    }
    if (value.getLastSecondTime() != Node.INIT) {
        value.setLastSecondTime(value.getLastTime());
    } else {
        value.setLastSecondTime(count);
    }
    value.setLastTime(count++);
    value.setIndex(currentSize);
    heap[currentSize++] = value;
    siftUp(currentSize - 1);
    return previous;
}

Node<K, V> getMax() {
    return heap[0];
}

Node<K, V> removeMax() {
    return remove(0);
}

Node<K, V> reVisited(int index) {
    Node<K, V> node = heap[index];
    remove(node.getIndex());
    add(node);
    return node;
}

Node<K, V> remove(int index) {
    Node<K, V> previous = heap[index];
    heap[index] = heap[--currentSize];
    siftDown(index);
    return previous;
}

private void siftDown(int index) {
    int left = 2 * index;
    int right = 2 * index + 1;
    int largest;
    if (left < currentSize && heap[left].compareTo(heap[index]) > 0)
        largest = left;
    else
        largest = index;
    if (right < currentSize && heap[right].compareTo(heap[largest]) > 0)
        largest = right;
    if (largest != index) {
        Node<K, V> temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;
        heap[index].setIndex(largest);
        heap[largest].setIndex(index);
        siftDown(largest);
    }
}

private void siftUp(int index) {
    while (index > 1 && heap[index].compareTo(heap[index / 2]) > 0) {
        Node<K, V> temp = heap[index];
        heap[index] = heap[index / 2];
        heap[index / 2] = temp;
        heap[index].setIndex(index / 2);
        heap[index / 2].setIndex(index);
        index = index / 2;
    }
}
}

LRU2Cache.java，-这是LRU-2缓存算法的条目.它只提供两个函数，get()和put()。

package me.york;

import java.util.HashMap;
import java.util.Map;

public class LRU2Cache<K, V extends Comparable<V>> {
private MaxHeap<K, V> maxHeap;
private Map<K, Node<K, V>> map;

public LRU2Cache(int cacheSize) {
    maxHeap = new MaxHeap<K, V>(cacheSize);
    map = new HashMap<K, Node<K, V>>((int) ((float) cacheSize / 0.75F + 1.0F));
}

public void put(K key, V value) {
    if (key != null && value != null) {
        Node<K, V> previous;
        if ((previous = map.get(key)) != null) {
            maxHeap.remove(previous.getIndex());
        }
        if (maxHeap.isFull())
            map.remove(maxHeap.getMax().getKey());
        previous = new Node<K, V>(key, value);
        map.put(key, previous);
        maxHeap.add(previous);
    }
}

public V get(K key) {
    V value = null;
    if (key != null) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            value = node.getValue();
            maxHeap.reVisited(node.getIndex());
        }
    }
    return value;
}
}