Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
mutating a deque whilst iterating over it
1,452 views
Skip to first unread message
duncan smith
Feb 11, 2021, 3:22:33 PM2/11/21
to
Hello,
It seems that I can mutate a deque while iterating over it if I
assign to an index, but not if I append to it. Is this the intended
behaviour? It seems a bit inconsistent. Cheers.
Duncan
>>> from collections import deque
>>> d = deque(range(8))
>>> it = iter(d)
>>> next(it)
0
>>> d[1] = 78
>>> next(it)
78
>>> d.append(8)
>>> next(it)
Traceback (most recent call last):
File "<pyshell#650>", line 1, in <module>
next(it)
RuntimeError: deque mutated during iteration
>>>
It seems that I can mutate a deque while iterating over it if I
assign to an index, but not if I append to it. Is this the intended
behaviour? It seems a bit inconsistent. Cheers.
Duncan
>>> from collections import deque
>>> d = deque(range(8))
>>> it = iter(d)
>>> next(it)
0
>>> d[1] = 78
>>> next(it)
78
>>> d.append(8)
>>> next(it)
Traceback (most recent call last):
File "<pyshell#650>", line 1, in <module>
next(it)
RuntimeError: deque mutated during iteration
>>>
dn
Feb 11, 2021, 4:17:57 PM2/11/21
to
On 12/02/2021 09.22, duncan smith wrote:
> Hello,
> It seems that I can mutate a deque while iterating over it if I
> assign to an index, but not if I append to it. Is this the intended
> behaviour? It seems a bit inconsistent. Cheers.
Yes, and no! Agree and disagree. (see how decisive I can be?)
> Hello,
> It seems that I can mutate a deque while iterating over it if I
> assign to an index, but not if I append to it. Is this the intended
> behaviour? It seems a bit inconsistent. Cheers.
Inconsistent when compared with what?
A tuple is immutable, but if it contains mutable objects as elements,
they are mutable. Consistent!
That said, tuples can't be append-ed/extend-ed, so a deque may seem more
like a list than a tuple. A list will allow both element and list mutation.
Substituting a list in the sample code, the iterator will adjust to
include an appended element. Inconsistent!
However... what happens if you have a for-loop which processes a list,
and within the loop one element is mutated in value and another appended
to the list?
Oops!
Maybe the deque authors wanted to avoid that, or perhaps such is related
to the option to bound the length of a deque (by design or side-effect)?
Imagine a bounded-deque (completely 'filled') and the code is
(overly-simple example) printing its contents. If the deque-element
printing-loop also allows deque-mutation, then the first value(s),
previously printed, will no longer exist within the queue.
I'm enjoying the question: wither inconsistency? Perhaps someone (wiser)
will jump in...
--
Regards,
=dn
Cameron Simpson
Feb 11, 2021, 11:06:04 PM2/11/21
to
On 11Feb2021 20:22, duncan smith <dun...@invalid.invalid> wrote:
> It seems that I can mutate a deque while iterating over it if I
>assign to an index, but not if I append to it. Is this the intended
>behaviour? It seems a bit inconsistent. Cheers.
I think that just means that the deque didn't _notice_ your change in
> It seems that I can mutate a deque while iterating over it if I
>assign to an index, but not if I append to it. Is this the intended
>behaviour? It seems a bit inconsistent. Cheers.
the former case. Not necessarily that it wouldn't want to.
I confess to not being sure that appending to a deque during an
iteration should be a bad thing, except that with a bounded deque that
might entail discarding the element at your current iteration point.
Maybe.
Cheers,
Cameron Simpson <c...@cskk.id.au>
Terry Reedy
Feb 12, 2021, 4:35:57 PM2/12/21
to
On 2/11/2021 3:22 PM, duncan smith wrote:
> It seems that I can mutate a deque while iterating over it if I
> assign to an index, but not if I append to it. Is this the intended
> behaviour?
Does the deque doc say anything about mutation while iterating?
> It seems that I can mutate a deque while iterating over it if I
> assign to an index, but not if I append to it. Is this the intended
> behaviour?
(Knowing the author of deque, I would consider everything about it
intentional without *good* reason to think otherwise.
>>>> from collections import deque
>>>> d = deque(range(8))
>>>> it = iter(d)
>>>> next(it)
> 0
>>>> d[1] = 78
notice. It could be considered not be a mutation. It could be detected
by changing deque.__setitem__, but why bother and slow down all
__setitem__ calls.
>>>> next(it)
> 78
>>>> d.append(8)
This changes the structure, which can apparently mess-up iteration.
>>>> next(it)
> Traceback (most recent call last):
> File "<pyshell#650>", line 1, in <module>
> next(it)
> RuntimeError: deque mutated during iteration
>>>>
Terry Jan Reedy
duncan smith
Feb 13, 2021, 1:20:42 PM2/13/21
to
because of the implementation or because it's how deques should ideally
behave. i.e. In my implementation do I stick strictly to the same API,
or allow it to differ? In some places I'm jumping through hoops to stick
to the API, and (when it comes to iteration) I'm jumping through
different hoops for different types of container (e.g. lists versus
deques). BTW, the reason I am implementing these at all is that my
containers are on-disk. Cheers.
Duncan
Dan Stromberg
Feb 13, 2021, 2:13:23 PM2/13/21
to
On Sat, Feb 13, 2021 at 10:25 AM duncan smith <dun...@invalid.invalid>
wrote:
> On 12/02/2021 03:04, Terry Reedy wrote:
> > On 2/11/2021 3:22 PM, duncan smith wrote:
> >
> >> It seems that I can mutate a deque while iterating over it if I
> >> assign to an index, but not if I append to it. Is this the intended
> >> behaviour?
>
can based on our implementation, and trust the client not to overuse
features".
In fact, in Python, "over abstraction" is often seen as a bad thing, mostly
because it slows things down so much.
If you want something more abstracted, you might have a look at:
https://stromberg.dnsalias.org/~strombrg/linked-list/
https://pypi.org/project/linked_list_mod/
(Both URL's are about the same module)
Note that linked_list_mod is quite a bit slower than a collections.deque.
Deques use a clever-but-hidden trick to gain a lot of speed - it's really a
linked list of built in lists, which gives better locality of reference
that masks CPU caches very happy. linked_list_mod goes for abstraction and
simplicity.
wrote:
> On 12/02/2021 03:04, Terry Reedy wrote:
> > On 2/11/2021 3:22 PM, duncan smith wrote:
> >
> >> It seems that I can mutate a deque while iterating over it if I
> >> assign to an index, but not if I append to it. Is this the intended
> >> behaviour?
>
> What I was really wondering was whether the behaviour is as it is
> because of the implementation or because it's how deques should ideally
> behave. i.e. In my implementation do I stick strictly to the same API,
> or allow it to differ? In some places I'm jumping through hoops to stick
> to the API, and (when it comes to iteration) I'm jumping through
> different hoops for different types of container (e.g. lists versus
> deques). BTW, the reason I am implementing these at all is that my
> containers are on-disk. Cheers.
>
> collections.deque appears to take the approach of "allow everything we
> because of the implementation or because it's how deques should ideally
> behave. i.e. In my implementation do I stick strictly to the same API,
> or allow it to differ? In some places I'm jumping through hoops to stick
> to the API, and (when it comes to iteration) I'm jumping through
> different hoops for different types of container (e.g. lists versus
> deques). BTW, the reason I am implementing these at all is that my
> containers are on-disk. Cheers.
>
can based on our implementation, and trust the client not to overuse
features".
In fact, in Python, "over abstraction" is often seen as a bad thing, mostly
because it slows things down so much.
If you want something more abstracted, you might have a look at:
https://stromberg.dnsalias.org/~strombrg/linked-list/
https://pypi.org/project/linked_list_mod/
(Both URL's are about the same module)
Note that linked_list_mod is quite a bit slower than a collections.deque.
Deques use a clever-but-hidden trick to gain a lot of speed - it's really a
linked list of built in lists, which gives better locality of reference
that masks CPU caches very happy. linked_list_mod goes for abstraction and
simplicity.
Avi Gross
Feb 13, 2021, 2:39:10 PM2/13/21
to
I agree both with the idea that it is not good to mutate things during
iteration and that some things we want to do may seemingly require
effectively something like a mutation.
I want to consider what data structure might capture a normal activity like
having a to-do-list for TODAY and another for further in the future. I might
sit down in the morning and look at my day and the list of activities I was
going to do. I might note new activities to add, some that are done or moot
and can be removed and some that should be done earlier or deferred to later
or even into the next day. This does not seem easy to do iteratively.
Weirder, if I throw each item at the end, I end up with the same items in
the same order.
So creating a data structure (such as an object like a deque but with more
specific functionality) might take some work. To begin, you might want an
iteration protocol that locks it till done. Not necessarily because of
mutation, though. Within the iteration you might have code asking for what I
might consider delayed actions. You can ask for the current item to be
deleted or moved to a data structure for the next day and it will not be
done now but some reference might be stored inside the object such as a
DELETE list and a MOVE list. You may also have lists with names like HIGH,
MEDIUM and LOW or priorities from 1 to N. I don't mean python lists, just
some kind of way of assigning some meaning to each item as you go. You may
even want a way to break a task into multiple parts or declare a dependency
between them such as one having to be done before the other.
When you are done iterating, presumably the data structure will then reorder
itself in a scenario where mutability is done harmlessly and a new list or
deque or whatever is reconstituted and you can unlock.
I do note that years ago I took a course in time management that ended up
spending way too much time doing this kind of task on paper multiple time a
day with lots of erasing or rewriting. The idea was to get more of the
important things done. These days, I am so interrupt-driven that such a
system is not useful albeit a nice automated way might be helpful as my day
constantly mutates to become unrecognizable.
There are project management tools along the lines I describe that try to
manage timelines and dependencies across multiple groups and measure
deliverables and note when something will cause delays in others and so on.
Obviously, beyond the scope but my point is they do not necessarily operate
in one pass over the list and are quite a bit more complex.
-----Original Message-----
From: Python-list <python-list-bounces+avigross=veriz...@python.org> On
Behalf Of Dan Stromberg
Sent: Saturday, February 13, 2021 2:13 PM
To: duncan smith <dun...@invalid.invalid>
Cc: Python List <pytho...@python.org>
Subject: Re: mutating a deque whilst iterating over it
On Sat, Feb 13, 2021 at 10:25 AM duncan smith <dun...@invalid.invalid>
wrote:
https://mail.python.org/mailman/listinfo/python-list
iteration and that some things we want to do may seemingly require
effectively something like a mutation.
I want to consider what data structure might capture a normal activity like
having a to-do-list for TODAY and another for further in the future. I might
sit down in the morning and look at my day and the list of activities I was
going to do. I might note new activities to add, some that are done or moot
and can be removed and some that should be done earlier or deferred to later
or even into the next day. This does not seem easy to do iteratively.
Weirder, if I throw each item at the end, I end up with the same items in
the same order.
So creating a data structure (such as an object like a deque but with more
specific functionality) might take some work. To begin, you might want an
iteration protocol that locks it till done. Not necessarily because of
mutation, though. Within the iteration you might have code asking for what I
might consider delayed actions. You can ask for the current item to be
deleted or moved to a data structure for the next day and it will not be
done now but some reference might be stored inside the object such as a
DELETE list and a MOVE list. You may also have lists with names like HIGH,
MEDIUM and LOW or priorities from 1 to N. I don't mean python lists, just
some kind of way of assigning some meaning to each item as you go. You may
even want a way to break a task into multiple parts or declare a dependency
between them such as one having to be done before the other.
When you are done iterating, presumably the data structure will then reorder
itself in a scenario where mutability is done harmlessly and a new list or
deque or whatever is reconstituted and you can unlock.
I do note that years ago I took a course in time management that ended up
spending way too much time doing this kind of task on paper multiple time a
day with lots of erasing or rewriting. The idea was to get more of the
important things done. These days, I am so interrupt-driven that such a
system is not useful albeit a nice automated way might be helpful as my day
constantly mutates to become unrecognizable.
There are project management tools along the lines I describe that try to
manage timelines and dependencies across multiple groups and measure
deliverables and note when something will cause delays in others and so on.
Obviously, beyond the scope but my point is they do not necessarily operate
in one pass over the list and are quite a bit more complex.
-----Original Message-----
From: Python-list <python-list-bounces+avigross=veriz...@python.org> On
Behalf Of Dan Stromberg
Sent: Saturday, February 13, 2021 2:13 PM
To: duncan smith <dun...@invalid.invalid>
Cc: Python List <pytho...@python.org>
Subject: Re: mutating a deque whilst iterating over it
On Sat, Feb 13, 2021 at 10:25 AM duncan smith <dun...@invalid.invalid>
wrote:
> On 12/02/2021 03:04, Terry Reedy wrote:
> > On 2/11/2021 3:22 PM, duncan smith wrote:
> >
> >> It seems that I can mutate a deque while iterating over it
> >> if I assign to an index, but not if I append to it. Is this the
> >> intended behaviour?
>
> > On 2/11/2021 3:22 PM, duncan smith wrote:
> >
> >> It seems that I can mutate a deque while iterating over it
> >> if I assign to an index, but not if I append to it. Is this the
> >> intended behaviour?
>
> What I was really wondering was whether the behaviour is as it is
> because of the implementation or because it's how deques should
> ideally behave. i.e. In my implementation do I stick strictly to the
> same API, or allow it to differ? In some places I'm jumping through
> hoops to stick to the API, and (when it comes to iteration) I'm
> jumping through different hoops for different types of container (e.g.
> lists versus deques). BTW, the reason I am implementing these at all
> is that my containers are on-disk. Cheers.
>
> because of the implementation or because it's how deques should
> ideally behave. i.e. In my implementation do I stick strictly to the
> same API, or allow it to differ? In some places I'm jumping through
> hoops to stick to the API, and (when it comes to iteration) I'm
> jumping through different hoops for different types of container (e.g.
> lists versus deques). BTW, the reason I am implementing these at all
> is that my containers are on-disk. Cheers.
>
> collections.deque appears to take the approach of "allow everything
> we
can based on our implementation, and trust the client not to overuse
features".
In fact, in Python, "over abstraction" is often seen as a bad thing, mostly
because it slows things down so much.
If you want something more abstracted, you might have a look at:
https://stromberg.dnsalias.org/~strombrg/linked-list/
https://pypi.org/project/linked_list_mod/
(Both URL's are about the same module)
Note that linked_list_mod is quite a bit slower than a collections.deque.
Deques use a clever-but-hidden trick to gain a lot of speed - it's really a
linked list of built in lists, which gives better locality of reference that
masks CPU caches very happy. linked_list_mod goes for abstraction and
simplicity.
--
> we
can based on our implementation, and trust the client not to overuse
features".
In fact, in Python, "over abstraction" is often seen as a bad thing, mostly
because it slows things down so much.
If you want something more abstracted, you might have a look at:
https://stromberg.dnsalias.org/~strombrg/linked-list/
https://pypi.org/project/linked_list_mod/
(Both URL's are about the same module)
Note that linked_list_mod is quite a bit slower than a collections.deque.
Deques use a clever-but-hidden trick to gain a lot of speed - it's really a
linked list of built in lists, which gives better locality of reference that
masks CPU caches very happy. linked_list_mod goes for abstraction and
simplicity.
https://mail.python.org/mailman/listinfo/python-list
duncan smith
Feb 14, 2021, 11:41:17 AM2/14/21
to
deque class that doesn't stick strictly to the Python deque API, then a
second class that implements a deque as a Python deque containing
instances of my basic on-disk deque class (with fixed size apart from
the first and last instances). Of course, this could change when I get
to testing / profiling. Cheers.
Duncan
0 new messages