Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #27194 > unrolled thread

set and dict iteration

Back to article view | Back to comp.lang.python

Contents

  set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-16 11:00 -0700
    Re: set and dict iteration Dave Angel <d@davea.name> - 2012-08-16 15:49 -0400
      Re: set and dict iteration Paul Rubin <no.email@nospam.invalid> - 2012-08-16 14:26 -0700
        Re: set and dict iteration Dave Angel <davea@dejaviewphoto.com> - 2012-08-16 19:11 -0400
          Re: set and dict iteration Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-17 02:24 +0000
            Re: set and dict iteration Paul Rubin <no.email@nospam.invalid> - 2012-08-16 19:30 -0700
              Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 11:11 -0700
            Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 11:37 -0700
              Re: set and dict iteration Chris Angelico <rosuav@gmail.com> - 2012-08-18 07:57 +1000
                Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 13:29 -0700
                Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 13:29 -0700
                  Re: set and dict iteration MRAB <python@mrabarnett.plus.com> - 2012-08-18 23:14 +0100
                    Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 19:28 -0700
                      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-23 09:49 -0700
                      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-23 09:49 -0700
                        Re: set and dict iteration Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-08-23 18:11 +0000
                    Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-18 19:28 -0700
        Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-16 17:43 -0600
          Re: set and dict iteration Paul Rubin <no.email@nospam.invalid> - 2012-08-16 18:01 -0700
            Re: set and dict iteration Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2012-08-17 13:16 +0200
            Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 11:03 -0700
    Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-16 16:55 -0600
    Re: set and dict iteration Ian Kelly <ian.g.kelly@gmail.com> - 2012-08-16 17:07 -0600
      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 10:47 -0700
      Re: set and dict iteration Aaron Brady <castironpi@gmail.com> - 2012-08-17 10:47 -0700

Page 2 of 2 — ← Prev page 1 [2]

#27252

On Thursday, August 16, 2012 8:01:39 PM UTC-5, Paul Rubin wrote:
> Ian Kelly <ian.g.kelly@gmail.com> writes:
> 
> > With regard to key insertion and deletion while iterating over a dict
> 
> > or set, though, there is just no good reason to be doing that
> 
> > (especially as the result is very implementation-specific), and I
> 
> > wouldn't mind a more complete low-level check against it as long as
> 
> > it's not too expensive (which is not clearly the case with the current
> 
> > suggestion at all).
> 
> 
> 
> One possible approach is to freeze the dictionary against modification
> 
> while any iterator is open on it.  You could keep a count of active
> 
> iterators in the dict structure, adjusting it whenever an iterator is
> 
> created or closed/destroyed.

Good point.  Your approach is another consistent solution.

The difference is in where the exception is raised.  Invalidating the iterators raises an exception when they're called.  Locking the set/dict raises an exception on 'add' and 'remove' calls.

The latter also forces additional statements to delete iterators before they leave scope in some cases.  We wouldn't be able to make modifications in a 'for' suite, even if followed by a 'break', which could be a problem for existing code.

[toc] | [prev] | [next] | [standalone]

#27211

On Thu, Aug 16, 2012 at 12:00 PM, Aaron Brady <castironpi@gmail.com> wrote:
> The inconsistency is, if we remove an element from a set and add another during iteration, the new element might appear later in the iteration, and might not, depending on the hash code; therefore comparing the size of the set between iterations isn't adequate.  Example:

It can be more than just the new element.  For example, here the
entire set is repeated (Python 3.2):

>>> s = set(range(8, 13))
>>> it = iter(s)
>>> from itertools import islice
>>> list(islice(it, 5))  # avoid exhausting the iterator
[8, 9, 10, 11, 12]
>>> s.add(13)
>>> s.remove(13)
>>> list(it)
[8, 9, 10, 11, 12]

This occurs because the addition of the sixth item triggers a resize
of the underlying hash table, and the existing items, which were
originally in slots 0-4, are now in slots 8-12.

[toc] | [prev] | [next] | [standalone]

#27212

On Thu, Aug 16, 2012 at 4:55 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Thu, Aug 16, 2012 at 12:00 PM, Aaron Brady <castironpi@gmail.com> wrote:
>> The inconsistency is, if we remove an element from a set and add another during iteration, the new element might appear later in the iteration, and might not, depending on the hash code; therefore comparing the size of the set between iterations isn't adequate.  Example:
>
> It can be more than just the new element.  For example, here the
> entire set is repeated (Python 3.2):
>
>>>> s = set(range(8, 13))
>>>> it = iter(s)
>>>> from itertools import islice
>>>> list(islice(it, 5))  # avoid exhausting the iterator
> [8, 9, 10, 11, 12]
>>>> s.add(13)
>>>> s.remove(13)
>>>> list(it)
> [8, 9, 10, 11, 12]
>
> This occurs because the addition of the sixth item triggers a resize
> of the underlying hash table, and the existing items, which were
> originally in slots 0-4, are now in slots 8-12.

Another curious example:

>>> s = set(range(8, 48, 8))
>>> s
{8, 16, 40, 24, 32}
>>> it = iter(s)
>>> from itertools import islice
>>> list(islice(it, 4))
[8, 16, 40, 24]
>>> s.add(48)
>>> s.remove(48)
>>> list(it)
[8, 16, 40, 24]

Hey, what happened to 32?

[toc] | [prev] | [next] | [standalone]

#27249

On Thursday, August 16, 2012 6:07:40 PM UTC-5, Ian wrote:
> On Thu, Aug 16, 2012 at 4:55 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> 
> > On Thu, Aug 16, 2012 at 12:00 PM, Aaron Brady <castironpi@gmail.com> wrote:
> 
> >> The inconsistency is, if we remove an element from a set and add another during iteration, the new element might appear later in the iteration, and might not, depending on the hash code; therefore comparing the size of the set between iterations isn't adequate.  Example:
> 
> >
> 
> > It can be more than just the new element.  For example, here the
> 
> > entire set is repeated (Python 3.2):
> 
> >
> 
> >>>> s = set(range(8, 13))
> 
> >>>> it = iter(s)
> 
> >>>> from itertools import islice
> 
> >>>> list(islice(it, 5))  # avoid exhausting the iterator
> 
> > [8, 9, 10, 11, 12]
> 
> >>>> s.add(13)
> 
> >>>> s.remove(13)
> 
> >>>> list(it)
> 
> > [8, 9, 10, 11, 12]
> 
> >
> 
> > This occurs because the addition of the sixth item triggers a resize
> 
> > of the underlying hash table, and the existing items, which were
> 
> > originally in slots 0-4, are now in slots 8-12.
> 
> 
> 
> Another curious example:
> 
> 
> 
> >>> s = set(range(8, 48, 8))
> 
> >>> s
> 
> {8, 16, 40, 24, 32}
> 
> >>> it = iter(s)
> 
> >>> from itertools import islice
> 
> >>> list(islice(it, 4))
> 
> [8, 16, 40, 24]
> 
> >>> s.add(48)
> 
> >>> s.remove(48)
> 
> >>> list(it)
> 
> [8, 16, 40, 24]
> 
> 
> 
> Hey, what happened to 32?

Good examples.  The former occurs without the 'islice' as well.

s= set( range( 8, 13 ) ) 
it= iter( s ) 
print( [ next( it ) for _ in range( 5 ) ] )
s.add( 13 ) 
s.remove( 13 ) 
print( [ next( it ) for _ in range( 5 ) ] )

Output:

[8, 9, 10, 11, 12]
[8, 9, 10, 11, 12]

[toc] | [prev] | [next] | [standalone]

#27251

On Thursday, August 16, 2012 6:07:40 PM UTC-5, Ian wrote:
> On Thu, Aug 16, 2012 at 4:55 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> 
> > On Thu, Aug 16, 2012 at 12:00 PM, Aaron Brady <castironpi@gmail.com> wrote:
> 
> >> The inconsistency is, if we remove an element from a set and add another during iteration, the new element might appear later in the iteration, and might not, depending on the hash code; therefore comparing the size of the set between iterations isn't adequate.  Example:
> 
> >
> 
> > It can be more than just the new element.  For example, here the
> 
> > entire set is repeated (Python 3.2):
> 
> >
> 
> >>>> s = set(range(8, 13))
> 
> >>>> it = iter(s)
> 
> >>>> from itertools import islice
> 
> >>>> list(islice(it, 5))  # avoid exhausting the iterator
> 
> > [8, 9, 10, 11, 12]
> 
> >>>> s.add(13)
> 
> >>>> s.remove(13)
> 
> >>>> list(it)
> 
> > [8, 9, 10, 11, 12]
> 
> >
> 
> > This occurs because the addition of the sixth item triggers a resize
> 
> > of the underlying hash table, and the existing items, which were
> 
> > originally in slots 0-4, are now in slots 8-12.
> 
> 
> 
> Another curious example:
> 
> 
> 
> >>> s = set(range(8, 48, 8))
> 
> >>> s
> 
> {8, 16, 40, 24, 32}
> 
> >>> it = iter(s)
> 
> >>> from itertools import islice
> 
> >>> list(islice(it, 4))
> 
> [8, 16, 40, 24]
> 
> >>> s.add(48)
> 
> >>> s.remove(48)
> 
> >>> list(it)
> 
> [8, 16, 40, 24]
> 
> 
> 
> Hey, what happened to 32?

Good examples.  The former occurs without the 'islice' as well.

s= set( range( 8, 13 ) ) 
it= iter( s ) 
print( [ next( it ) for _ in range( 5 ) ] )
s.add( 13 ) 
s.remove( 13 ) 
print( [ next( it ) for _ in range( 5 ) ] )

Output:

[8, 9, 10, 11, 12]
[8, 9, 10, 11, 12]

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web