Steven D'Aprano wrote:
> On Thu, Dec 23, 2021 at 05:53:46PM -0000, Stefan Pochmann wrote:
> > Chris Angelico wrote:
> > If you're removing multiple, it's usually best to filter. This is a
> > great opportunity to learn about list comprehensions and the
> > difference between O(n) and O(n²) :)
> > ChrisA
> > It would be O(n) if done right.
> > Can you sketch an O(n) algorithm for removing multiple items from an
> array, which *doesn't* involving building a temporary new list?
> I thought of this:
> - walk forward along the list, identifying the indices where the item
> equals the target;
> - stop when you reach maxcount, or the end of the list;
> - delete the indices in reverse order
> which I am pretty sure minimises movement of the items, but that's still
> O(N**2). (To be precise, O(N*M) where M is the number of items to be
> removed.)
> Anyway, it doesn't matter how efficient the code is if nobody uses it.
> Some use-cases would be nice.
I think you can iterate over the list and remove while iterating over it. When
elements removed reach maxcount, stop iterating and return.
The word "return" makes me feel like making `list.remove` return how much
elements it ACTUALLY removed from the list.
_______________________________________________
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/XR25DEAQ67X5TNTW6DV32VFFXUUXVFMK/
Code of Conduct: http://python.org/psf/codeofconduct/
