Есть ли питонный способ проверить, отсортирован ли уже список ASC
илиDESC
listtimestamps = [1, 2, 3, 5, 6, 7]
что-то подобное isttimestamps.isSorted()
возвращается True
илиFalse
.
Я хочу ввести список временных меток для некоторых сообщений и проверить, отображаются ли транзакции в правильном порядке.
key
функцию для использования.key=lambda x, y: x < y
делает хороший дефолт.def isSorted(x, key = lambda x: x): return all([key(x[i]) <= key(x[i + 1]) for i in xrange(len(x) - 1)])
operator.le
должно быть быстрее, чем лямбда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
xrange
, просто используйтеrange
. Я получаю,NameError: name 'xrange' is not defined
когда я запускаю этот код. Я переключил его просто использоватьrange
вместо,xrange
и это прекрасно работает. См .: stackoverflow.com/questions/15014310/…Я бы просто использовал
если это не очень большой список, в этом случае вы можете захотеть создать пользовательскую функцию.
если вы просто собираетесь отсортировать его, если он не отсортирован, тогда забудьте о проверке и сортируйте его.
и не думай об этом слишком много.
если вы хотите пользовательскую функцию, вы можете сделать что-то вроде
Это будет O (n), если список уже отсортирован (и O (n) в
for
цикле!), Так что, если вы не ожидаете, что он не будет отсортирован (и довольно случайен) большую часть времени, я бы, опять же, просто отсортировать список.источник
Эта форма итератора на 10-15% быстрее, чем при использовании целочисленной индексации:
источник
izip
иislice
из itertools, чтобы сделать это быстрее.Прекрасный способ реализовать это - использовать
imap
функцию изitertools
:Эта реализация быстра и работает на любых итерациях.
источник
is_sorted(iter([1,2,3,2,5,8]))
или эквивалентный генератор. Вам нужно использовать независимый итератор дляtail
, попробуйтеitertools.tee
.iter(x) is x
для итераторовitertools.imap
был переименован в[__builtins__.]map
.Я проводил тестирование
и. Эти тесты были выполнены на MacBook Pro 2010 13 "(Core2 Duo 2,66 ГГц, 4 ГБ 1067 МГц DDR3 RAM, Mac OS X 10.6.5).sorted(lst, reverse=True) == lst
был самым быстрым для длинных списков, и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))
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 самый быстрый, потому что он не имеет слоя косвенности для поиска ключа.
источник
enumerate
неверны.enumerate(l[1:])
следует заменить наenumerate(l[1:], 1)
enumerate(l[1:])
наenumerate(l[1:], 1)
вас могли бы заменитьl[i-1]
наl[i]
.L5=range(100); random.shuffle(L5)
то # 5 будет сравнительно медленным. В этом случае измененная # 7 быстрее всего codepad.org/xmWPxHQYЯ бы сделал это (крадя здесь множество ответов [Аарон Стерлинг, Вай Ип Тунг, Сорта из Пола МакГуайра] и в основном Армин Ронахер ):
Одна приятная вещь: вам не нужно реализовывать вторую итерацию для серии (в отличие от списка фрагментов).
источник
key
.key
следует использовать для превращения предметов в сопоставимые значения.Я использую этот однострочник на основе numpy.diff ():
Я на самом деле не рассчитывал это против любого другого метода, но я предполагаю, что он быстрее, чем любой чистый метод Python, особенно для больших n, поскольку цикл в numpy.diff (возможно) выполняется непосредственно в C (n-1 вычитаний, за которыми следует n -1 сравнение).
Однако вы должны быть осторожны, если x - это беззнаковое целое, что может привести к потере целочисленного значения в numpy.diff (), что приведет к ложному положительному результату. Вот модифицированная версия:
источник
Это похоже на верхний ответ, но мне больше нравится, потому что он избегает явной индексации. Предполагая, что у вашего списка есть имя
lst
, вы можете генерировать(item, next_item)
кортежи из вашего списка с помощьюzip
:В Python 3
zip
уже возвращается генератор, в Python 2 вы можете использоватьitertools.izip
для большей эффективности памяти.Небольшая демонстрация:
Последний сбой при оценке кортежа
(3, 2)
.Бонус: проверка конечных (!) Генераторов, которые не могут быть проиндексированы:
Обязательно используйте
itertools.izip
здесь, если вы используете Python 2, в противном случае вы бы победили цель не создавать списки из генераторов.источник
islice
для оптимизации нарезки. Также в модуле itertools.all(x <= y for x, y in izip(lst, islice(lst, 1)))
,SapphireSun совершенно прав. Вы можете просто использовать
lst.sort()
. Реализация сортировки Python (TimSort) проверяет, отсортирован ли список. В этом случае sort () будет завершен за линейное время. Похоже на Pythonic способ убедиться, что список отсортирован;)источник
Хотя я не думаю, что есть гарантия, что
sorted
встроенная программа вызовет свою функцию cmp сi+1, i
, похоже, она делает это для CPython.Таким образом, вы могли бы сделать что-то вроде:
Или так (без операторов if -> EAFP пошло не так? ;-)):
источник
Не совсем Pythonic, но нам нужен хотя бы один
reduce()
ответ, верно?Переменная аккумулятора просто хранит это последнее проверенное значение, и, если какое-либо значение меньше предыдущего значения, аккумулятор устанавливается на бесконечность (и, таким образом, все равно будет бесконечностью в конце, поскольку «предыдущее значение» всегда будет больше, чем текущий).
источник
Как отмечает @aaronsterling, следующее решение является самым коротким и кажется самым быстрым, когда массив отсортирован и не слишком мал: def is_sorted (lst): return (sorted (lst) == lst)
Если большую часть времени массив не сортируется, было бы желательно использовать решение, которое не сканирует весь массив и возвращает False, как только обнаруживается несортированный префикс. Вот самое быстрое решение, которое я смог найти, оно не особенно элегантно:
Используя эталонный тест Натана Фаррингтона, это обеспечивает лучшее время выполнения, чем использование sorted (lst) во всех случаях, кроме случаев, когда выполняется большой отсортированный список.
Вот результаты тестов на моем компьютере.
отсортировано (lst) == lst решение
Второе решение:
источник
Если вы хотите самый быстрый способ для массивов numpy, используйте numba , который, если вы используете conda, должен быть уже установлен
Код будет быстрым, потому что он будет скомпилирован numba
а потом:
источник
Просто чтобы добавить другой способ (даже если для этого требуется дополнительный модуль)
iteration_utilities.all_monotone
:Чтобы проверить заказ DESC:
Существует также
strict
параметр, если вам нужно проверять строго (если последовательные элементы не должны быть равными) монотонные последовательности.Это не проблема в вашем случае, но если ваши последовательности содержат
nan
значения, то некоторые методы потерпят неудачу, например с sorted:Обратите внимание, что
iteration_utilities.all_monotone
работает быстрее по сравнению с другими решениями, упомянутыми здесь, особенно для несортированных входных данных (см. Бенчмарк ).источник
ленивый
источник
all(a <= b for a, b in zip(l, l[1:]))
l
это генератор, и не поддерживает нарезку.Python 3.6.8
источник
Самый простой способ:
источник
Полученное значение сокращения представляет собой кортеж из 3 частей ( sortedSoFarFlag , firstTimeFlag , lastElementValue ). Первоначально она начинается с (
True
,True
,None
), который также используются в качестве результата для пустого списка (считаются отсортировано , потому что нет испорченных элементов). Обрабатывая каждый элемент, он вычисляет новые значения для кортежа (используя предыдущие значения кортежа со следующим elementValue):Окончательный результат сокращения - кортеж из:
Первое значение - это то, что нас интересует, поэтому мы используем его
[0]
для получения результата сокращения.источник
Поскольку я не вижу эту опцию выше, я добавлю ее ко всем ответам. Позвольте обозначить список через
l
, то:источник
Решение с использованием выражений присваивания (добавлено в Python 3.8):
дает:
источник
На самом деле это самый короткий способ сделать это с помощью рекурсии:
если отсортировано, будет напечатано True, иначе будет напечатано False
источник
RuntimeError: maximum recursion depth exceeded
для длинных списков. Попробуйany_list = range(1000)
.Как насчет этого ? Просто и понятно.
источник
Определенно работает в Python 3 и выше для целых чисел или строк:
================================================== ===================
Другой способ узнать, отсортирован ли данный список или нет
источник