The complexity of the LRU cache algorithm

Question

I have in front of me a task to implement the LRU cache. And the longest operation in the system should take O(log (n)). As my Cache I use std :: MAP. I still need a second container for storing key + Creation Time - Sort by time. And when I need to update the address to the cache it should take somewhere:

Find by key O(log (n)).
Remove to an iterator O(1).
Insert a new element of the O(log (n)).

The oldest member must reside naturally in container.begin().

I can use only STL.

List - does not suit me.

list.find() - O (n)

Priority Queue - delete items not implemented.

I think it could ideally be stored in a std::set;

std::set<pair<KEY, TIME>>;

Sort std::set:

struct compare
{
    bool operator ()(const pair<K, TIME> &a, const pair<K, TIME> &b)
    {
        return a.second < b.second;
    }
};

And to find a key in std :: set to write the function wich looks for the first element of the pair - std::set<pair<KEY, TIME>>;.

What do you think? Can anyone tell if this suits my specified complexity requirements?

advocateofnone · Accepted Answer · 2015-01-18 19:23:01Z

1

Yes you can use map plus set to get the complexity of deleting/updating/inserting as O(logn).

map stores key,value pair.
set should store time,key in this order ( you have done opposite ). When cache is full and you want to remove a key it will be correspong to the element in set to which it = myset.begin() points to.

Having said that you can improve performance by using hash + double linked list.

answered Jan 18, 2015 at 19:23

advocateofnone

2,5393 gold badges20 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

etotientz Over a year ago

Does using a hash and list improve the time complexity to O(1) ?

Arahdalum · Accepted Answer · 2022-10-15 14:39:15Z

0

You can achieve O(1) complexity when chose proper data structures:

template<typename Key_t, typename Value_t>
class LruCache {
....
using Order_t = std::list<Key_t>;
Order_t m_order;
std::unordered_map<Key_t, std::pair<typename Order_t::iterator, Value_t>> m_container;
};

m_order is a list. You need to add some elements at the beginning or at the end of the list (O(1)). Removing an item from a list if you have iterator to it: m_order.erase(it) - O(1).
Removing Recently Used Key from a list: pop_front/pop_back: O(1).

When you need to find a key, use hash_map - find - (O(1) on average). When you found a key, you have a value, which is the real value and in addition an iterator to proper item in the list.

The whole complexity can be O(1), then.

edited Oct 15, 2022 at 14:39

answered Oct 15, 2022 at 14:16

Arahdalum

113 bronze badges

1 Comment

Mohamed Bana Over a year ago

"The whole complexity can be O(1), then." this simply cannot be. Please provide a proof.

Collectives™ on Stack Overflow

The complexity of the LRU cache algorithm

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related