[Python-ideas] Re: Add a `count` argument to `list.remove`
Steven D'Aprano wrote: > Can you sketch an O(n) algorithm for removing multiple items from an > array, which *doesn't* involving building a temporary new list? Here's what I meant. Have read/write indexes, delete the gap after maxcount occurrences: def remove(lst, value, maxcount): read = write = 0 while maxcount > 0 and read < len(lst): if lst[read] == value: maxcount -= 1 else: lst[write] = lst[read] write += 1 read += 1 del lst[write:read] Note that the remaining elements aren't looked at, just their references are memmoved (or whatever del does). ___ 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/DQMTVZMJ2RYG624FALIA7WGBFORMNY6T/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
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 -, 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/
[Python-ideas] Re: Add a `count` argument to `list.remove`
On Sun, Dec 26, 2021 at 11:32 AM Jeremiah Vivian wrote: > > Steven D'Aprano wrote: > > On Thu, Dec 23, 2021 at 05:53:46PM -, 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 ___ 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/LQA56SOM7FCLZTHVNU7OQE33EG2MSIQB/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
Steven D'Aprano wrote: > On Thu, Dec 23, 2021 at 05:53:46PM -, 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/
[Python-ideas] Re: Add a `count` argument to `list.remove`
On Sun, Dec 26, 2021 at 11:00 AM Steven D'Aprano wrote: > > On Thu, Dec 23, 2021 at 05:53:46PM -, 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 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 ___ 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/VXDE4GYRSF6WYDGRXW73RH2PZ2WC5Y4W/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
On 2021-12-25 23:52, Steven D'Aprano wrote: On Thu, Dec 23, 2021 at 05:53:46PM -, 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/
[Python-ideas] Re: Add a `count` argument to `list.remove`
On Thu, Dec 23, 2021 at 05:53:46PM -, 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. -- Steve ___ 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/SQINWYIB4FXXZM5V3LGMVEB6JBGIXHRT/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
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. And could be much more efficient than a list comprehension, because: 1) The list's C code would do it. 2) It could stop comparing early. 3) It wouldn't have to touch the later elements (a list comp would, to increment ref counts). 4) Doesn't need to build a new list. Also, how would you write it as a list comprehension? Trivial for removing *all* occurrences, but for removing only up to some count? I can do it, but it's not pretty. ___ 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/TBTHNS4M6EOLJ6YQOFNPWSNKVO3PP5CS/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
> When called with the count argument, should it raise ValueError if there > are fewer than `count` occurrences of the element in the list? No, it shouldn't. It would raise ValueError if the element is not found within the list though. ___ 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/INQAKMFLPSA5J24DO6L372C27CV6RHLD/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
On 2021-12-22 01:53, Rob Cliffe via Python-ideas wrote: Currently list.remove raises ValueError if the element is not in the list. When called with the count argument, should it raise ValueError if there are fewer than `count` occurrences of the element in the list? There's str.replace and str.split that accept a maximum count, and functions and methods in the re module that accept a maximum count. Is there any place where such a count isn't treated as a maximum? On 22/12/2021 00:09, Jeremiah Vivian wrote: I expect some sort of "there's no benefit in this, just write the current implementation", indirectly or directly. Currently, this is the way to remove `num` occurrences of an element from a list: idx = 0 while idx < len(the_list) and num: if the_list[idx] == element_to_remove: del the_list[idx] num -= 1 else: idx += 1 With a `count` argument to `list.remove`, this is how it would be done: the_list.remove(element_to_remove, count=num) (Doesn't necessarily have to be a keyword argument) Is this a good idea? Speaking of which, is there a use case for a 'key' argument? Just wondering... ___ 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/3MJG34K4BNB6ZW3POYC4BKMJISKGUXIN/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
Currently list.remove raises ValueError if the element is not in the list. When called with the count argument, should it raise ValueError if there are fewer than `count` occurrences of the element in the list? Best wishes Rob Cliffe On 22/12/2021 00:09, Jeremiah Vivian wrote: I expect some sort of "there's no benefit in this, just write the current implementation", indirectly or directly. Currently, this is the way to remove `num` occurrences of an element from a list: idx = 0 while idx < len(the_list) and num: if the_list[idx] == element_to_remove: del the_list[idx] num -= 1 else: idx += 1 With a `count` argument to `list.remove`, this is how it would be done: the_list.remove(element_to_remove, count=num) (Doesn't necessarily have to be a keyword argument) Is this a good idea? ___ 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/MMLIWVJEMBTQYTOI3QXJCHV5VYSDEQ66/ Code of Conduct: http://python.org/psf/codeofconduct/ ___ 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/I6G27U5NNXC4QRGE62KJSMTLNZOSQRN5/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add a `count` argument to `list.remove`
On Wed, Dec 22, 2021 at 11:12 AM Jeremiah Vivian wrote: > > I expect some sort of "there's no benefit in this, just write the current > implementation", indirectly or directly. > Currently, this is the way to remove `num` occurrences of an element from a > list: > > idx = 0 > > while idx < len(the_list) and num: > > if the_list[idx] == element_to_remove: > > del the_list[idx] > > num -= 1 > > else: > > idx += 1 > With a `count` argument to `list.remove`, this is how it would be done: > > the_list.remove(element_to_remove, count=num) > (Doesn't necessarily have to be a keyword argument) > Is this a good idea? 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 ___ 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/LKUTUKQPG6QT5UCUDX2WBQFUZNBN4RQ5/ Code of Conduct: http://python.org/psf/codeofconduct/
