Chris Angelico wrote:
On Sun, Dec 26, 2021 at 11:32 AM Jeremiah Vivian nohackingofkrowten@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.