LRU Cache C++ проблема реализации

Question

я делал упражнения в интернет-судьи:

Разработка и внедрение структуры данных для наименее недавно использовавшихся (LRU) кэша. Он должен поддерживать следующие операции: get и set.

get (key) - Получите значение (всегда будет положительным) ключа, если ключ существует в кеше, иначе возвратите -1.

set (ключ, значение) - Установить или вставить значение, если ключ еще не присутствует. Когда кеш достигнет своей емкости, он должен аннулировать последний использованный элемент перед вставкой нового элемента.

В основном я использую std::list и std::unordered_map и работает хорошо в маленьком корпусе ввода. Но OJ дает лимит времени превышен на входе: размер кеша - 2048 и 20000+ - &.

Лимит времени Превышен версия:

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; 
}; 

Тогда я подумал, почему бы не удалить элемент, прежде чем вставить один, так что я изменить set функцию и OJ принять!

Accept версия:

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())); 
     } 
    } 

Интересно, что делает такие разные?

Answer 1

Причина в том, что используемый вами OJ использует компилятор C++, который имеет std::list::size с линейной сложностью. В C++ 11 они требуют, чтобы он был постоянным, но в C++ 98 он мог быть до линейного, и многие реализации фактически имеют его линейный.

См complexity здесь на вкладке C++98: http://www.cplusplus.com/reference/list/list/size/

Я находится в OJ, что вы используете, и удалось получить TLE с кодом, но удалось получить его приняли с небольшой модификацией, которая просто отслеживает размер списка вместо вызова 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; 
};