Why got TLE using list and unorder_map in c++?


  • 1
    J

    Hi,all. I implement LRU with list and unordered_map in c++,both get and set should run in a constant time complexity. But i got a TLE. I have observed for a long time, but could not figure out why. Thanks a lot!

     typedef pair<int,int> KV;
     typedef list<KV>::iterator Iter;
    
     class LRUCache{
       public:
        LRUCache(int capacity):max_size(capacity) {
            
        }
    
        int get(int key) {
            unordered_map<int,Iter>::iterator pos = mp.find(key);
            if(pos == mp.end())
                return -1;
            else{
                Iter iter = mp[key];
                int re = iter->second;
                KV kv = *iter;
                cache.splice(cache.begin(),cache,iter);
                return re;
            }
        }
    
        void set(int key, int value) {
            unordered_map<int,Iter>::iterator pos = mp.find(key);
            if(pos != mp.end()){
                mp[key]->second = value;
                return; 
            }
                
            if(cache.size() > 0 && cache.size() == max_size ){
                KV kv = *cache.rbegin();
                mp.erase(kv.first);
                cache.pop_back();         
            }
            if(cache.size() < max_size){
                cache.push_front(KV(key,value)); 
                mp[key] = cache.begin();
            }
          
        }
    
    private:
        int max_size;     
        list<KV> cache;
        unordered_map<int,Iter> mp;
    

    };


  • 2
    Q
    1. FIrst there is a bug in your code. In the set() operation, if the key is in the lru, you should also adjust the item in the list to the front instead of just setting the value and return. Since after set() this item becomes the most recently used item. One easy way to do this:

      mp[key]->second = value;
      get(key);
      return;

    2. list::size() is an expensive operation. You should replace 'cache.size()' with 'mp.size()', since the latter takes O(1).

    Well, it takes me a while to find the issue, but I must thank you first for me to realize one of my misunderstanding. My solution is very similar to yours yet I'm just lucky to pass. It's indeed a misunderstanding of the list structure. I though list::size() is O(1) but it's probably not. It probably takes O(n). But I don't have time to verify, maybe you do and share the it to us :).


  • 0
    J

    thank you very much


  • 0
    A

    It is interesting to discuss the complexity of list::size(). I guess the short answer is that it depends on which STL standard you are using. According to http://www.cplusplus.com/reference/list/list/size/, in C++98, it is up to linear, but in C++11, it is constant. We will need to look at the actual implementation.
    Another discussion on this from StackOverflow:
    http://stackoverflow.com/questions/228908/is-listsize-really-on

    For this problem, using either list::size() or unordered_map::size() will pass, as far as I have tried.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.