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

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

Is there a canonical way to check whether an iterable is ordered?

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

Contents

  Is there a canonical way to check whether an iterable is ordered? cool-RR <ram.rachum@gmail.com> - 2014-09-18 04:55 -0700
    Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-18 22:10 +1000
      Re: Is there a canonical way to check whether an iterable is ordered? Roy Smith <roy@panix.com> - 2014-09-18 08:58 -0400
        Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-18 23:33 +1000
          Re: Is there a canonical way to check whether an iterable is ordered? Roy Smith <roy@panix.com> - 2014-09-18 19:52 -0400
            Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 12:45 +1000
            Re: Is there a canonical way to check whether an iterable is ordered? Terry Reedy <tjreedy@udel.edu> - 2014-09-19 18:02 -0400
            Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-20 15:01 +1000
        Re: Is there a canonical way to check whether an iterable is ordered? Terry Reedy <tjreedy@udel.edu> - 2014-09-18 09:46 -0400
        Re: Is there a canonical way to check whether an iterable is ordered? Tim Chase <python.list@tim.thechases.com> - 2014-09-18 09:32 -0500
        Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 15:15 +1000
          Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 15:40 +1000
            Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 20:59 +1000
              Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 21:19 +1000
                Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 21:58 +1000
                  Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 22:06 +1000
              Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 21:25 +1000
                Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 21:46 +1000
                  Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 21:56 +1000
                    Re: Is there a canonical way to check whether an iterable is ordered? alister <alister.nospam.ware@ntlworld.com> - 2014-09-19 12:26 +0000
                      Re: Is there a canonical way to check whether an iterable is ordered? Chris Angelico <rosuav@gmail.com> - 2014-09-19 22:36 +1000
    Re: Is there a canonical way to check whether an iterable is ordered? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-19 15:04 +1000

Page 1 of 2  [1] 2  Next page →

#78010 — Is there a canonical way to check whether an iterable is ordered?

My function gets an iterable of an unknown type. I want to check whether it's ordered. I could check whether it's a `set` or `frozenset`, which would cover many cases, but I wonder if I can do better. Is there a nicer way to check whether an iterable is ordered or not? 


Thanks,
Ram.

[toc] | [next] | [standalone]

#78011

On Thu, Sep 18, 2014 at 9:55 PM, cool-RR <ram.rachum@gmail.com> wrote:
> My function gets an iterable of an unknown type. I want to check whether it's ordered. I could check whether it's a `set` or `frozenset`, which would cover many cases, but I wonder if I can do better. Is there a nicer way to check whether an iterable is ordered or not?
>

An iterable is always ordered. You call next() and you get the next
value. Are you asking if there's a way to find out if the order
matters? Not easily. What's your use-case? Why do you need to know?

Also, you're still using Google Groups, which means your formatting is
b0rked. Please can you use something better, or else look into fixing
this.

ChrisA

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

#78013

In article <mailman.14101.1411042251.18130.python-list@python.org>,
 Chris Angelico <rosuav@gmail.com> wrote:

> On Thu, Sep 18, 2014 at 9:55 PM, cool-RR <ram.rachum@gmail.com> wrote:
> > My function gets an iterable of an unknown type. I want to check whether 
> > it's ordered. I could check whether it's a `set` or `frozenset`, which 
> > would cover many cases, but I wonder if I can do better. Is there a nicer 
> > way to check whether an iterable is ordered or not?
> >
> 
> An iterable is always ordered. You call next() and you get the next
> value.

I suspect what he meant was "How can I tell if I'm iterating over an 
ordered collection?", i.e. iterating over a list vs. iterating over a 
set.

Is there anything which requires an iterator to be deterministic?  For 
example, let's say I have an iterable, i, and I do:

list1 = [item for item in i]
list2 = [item for item in i]

am I guaranteed that list1 == list2?  It will be for all the collections 
I can think of in the standard library, but if I wrote my own class with 
an __iter__() which yielded the items in a non-deterministic order, 
would I be violating something other than the principle of least 
astonishment?

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

#78015

On Thu, Sep 18, 2014 at 10:58 PM, Roy Smith <roy@panix.com> wrote:
> I suspect what he meant was "How can I tell if I'm iterating over an
> ordered collection?", i.e. iterating over a list vs. iterating over a
> set.

Right, which is what I meant by asking if the order mattered. When you
iterate over a set, you'll get some kind of order (because iterables
have to have an order), but it won't mean anything.

> Is there anything which requires an iterator to be deterministic?  For
> example, let's say I have an iterable, i, and I do:
>
> list1 = [item for item in i]
> list2 = [item for item in i]
>
> am I guaranteed that list1 == list2?  It will be for all the collections
> I can think of in the standard library, but if I wrote my own class with
> an __iter__() which yielded the items in a non-deterministic order,
> would I be violating something other than the principle of least
> astonishment?

It's not guaranteed. If you do exactly that, with no operations in
between, then yes, all the stdlib collections will (AFAIK) give you
matching lists, but that's definitely not required by iterator
protocol.

The one thing you can rely on (and therefore must comply with, when
you design an iterable) is that iteration will hit every element
exactly once. Implementing that on most collections means returning
the values in some internal representational order, something that's
consistent across the lifetime of the iterator; having that not be
consistent across multiple iterators would be the exception, not the
rule.

There would be a few special cases where you specifically *want to*
have the lists differ, though. Imagine DNS records: perhaps you have
four A records for some name, and you want to distribute load between
them [1]. You could have your name server do something like this:

class _cl_iter:
    def __init__(self, lst, start):
        self._data = lst
        self._start = self._next = start
    def __iter__(self): return self
    def __next__(self):
        if self._next is None: raise StopIteration
        val = self._data[self._next]
        self._next = (self._next + 1) % len(self._data)
        if self._next == self._start: self._next = None
        return val

class CircularList:
    def __init__(self, it):
        self._data = list(it)
        self._next = -1
    def __iter__(self):
        self._next = (self._next + 1) % len(self._data)
        return _cl_iter(self._data, self._next)

Every time you iterate over a given CircularList, you'll get the same
results, but starting at a different point:

>>> lst = CircularList(("192.0.2.1","192.0.2.2","192.0.2.3","192.0.2.4"))
>>> list(lst)
['192.0.2.1', '192.0.2.2', '192.0.2.3', '192.0.2.4']
>>> list(lst)
['192.0.2.2', '192.0.2.3', '192.0.2.4', '192.0.2.1']
>>> list(lst)
['192.0.2.3', '192.0.2.4', '192.0.2.1', '192.0.2.2']
>>> list(lst)
['192.0.2.4', '192.0.2.1', '192.0.2.2', '192.0.2.3']

So if you have a whole bunch of these for your different A records,
and you return them in iteration order to each client, you'll end up
with different clients getting them in a different order, with minimal
extra storage space. (This is Py3 code; to make it Py2 compatible,
probably all you need to do is subclass object and rename __next__ to
next.)

But this is a pretty unusual case. I would expect that most objects
will either iterate consistently until mutated, or return only what
wasn't previously consumed (like an iterator, which is itself
iterable).

ChrisA

[1] This isn't true load-balancing, of course, but it's a simple way
to distribute requests a bit. It's better than nothing.

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

#78052

In article <mailman.14103.1411047208.18130.python-list@python.org>,
 Chris Angelico <rosuav@gmail.com> wrote:

> The one thing you can rely on (and therefore must comply with, when
> you design an iterable) is that iteration will hit every element
> exactly once. 

Does it actually say that somewhere?  For example:

for i in bag.pick_randomly_with_replacement(n=5):
   print i

shouldn't do that.

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

#78054

On Fri, Sep 19, 2014 at 9:52 AM, Roy Smith <roy@panix.com> wrote:
> In article <mailman.14103.1411047208.18130.python-list@python.org>,
>  Chris Angelico <rosuav@gmail.com> wrote:
>
>> The one thing you can rely on (and therefore must comply with, when
>> you design an iterable) is that iteration will hit every element
>> exactly once.
>
> Does it actually say that somewhere?  For example:
>
> for i in bag.pick_randomly_with_replacement(n=5):
>    print i
>
> shouldn't do that.

When you pick randomly from a population, you create a new population,
which may have duplicates compared to the original. (For efficiency's
sake it probably won't all actually exist immediately, but
conceptually it does exist.) That's what you're iterating over - not
the bag itself.

ChrisA

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

#78089

On 9/18/2014 10:45 PM, Chris Angelico wrote:
> On Fri, Sep 19, 2014 at 9:52 AM, Roy Smith <roy@panix.com> wrote:
>> In article <mailman.14103.1411047208.18130.python-list@python.org>,
>>   Chris Angelico <rosuav@gmail.com> wrote:
>>
>>> The one thing you can rely on (and therefore must comply with, when
>>> you design an iterable) is that iteration will hit every element

in what, a collection that exists separately from the iteration?  or a 
collection generated by the iteration?

This is actually two statements in one -- what the user can rely on, 
which I claim is very little (see below) -- and what the designer must 
'comply with', which is correspondingly very little (again see below) 
except as the designer claims otherwise in specific documentation.

>>> exactly once.

There are only two things to rely on without further, special case, 
information.

iter(iterable) = iterator (if not, 'iterable' is not an iterable)

next(iterator) = object or raises StopIteration (with raising not 
guaranteed)

The conceptual flaw in the statement above, as I think originally 
intended, is the notion that 'every element [of a collection]' exists, 
or is defined before the iteration.  Iterators can be creative, in the 
sense of generating collections as they go, in a manner not determined 
by the past.  It is also possible that the next item depends on what the 
iterator user has done with previous items.  Such feedback loops are 
common for programs that interact with users.

If the statement above is interpreted retrospectively, as "iteration 
hits every item of the sequence it generates", then it is trivially true 
and is equivalent to "iteration yields every element that it yields, in 
the order that it yields them".  To paraphase the OP's question, given 
completion of

yielded1 = [item for item in iterable]
yielded2 = [item for item in yielded1]

then yielded2 == yielded1 *is* guarenteed.  But this is all that is 
guaranteed.

Itertools.tee operates similarly to the above code except that 
processing of the duplicate streams can be interleaved.  There is an 
internal queue of items yielded on one branch not the other.  For best 
operation, accesses should be interleaved, with the maximum lag bounded. 
  Itertools.tee guarantees that the two branches yield the same items in 
the same order.

>> Does it actually say that somewhere?  For example:
>>
>> for i in bag.pick_randomly_with_replacement(n=5):
>>     print i
>>
>> shouldn't do that.
>
> When you pick randomly from a population, you create a new population,
> which may have duplicates compared to the original. (For efficiency's
> sake it probably won't all actually exist immediately, but
> conceptually it does exist.)

When the next item depends on feedback from the user, that conceptual 
trick does not work as well.

 > That's what you're iterating over - not the bag itself.

If one iterates over anything other that a sequence, in forward order, 
then one is, in effect, iterating over a new sequence generated from the 
'base' collection.  In particular, set and dict iteration iterates over 
an arbitrary serialization of the set or dict.

In the example above, the underlying collection (or specification 
thereof) and size of selection can be hidden away in a class instance so 
that the code may just look like 'for i in my_iterable:", just as for 
iterating over a set.

-- 
Terry Jan Reedy

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

#78097

On Sat, Sep 20, 2014 at 8:02 AM, Terry Reedy <tjreedy@udel.edu> wrote:
>> That's what you're iterating over - not the bag itself.
>
> If one iterates over anything other that a sequence, in forward order, then
> one is, in effect, iterating over a new sequence generated from the 'base'
> collection.  In particular, set and dict iteration iterates over an
> arbitrary serialization of the set or dict.

Yeah, that's basically what I was trying to say. Didn't realize how
empty the statement was till you dug deeper into it, heh. Yes, an
iterator yields the items it yields, in the order it yields them...
*twiddles thumbs*

ChrisA

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

#78016

On 9/18/2014 8:58 AM, Roy Smith wrote:

> I suspect what he meant was "How can I tell if I'm iterating over an
> ordered collection?", i.e. iterating over a list vs. iterating over a
> set.

One can check whether the iterable is a tuple, list, range, or tuple or 
list iterator (the latter not being re-iterable).

 >>> type(iter([]))
<class 'list_iterator'>
 >>> type(iter(()))
<class 'tuple_iterator'>

> Is there anything which requires an iterator to be deterministic?

No. An iterator can yields random number, input from a non-deterministic 
source -- human or mechanical, or items from a collection in shuffled 
order.  Generator that do such can easily be turned into the __iter__ 
method of a class.

 > For example, let's say I have an iterable, i, and I do:
>
> list1 = [item for item in i]
> list2 = [item for item in i]

If i is an iterator or other non-reiterable, list2 will be empty.
If i is an instance of a class with a non-deterministic __iter__ method, 
list2 will not necessarily be either empty or a copy of list1.

> am I guaranteed that list1 == list2?

Clearly not.

 > It will be for all the collections I can think of in the standard 
library, but if I wrote my own class with
> an __iter__() which yielded the items in a non-deterministic order,
> would I be violating something other than the principle of least
> astonishment?

There should not be any astonishment.  'Iterable' is a much broader 
category than 'deterministically re-iterable iterable'.

-- 
Terry Jan Reedy

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

#78027

On 2014-09-18 08:58, Roy Smith wrote:
> I suspect what he meant was "How can I tell if I'm iterating over
> an ordered collection?", i.e. iterating over a list vs. iterating
> over a set.
> 
> list1 = [item for item in i]
> list2 = [item for item in i]
> 
> am I guaranteed that list1 == list2?  It will be for all the
> collections I can think of in the standard library,

For stdlib *collections*, yes, but if you're just talking generic
iterators, then it can become exhausted in the first:

  with open('example.txt') as f:
    list1 = [item for item in f]
    list2 = [item for item in f]
    assert list1 == list2, "Not equal"

The OP would have to track the meta-information regarding whether the
iterable was sorted.

At least for dicts, order is guaranteed by the specs as long as the
container isn't modified between iterations[1], but I don't see any
similar claim for sets.

You can always test the thing:

  def foo(iterable):
    if isinstance(iterable, (set, frozenset)):
      iterable = sorted(iterable)
    for thing in iterable:
      do_stuff(thing)    
    
but nothing prevents that from being called with an unsorted list.

That said, sorting in the stdlib is pretty speedy on pre-sorted lists,
so I'd just start by sorting whatever it is that you have, unless
you're positive it's already sorted.

-tkc

[1]
https://docs.python.org/2/library/stdtypes.html#dict.items

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

#78058

Roy Smith wrote:

> Is there anything which requires an iterator to be deterministic?

Absolutely not.

py> def spam():
...     while True:
...         n = random.randint(0, 10)
...         s = ' '.join(['spam']*n)
...         if not s:
...             return
...         yield s + '!'
...
py> for s in spam():
...     print(s)
...
spam spam spam spam spam spam!
spam spam!
spam spam spam spam spam spam spam spam spam!
spam spam spam spam spam spam spam!
py>


> For 
> example, let's say I have an iterable, i, and I do:
> 
> list1 = [item for item in i]
> list2 = [item for item in i]

Don't do that. Just write:

list1 = list(i)
list2 = list(i)

> am I guaranteed that list1 == list2?

No.

However, as far as I am aware, there are no built-ins that will fail that
test, yet. Although the iteration order of dicts and sets is arbitrary, I
think that (at least to date) it will be the same order every time you
iterate over the dict or set within a single run of the Python interpreter.
(Provided the dict or set hasn't changed.)

That's not a language guarantee though. It's an implementation detail. In
principle, it could be different each time:

s = set("abcd")
list(s)
=> returns ['d', 'a', 'b', 'c']
list(s)
=> returns ['c', 'a', 'd', 'b']


> It will be for all the collections 
> I can think of in the standard library, but if I wrote my own class with
> an __iter__() which yielded the items in a non-deterministic order,
> would I be violating something other than the principle of least
> astonishment?

Nope.


-- 
Steven

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

#78059

On Fri, Sep 19, 2014 at 3:15 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> However, as far as I am aware, there are no built-ins that will fail that
> test, yet. Although the iteration order of dicts and sets is arbitrary, I
> think that (at least to date) it will be the same order every time you
> iterate over the dict or set within a single run of the Python interpreter.
> (Provided the dict or set hasn't changed.)
>
> That's not a language guarantee though. It's an implementation detail. In
> principle, it could be different each time:
>
> s = set("abcd")
> list(s)
> => returns ['d', 'a', 'b', 'c']
> list(s)
> => returns ['c', 'a', 'd', 'b']

Possibly for the set, but the dict is guaranteed some measure of stability:

https://docs.python.org/3.4/library/stdtypes.html#dict-views
"""If keys, values and items views are iterated over with no
intervening modifications to the dictionary, the order of items will
directly correspond."""

Also, a little above:
"""
iter(d)

Return an iterator over the keys of the dictionary. This is a shortcut
for iter(d.keys()).
"""

So if iterating over d.keys() and then d.values() with no mutations is
guaranteed to give the same order, then so is iterating over d.keys(),
then d.keys(), then d.values(), and since there's no magic in
iterating over d.values(), it logically follows that iterating over
d.keys() twice will give the same order.

But yes, it's conceivable that the set might change iteration order
arbitrarily. I don't know of any good reason for it to, but it
certainly isn't forbidden.

ChrisA

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

#78067

Chris Angelico wrote:

> On Fri, Sep 19, 2014 at 3:15 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> However, as far as I am aware, there are no built-ins that will fail that
>> test, yet. Although the iteration order of dicts and sets is arbitrary, I
>> think that (at least to date) it will be the same order every time you
>> iterate over the dict or set within a single run of the Python
>> interpreter. (Provided the dict or set hasn't changed.)
>>
>> That's not a language guarantee though. It's an implementation detail. In
>> principle, it could be different each time:
>>
>> s = set("abcd")
>> list(s)
>> => returns ['d', 'a', 'b', 'c']
>> list(s)
>> => returns ['c', 'a', 'd', 'b']
> 
> Possibly for the set, but the dict is guaranteed some measure of
> stability:
> 
> https://docs.python.org/3.4/library/stdtypes.html#dict-views
> """If keys, values and items views are iterated over with no
> intervening modifications to the dictionary, the order of items will
> directly correspond."""

Yes, but that doesn't mean that if you iterate over them twice, they will
necessarily be the same each time. The promise is that:

keys = list(mydict)
values = list(mydict.values())
assert keys == [item[0] for item in mydict.items()]
assert values == [item[1] for item in mydict.items()]

But *not* this:

keys1 = list(mydict)
keys2 = list(mydict)
assert keys1 == keys2

It's hard to think of an implementation which would support the first but
not the second, but if you did, Python would allow it :-)

[...]
> So if iterating over d.keys() and then d.values() with no mutations is
> guaranteed to give the same order, then so is iterating over d.keys(),
> then d.keys(), then d.values(), 

Not so! So long as the iteration of values() matched the *second* iteration
of keys(), it would be allowed. There's nothing which says that the first
iteration of keys() has to match the second.

Here's a proof of concept of what would be allowed:

import random
class MyDict:
    def __init__(self, items):
        self._items = list(dict(items).items())
        self._flags = [False, False, False]
    def keys(self):
        k = [item[0] for item in self._items]
        self._check(0)
        return k
    def values(self):
        k = [item[1] for item in self._items]
        self._check(1)
        return k
    def items(self):
        k = self._items[:]
        self._check(2)
        return k
    def _check(self, i):
        self._flags[i] = True
        if self._flags == [True, True, True]:
            random.shuffle(self._items)
            self._flags = [False, False, False]


-- 
Steven

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

#78069

On Fri, Sep 19, 2014 at 8:59 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
>> https://docs.python.org/3.4/library/stdtypes.html#dict-views
>> """If keys, values and items views are iterated over with no
>> intervening modifications to the dictionary, the order of items will
>> directly correspond."""
>> So if iterating over d.keys() and then d.values() with no mutations is
>> guaranteed to give the same order, then so is iterating over d.keys(),
>> then d.keys(), then d.values(),
>
> Not so! So long as the iteration of values() matched the *second* iteration
> of keys(), it would be allowed. There's nothing which says that the first
> iteration of keys() has to match the second.

I disagree. Between the first iteration of keys() and the iteration of
values(), there were no modifications to the dictionary - another
iteration over keys() isn't a modification - ergo the guarantee ought
to hold. If you replace that inner iteration with the opening of a
file, or the division of a float by a Decimal, or the definition of a
new class, I'm sure everyone would agree that the guarantee still
holds, because they don't change the dict; so why should iterating
over keys() be any different?

ChrisA

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

#78074

Chris Angelico wrote:

> On Fri, Sep 19, 2014 at 8:59 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>>> https://docs.python.org/3.4/library/stdtypes.html#dict-views
>>> """If keys, values and items views are iterated over with no
>>> intervening modifications to the dictionary, the order of items will
>>> directly correspond."""
>>> So if iterating over d.keys() and then d.values() with no mutations is
>>> guaranteed to give the same order, then so is iterating over d.keys(),
>>> then d.keys(), then d.values(),
>>
>> Not so! So long as the iteration of values() matched the *second*
>> iteration of keys(), it would be allowed. There's nothing which says that
>> the first iteration of keys() has to match the second.
> 
> I disagree. Between the first iteration of keys() and the iteration of
> values(), there were no modifications to the dictionary - another
> iteration over keys() isn't a modification - ergo the guarantee ought
> to hold.

All it says is that keys/values/items will correspond, not keys/keys, etc.

Hmmm. On second thought, there is a problem with this:

a = list(mydict)
c = list(mydict.items())  # now the internal order is shuffled
b = list(mydict.values())
assert list(zip(a, b)) == c

and the assertion fails.

So I guess that rules out dict internal order changing during a single run
of the interpreter, unless the dict is modified.

Anyway, that's just dicts. Custom iterables can change any time they like.



-- 
Steven

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

#78075

On Fri, Sep 19, 2014 at 9:58 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> All it says is that keys/values/items will correspond, not keys/keys, etc.
>
> Hmmm. On second thought, there is a problem with this:
>
> a = list(mydict)
> c = list(mydict.items())  # now the internal order is shuffled
> b = list(mydict.values())
> assert list(zip(a, b)) == c
>
> and the assertion fails.
>
> So I guess that rules out dict internal order changing during a single run
> of the interpreter, unless the dict is modified.

Precisely. If you iterate keys, keys, values with no mutations in
between, the first keys has to correspond to values, and the second
keys has to correspond to values, ergo they must correspond to each
other.

> Anyway, that's just dicts. Custom iterables can change any time they like.

Oh, sure. That's a very specific promise of the dict, nothing else.
The set might well randomize, if it wished. But we still come back to
there being no reason for it to change.

ChrisA

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

#78070

On Fri, Sep 19, 2014 at 8:59 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Here's a proof of concept of what would be allowed:
>
> import random
> class MyDict:
>     def __init__(self, items):
>         self._items = list(dict(items).items())
>         self._flags = [False, False, False]
>     def keys(self):
>         k = [item[0] for item in self._items]
>         self._check(0)
>         return k
>     def values(self):
>         k = [item[1] for item in self._items]
>         self._check(1)
>         return k
>     def items(self):
>         k = self._items[:]
>         self._check(2)
>         return k
>     def _check(self, i):
>         self._flags[i] = True
>         if self._flags == [True, True, True]:
>             random.shuffle(self._items)
>             self._flags = [False, False, False]

Also, this can't possibly offer the same guarantee. Watch:

d = MyDict(some_lot_of_items)
d.values(); d.items()
# mutate the dict in whatever way you like
pairs = zip(d.keys(), d.values())

This might well create mismatched pairs, because after generating the
keys() return value, the list gets shuffled, prior to generating
values() in the same expression. This would not be allowed.

ChrisA

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

#78072

Chris Angelico wrote:

> On Fri, Sep 19, 2014 at 8:59 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> Here's a proof of concept of what would be allowed:
[...]
> Also, this can't possibly offer the same guarantee. Watch:
> 
> d = MyDict(some_lot_of_items)
> d.values(); d.items()
> # mutate the dict in whatever way you like
> pairs = zip(d.keys(), d.values())
> 
> This might well create mismatched pairs, because after generating the
> keys() return value, the list gets shuffled, prior to generating
> values() in the same expression. This would not be allowed.

That would be a bug, and an easy one to fix. Every mutation of the dict
would have to reset the internal flags back to the starting state.


-- 
Steven

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

#78073

On Fri, Sep 19, 2014 at 9:46 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Chris Angelico wrote:
>
>> On Fri, Sep 19, 2014 at 8:59 PM, Steven D'Aprano
>> <steve+comp.lang.python@pearwood.info> wrote:
>>> Here's a proof of concept of what would be allowed:
> [...]
>> Also, this can't possibly offer the same guarantee. Watch:
>>
>> d = MyDict(some_lot_of_items)
>> d.values(); d.items()
>> # mutate the dict in whatever way you like
>> pairs = zip(d.keys(), d.values())
>>
>> This might well create mismatched pairs, because after generating the
>> keys() return value, the list gets shuffled, prior to generating
>> values() in the same expression. This would not be allowed.
>
> That would be a bug, and an easy one to fix. Every mutation of the dict
> would have to reset the internal flags back to the starting state.

What if there's no mutation, then? Just calling values() and items()
means that the zip of keys and values will make mismatches.

ChrisA

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

#78076

On Fri, 19 Sep 2014 21:56:05 +1000, Chris Angelico wrote:

> On Fri, Sep 19, 2014 at 9:46 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> Chris Angelico wrote:
>>
>>> On Fri, Sep 19, 2014 at 8:59 PM, Steven D'Aprano
>>> <steve+comp.lang.python@pearwood.info> wrote:
>>>> Here's a proof of concept of what would be allowed:
>> [...]
>>> Also, this can't possibly offer the same guarantee. Watch:
>>>
>>> d = MyDict(some_lot_of_items)
>>> d.values(); d.items()
>>> # mutate the dict in whatever way you like pairs = zip(d.keys(),
>>> d.values())
>>>
>>> This might well create mismatched pairs, because after generating the
>>> keys() return value, the list gets shuffled, prior to generating
>>> values() in the same expression. This would not be allowed.
>>
>> That would be a bug, and an easy one to fix. Every mutation of the dict
>> would have to reset the internal flags back to the starting state.
> 
> What if there's no mutation, then? Just calling values() and items()
> means that the zip of keys and values will make mismatches.
> 
> ChrisA

As far as I understand it the order of keys in a dict is not guaranteed
iterating over the same dict twice (without changes) does not have to 
return the keys in the same order.

In my installation of python the order does remain constant unless the 
dict is modified but I am reasonably sure this is just due to 
implementation detail & should not be relied upon.

As simple amateur I may be mistaken.



-- 
"Tell the truth and run."
-- Yugoslav proverb

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web