Python Forum

i am thinking about a list to be a stack where i keep a most recently used index. when an index is used or created it gets put on one end. once the stack reaches a configured size, then every time an index is added to the stack, another index at the other end is deleted from the stack to keep it from growing too much.

i started writing some code to do this and quickly realized i needed to decide which end of the list (the [0] end or the [-1] end) would be which. i believe either choice can be made to work but one might be more efficient than the other. any ideas?

i am doing this to create a cache of data lookups that would be slow. the slowness can vary since this thing is general purpose. when the data is found in the cache, that one moves all the way to the "recent" end. when data is not found, it is looked up from a file or database or over the local network or over the internet. the new data is added to the cache at the "recent" end and if the cache has reached its maximum size a data item is deleted from the opposite end. the cache usually will have a dictionary along side.

should the "recent" end be at [0] in the list, or at [-1]. assume a tuple would never be used for this.

Quote:should the "recent" end be at [0] in the list, or at [-1]

This should be simple to check for yourself with a print statement.

Before "reinventing the wheel", check collections.deque. That's what you want, even if you need to inherit from the built-in class.

Quote:Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

(Feb-25-2019, 06:32 AM)woooee Wrote: [ -> ]

Quote:should the "recent" end be at [0] in the list, or at [-1]

This should be simple to check for yourself with a print statement.

i'm sure both will work. but which would be more efficient?

---

(Feb-25-2019, 07:26 AM)buran Wrote: [ -> ]Before "reinventing the wheel", check collections.deque. That's what you want, even if you need to inherit from the built-in class.

Quote:Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

i will need to use remove(value) which would be O(n). i would still need to track how many items are in it but that's just one int.

but .pop() only works from the right end ("Remove and return an element from the right side of the deque."). there is also .popleft() for the other end. it is therefore not usable for the step of taking a reference from wherever it is in the deque and putting on an end (the chosen end to represent most recently used items). yes, .pop() can easily be O(1) because it does not need to search for what it wants to move from the middle of deque. but .remove(value) has to find value, which not an O(1) operation (you knew that). the documentation does not say if .remove(value) returns the item. but that is not an issue right now since the value is already had and i can .append(value) or .appendleft(value) it after .remove(value).

Sorry, I realized my mistake immediately after post and removed the post, but probably it was too late and you respond to it

i am working on using collections.deque but i need to know when and what, when it removes items from the "opposite side" so the same item can be removed from the dictionary that saves actual data. a first implementation will be used to keep a cache for pwd.getpwuid() lookups at a finite size (in reality, even the largest systems i have seen can keep all the data in a dictionary, so cache limitation isn't really needed).