python - listas - sorting a list
Manera pitónica de verificar si una lista está ordenada o no (18)
Esta es, de hecho, la forma más sencilla de hacerlo mediante recursión:
si se ordena, se imprimirá Verdadero, 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)
¿Hay alguna manera pitónica de verificar si una lista ya está ordenada en ASC o DESC
listtimestamps = [1, 2, 3, 5, 6, 7]
algo como isttimestamps.isSorted() que devuelve True o False .
Quiero ingresar una lista de marcas de tiempo para algunos mensajes y verificar si las transacciones aparecieron en el orden correcto.
Perezoso
def is_sorted(l):
l2 = iter(l)
next(l2, None)
return all(a <= b for a, b in zip(l, l2))
Aunque no creo que haya una garantía de que el built-in sorted llama a su función cmp con 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
Como señala @aaronsterling, la siguiente solución es la más corta y parece más rápida cuando el arreglo está ordenado y no es demasiado pequeño: def is_sorted (lst): return (sorted (lst) == lst)
Si la mayoría de las veces el conjunto no está ordenado, sería deseable usar una solución que no escanee todo el conjunto y devuelva False tan pronto como se descubra un prefijo sin clasificar. 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
Al utilizar el punto de referencia de Nathan Farrington, se logra un mejor tiempo de ejecución que utilizando el ordenado (lst) en todos los casos, excepto cuando se ejecuta en la lista clasificada grande.
Estos son los resultados de referencia en mi computadora.
solucionado (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
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'')
Ejecuté un punto de referencia y . Estos puntos de referencia se ejecutaron en una MacBook Pro 2010 13 "(Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5). sorted(lst, reverse=True) == lst fue el más rápido para listas largas, y all(l[i] >= l[i+1] for i in xrange(len(l)-1)) fue el más rápido para listas cortas
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 ordenadas y no ordenadas.
- Lo mejor para listas ordenadas cortas:
all(l[i] >= l[i+1] for i in xrange(len(l)-1)) - Lo mejor para largas listas ordenadas:
sorted(l, reverse=True) == l - Lo mejor para listas cortas sin clasificar:
all(l[i] >= l[i+1] for i in xrange(len(l)-1)) - Lo mejor para largas listas sin clasificar:
all(l[i] >= l[i+1] for i in xrange(len(l)-1))
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
En realidad, no estamos dando la respuesta que anijhaw está buscando. Aquí está el trazador de líneas:
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))
Este formulario de iterador es 10-15% más rápido que el uso de índices enteros:
# from itertools import izip as zip # python 2 only!
def is_sorted(l):
return all(a <= b for a, b in zip(l, l[1:]))
Esto es similar a la respuesta principal, pero me gusta más porque evita la indexación explícita. Suponiendo que su lista tiene el nombre lst , puede generar
(item, next_item) tuplas de tu lista con zip :
all(x <= y for x,y in zip(lst, lst[1:]))
En Python 3, zip ya devuelve un generador, en Python 2 puede usar itertools.izip para una mejor eficacia de la 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 se evalúa la tupla (3, 2) .
Bonificación: verificar generadores finitos (!) Que no pueden ser indexados:
>>> 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 utilizar itertools.izip aquí si estás usando Python 2, de lo contrario, evitarías el propósito de no tener que crear listas de los generadores.
Haría esto (robando un montón de respuestas aquí [Aaron Sterling, Wai Yip Tung, sorta de Paul McGuire] y sobre todo 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 tienes que darte cuenta de la segunda iterable de la serie (a diferencia de una porción de la lista).
No es muy pitónico en absoluto, pero necesitamos al menos una respuesta de reduce() , ¿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 ese último valor comprobado, y si cualquier valor es menor que el valor anterior, el acumulador se establece en infinito (y así seguirá siendo infinito al final, ya que el ''valor anterior'' siempre será más grande que el actual).
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
Si quieres la forma más rápida para las matrices numpy, usa numba , que si usas 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 orden de DESC:
>>> all_monotone(listtimestamps, decreasing=True)
False
>>> all_monotone([3,2,1], decreasing=True)
True
También hay un parámetro strict si necesita verificar estrictamente (si los sucesivos elementos no deberían ser iguales) las secuencias monótonas.
No es un problema en su caso, pero si sus secuencias contienen valores nan , algunos métodos fallarán, por ejemplo, con los ordenados:
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_monotone comporta más rápido en comparación con las otras soluciones mencionadas aquí, especialmente para las entradas no ordenadas (ver benchmark ).
Una forma hermosa de implementar esto es usar la función imap de 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.
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, olvídese del cheque y oriéntelo.
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
Esta será O (n) si la lista ya está ordenada (¡y O (n) en un bucle for !) Entonces, a menos que esperes que no esté ordenada (y bastante aleatoria) la mayor parte del tiempo, lo haría , de nuevo, solo ordena la 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 contra ningún otro método, pero supongo que es más rápido que cualquier método de Python puro, especialmente para n grande, ya que el ciclo en numpy.diff (probablemente) se ejecuta directamente en C (resta n-1 seguida de n -1 comparaciones).
Sin embargo, debe tener cuidado si x es un int sin firmar, lo que podría causar un subdesbordamiento del entero silencioso en numpy.diff (), dando 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()
SapphireSun tiene toda la razón. Puedes simplemente 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 manera Pythonic para asegurar que una lista esté ordenada;)