Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 18 Sep 2014 09:32:15 -0500
From: Tim Chase <python.list@tim.thechases.com>
To: Roy Smith <roy@panix.com>
Subject: Re: Is there a canonical way to check whether an iterable is ordered?
In-Reply-To: <roy-E21095.08580518092014@news.panix.com>
References: <efcc61e6-f132-4f14-80b5-0536816b6c7b@googlegroups.com> <mailman.14101.1411042251.18130.python-list@python.org> <roy-E21095.08580518092014@news.panix.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.14111.1411059441.18130.python-list@python.org>
Lines: 46
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python: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