I am trying to calculate the miss ratio curve for an LRU cache. I have implemented the cache as an ordered dictionary. whenever I add a key to the cache, to find the previous location of the key in the cache, I have to create a list of dictionary keys and index them.
Having a huge number of keys (around 10,000,000), this method obviously is very slow. Is there a faster way to find the location of the key in an ordered dictionary? Or do you suggest using another structure instead of an ordered dictionary to implement the cache?