On Sat, Aug 1, 2020 at 2:28 AM Marco Sulla <marco.sulla.pyt...@gmail.com> wrote:
> On Sat, 1 Aug 2020 at 03:00, Inada Naoki <songofaca...@gmail.com> wrote: > >> Please teach me if you know any algorithm which has no hole, O(1) >> deletion, preserving insertion order, and efficient and fast as array. >> > 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? One option: maybe too specialized, but it could re-pack the array when an indexing operation is made -- since that operation is O(N) anyway. And that would then address the issue of performance for multiple indexing operations -- if you made a bunch of indexing operation in a row without deleting (which would be the case, if this is an alternative to making a copy in a Sequence first), then the first one would repack the internal array (presumably faster than making a copy) and the rest would have O(1) access. Given that this use case doesn't appear to be very important, I doubt it's worth it, but it seems it would be possible. Another thought -- could the re-packing happen whenever the entire dict is iterated through? Though maybe there's no way to know when that's going to happen -- all you get are the individual calls for the next one, yes? > 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? -CHB -- Christopher Barker, PhD Python Language Consulting - Teaching - Scientific Software Development - Desktop GUI and Web Development - wxPython, numpy, scipy, Cython
_______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/KGRYRDCLFIH3PAEOZ7HFFIN4SLV5KHIF/ Code of Conduct: http://python.org/psf/codeofconduct/
