On 2021-12-25 23:52, 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.
It can be done with a pass to remove the matches and pack the list:
Where there's a match, move it if you've exceeded maxcount, else
skip it.
Where there isn't a match, move it.
followed by truncation of the list if necessary.
_______________________________________________
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/3XWXHM5KXBISDOHOKXDYDMAW7KQW6F76/
Code of Conduct: http://python.org/psf/codeofconduct/
