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

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

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

что-то вроде isttimestamps.isSorted() которое возвращает True или False .

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

17 Solutions collect form web for “Pythonic способ проверить, отсортирован ли список или нет.”

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

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

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

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

Эта форма итератора на 10-15% выше, чем при использовании целочисленного индексации:

 # from itertools import izip as zip # python 2 only! def is_sorted(l): return all(a <= b for a, b in zip(l[:-1], 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)) 

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

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

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

Хотя я не думаю, что есть гарантия, что 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]) 

Или так (без каких-либо утверждений -> 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 

Совсем не очень 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') 

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

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

Как отмечено в @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 

С помощью теста Натана Фаррингтона это обеспечивает лучшее время исполнения, чем использование отсортированного (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

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

Это похоже на верхний ответ, но мне он нравится, потому что он избегает явной индексации. Предполагая, что ваш список имеет имя 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, иначе вы itertools.izip цель не создавать списки из генераторов.

ленивый

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

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

если оно Сортировано, будет напечатано True else распечатает 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) 

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

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

 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 работает быстрее по сравнению с другими решениями, упомянутыми здесь, особенно для несортированных входов (см. Сравнительный тест ).

Определенно работает в 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') 
  • Как вы присоединяетесь ко всем элементам в списке в python
  • Эффективная альтернатива "в"
  • Использование Loop для добавления объектов в список (python)
  • Tuple () в GenExp и ListComp
  • Сгладить список списков
  • Как создать двух циклов для представления в python
  • Создать список с номерами, получающими больше каждый раз Python
  • Сортировка подсписок элементов в списке, оставляющий остальное на месте
  •  
    Interesting Posts for Van-Lav

    Где установлен скрипт pyvenv в Python 3 на Windows?

    Как ограничить размер файла журнала в python

    Нарезка массива NumPy 2d или как извлечь подматрицу mxm из массива nxn (n> m)?

    У вас есть предложения для этой сборной мнемоники?

    Случайность в Jython

    «Ошибка значения: сообщение« Смешение итерации и чтение методов потеряет данные »при извлечении чисел из строки из .txt-файла с помощью python

    Идиоматический способ принятия мер по попытке петли над пустой итерируемой

    Среди MATLAB и Python, какой из них хорош для статистического анализа?

    Как вызвать функцию задержки задачи сельдерея из языков, отличных от python, таких как Java?

    Используя Python, найдите анаграммы для списка слов

    Caffe: Как получить параметры `solver.prototxt` по коду?

    Вложенные петли, использующие понимание списков

    Группировка констант в python

    Можно ли использовать Python с php

    Python: мышление модуля и его переменных как одноэлементный подход – чистый подход?

    Python - лучший язык программирования в мире.