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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

Эта форма итератора на 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:]))

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

Не совсем 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')

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