On Wed, Apr 29, 2020 at 01:42:05PM +0300, Ram Rachum wrote:
> I was iterating through items of a deque, and in some cases I wanted to
> delete an item that I've found.
Deleting items from a container while iterating through it is an
anti-pattern, easy to get wrong, prone to bugs, and in a high-level
language like Python, very likely to be slower than creating a new
container and copying it across.
I haven't tried it with dequeues, but some versions ago I tried to find
the cross-over point where it was more efficient to delete items from a
list in place, instead of copying:
mylist[:] = [x from x in mylist if not condition]
versus:
for i in range(len(mylist)-1, -1, -1):
if condition:
del mylist[i]
My reasoning was that *eventually* for a big enough list, the cost of
making the copy would outweigh the cost of moving the items. I don't
know if my reasoning was valid or not, but I was unable to find any such
cutoff on my computer, up to hundreds of millions of items. Deletion was
always slower.
But, if you insist on doing it, dequeues support deletion.
> As far as I understand, this is an
> operation that should be O(1) in a linked list, but Python only provides an
> O(N) way to do that, which is `del d[i]`.
Dequeues are not linked lists. I don't believe that they are implemented
as linked lists, and I know that they certainly do not offer a linked
list API.
You could try rotating the dequeue, popping it, then rotating it back.
That might be faster, if rotation is fast.
But if you are only deleting one or two items, is that deletion a
bottle-neck in your code?
> The same can be said for inserting items in the middle.
If you want to insert and delete items in the middle, you are probably
better off using a list. Dequeues are explicitly optimised for insertion
and deletion at the ends, not the middle. It's a tradeoff.
> What do you think about adding this to `deque`?
Not much.
If you have a clever implementation in mind that will make deletion more
efficient, that's an implementation detail that will depend on (1)
whether you have someone willing and able to do the work and (2) whether
or not that implementation will rule out other possible future
improvements.
> The API will be tricky,
> admittedly, because you'll have to save some kind of reference to a cell in
> the deque.
I think you mean the implementation will be tricky. The API will surely
be trivial: either `del mydeque[i]`, as now, or `mydequeue.delete(i)`.
If you have some other API in mind, please describe it.
--
Steven
_______________________________________________
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/24RPFEJ6V6Y2ACZYKJRWJUV6TJUWKLTO/
Code of Conduct: http://python.org/psf/codeofconduct/
