6
\$\begingroup\$

Is the trade-off between simplicity and performance worth it?

def is_sorted(list_):
    """
    Is the list sorted?

    The simpler `list_ == list(sorted(list_))` has
    time complexity O(N log N), this O(n).

    >>> is_sorted([1, 2, 3])
    True
    >>> is_sorted([1, 2, 7, 3])
    False
    """
    return all(curr <= list_[index + 1]
                  for index, curr in enumerate(list_[:-1]))
\$\endgroup\$
  • \$\begingroup\$ I think you'd have to be dealing with a lot of large, mostly-already-sorted lists to beat the cost of calling the function and making a copy of the list (the slice, another O(n)). You can't determine if it's worth it a priori. \$\endgroup\$ – jonrsharpe Jun 22 '15 at 17:57
  • \$\begingroup\$ @jonrsharpe interesting, so this function may be slower than the alternative despite the time-complexity... this is what I get when I don't benchmark. :) \$\endgroup\$ – Caridorc Jun 22 '15 at 17:58
  • \$\begingroup\$ Well, maybe. O(2n) is still O(n), after all. But there are fixed costs to consider too. \$\endgroup\$ – jonrsharpe Jun 22 '15 at 18:01
  • 2
    \$\begingroup\$ "pythonic way to check if a list is sorted or not": stackoverflow.com/questions/3755136/… \$\endgroup\$ – Steve Jessop Jun 22 '15 at 20:22
6
\$\begingroup\$

In my opinion the cleanest way to do this is with itertools.tee. It basically makes an arbitrary number of copies of iterators. This avoids having to make a copy of the list (which any slice-based approach would do), avoids having to do any math or indexing, and works on arbitrary iterables, not just lists.

try:
    itertools.izip as zip
except ImportError:
    pass
from itertools import tee

def issorted(mylist):
    if not mylist:
        return True
    list1, list2 = tee(mylist)  # make two copies of the list's iterator
    next(list2)  # advance one copy one element
    return all(a<=b for a, b in zip(list1, list2))
\$\endgroup\$
  • \$\begingroup\$ Instead of tee you could use the builtin iter in a similar way: list2 = iter(mylist); next(list2) \$\endgroup\$ – Janne Karila Jun 23 '15 at 5:44
  • \$\begingroup\$ Yes, if you are sure you will only ever have certain types. Assuming the data type isn't really idiomatic, though. \$\endgroup\$ – TheBlackCat Jun 23 '15 at 6:43
7
\$\begingroup\$

This can be written much more simply with izip from itertools. This removes having to fiddle with indices that enumerate gives back. Of course, it should probably also have a check for an list of length 0 or 1 as well.

return all(x <= y for x, y in izip(list, list[1:]))

Edit: The problem with built-in zip for Python 2 is that it will completely construct the list again in memory, which will kill performance for a large list. If you really want code that's portable between both Python 2 and 3, I'd suggest something like:

try:
    from itertools import izip
except ImportError:
    izip = zip
\$\endgroup\$
  • \$\begingroup\$ No need for a special case, it already works for zero and one elements. \$\endgroup\$ – Caridorc Jun 22 '15 at 18:45
  • \$\begingroup\$ By the way, I would avoid Python-2 only methods, in Python-3: >>> from itertools import izip Traceback (most recent call last): File "<pyshell#0>", line 1, in <module> from itertools import izip ImportError: cannot import name 'izip' the built-in zip seems the only choice. \$\endgroup\$ – Caridorc Jun 22 '15 at 18:46
  • 3
    \$\begingroup\$ You should islice as well, to avoid the creation of a list copy. \$\endgroup\$ – jonrsharpe Jun 22 '15 at 19:30
  • \$\begingroup\$ @jonrsharpe Yep, that'd also be a good idea... \$\endgroup\$ – Yuushi Jun 22 '15 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.