首页 > c/c++, LeetCode, 算法, 通用概念, 面试 > LeetCode面试题之LRU

LeetCode面试题之LRU

2016年7月2日 357 人阅读 发表评论 阅读评论

1.问题

在刷LeetCode时遇到了一道这样的题目

1.1LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

  class LRUCache{
  public:
      LRUCache(int capacity) {
          
      }
      
      int get(int key) {
          
      }
      
      void set(int key, int value) {
          
      }
  };
  

2.答案

2.1算法介绍

LRU是操作系统的内存置换算法,只保留最近被使用过的内存页,保存当前所需要的热点内存页。该算法扩展到应用层可以用来保留固定大小的最近被访问的热点数据,是全部使用缓存还是全部穿透到数据库查询的一种折中。

2.2算法实现

哈希(hash) + 双向链表(doubly linked list)来实现。

2.2.1插入(set)操作

  • 步骤1
    判断要插入的值是否已经在缓存中,如果已经在链表中,则先在链表中删除该节点,然后把该节点插入到链表尾部。
  • 步骤2
    如果要插入的元素不在链表中,先判断缓存是否已满,如果已满则先删除链表头元素,并删除该元素在hash表中的映射关系;最后把要插入的元素插入链表尾,并在hash表中创建相关的映射关系。

2.2.2获取(get)操作

  • 步骤1
    通过key查询hash映射表,判断元素是否在缓存中。
  • 步骤2
    如果元素在缓存中,则先在链表中删除该节点,然后把该节点插入到链表尾部。如果元素不在缓存中,则返回一个异常值表明不存在和key对应的value。

3.解题过程

3.1解法1

双map方案,对LRU算法了解不够透彻,使用map来替换链表,每个value都关联一个id,id是全局递增的;如果元素value被再次访问,则重新生成一个全局递增的id来关联value;全局维护一个最小的没被删除的关联id,当缓存满时则从这个最小id开始一直递增直到找到一个关联的value,然后删除这个value。具体代码如下:

/*
    17 / 17 test cases passed.
    Status: Accepted
    Runtime: 288 ms
    CreateTime: 2016年6月28日12:52:48
    Desc: 双map太慢了,需要优化(hash + doubly linked list)?
 */
class LRUCache{
public:
    int minId;
    int vistId;
    int capacity;

    struct node
    {
        int key;
        int value;
    };

    map<int, node> vmap;
    map<int, int> kmap;


    LRUCache(int capacity) {
        this->minId = 0;
        this->vistId = 0;
        this->capacity = capacity;
    }

    int get(int key) {
        if (kmap.find(key) == kmap.end())
        {
            return -1;
        }
        int value = 0;
        value = vmap[kmap[key]].value;

        int tempId = kmap[key];
        kmap.erase(key);
        vmap.erase(tempId);

        vistId++;
        vmap[vistId].value = value;
        vmap[vistId].key = key;
        kmap[key] = vistId;

        return value;
    }

    void set(int key, int value) {
        if (kmap.find(key) == kmap.end())
        {
            if (kmap.size() < capacity)
            {
                vistId++;
                vmap[vistId].value = value;
                vmap[vistId].key = key;
                kmap[key] = vistId;
            }
            else
            {
                minId++;
                while (vmap.find(minId) == vmap.end())
                {
                    minId++;
                }

                kmap.erase(vmap[minId].key);
                vmap.erase(minId);

                vistId++;
                vmap[vistId].value = value;
                vmap[vistId].key = key;
                kmap[key] = vistId;
            }
        }
        else
        {
            int tempId = kmap[key];
            kmap.erase(key);
            vmap.erase(tempId);

            vistId++;
            vmap[vistId].value = value;
            vmap[vistId].key = key;
            kmap[key] = vistId;
        }
    }   
};

3.2解法2

map+doubly link list,c++ stl中没有提供hash_map(stl扩展和gnu扩展中有hash_map)故这里使用map来实现hash表的功能,map的查询和插入的时间复杂度为O(log(N)),双向链表插入和删除的时间复杂度是O(1)。代码实现如下:

/*
    17 / 17 test cases passed.
    Status: Accepted
    Runtime: 116 ms
    CreateTime: 2016年6月28日15:52:48
    Desc: map + doubly linked list相比解法1提升了1倍的性能,是否能再次优化?
 */
class LRUCache{
public:
    struct ListNode
    {
        ListNode * prev; 
        ListNode * next;
        int value;
        int key;
    };

    ListNode * head;
    ListNode * tail;
    int listLen;
    int maxLen;

    map<int, ListNode *> kmap;

    ListNode * createList()
    {
        ListNode * node = new ListNode;
        node->prev = node->next = NULL;
        return node;
    }

    ListNode * insertNode(int key, int value)
    {
        ListNode * node = new ListNode;
        node->key = key;
        node->value = value;
        node->next = NULL;
        node->prev = tail;
        tail->next = node;
        tail = node;
        ++listLen;
        return node;
    }

    int deleteOldNode()
    {
        int deleteKey = 0;
        ListNode * oldNode = head->next;
        deleteKey = oldNode->key;

        //delete oldNode;

        //head->next = head->next->next; runtime error,prev没更新

        head = head->next; //head往下移

        return deleteKey;
    }

    void updateNode(int key, int * value)
    {
        ListNode * tailNode = kmap[key];
        if (value != NULL)
        {
            tailNode->value = *value;
        }

        if (tail == tailNode) return;

        if (tailNode->prev && tailNode->next)
        {
            tailNode->prev->next = tailNode->next;
            tailNode->next->prev = tailNode->prev;
        }

        if (tailNode != tail)
        {
            tailNode->next = NULL;
            tailNode->prev = tail;
            tail->next = tailNode;
            tail = tailNode;
        }
    }

    LRUCache(int capacity) {
        maxLen = capacity;
        head = createList();
        tail = head;
    }

    int get(int key) {
        if (kmap.find(key) == kmap.end())
        {
            //cout << "not find key = " << key << endl;
            return -1;
        }

        updateNode(key, NULL);
        //cout << "find key = " << key << "value = " << kmap[key]->value << endl;
        return kmap[key]->value;
    }

    void set(int key, int value) {
        if (kmap.find(key) == kmap.end())
        {
            if (kmap.size() < maxLen)
            {
                kmap[key] = insertNode(key, value);
                //cout << "insert key = " << key << "value = " << value << endl;
            }
            else
            {
                int deleteKey = deleteOldNode();
                kmap.erase(deleteKey);
                //cout << "delete key = " << deleteKey << endl;
                kmap[key] = insertNode(key, value);
            }
        }
        else
        {
            //cout << "update key = " << key << " value = " << value << endl;
            updateNode(key, &value);
        }
    }
};

3.3解法3

猜测双向链表更新prev和next指针对性能产生了影响,故采用hash + single link list,这里单向链表的节点删除”采用拷贝要删除节点的下一个节点值到当前要删除的节点,然后删除要删除节点的下一个节点”的方式来实现。实现代码如下:

/*
    17 / 17 test cases passed.
    Status: Accepted
    Runtime: 156 ms
    CreateTime: 2016年6月28日23:46:42
    Desc: 单链表时在update时hash操作反而多了2次,反而比较耗时,所以性能瓶颈在哈希操作
 */
class LRUCache{
public:
    struct ListNode 
    {
        ListNode * next;
        int key;
        int value;
    };

    ListNode * head;
    ListNode * tail;
    int maxSize;
    map<int, ListNode *> kmap;

    ListNode * createList()
    {
        ListNode * node = new ListNode;
        node->next = NULL;
        node->key = 0;
        node->value = 0;

        return node;
    }

    ListNode * insertNode(int key, int value)
    {
        ListNode * node = new ListNode;
        node->key = key;
        node->value = value;
        node->next = NULL;

        tail->next = node;
        tail = node;

        return node;
    }

    int deleteOldNode()
    {
        ListNode * oldNode = head->next;
        int deleteKey = oldNode->key;
        head = head->next; //head往后移
        return deleteKey;
    }

    void updateNode(int key, int * value)
    {
        int oldValue = 0;
        ListNode * cur = kmap[key];
        oldValue = cur->value;

        if (cur->next != NULL)
        {
            if (cur->next != tail)
            {
                ListNode * curNext = cur->next;
                cur->next = curNext->next;
                cur->key = curNext->key;
                cur->value = curNext->value;
                kmap[cur->key] = cur;

                curNext->next = NULL;
                curNext->key = key;
                if (value != NULL)
                {
                    curNext->value = *value;
                }
                else
                {
                    curNext->value = oldValue;
                }

                tail->next = curNext;
                tail = curNext;
                kmap[key] = tail;
            }
            else
            {
                ListNode * curNext = cur->next;
                cur->key = curNext->key;
                cur->value = curNext->value;
                kmap[cur->key] = cur;

                curNext->key = key;
                if (value != NULL)
                {
                    curNext->value = *value;
                }
                else
                {
                    curNext->value = oldValue;
                }
                kmap[key] = curNext;
            }
        }
        else
        {
            if (value != NULL)
            {
                cur->value = *value;
            }
        }
    }

    LRUCache(int capacity) {
        maxSize = capacity;
        head = createList();
        tail = head;
    }

    int get(int key) {
        if (kmap.find(key) == kmap.end())
        {
            return -1;
        }

        updateNode(key, NULL);
        return kmap[key]->value;
    }

    void set(int key, int value) {
        if (kmap.find(key) == kmap.end())
        {
            if (kmap.size() < maxSize)
            {
                kmap[key] = insertNode(key, value);
            }
            else
            {
                int deleteKey = deleteOldNode();
                kmap.erase(deleteKey);
                kmap[key] = insertNode(key, value);
            }
        }
        else
        {
            updateNode(key, &value);
        }
    }
};

3.4解法4

解法3相对解法2反而跟耗时,分析发现指针更新虽然是少了一遍,但是map更新多了两次,性能反而下降。解法4采用 热点hash + map + doubly linked list,认为key:0~5000是热点数据,这部分数据才用数组hash来做映射,实现O(1)的映射查询,而不在0~5000之间的key采用map来做映射。代码如下:

/*
    17 / 17 test cases passed.
    Status: Accepted
    Runtime: 60 ms
    CreateTime: 016年6月28日23:46:42
    Desc: 热点缓存的思维,在发现性能瓶颈在hash操作时,就引入了数组O(1)的插入和查询,对原来map做一个热点的查询缓存优化,把热点数据的hash操作移到了数组中进行,足足提升快一倍的性能。
 */
class LRUCache{
public:
    struct ListNode
    {
        ListNode * prev; 
        ListNode * next;
        int value;
        int key;
    };

    ListNode * head;
    ListNode * tail;
    int listLen;
    int maxLen;

    ListNode * d[5000];

    map<int, ListNode *> kmap;

    ListNode * createList()
    {
        ListNode * node = new ListNode;
        node->prev = node->next = NULL;
        return node;
    }

    ListNode * insertNode(int key, int value)
    {
        ListNode * node = new ListNode;
        node->key = key;
        node->value = value;
        node->next = NULL;
        node->prev = tail;
        tail->next = node;
        tail = node;
        ++listLen;
        return node;
    }

    int deleteOldNode()
    {
        int deleteKey = 0;
        ListNode * oldNode = head->next;
        deleteKey = oldNode->key;

        //delete oldNode;

        //head->next = head->next->next; runtime error,prev没更新

        head = head->next; //head往下移
        --listLen;
        return deleteKey;
    }

    void updateNode(ListNode * tailNode, int key, int * value)
    {
        //ListNode * tailNode = kmap[key];
        if (value != NULL)
        {
            tailNode->value = *value;
        }

        if (tail == tailNode) return;

        if (tailNode->prev && tailNode->next)
        {
            tailNode->prev->next = tailNode->next;
            tailNode->next->prev = tailNode->prev;
        }

        if (tailNode != tail)
        {
            tailNode->next = NULL;
            tailNode->prev = tail;
            tail->next = tailNode;
            tail = tailNode;
        }
    }

    LRUCache(int capacity) {
        listLen = 0;
        maxLen = capacity;
        head = createList();
        tail = head;
        memset(d, 0x0, sizeof(d));
    }

    ListNode * find(int key)
    {
        if (key >= 0 && key < 5000)
        {
            return d[key];
        }
        else
        {
            if (kmap.find(key) == kmap.end())
            {
                return NULL;
            }
            return kmap[key];
        }
    }

    void setKeyMap(int key, ListNode * cur)
    {
        if (key >= 0 && key < 5000) d[key] = cur;
        else kmap[key] = cur;
    }

    void delKeyMap(int key)
    {
        if (key >= 0 && key < 5000) d[key] = 0;
        else kmap.erase(key);
    }

    int get(int key) {
        ListNode * cur = find(key);
        if (cur == NULL)
        {
            //cout << "not find key = " << key << endl;
            return -1;
        }

        updateNode(cur, key, NULL);
        //cout << "find key = " << key << "value = " << kmap[key]->value << endl;
        return cur->value;
    }

    void set(int key, int value) {
        ListNode * cur = find(key);
        if (cur == NULL)
        {
            if (listLen < maxLen)
            {
                setKeyMap(key, insertNode(key, value));
                //cout << "insert key = " << key << "value = " << value << endl;
            }
            else
            {
                int deleteKey = deleteOldNode();
                delKeyMap(deleteKey);
                //cout << "delete key = " << deleteKey << endl;
                setKeyMap(key, insertNode(key, value));
            }
        }
        else
        {
            //cout << "update key = " << key << " value = " << value << endl;
            updateNode(cur, key, &value);
        }
    }
};

4.参考

分类: c/c++, LeetCode, 算法, 通用概念, 面试 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.