On Sun, Dec 26, 2021 at 11:00 AM Steven D'Aprano <steve@pearwood.info> 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.
Let's see. Start with an offset of zero. Walk forward along the list until you find the first thing to remove, and then set the offset to 1. Continue walking forward through the list until you reach the end. Move the current element from idx to idx-offset. Any time the current element matches the thing to remove, increment the offset. Once you're at the end, prune the last <offset> elements. This should move each element a maximum of once, to the exact position it should end up in. Downside: This is not an atomic operation. If any other action (another thread, or a predicate function used to figure out whether to remove this element, etc, etc) looks at the list during this procedure, it will see it in an inconsistent state (with possible duplicate elements and such). But at least it's O(n). ChrisA