Apakah ada cara pythonic untuk memeriksa apakah daftar sudah diurutkan dalam ASCatauDESC

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

sesuatu seperti isttimestamps.isSorted() itu kembali Trueatau False.

Saya ingin memasukkan daftar cap waktu untuk beberapa pesan dan memeriksa apakah transaksi muncul dalam urutan yang benar.

Sebenarnya kami tidak memberikan jawaban yang dicari oleh anijhaw. Inilah satu-satunya liner:

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

Untuk Python 3:

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

Saya hanya akan menggunakan

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

kecuali itu daftar yang sangat besar dalam hal ini Anda mungkin ingin membuat fungsi kustom.

jika Anda hanya akan mengurutkannya jika tidak diurutkan, lupakan tanda centang dan urutkan.

lst.sort()

dan jangan terlalu memikirkannya.

jika Anda menginginkan fungsi khusus, Anda dapat melakukan sesuatu seperti

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

Ini akan menjadi O (n) jika daftar sudah diurutkan (dan O (n) dalam satu forlingkaran pada saat itu!) Jadi, kecuali Anda mengharapkannya tidak diurutkan (dan cukup acak) sebagian besar waktu, saya akan, sekali lagi, cukup urutkan daftar.

Bentuk iterator ini 10-15% lebih cepat daripada menggunakan pengindeksan bilangan bulat:

# 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:]))

Cara yang indah untuk mengimplementasikan ini adalah dengan menggunakan imapfungsi dari 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))

Implementasi ini cepat dan bekerja pada semua iterables.

Saya menjalankan tolok ukur dan sorted(lst, reverse=True) == lsttercepat untuk daftar panjang, dan all(l[i] >= l[i+1] for i in xrange(len(l)-1))tercepat untuk daftar pendek . Benchmark ini dijalankan pada MacBook Pro 2010 13 "(Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5).

UPDATE: Saya merevisi skrip sehingga Anda dapat menjalankannya langsung di sistem Anda sendiri. Versi sebelumnya memiliki bug. Juga, saya telah menambahkan input yang diurutkan dan yang tidak disortir.

Jadi dalam banyak kasus ada pemenang yang jelas.

UPDATE: jawaban aaronsterling (# 6 dan # 7) sebenarnya yang tercepat dalam semua kasus. # 7 adalah yang tercepat karena tidak memiliki lapisan tipuan untuk mencari kunci.

#!/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

Saya akan melakukan ini (mencuri dari banyak jawaban di sini [Aaron Sterling, Wai Yip Tung, agak dari Paul McGuire] dan sebagian besar 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))

Satu hal yang menyenangkan: Anda tidak perlu menyadari iterable kedua untuk seri (tidak seperti dengan slice daftar).

Saya menggunakan one-liner ini berdasarkan numpy.diff ():

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

Saya belum benar-benar menghitung waktunya terhadap metode lain, tapi saya menganggap itu lebih cepat daripada metode Python murni, terutama untuk n besar, karena loop di numpy.diff (mungkin) berjalan langsung di C (n-1 pengurangan diikuti oleh n -1 perbandingan).

Namun, Anda perlu berhati-hati jika x adalah int unsigned, yang dapat menyebabkan underflow integer diam di numpy.diff (), menghasilkan false positive. Ini versi modifikasi:

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()

Ini mirip dengan jawaban teratas, tapi saya suka lebih baik karena menghindari pengindeksan eksplisit. Dengan asumsi daftar Anda memiliki nama lst, Anda dapat membuat
(item, next_item)tupel dari daftar Anda dengan zip:

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

Di Python 3, zipsudah mengembalikan generator, di Python 2 Anda dapat menggunakan itertools.izipuntuk efisiensi memori yang lebih baik.

Demo kecil:

>>> 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

Yang terakhir gagal ketika tuple (3, 2)dievaluasi.

Bonus: memeriksa generator yang terbatas (!) Yang tidak dapat diindeks:

>>> 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

Pastikan untuk menggunakan di itertools.izipsini jika Anda menggunakan Python 2, jika tidak, Anda akan mengalahkan tujuan tidak harus membuat daftar dari generator.

SapphireSun benar. Anda bisa menggunakannya lst.sort(). Implementasi semacam Python (TimSort) memeriksa apakah daftar sudah diurutkan. Jika demikian sort () akan selesai dalam waktu linier. Kedengarannya seperti cara Pythonic untuk memastikan daftar diurutkan;)

Meskipun saya tidak berpikir ada jaminan untuk itu sortedbuilt-in memanggil fungsi CMP-nya i+1, i, sepertinya memang demikian untuk CPython.

Jadi Anda bisa melakukan sesuatu seperti:

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])

Atau dengan cara ini (tanpa pernyataan if -> EAFP salah? ;-)):

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

Sama sekali tidak Pythonic, tetapi kita membutuhkan setidaknya satu reduce()jawaban, kan?

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')

Variabel akumulator hanya menyimpan nilai yang terakhir diperiksa, dan jika ada nilai yang lebih kecil dari nilai sebelumnya, akumulator diatur hingga tak terhingga (dan dengan demikian akan tetap tak terhingga pada akhirnya, karena 'nilai sebelumnya' akan selalu lebih besar daripada yang sekarang).

Seperti dicatat oleh @aaronsterling solusi berikut adalah yang terpendek dan tampaknya tercepat ketika array diurutkan dan tidak terlalu kecil: def is_sorted (lst): return (diurutkan (lst) == lst)

Jika sebagian besar waktu array tidak diurutkan, itu akan diinginkan untuk menggunakan solusi yang tidak memindai seluruh array dan mengembalikan False segera setelah awalan yang tidak disortir ditemukan. Berikut ini adalah solusi tercepat yang bisa saya temukan, tidak terlalu elegan:

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

Menggunakan tolok ukur Nathan Farrington, ini menghasilkan runtime yang lebih baik daripada menggunakan diurutkan (pertama) dalam semua kasus kecuali ketika berjalan pada daftar besar yang diurutkan.

Ini adalah hasil benchmark di komputer saya.

diurutkan (pertama) == solusi pertama

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

Solusi kedua:

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

Jika Anda menginginkan cara tercepat untuk numpy array, gunakan numba , yang jika Anda menggunakan conda harus sudah diinstal

Kode akan cepat karena akan dikompilasi oleh 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

lalu:

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

Hanya dengan menambahkan cara lain (walaupun itu membutuhkan modul tambahan) 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

Untuk memeriksa pesanan DESC:

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

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

Ada juga strictparameter jika Anda perlu memeriksa secara ketat (jika elemen berturut-turut tidak boleh sama) urutan monoton.

Ini bukan masalah dalam kasus Anda tetapi jika urutan Anda berisi nannilai maka beberapa metode akan gagal, misalnya dengan diurutkan:

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

Perhatikan bahwa iteration_utilities.all_monotonekinerjanya lebih cepat dibandingkan dengan solusi lain yang disebutkan di sini terutama untuk input yang tidak disortir (lihat benchmark ).

Malas

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

Cara termudah:

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]

Nilai reduksi yang diturunkan adalah 3 bagian tupel ( diurutkanSoFarFlag , firstTimeFlag , lastElementValue ). Ini awalnya dimulai dengan ( True, True, None), yang juga digunakan sebagai hasil untuk daftar kosong (dianggap sebagai diurutkan karena tidak ada out-of-order elemen). Saat memproses setiap elemen, ia menghitung nilai baru untuk tuple (menggunakan nilai tuple sebelumnya dengan elementValue berikutnya):

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

Hasil akhir dari reduksi adalah tuple dari:

[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

Nilai pertama adalah yang kami minati, jadi kami gunakan [0]untuk mengambilnya dari hasil pengurangan.

Karena saya tidak melihat opsi ini di atas, saya akan menambahkannya ke semua jawaban. Biarkan tandai daftar dengan l, lalu:

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:])

Solusi menggunakan ekspresi penugasan (ditambahkan dengan 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))

Memberi:

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

Ini sebenarnya cara terpendek untuk melakukannya menggunakan rekursi:

jika itu Diurutkan akan mencetak Benar yang lain akan mencetak Salah

 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)

Bagaimana dengan yang ini ? Sederhana dan mudah.

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

Jelas berfungsi di Python 3 dan di atasnya untuk bilangan bulat atau string:

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.')

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

Cara lain untuk menemukan apakah daftar yang diberikan diurutkan atau tidak

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