Chris Angelico wrote:
> On Sun, Dec 26, 2021 at 11:32 AM Jeremiah Vivian
> nohackingofkrow...@gmail.com wrote:
> > 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.
> > "Remove while iterating" is underspecified. If you want list.remove()
> to be able to remove more than one thing, you'll need to be clearer
> about exactly what happens if it removes multiple elements, what
> happens if it doesn't reach maxcount, etc.
> Most of the time, it's okay to create a second list; if you need to
> mutate the original, you can slice-assign. If that's not suitable, an
> algorithm like Steve described, or the one I described, may be more
> useful, but you'd have to pin down your exact use-case and needs.
> ChrisA
About the maxcount one. if the number of elements removed doesn't reach
maxcount, it just returns. The name describes what it is, a MAX count, so it is
just an upper limit to how much will be needed to remove.
_______________________________________________
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/533HDATPNMAF5MP55Y3NBEBT2J5S6B4H/
Code of Conduct: http://python.org/psf/codeofconduct/
