¿Hay una manera pitónica de verificar si una lista ya está ordenada ASCoDESC

listtimestamps = [1, 2, 3, 5, 6, 7]

algo así isttimestamps.isSorted()regresa Trueo False.

Quiero ingresar una lista de marcas de tiempo para algunos mensajes y verificar si las transacciones aparecieron en el orden correcto.

En realidad no estamos dando la respuesta que anijhaw está buscando. Aquí está el revestimiento:

all(l[i] <= l[i+1] for i in xrange(len(l)-1))

Para Python 3:

all(l[i] <= l[i+1] for i in range(len(l)-1))

Yo solo usaría

if sorted(lst) == lst:
    # code here

a menos que sea una lista muy grande, en cuyo caso es posible que desee crear una función personalizada.

si solo va a ordenarlo si no está ordenado, entonces olvide el cheque y ordénelo.

lst.sort()

y no lo pienses demasiado.

si quieres una función personalizada, puedes hacer algo como

def is_sorted(lst, key=lambda x: x):
    for i, el in enumerate(lst[1:]):
        if key(el) < key(lst[i]): # i is the index of the previous element
            return False
    return True

Esto será O (n) si la lista ya está ordenada (¡y O (n) en un forciclo!) Así que, a menos que espere que no esté ordenada (y sea bastante aleatoria) la mayor parte del tiempo, lo haría, de nuevo, solo ordena la lista.

Este formulario iterador es 10-15% más rápido que usar la indexación de enteros:

# python2 only
if str is bytes:
    from itertools import izip as zip

def is_sorted(l):
    return all(a <= b for a, b in zip(l, l[1:]))

Una hermosa manera de implementar esto es usar la imapfunción desde itertools:

from itertools import imap, tee
import operator

def is_sorted(iterable, compare=operator.le):
  a, b = tee(iterable)
  next(b, None)
  return all(imap(compare, a, b))

Esta implementación es rápida y funciona en cualquier iterable.

Ejecuté un punto de referencia y sorted(lst, reverse=True) == lstfui el más rápido para listas largas y all(l[i] >= l[i+1] for i in xrange(len(l)-1))el más rápido para listas cortas . Estos puntos de referencia se ejecutaron en un MacBook Pro 2010 13 "(Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5).

ACTUALIZACIÓN: Revisé el script para que pueda ejecutarlo directamente en su propio sistema. La versión anterior tenía errores. Además, he agregado entradas clasificadas y no clasificadas.

Entonces, en la mayoría de los casos hay un claro ganador.

ACTUALIZACIÓN: las respuestas de aaronsterling (# 6 y # 7) son en realidad las más rápidas en todos los casos. # 7 es el más rápido porque no tiene una capa de indirección para buscar la clave.

#!/usr/bin/env python

import itertools
import time

def benchmark(f, *args):
    t1 = time.time()
    for i in xrange(1000000):
        f(*args)
    t2 = time.time()
    return t2-t1

L1 = range(4, 0, -1)
L2 = range(100, 0, -1)
L3 = range(0, 4)
L4 = range(0, 100)

# 1.
def isNonIncreasing(l, key=lambda x,y: x >= y): 
    return all(key(l[i],l[i+1]) for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 2.47253704071
print benchmark(isNonIncreasing, L2) # 34.5398209095
print benchmark(isNonIncreasing, L3) # 2.1916718483
print benchmark(isNonIncreasing, L4) # 2.19576501846

# 2.
def isNonIncreasing(l):
    return all(l[i] >= l[i+1] for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 1.86919999123
print benchmark(isNonIncreasing, L2) # 21.8603689671
print benchmark(isNonIncreasing, L3) # 1.95684289932
print benchmark(isNonIncreasing, L4) # 1.95272517204

# 3.
def isNonIncreasing(l, key=lambda x,y: x >= y): 
    return all(key(a,b) for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.65468883514
print benchmark(isNonIncreasing, L2) # 29.7504849434
print benchmark(isNonIncreasing, L3) # 2.78062295914
print benchmark(isNonIncreasing, L4) # 3.73436689377

# 4.
def isNonIncreasing(l):
    return all(a >= b for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.06947803497
print benchmark(isNonIncreasing, L2) # 15.6351969242
print benchmark(isNonIncreasing, L3) # 2.45671010017
print benchmark(isNonIncreasing, L4) # 3.48461818695

# 5.
def isNonIncreasing(l):
    return sorted(l, reverse=True) == l
print benchmark(isNonIncreasing, L1) # 2.01579380035
print benchmark(isNonIncreasing, L2) # 5.44593787193
print benchmark(isNonIncreasing, L3) # 2.01813793182
print benchmark(isNonIncreasing, L4) # 4.97615599632

# 6.
def isNonIncreasing(l, key=lambda x, y: x >= y): 
    for i, el in enumerate(l[1:]):
        if key(el, l[i-1]):
            return False
    return True
print benchmark(isNonIncreasing, L1) # 1.06842684746
print benchmark(isNonIncreasing, L2) # 1.67291283607
print benchmark(isNonIncreasing, L3) # 1.39491200447
print benchmark(isNonIncreasing, L4) # 1.80557894707

# 7.
def isNonIncreasing(l):
    for i, el in enumerate(l[1:]):
        if el >= l[i-1]:
            return False
    return True
print benchmark(isNonIncreasing, L1) # 0.883186101913
print benchmark(isNonIncreasing, L2) # 1.42852401733
print benchmark(isNonIncreasing, L3) # 1.09229516983
print benchmark(isNonIncreasing, L4) # 1.59502696991

Haría esto (robando muchas respuestas aquí [Aaron Sterling, Wai Yip Tung, más o menos de Paul McGuire] y principalmente Armin Ronacher ):

from itertools import tee, izip

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def is_sorted(iterable, key=lambda a, b: a <= b):
    return all(key(a, b) for a, b in pairwise(iterable))

Una cosa buena: no tiene que darse cuenta del segundo iterable para la serie (a diferencia de un segmento de lista).

Yo uso este one-liner basado en numpy.diff ():

def issorted(x):
    """Check if x is sorted"""
    return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 0?

Realmente no lo he cronometrado con ningún otro método, pero supongo que es más rápido que cualquier método Python puro, especialmente para n grande, ya que el bucle en numpy.diff (probablemente) se ejecuta directamente en C (n-1 sustracciones seguidas de n -1 comparaciones).

Sin embargo, debe tener cuidado si x es un int sin signo, lo que podría causar un flujo de entero entero silencioso en numpy.diff (), lo que da como resultado un falso positivo. Aquí hay una versión modificada:

def issorted(x):
    """Check if x is sorted"""
    try:
        if x.dtype.kind == 'u':
            # x is unsigned int array, risk of int underflow in np.diff
            x = numpy.int64(x)
    except AttributeError:
        pass # no dtype, not an array
    return (numpy.diff(x) >= 0).all()

Esto es similar a la respuesta principal, pero me gusta más porque evita la indexación explícita. Suponiendo que su lista tenga el nombre lst, puede generar
(item, next_item)tuplas a partir de su lista con zip:

all(x <= y for x,y in zip(lst, lst[1:]))

En Python 3, zipya devuelve un generador, en Python 2 puede usar itertools.izippara una mejor eficiencia de memoria.

Pequeña demostración:

>>> lst = [1, 2, 3, 4]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 4)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
True
>>> 
>>> lst = [1, 2, 3, 2]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 2)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
False

El último falla cuando (3, 2)se evalúa la tupla .

Bonificación: comprobación de generadores finitos (!) Que no pueden indexarse:

>>> def gen1():
...     yield 1
...     yield 2
...     yield 3
...     yield 4
...     
>>> def gen2():
...     yield 1
...     yield 2
...     yield 4
...     yield 3
... 
>>> g1_1 = gen1()
>>> g1_2 = gen1()
>>> next(g1_2)
1
>>> all(x <= y for x,y in zip(g1_1, g1_2))
True
>>>
>>> g2_1 = gen2()
>>> g2_2 = gen2()
>>> next(g2_2)
1
>>> all(x <= y for x,y in zip(g2_1, g2_2))
False

Asegúrate de usar itertools.izipaquí si estás usando Python 2, de lo contrario anularías el propósito de no tener que crear listas a partir de los generadores.

SapphireSun tiene toda la razón. Solo puedes usar lst.sort(). La implementación de clasificación de Python (TimSort) verifica si la lista ya está ordenada. Si es así, sort () se completará en tiempo lineal. Suena como una forma pitónica para asegurar que una lista esté ordenada;)

Aunque no creo que haya una garantía de que la función sortedincorporada llame a su función cmp i+1, i, parece que lo hace para CPython.

Entonces podrías hacer algo como:

def my_cmp(x, y):
   cmpval = cmp(x, y)
   if cmpval < 0:
      raise ValueError
   return cmpval

def is_sorted(lst):
   try:
      sorted(lst, cmp=my_cmp)
      return True
   except ValueError:
      return False

print is_sorted([1,2,3,5,6,7])
print is_sorted([1,2,5,3,6,7])

O de esta manera (sin declaraciones if -> EAFP salió mal? ;-)):

def my_cmp(x, y):
   assert(x >= y)
   return -1

def is_sorted(lst):
   try:
      sorted(lst, cmp=my_cmp)
      return True
   except AssertionError:
      return False

No es muy pitónico, pero necesitamos al menos una reduce()respuesta, ¿verdad?

def is_sorted(iterable):
    prev_or_inf = lambda prev, i: i if prev <= i else float('inf')
    return reduce(prev_or_inf, iterable, float('-inf')) < float('inf')

La variable del acumulador simplemente almacena el último valor verificado, y si algún valor es menor que el valor anterior, el acumulador se establece en infinito (y, por lo tanto, seguirá siendo infinito al final, ya que el 'valor anterior' siempre será mayor que el actual).

Como señaló @aaronsterling, la siguiente solución es la más corta y parece más rápida cuando la matriz está ordenada y no es demasiado pequeña: def is_sorted (lst): return (sorted (lst) == lst)

Si la mayoría de las veces la matriz no está ordenada, sería deseable usar una solución que no escanee la matriz completa y devuelva False tan pronto como se descubra un prefijo no ordenado. La siguiente es la solución más rápida que pude encontrar, no es particularmente elegante:

def is_sorted(lst):
    it = iter(lst)
    try:
        prev = it.next()
    except StopIteration:
        return True
    for x in it:
        if prev > x:
            return False
        prev = x
    return True

Usando el punto de referencia de Nathan Farrington, esto logra un mejor tiempo de ejecución que usar sorted (lst) en todos los casos, excepto cuando se ejecuta en la lista ordenada grande.

Aquí están los resultados de referencia en mi computadora.

sorted (lst) == lst solution

• L1: 1.23838591576
• L2: 4.19063091278
• L3: 1.17996287346
• L4: 4.68399500847

Segunda solución:

• L1: 0.81095790863
• L2: 0.802397012711
• L3: 1.06135106087
• L4: 8.82761001587

Si desea la forma más rápida para matrices numpy, use numba , que si usa conda ya debería estar instalado

El código será rápido porque será compilado por numba

import numba
@numba.jit
def issorted(vec, ascending=True):
    if len(vec) < 2:
        return True
    if ascending:
        for i in range(1, len(vec)):
            if vec[i-1] > vec[i]:
                return False
        return True
    else:
        for i in range(1, len(vec)):
            if vec[i-1] < vec[i]:
                return False
        return True

y entonces:

>>> issorted(array([4,9,100]))
>>> True

Solo para agregar otra forma (incluso si requiere un módulo adicional) iteration_utilities.all_monotone::

>>> from iteration_utilities import all_monotone
>>> listtimestamps = [1, 2, 3, 5, 6, 7]
>>> all_monotone(listtimestamps)
True

>>> all_monotone([1,2,1])
False

Para verificar el pedido DESC:

>>> all_monotone(listtimestamps, decreasing=True)
False

>>> all_monotone([3,2,1], decreasing=True)
True

También hay un strictparámetro si necesita verificar estrictamente (si los elementos sucesivos no deben ser iguales) secuencias monotónicas.

No es un problema en su caso, pero si sus secuencias contienen nanvalores, algunos métodos fallarán, por ejemplo con sorted:

def is_sorted_using_sorted(iterable):
    return sorted(iterable) == iterable

>>> is_sorted_using_sorted([3, float('nan'), 1])  # definetly False, right?
True

>>> all_monotone([3, float('nan'), 1])
False

Tenga en cuenta que iteration_utilities.all_monotonefunciona más rápido en comparación con las otras soluciones mencionadas aquí, especialmente para las entradas no ordenadas (ver punto de referencia ).

Perezoso

from itertools import tee

def is_sorted(l):
    l1, l2 = tee(l)
    next(l2, None)
    return all(a <= b for a, b in zip(l1, l2))

Python 3.6.8

from more_itertools import pairwise

class AssertionHelper:
    @classmethod
    def is_ascending(cls, data: iter) -> bool:
        for a, b in pairwise(data):
            if a > b:
                return False
        return True

    @classmethod
    def is_descending(cls, data: iter) -> bool:
        for a, b in pairwise(data):
            if a < b:
                return False
        return True

    @classmethod
    def is_sorted(cls, data: iter) -> bool:
        return cls.is_ascending(data) or cls.is_descending(data)

>>> AssertionHelper.is_descending((1, 2, 3, 4))
False
>>> AssertionHelper.is_ascending((1, 2, 3, 4))
True
>>> AssertionHelper.is_sorted((1, 2, 3, 4))
True

La forma más simple:

def isSorted(arr):
  i = 1
  while i < len(arr):
    if(result[i] < result[i - 1]):
      return False
    i += 1
  return True

from functools import reduce

# myiterable can be of any iterable type (including list)
isSorted = reduce(lambda r, e: (r[0] and (r[1] or r[2] <= e), False, e), myiterable, (True, True, None))[0]

El valor de reducción derivado es una tupla de 3 partes de ( sortedSoFarFlag , firstTimeFlag , lastElementValue ). En un primer momento se inicia con ( True, True, None), que también se utiliza como el resultado de una lista vacía (considerado como ordenados, porque no hay elementos fuera de la orden). A medida que procesa cada elemento, calcula nuevos valores para la tupla (utilizando valores de tupla anteriores con el siguiente elementValue):

[0] (sortedSoFarFlag) evaluates true if: prev_0 is true and (prev_1 is true or prev_2 <= elementValue)
[1] (firstTimeFlag): False
[2] (lastElementValue): elementValue

El resultado final de la reducción es una tupla de:

[0]: True/False depending on whether the entire list was in sorted order
[1]: True/False depending on whether the list was empty
[2]: the last element value

El primer valor es el que nos interesa, por lo que usamos [0]para obtenerlo del resultado de reducción.

Como no veo esta opción arriba, la agregaré a todas las respuestas. Deje denotar la lista por l, entonces:

import numpy as np

# Trasform the list to a numpy array
x = np.array(l)

# check if ascendent sorted:
all(x[:-1] <= x[1:])

# check if descendent sorted:
all(x[:-1] >= x[1:])

Una solución que usa expresiones de asignación (agregadas en Python 3.8):

def is_sorted(seq):
    seq_iter = iter(seq)
    cur = next(seq_iter, None)
    return all((prev := cur) <= (cur := nxt) for nxt in seq_iter)

z = list(range(10))
print(z)
print(is_sorted(z))

import random
random.shuffle(z)
print(z)
print(is_sorted(z))

z = []
print(z)
print(is_sorted(z))

Da:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
True
[1, 7, 5, 9, 4, 0, 8, 3, 2, 6]
False
[]
True

De hecho, esta es la forma más corta de hacerlo utilizando la recursividad:

si está ordenado se imprimirá Verdadero, de lo contrario se imprimirá Falso

 def is_Sorted(lst):
    if len(lst) == 1:
       return True
    return lst[0] <= lst[1] and is_Sorted(lst[1:])

 any_list = [1,2,3,4]
 print is_Sorted(any_list)

Que tal este ? Simple y directo.

def is_list_sorted(al):

    llength =len(al)


    for i in range (llength):
        if (al[i-1] > al[i]):
            print(al[i])
            print(al[i+1])
            print('Not sorted')
            return -1

    else :
        print('sorted')
        return  true

Definitivamente funciona en Python 3 y superior para enteros o cadenas:

def tail(t):
    return t[:]

letters = ['a', 'b', 'c', 'd', 'e']
rest = tail(letters)
rest.sort()
if letters == rest:
    print ('Given list is SORTED.')
else:
    print ('List NOT Sorted.')

================================================== ===================

Otra forma de encontrar si la lista dada está ordenada o no

trees1 = list ([1, 4, 5, 3, 2])
trees2 = list (trees1)
trees2.sort()
if trees1 == trees2:
    print ('trees1 is SORTED')
else:
    print ('Not sorted')