On Sun, Aug 2, 2020 at 2:34 AM Christopher Barker <email@example.com> wrote:
> On Sat, Aug 1, 2020 at 2:28 AM Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:
>> On Sat, 1 Aug 2020 at 03:00, Inada Naoki <firstname.lastname@example.org> 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.
Repacking is mutation, and mutating dict while iterating it breaks the iterator.
But `d.items()` don't looks like mutation.
> 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?
You are right. it couldn't.
Inada Naoki <email@example.com>
Python-ideas mailing list -- firstname.lastname@example.org
To unsubscribe send an email to email@example.com
Message archived at https://firstname.lastname@example.org/message/ED2GRWD4RARR2LGP45PK4M6R3MLTAF75/
Code of Conduct: http://python.org/psf/codeofconduct/