Pythonic способ проверить, отсортирован ли список или нет

145

Есть ли питонный способ проверить, отсортирован ли уже список ASCилиDESC

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

что-то подобное isttimestamps.isSorted()возвращается TrueилиFalse .

Я хочу ввести список временных меток для некоторых сообщений и проверить, отображаются ли транзакции в правильном порядке.

anijhaw
источник

Ответы:

212

На самом деле мы не даем ответ, который ищет аниджхау. Вот один лайнер:

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

Для Python 3:

all(l[i] <= l[i+1] for i in range(len(l)-1))
Вай Ип Тунг
источник
2
это мило. Возможно, вы захотите обернуть его в функцию, чтобы вы могли передать keyфункцию для использования. key=lambda x, y: x < yделает хороший дефолт.
Ааронастерлинг
3
Комбинированная пару решений:def isSorted(x, key = lambda x: x): return all([key(x[i]) <= key(x[i + 1]) for i in xrange(len(x) - 1)])
eacousineau
2
@aaronasterling: operator.leдолжно быть быстрее, чем лямбда
Мариан
Это не работает для меня (python --version = 2.6.4) l = [1, 2, 3, 4, 1, 6, 7, 8, 7] all(l[i] <= l[i+1] for i in xrange(len(l)-1)) print как результат:True
prodev_paris
1
Похоже, Python 3.x больше не имеет xrange, просто используйте range. Я получаю, NameError: name 'xrange' is not definedкогда я запускаю этот код. Я переключил его просто использовать rangeвместо, xrangeи это прекрасно работает. См .: stackoverflow.com/questions/15014310/…
Кейл Суини
78

Я бы просто использовал

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 (n), если список уже отсортирован (и O (n) в forцикле!), Так что, если вы не ожидаете, что он не будет отсортирован (и довольно случайен) большую часть времени, я бы, опять же, просто отсортировать список.

aaronasterling
источник
10
Если это то, что вы собираетесь делать, вы можете просто сказать: lst.sort () без условной проверки ;-)
SapphireSun
5
То есть, в O (n) явно более быстрый путь с использованием простого цикла for.
Anijhaw
1
@SapphireSun. Вот что я сказал;)
Ааронастерлинг
@anijhaw, посмотрите обновление, которое я сделал, когда вы оставляли комментарий. проверка - O (n), а сортировка - O (nlgn). Лучше взять O (n) стоимость, чтобы просто развернуться и добавить O (nlgn) или просто взять стоимость сортировки отсортированного списка, который (я полагаю) O (n) для timsort.
Ааронастерлинг
@ Аарон: Проверьте Править к первоначальному вопросу,
anijhaw
44

Эта форма итератора на 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:]))
PaulMcG
источник
Я не вижу существенных различий в моей машине gist.github.com/735259 Модифицированный вариант № 7 от ответа @Nathan Farrington в 2 раза быстрее stackoverflow.com/questions/3755136/…
jfs
Это будет работать только для «индексируемых» контейнеров, таких как список, и в этом случае два новых списка создаются с разрезанием. Для общих итераторов я предпочитаю решение Александра .
Бас Суинкельс
1
Элегантный ответ, вы можете использовать izipи isliceиз itertools, чтобы сделать это быстрее.
Elmex80s
@jfs: «# 7 вариант от Натана Фаррингтона» неправильный. он просто не делает то, что должен, и поэтому он быстрее. см мой комментарий там.
olivecoder
1
Вы можете упростить свое решение для zip (l, l [1:]), потому что zip останавливается, когда исчерпан самый короткий аргумент
Gelineau
20

Прекрасный способ реализовать это - использовать 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))

Эта реализация быстра и работает на любых итерациях.

Александр Вассалотти
источник
4
Хорошо, но глючит! Примерьте is_sorted(iter([1,2,3,2,5,8]))или эквивалентный генератор. Вам нужно использовать независимый итератор для tail, попробуйте itertools.tee.
Кос
Помните, что iter(x) is xдля итераторов
Кос
1
Ах, это неприятный сюрприз! Я исправил это сейчас. Спасибо!
Александр Вассалотти
3
Обратите внимание, что в Python 3 itertools.imapбыл переименован в [__builtins__.]map.
Ник Т
10

Я проводил тестирование и 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,66 ГГц, 4 ГБ 1067 МГц 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))

Так что в большинстве случаев есть явный победитель.

ОБНОВЛЕНИЕ: ответы aaronsterling (№ 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
Натан Фаррингтон
источник
1
Вы тестируете, тестируете худший вариант для форм выражения генератора и лучший вариант для моего решения. Вы можете также проверить несортированный список. Тогда вы увидите, что, если вы не ожидаете, что список будет отсортирован большую часть времени, выражение генератора лучше.
Ааронастерлинг
@aaronsterling, я обновил скрипт, чтобы иметь как отсортированные, так и несортированные входные данные.
Натан Фаррингтон
Все функции с enumerateневерны. enumerate(l[1:])следует заменить наenumerate(l[1:], 1)
JFS
1
вместо того , чтобы заменить enumerate(l[1:])на enumerate(l[1:], 1)вас могли бы заменить l[i-1]на l[i].
JFS
Если вы добавите случайный ввод, например, L5=range(100); random.shuffle(L5)то # 5 будет сравнительно медленным. В этом случае измененная # 7 быстрее всего codepad.org/xmWPxHQY
jfs
9

Я бы сделал это (крадя здесь множество ответов [Аарон Стерлинг, Вай Ип Тунг, Сорта из Пола МакГуайра] и в основном Армин Ронахер ):

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

Одна приятная вещь: вам не нужно реализовывать вторую итерацию для серии (в отличие от списка фрагментов).

hughdbrown
источник
2
вводящее в заблуждение имя key. keyследует использовать для превращения предметов в сопоставимые значения.
InQβ
4

Я использую этот однострочник на основе numpy.diff ():

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

Я на самом деле не рассчитывал это против любого другого метода, но я предполагаю, что он быстрее, чем любой чистый метод Python, особенно для больших n, поскольку цикл в numpy.diff (возможно) выполняется непосредственно в C (n-1 вычитаний, за которыми следует n -1 сравнение).

Однако вы должны быть осторожны, если x - это беззнаковое целое, что может привести к потере целочисленного значения в 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()
Мартин Спейсек
источник
4

Это похоже на верхний ответ, но мне больше нравится, потому что он избегает явной индексации. Предполагая, что у вашего списка есть имя lst, вы можете генерировать
(item, next_item)кортежи из вашего списка с помощью zip:

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

В Python 3 zipуже возвращается генератор, в Python 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, в противном случае вы бы победили цель не создавать списки из генераторов.

timgeb
источник
2
Вы даже можете использовать isliceдля оптимизации нарезки. Также в модуле itertools. all(x <= y for x, y in izip(lst, islice(lst, 1))),
Elmex80s
3

SapphireSun совершенно прав. Вы можете просто использовать lst.sort(). Реализация сортировки Python (TimSort) проверяет, отсортирован ли список. В этом случае sort () будет завершен за линейное время. Похоже на Pythonic способ убедиться, что список отсортирован;)

Вай Ип Тунг
источник
20
Только линейное время, если список, по сути, отсортирован. Если нет, то нет короткого замыкания, чтобы пропустить реальную задачу сортировки, поэтому может быть огромный штраф, если список длинный.
PaulMcG,
Это отличный ответ, если ваша задача «убедиться, что список отсортирован и умереть, если нет». Что довольно часто встречается при проверке работоспособности данных, которые должны быть отсортированы по какой-то другой причине. Тогда только случай ошибки медленный.
Эд Авис
3

Хотя я не думаю, что есть гарантия, что sortedвстроенная программа вызовет свою функцию cmp сi+1, i , похоже, она делает это для CPython.

Таким образом, вы могли бы сделать что-то вроде:

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

Или так (без операторов if -> 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
Энтон
источник
3

Не совсем Pythonic, но нам нужен хотя бы один 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')

Переменная аккумулятора просто хранит это последнее проверенное значение, и, если какое-либо значение меньше предыдущего значения, аккумулятор устанавливается на бесконечность (и, таким образом, все равно будет бесконечностью в конце, поскольку «предыдущее значение» всегда будет больше, чем текущий).

orlade
источник
2

Как отмечает @aaronsterling, следующее решение является самым коротким и кажется самым быстрым, когда массив отсортирован и не слишком мал: def is_sorted (lst): return (sorted (lst) == lst)

Если большую часть времени массив не сортируется, было бы желательно использовать решение, которое не сканирует весь массив и возвращает False, как только обнаруживается несортированный префикс. Вот самое быстрое решение, которое я смог найти, оно не особенно элегантно:

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

Используя эталонный тест Натана Фаррингтона, это обеспечивает лучшее время выполнения, чем использование sorted (lst) во всех случаях, кроме случаев, когда выполняется большой отсортированный список.

Вот результаты тестов на моем компьютере.

отсортировано (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
Амит Москович
источник
2

Если вы хотите самый быстрый способ для массивов 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
тал
источник
2

Просто чтобы добавить другой способ (даже если для этого требуется дополнительный модуль) 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

Чтобы проверить заказ DESC:

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

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

Существует также strictпараметр, если вам нужно проверять строго (если последовательные элементы не должны быть равными) монотонные последовательности.

Это не проблема в вашем случае, но если ваши последовательности содержат nanзначения, то некоторые методы потерпят неудачу, например с 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

Обратите внимание, что iteration_utilities.all_monotoneработает быстрее по сравнению с другими решениями, упомянутыми здесь, особенно для несортированных входных данных (см. Бенчмарк ).

MSeifert
источник
2

ленивый

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))
Sergey11g
источник
1
Абсолютно потрясающе! Вот мое улучшение, чтобы сделать его однострочным - вместо iter () и next () используйте нарезку с одинаковым результатом:all(a <= b for a, b in zip(l, l[1:]))
Matt
1
@LiborJelinek хорошо, но моя версия работает, когда lэто генератор, и не поддерживает нарезку.
Sergey11g
2

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
Чвенг Мега
источник
0

Самый простой способ:

def isSorted(arr):
  i = 1
  while i < len(arr):
    if(result[i] < result[i - 1]):
      return False
    i += 1
  return True
Aluis92
источник
0
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]

Полученное значение сокращения представляет собой кортеж из 3 частей ( sortedSoFarFlag , firstTimeFlag , lastElementValue ). Первоначально она начинается с ( True, True, None), который также используются в качестве результата для пустого списка (считаются отсортировано , потому что нет испорченных элементов). Обрабатывая каждый элемент, он вычисляет новые значения для кортежа (используя предыдущие значения кортежа со следующим 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

Окончательный результат сокращения - кортеж из:

[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

Первое значение - это то, что нас интересует, поэтому мы используем его [0]для получения результата сокращения.

Мистер Уизель
источник
Обратите внимание, что это решение работает для любых итерируемых типов элементов, которые можно сравнивать друг с другом. Это включает в себя списки логических значений (проверяет, что ложные значения встречаются перед значениями True), списки чисел, списки строк (в алфавитном порядке), списки множеств (подмножества встречаются перед надмножествами) и т. Д.
Mr Weasel
0

Поскольку я не вижу эту опцию выше, я добавлю ее ко всем ответам. Позвольте обозначить список через 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:])
FBruzzesi
источник
0

Решение с использованием выражений присваивания (добавлено в 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
PaulMcG
источник
-1

На самом деле это самый короткий способ сделать это с помощью рекурсии:

если отсортировано, будет напечатано True, иначе будет напечатано False

 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)
Baraa
источник
Обратите внимание, что это поднимет RuntimeError: maximum recursion depth exceededдля длинных списков. Попробуй any_list = range(1000).
Timgeb
-1

Как насчет этого ? Просто и понятно.

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
Цукерберг
источник
-3

Определенно работает в 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')
cooldeal
источник