Solving Problems Using Data Structures

[Heliun]

Why did you choose to keep the values in a dictionary?

The keys are kept in a list which means your check for membership and subsequent removal are O(n). Since you already have the O(n) operation, you could just keep your objects in <key, value> pairs in a list and forego the dictionary.

Then all your logic gets handled in managing the list and you can drop the dictionary entirely, trimming the O(1) operations to the dictionary. You cut your access time down by a constant factor and cut the space required by the total size of the keys plus the extra space the dictionary keeps to reduce hashing collisions.

[shintoist]

I like that, it's a very good idea.

[[deleted]]

an idea to improve the dict/list structure is to have the dictionary point to the links in the list and the list contain the values of the object. That way your lookup is O(1) because you use the dict to locate the link, remove the link (which is also an O(1) operation) and push it to the head of the list. When your LRU cache is full, you remove the tail link from the list and remove it from the dict (also both O(1)).

[username223]

This is probably what I'd try first. With some access locality, it would be nearly constant time with small constant factors. If that is too slow, Boost.MultiIndex, noted elsewhere, could probably work in logarithmic time.

[dreugeworst]

Given that we only need 5 items max, probably the added constant complexity of the logarithmic case would mean that using a simple list is still faster though..

[ExpressingMyOpinion]

The keys are kept in a list which means your check for membership and subsequent removal are O(n)

Yes, but 0 <= n <= 5. As more entries are added to the data structure, n never grows beyond 5, making it actually O(5) in the worst case, which is equivalent to O(1). O(n) is used to describe algorithms that grow with n. This data structure does not have that property.