On Sat, 1 Aug 2020 at 19:34, Christopher Barker <pythonchb@gmail.com> wrote:
I would think the goal here would be to re-order once in a while to remove the holes. But that would take time, of course, so you wouldn't want to do it on every deletion. But when?
You should have a separate process that does this, so "normal" operations will be not blocked. The process could also cache objects and do garbage collection. A sort of domestic worker. Don't know if this is possible.
About the hole, I was thinking that in theory the problem can be circumvented using a modified version of lookdict.
lookdict searches for a key and returns its position in the ma_keys array. I suppose it's possible to do the contrary: search for the index and return the key. What do you think (theoretically speaking)?
but isn't searching for the index going to require iterating through the array until you find it? i.e. that O(N) operation we're trying to avoid?
O(n) is an+b. If a and b are small, the algorithm is fast for not-so-big n. To sum up the alternatives: 1. rearrange the items array at positional lookup. As Inada said, it will mutate the dict while reading, that is quite unexpected 2. rearrange the items array at deletion. It will slow down deletion. Probably not an option... a NAO 3. no positional indexing. It seems the more simple solution. A number of alternatives are offered (by Tim Peters too) 4. something else.