목록이 정렬되었는지 여부를 확인하는 Pythonic 방법

목록이 정렬되었는지 여부를 확인하는 Pythonic 방법

목록이 이미 정렬되었는지 확인하는 파이썬적인 방법이 있습니까?ASC또는DESC

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

같은 것isttimestamps.isSorted()그것이 돌아오는 것True또는False.

일부 메시지에 대한 타임스탬프 목록을 입력하고 트랜잭션이 올바른 순서로 표시되었는지 확인하고 싶습니다.

다음은 하나의 라이너입니다.

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

2를 Python 2를 합니다.xrange에 range.

위해서reverse=True,사용하다>=에 <=.

저는 그냥.

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

사용자 정의 함수를 생성할 수 있는 매우 큰 목록이 아닌 경우.

정렬되지 않은 경우 정렬하려면 체크를 잊고 정렬합니다.

lst.sort()

그리고 너무 많이 생각하지 마세요.

만약 당신이 사용자 정의 기능을 원한다면, 당신은 다음과 같은 것을 할 수 있습니다.

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

되어 있으면 O가 O(n)가 for반복!) 그래서, 대부분의 경우 정렬되지 않을 것으로 예상하지 않는 한, 다시 한번, 목록을 정렬할 것입니다.

이 반복기 양식은 정수 인덱싱을 사용하는 것보다 10-15% 더 빠릅니다.

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

이를 구현하는 아름다운 방법은 다음을 사용하는 것입니다.imap에서 합니다.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))

이 구현은 빠르고 반복 가능한 모든 항목에서 작동합니다.

저는 이것을 할 것입니다. (여기 [Aaron Sterling, Wai Yip Tung, Paul McGuire의 소르타] 많은 답변을 훔치고 대부분 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))

한 가지 좋은 점은 (목록 조각과 달리) 시리즈의 두 번째 반복 가능성을 인식할 필요가 없다는 것입니다.

벤치마크를 실행했습니다. 그리고 sorted(lst, reverse=True) == lst 긴 목록에서 가장 빨랐고, 그리고. all(l[i] >= l[i+1] for i in xrange(len(l)-1)) 최종 후보 목록에서 가장 빨랐습니다. 이러한 벤치마크는 MacBook Pro 2010 13"(Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5)에서 실행되었습니다.

업데이트: 사용자 시스템에서 직접 실행할 수 있도록 스크립트를 수정했습니다.이전 버전에는 버그가 있었습니다.또한 정렬된 입력과 정렬되지 않은 입력을 모두 추가했습니다.

• 목록에 : 짧게정목가장적합에:all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 목록에 : 긴정목 에가적합장:sorted(l, reverse=True) == l
• 되지 않은 목록에 합니다.all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 되지 않은 긴 목록에 합니다.all(l[i] >= l[i+1] for i in xrange(len(l)-1))

그래서 대부분의 경우에는 확실한 승자가 있습니다.

업데이트: 아론스터링의 답변(#6 및 #7)은 실제로 모든 경우에서 가장 빠릅니다.#7은 키를 조회할 수 있는 간접 레이어가 없기 때문에 가장 빠릅니다.

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

위에 이 옵션이 표시되지 않으므로 모든 답변에 추가합니다.을 목을다음표다니시합로으로 요.l그러면:

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

에서 시작Python 3.10새로운 함수는 연속적인 요소의 쌍을 슬라이드하여 이들 쌍이 모두 동일한 순서의 술어를 충족하는지 확인하는 방법을 제공합니다.

from itertools import pairwise

all(x <= y for x, y in pairwise([1, 2, 3, 5, 6, 7]))
# True

---

중간 .pairwise:

pairwise([1, 2, 3, 5, 6, 7])
# [(1, 2), (2, 3), (3, 5), (5, 6), (6, 7)]

나는 numpy.diff()를 기반으로 이 하나의 라이너를 사용합니다.

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

다른 방법과 비교해 본 적은 없지만, 특히 큰 n의 경우, numpy.diff의 루프가 C에서 직접 실행되기 때문에 순수한 파이썬 방법보다 빠르다고 생각합니다(n-1 감산 후 n-1 비교).

그러나 x가 부호 없는 int인 경우 numpy.diff()에서 무음 정수 언더플로를 발생시켜 잘못된 양수를 발생시킬 수 있으므로 주의해야 합니다.다음은 수정된 버전입니다.

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

이것은 상위 답변과 비슷하지만 명시적인 인덱싱을 피해서 더 좋습니다.이 목에이름있가다다정니합고이록다▁your▁name▁the▁has▁assuming니라고 가정합니다.lst할 수 있습니다.
(item, next_item)당신의 리스트에 있는 튜플들.zip:

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

에서 파썬에 3서이는zip합니다. 에서는 이미제반환다니합을 할 수 있습니다. 파이썬 2에서 사용할 수 있습니다.itertools.izip더 나은 메모리 효율성을 위해.

소규모 데모:

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

이 실패할 때 실패합니다.(3, 2)평가됩니다.

보너스: 인덱싱할 수 없는 유한(!) 생성기 확인:

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

반드시 사용하십시오.itertools.izip여기서 Python 2를 사용하는 경우, 그렇지 않으면 생성자로부터 목록을 만들지 않아도 된다는 목적을 달성하지 못할 것입니다.

비록 그것에 대한 보장이 없다고 생각하지만,sorted로 호출합니다.i+1, i그것은 Cython에게 그렇게 하는 것처럼 보입니다.

따라서 다음과 같은 작업을 수행할 수 있습니다.

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

아니면 이런 식으로 (만약 진술이 없다면 -> EAFP가 잘못되었습니까? ;-):

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

게으른

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

타사 패키지 방법은 아직 언급되지 않았습니다.

import more_itertools

ls = [1, 4, 2]

print(more_itertools.is_sorted(ls))

ls2 = ["ab", "c", "def"]

print(more_itertools.is_sorted(ls2, key=len))

@filensterling이 지적한 바와 같이, 다음 솔루션은 배열이 정렬될 때 가장 짧고, 너무 작지 않은 것처럼 보입니다. defis_filename(lst): 반환(lst) == lst

대부분의 경우 배열이 정렬되지 않으면 전체 배열을 검색하지 않고 정렬되지 않은 접두사가 발견되는 즉시 False를 반환하는 솔루션을 사용하는 것이 좋습니다.다음은 제가 찾을 수 있는 가장 빠른 해결책입니다. 특별히 우아하지는 않습니다.

def is_sorted(lst):
    it = iter(lst)
    try:
        prev = next(it)
    except StopIteration:
        return True
    for x in it:
        if prev > x:  # For reverse, use <
            return False
        prev = x
    return True

Nathan Farrington의 벤치마크를 사용하면 대규모 정렬 목록에서 실행되는 경우를 제외한 모든 경우에서 정렬(lst)을 사용하는 것보다 런타임이 향상됩니다.

여기 제 컴퓨터의 벤치마크 결과가 있습니다.

sorted(lst)==lst 솔루션

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

두 번째 솔루션:

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

다른 방법을 추가하기 위해(추가 모듈이 필요하더라도):

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

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

DESC 순서 확인하기

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

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

또한 다음이 있습니다.strict연속적인 요소가 동일하지 않아야 하는 경우 단조 시퀀스를 엄격하게 확인해야 하는 경우 매개변수를 선택합니다.

당신의 경우에는 문제가 없지만 당신의 시퀀스에nan값을 지정하면 정렬된 경우와 같이 일부 메서드가 실패합니다.

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

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

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

이는 특히 정렬되지 않은 입력에 대해 여기에 언급된 다른 솔루션에 비해 성능이 더 빠릅니다(벤치마크 참조).

파이썬적이지는 않지만 적어도 하나는 필요해요reduce()정답이죠?

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

누산기 변수는 마지막으로 확인한 값만 저장하며, 이전 값보다 작은 값이 있으면 누산기가 무한대로 설정됩니다(따라서 '이전 값'이 항상 현재 값보다 크기 때문에 끝에도 무한대가 됩니다).

Sapphire Sun의 말이 맞습니다.그냥 사용할 수 있습니다.lst.sort()Python의 정렬 구현(TimSort)은 목록이 이미 정렬되었는지 확인합니다.그렇다면 정렬()은 선형 시간 내에 완료됩니다.목록이 정렬되도록 하는 Pythonic 방법처럼 들립니다 ;)

파이썬 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

할당 표현식을 사용하는 솔루션(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))

제공:

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

판다를 이용한 이 접근법은 매우 느리지만, 완성도가 높은 것으로 알려져 있습니다.

from typing import Sequence

import pandas as pd

def is_sorted(seq: Sequence, reverse: bool = False) -> bool:
    index = pd.Index(seq)
    if reverse:
        return index.is_monotonic_decreasing
    return index.is_monotonic_increasing

numpy 배열을 위한 가장 빠른 방법을 원한다면 numba를 사용하십시오. 만약 당신이 conda를 사용한다면 이미 설치되어 있어야 합니다.

코드는 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

다음과 같은 경우:

>>> issorted(array([4,9,100]))
>>> 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]

파생된 감소 값은 (SoFarFlag, firstTimeFlag, lastElementValue로 정렬됨)의 3분할 튜플입니다.처음에는 다음으로 시작합니다.True,True,None목록의 됩니다. 됨), 빈 목 순 대 결 사 도 로 용 됩 니 다 않 요 없 정 가 때 렬 에 문 기 됨 regarded 소 는 맞 지 가 서 과 한 에 록 순 ▁), ▁which regarded ▁( 렬각 요소를 처리할 때 다음 요소 값과 함께 이전 튜플 값을 사용하여 튜플의 새 값을 계산합니다.

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

감소의 최종 결과는 다음과 같습니다.

[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

번째 있는 에 첫번째가우관심있가는다니치입리가치는▁is다▁use▁the니가를 사용합니다. 그래서 우리는 사용합니다.[0]감소 결과로부터 그것을 파악하는 것.

이것은 재귀를 사용합니다.

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

 some_list = [1,2,3,4]
 print(is_sorted(some_list))

이것은 상승할 것입니다.RuntimeError: maximum recursion depth exceeded긴 순서로

사용해 보십시오.

def is_sorted(arr) -> bool:
    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            return False
    return True

이것은 어떻습니까? 간단하고 간단합니다.

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

가장 간단한 방법:

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

정수 또는 문자열에 대해 Python 3 이상에서 확실히 작동합니다.

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

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

지정된 목록이 정렬되었는지 여부를 찾는 다른 방법

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

언급URL : https://stackoverflow.com/questions/3755136/pythonic-way-to-check-if-a-list-is-sorted-or-not