Подходящие для Python способ проверить, если список отсортирован или нет


есть ли подходящие для Python способ проверить, если список уже отсортирован в ASC или DESC

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

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

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

19 102

19 ответов:

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

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

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

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) в A 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, l[1:]))

красивый способ реализовать это-использовать

Я бы сделал это (кража из многих ответов здесь [Аарон Стерлинг, Wai Yip Tung, sorta от пола Макгуайра] и в основном Армин Ронахер):

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

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

обновление: ответы 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])

или таким образом (без 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

не очень подходящие для Python, но нам нужен хотя бы один 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')

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

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

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, что может привести к беззвучному целочисленному underflow в 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) is оцененный.

бонус: проверка конечного (!) генераторы, которые не могут быть проиндексированы:

>>> 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, иначе вы бы победили цель не создавать списки из генераторов.

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

Как отметил @aaronsterling следующее решение является самым коротким и кажется самым быстрым, когда массив отсортирован и не слишком мал: деф Отсортировано(ЛСТ): возвращение (отсортированный(ЛСТ) == ЛСТ)

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

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

есть еще и

лень

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

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

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

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

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

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

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