LRU Cache C++ implementation issue

Question

I was doing an exercise in an online judge:

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.

I basically use std::list and std::unordered_map and works good in small input case. But OJ give a Time Limit Exceeded on the input: cache size is 2048 and 20000+ get & set operations.

Time Limit Exceeded version:

class LRUCache {
public:
    LRUCache(int capacity):cacheSize(capacity) {

    }
    int get(int key) {
        auto it = mapping.find(key);
        if(it == mapping.end())
            return -1;
        itemList.splice(itemList.begin(),itemList,it->second);
        //mapping[key] == it->second still holds
        return it->second->second;
    }
    void set(int key, int value) {
        auto it = mapping.find(key);
        if(it != mapping.end()) {
            itemList.splice(itemList.begin(),itemList,it->second);
            it->second->second = value;
        } else {
            itemList.push_front(make_pair(key,value));
            mapping.insert(make_pair(key,itemList.begin()));
        }
        if(itemList.size() > cacheSize) {
            mapping.erase(itemList.back().first);
            itemList.pop_back();
        }
    }
private:
    int cacheSize;
    list<pair<int,int> > itemList;
    unordered_map<int,list<pair<int,int> >::iterator> mapping;
};

Then I thought why not erase element before insert one, so I modify set function and OJ accept!

Accept version:

    void set(int key, int value) {
        auto it = mapping.find(key);
        if(it != mapping.end()) {
            itemList.splice(itemList.begin(),itemList,it->second);
            it->second->second = value;
        } else {
            if(itemList.size() == cacheSize) {
                mapping.erase(itemList.back().first);
                itemList.pop_back();
            }
            itemList.push_front(make_pair(key,value));
            mapping.insert(make_pair(key,itemList.begin()));
        }
    }

I wonder what makes such a different?

You are checking cachesize even on "new insertions" - this is certainly unnecessary. You are also inserting another element, then removing one if it got too large, which may lead to further rebalancing of the tree than "remove first, then add" (although that's just a guess). — Mats Petersson

Ishamael Ishamael · Accepted Answer · 2015-01-19T09:38:23

The reason is that the OJ you use uses a C++ compiler which has std::list::size with linear complexity. In C++11 they require it to be constant, but in C++98 it could be up to linear, and many implementations actually have it linear.

See complexity here on the C++98 tab: http://www.cplusplus.com/reference/list/list/size/

I located the OJ that you were using, and managed to get TLE with your code, but managed to get it accepted with a small modification, which just tracks the size of the list instead of calling size()

class LRUCache {
public:
    LRUCache(int capacity):cacheSize(capacity) {
        listSize = 0;
    }
    int get(int key) {
        auto it = mapping.find(key);
        if(it == mapping.end())
            return -1;
        itemList.splice(itemList.begin(),itemList,it->second);
        //mapping[key] == it->second still holds
        return it->second->second;
    }
    void set(int key, int value) {
        auto it = mapping.find(key);
        if(it != mapping.end()) {
            itemList.splice(itemList.begin(),itemList,it->second);
            it->second->second = value;
        } else {
            itemList.push_front(make_pair(key,value));
            ++ listSize;
            mapping.insert(make_pair(key,itemList.begin()));
        }
        if(listSize > cacheSize) {
            mapping.erase(itemList.back().first);
            -- listSize;
            itemList.pop_back();
        }
    }
private:
    int cacheSize;
    int listSize;
    list<pair<int,int> > itemList;
    unordered_map<int,list<pair<int,int> >::iterator> mapping;
};

LRU Cache C++ implementation issue

1 Answers