Pythonic способ проверить, отсортирован ли список или нет
что-то вроде isttimestamps.isSorted() , которое возвращает True или False .
Я хочу ввести список временных меток для некоторых сообщений и проверить, появились ли транзакции в правильном порядке.
21 ответ
На самом деле мы не даем ответ, который ищет аниджхау. Вот один лайнер:
Я бы просто использовал
если это не очень большой список, и в этом случае вы можете создать пользовательскую функцию.
если вы просто собираетесь сортировать его, если он не отсортирован, затем забудьте проверить и отсортировать его.
и не думайте об этом слишком много.
Если вы хотите создать пользовательскую функцию, вы можете сделать что-то вроде
Это будет O (n), если список уже отсортирован (и O (n) в цикле for на этом!), поэтому, если вы не ожидаете, что он не будет отсортирован (и довольно случайным), большая часть время, я бы, просто, просто сортировать список.
Эта форма итератора на 10-15% быстрее, чем при использовании целочисленной индексации:
Прекрасным способом реализации этого является использование функции imap из itertools :
Эта реализация выполняется быстро и работает с любыми итерами.
Я бы сделал это (крадусь от множества ответов здесь [Аарон Стерлинг, Вай Ип Тунг, Сорта от Пола МакГира] и в основном Армин Роначер):
Одна хорошая вещь: вам не нужно понимать вторую итерабельность для серии (в отличие от списка).
Я провел тест , а 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).
UPDATE: Я пересмотрел script, чтобы вы могли запускать его непосредственно в своей собственной системе. В предыдущей версии были ошибки. Кроме того, я добавил как отсортированные, так и несортированные входы.
- Лучше всего для коротких отсортированных списков: 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 является самым быстрым, потому что у него нет слоя косвенности для поиска ключа.
Это похоже на верхний ответ, но мне он нравится, потому что он избегает явной индексации. Предполагая, что ваш список имеет имя lst , вы можете сгенерировать кортежи (item, next_item) из вашего списка с помощью zip :
В Python 3, zip уже возвращает генератор, в Python 2 вы можете использовать itertools.izip для повышения эффективности памяти.
Последний не выполняется, когда вычисляется кортеж (3, 2) .
Бонус: проверка конечных (!) генераторов, которые нельзя индексировать:
Обязательно используйте itertools.izip здесь, если вы используете Python 2, иначе вы бы проиграли цель не создавать списки из генераторов.
Я использую этот однострочный шрифт на основе numpy.diff():
Я действительно не приурочил его к любому другому методу, но я предполагаю его быстрее, чем любой чистый метод Python, особенно для больших n, поскольку цикл в numpy.diff(возможно) выполняется непосредственно в C (n-1 вычитаниях) с последующим сравнением n-1).
Однако вам нужно быть осторожным, если x является неподписанным int, что может привести к бесшумному целочисленному недопущению в numpy.diff(), что приведет к ложному срабатыванию. Здесь изменена версия:
Не очень Pythonic вообще, но нам нужен хотя бы один ответ reduce() , правильно?
Аккумуляторная переменная просто сохраняет это последнее значение, и если какое-либо значение меньше предыдущего значения, то накопитель устанавливается в бесконечность (и, таким образом, будет оставаться бесконечным в конце, так как «предыдущее значение» всегда будет больше, чем текущий).
Хотя я не думаю, что есть гарантия, что встроенный вызов sorted вызывает свою функцию cmp с помощью i+1, i , это похоже на CPython.
Итак, вы можете сделать что-то вроде:
Или этот способ (без каких-либо утверждений → EAFP пошло не так?;-)):
SapphireSun совершенно прав. Вы можете просто использовать lst.sort() . Реализация сортировки Python (TimSort) проверяет, отсортирован ли список. Если so sort() будет завершен в линейном времени. Похоже на Pythonic способ сортировки списка;)
Просто добавьте другой способ (даже если для этого требуется дополнительный модуль): iteration_utilities.all_monotone :
Чтобы проверить порядок DESC:
Существует также параметр strict , если вам нужно строго проверить (если последовательные элементы не должны быть равны) монотонные последовательности.
Это не проблема в вашем случае, но если ваши последовательности содержат значения nan , то некоторые методы будут терпеть неудачу, например, при сортировке:
Обратите внимание, что iteration_utilities.all_monotone работает быстрее по сравнению с другими решениями, упомянутыми здесь специально для несортированных входов (см. ).
Если вам нужен самый быстрый способ для массивов numpy, используйте numba, который, если вы используете conda, должен быть уже установлен
Код будет быстрым, потому что он будет скомпилирован numba
Как отмечено в @aaronsterling, следующее решение является самым коротким и кажется самым быстрым, когда массив отсортирован и не слишком мал: def is_sorted (lst): return (отсортировано (lst) == lst)
Если в большинстве случаев массив не сортируется, было бы желательно использовать решение, которое не сканирует весь массив и возвращает False, как только будет обнаружен несортированный префикс. Следующее — самое быстрое решение, которое я мог найти, это не особенно элегантно:
Используя контрольный показатель Nathan Farrington, это обеспечивает лучшее время исполнения, чем использование отсортированного (lst) во всех случаях, за исключением случаев, когда выполняется в большом отсортированном списке.
Сортировка списка Python
Сортировка данных — одна из самых распространенных задач при работе с Python. Например, вы можете отсортировать список членов команды по именам или список проектов в порядке приоритета.
В этой статье описывается, как сортировать списки в Python .
Python sort() и sorted()
В Python, вы можете сортировать список с помощью встроенного в list.sort() метод или встроенный в sorted() функцию.
Функция sorted() создает новый отсортированный список, а метод list.sort() сортирует список на месте. Если вы хотите сохранить, несортированный список используйте функцию sorted() . Еще одно отличие состоит в том, что функция sorted sorted() работает с любым итерируемым объектом.
Синтаксис sort() и sorted() следующий:
Необязательные ключевые аргументы key и reverse имеют следующее значение:
- key — функция, которая принимает один аргумент и преобразует его перед сравнением. Функция должна возвращать одно значение, которое используется для сравнения сортировки.
- reverse — значение reverse может быть True или False . Значение по умолчанию — True . Если для этого аргумента установлено значение false, список сортируется в обратном порядке.
Элементы списка сравниваются с помощью оператора «меньше чем» ( < ) и сортируются в порядке возрастания. Оператор < не поддерживает сравнение строки с целым числом, поэтому, если у вас есть список, содержащий строки и целые числа, операция сортировки завершится ошибкой.
В следующем примере показано, как отсортировать список строк в алфавитном порядке:
Если вы хотите сохранить исходный список без изменений, используйте функцию sorted() :
Чтобы отсортировать список в обратном (по убыванию) порядке, установите reverse аргумент в True :
Сортировка с функцией
Аргумент key принимает функцию и позволяет выполнять более сложные операции сортировки.
Самый простой пример — отсортировать элементы по их длине:
Мы используем функцию len() чтобы вернуть количество символов в строке, которая используется в качестве компаратора:
Вы также можете создать пользовательскую функцию и использовать ее в качестве key аргумента для сравнения. Вот пример, показывающий, как отсортировать список целых чисел по сумме их цифр:
Другой пример — использование ключевого аргумента для сортировки сложного списка, такого как список кортежей:
Мы используем анонимную (лямбда) функцию, которая возвращает первый элемент кортежа. Список отсортирован по значению, возвращаемому функцией:
Тот же подход можно использовать для сортировки списка словарей:
Лямбда-функция возвращает значение ключа name , которое используется для сравнения:
Лучший и более быстрый способ сортировки сложной функции — использовать функции модуля Оператор . Вот пример:
Функция itemgetter извлекает значение symbol ключа:
Выводы
Мы показали вам, как сортировать списки в Python с помощью метода sort() и функции sorted() .
Если у вас есть какие-либо вопросы или отзывы, не стесняйтесь оставлять комментарии.
Pythonic способ проверить, отсортирован ли список или нет
Что-то вроде isttimestamps.isSorted() , которое возвращает True или False .
Я хочу ввести список временных меток для некоторых сообщений и проверить, отображаются ли транзакции в правильном порядке.
22 ответа
На самом деле мы не даем ответ, который ищет аниджхау. Вот один лайнер:
Поскольку я не вижу эту опцию выше, я добавлю ее ко всем ответам. Позвольте обозначить список l , тогда:
Самый простой способ:
Не совсем Pythonic, но нам нужен хотя бы один ответ reduce() , верно?
Переменная аккумулятора просто хранит это последнее проверенное значение, и, если какое-либо значение меньше предыдущего значения, аккумулятор устанавливается на бесконечность (и, таким образом, все равно будет бесконечностью в конце, поскольку «предыдущее значение» всегда будет больше, чем текущий).
Это похоже на верхний ответ, но мне больше нравится, потому что он избегает явной индексации. Предполагая, что ваш список имеет имя lst , вы можете сгенерировать из своего списка
(item, next_item) кортежей с помощью zip :
В Python 3 zip уже возвращает генератор, в Python 2 вы можете использовать itertools.izip для повышения эффективности памяти.
Последний сбой при оценке кортежа (3, 2) .
Бонус: проверка конечных (!) Генераторов, которые не могут быть проиндексированы:
Убедитесь, что вы используете itertools.izip здесь, если вы используете Python 2, иначе вы бы потерпели поражение от необходимости создавать списки из генераторов.
Полученное значение сокращения представляет собой кортеж из трех частей ( sortedSoFarFlag , firstTimeFlag , lastElementValue ). Первоначально он начинается с ( True , True , None ), который также используется в качестве результата для пустого списка (считается отсортированным, поскольку нет элементов не по порядку) , Обрабатывая каждый элемент, он вычисляет новые значения для кортежа (используя предыдущие значения кортежа со следующим elementValue):
Окончательный результат сокращения — кортеж из:
Первое значение — это то, что нас интересует, поэтому мы используем [0] , чтобы получить это из результата сокращения.
Я бы просто использовал
Если это не очень большой список, в этом случае вы можете захотеть создать пользовательскую функцию.
Если вы просто собираетесь отсортировать его, если он не отсортирован, тогда забудьте о проверке и сортируйте его.
И не думай об этом слишком много.
Если вы хотите пользовательскую функцию, вы можете сделать что-то вроде
Это будет O (n), если список уже отсортирован (и O (n) в цикле for при этом!), Поэтому, если вы не ожидаете, что он не будет отсортирован (и довольно случайен), большая часть время, я бы, опять же, просто отсортировать список.
Хотя я не думаю, что есть гарантия, что встроенная sorted вызовет свою функцию cmp с i+1, i , похоже, она делает это для CPython.
Итак, вы можете сделать что-то вроде:
Или так (без операторов if -> EAFP пошло не так? ;-)):
Определенно работает в Python 3 и выше для целых чисел или строк:
Другой способ узнать, отсортирован ли данный список или нет
Как насчет этого ? Просто и понятно.
Если вы хотите самый быстрый способ для массивов с пустым фрагментом, используйте numba, который, если вы используете conda, уже должен быть установлен
Код будет быстрым, потому что он будет скомпилирован numba
На самом деле это самый короткий способ сделать это с помощью рекурсии:
Если отсортировано, будет напечатано True, иначе будет напечатано False
Решение с использованием выражений присваивания (добавлено в Python 3.8):
SapphireSun совершенно прав. Вы можете просто использовать lst.sort() . Реализация сортировки Python (TimSort) проверяет, отсортирован ли список. В этом случае sort () будет завершен за линейное время. Похоже на Pythonic способ убедиться, что список отсортирован;)
Ленивый
Я использую этот однострочник на основе numpy.diff ():
Я на самом деле не рассчитывал это против любого другого метода, но я предполагаю, что он быстрее, чем любой чистый метод Python, особенно для больших n, поскольку цикл в numpy.diff (вероятно) выполняется непосредственно в C (n-1 вычитаний, за которыми следует n -1 сравнение).
Однако вы должны быть осторожны, если x является беззнаковым целым, что может привести к потере целочисленного значения в numpy.diff (), что приведет к ложному положительному результату. Вот модифицированная версия:
Эта форма итератора на 10-15% быстрее, чем при использовании целочисленной индексации:
Как отмечает @aaronsterling, следующее решение является самым коротким и кажется самым быстрым, когда массив отсортирован и не слишком мал: def is_sorted (lst): return (sorted (lst) == lst)
Если большую часть времени массив не сортируется, было бы желательно использовать решение, которое не сканирует весь массив и возвращает False, как только обнаруживается несортированный префикс. Вот самое быстрое решение, которое я смог найти, оно не особенно элегантно:
Используя эталонный тест Натана Фаррингтона, это обеспечивает лучшее время выполнения, чем использование 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
Прекрасный способ реализовать это — использовать функцию imap из itertools :
Эта реализация быстра и работает на любых итерациях.
Я бы сделал это (крадя здесь множество ответов [Аарон Стерлинг, Вай Ип Тунг, Сорта из Пола МакГир) и в основном Армин Ронахер):
Одна приятная вещь: вам не нужно реализовывать вторую итерацию для серии (в отличие от фрагмента списка).
Просто чтобы добавить другой способ (даже если для этого требуется дополнительный модуль): iteration_utilities.all_monotone :
Чтобы проверить заказ DESC:
Существует также параметр strict , если необходимо строго проверить (если последовательные элементы не должны быть равными) монотонные последовательности.
В вашем случае это не проблема, но , если ваши последовательности содержат значения nan , некоторые методы завершатся неудачно, например, с помощью sorted:
Метод List sort() в Python
Метод List sort() в Python сортирует элементы списка в порядке возрастания.
В Python есть встроенная функция sorted(), которая используется для создания отсортированного списка из итерируемого объекта.
1. Использование метода List sort() по умолчанию
По умолчанию метод list sort() в Python упорядочивает элементы списка в порядке возрастания. Это также естественный способ сортировки элементов.
Элементы также могут быть символами или числами, и метод sort() продолжит сортировку в порядке возрастания.
2. Обратная сортировка списка
Если вы хотите, чтобы сортировка выполнялась в обратном порядке, передайте обратный аргумент, как True. Мы можем использовать это для сортировки списка чисел в порядке убывания.
3. Сортировка вложенного списка
Если мы вызываем функцию списка sort() для вложенного списка, для сортировки используются только первые элементы из элементов списка. Давайте разберемся в этом примере.
Понятно, что сортировка производится по первому элементу вложенного списка. Но иногда нам нужно отсортировать вложенный список по позициям разных элементов.
Допустим, вложенный список содержит информацию об имени, возрасте и поле человека. Давайте посмотрим, как отсортировать этот вложенный список по возрасту, который является вторым элементом вложенного списка.
Мы используем ключевой аргумент, чтобы указать элемент, который будет использоваться для целей сортировки. Функция custom_key возвращает ключ для сортировки списка.
4. Пользовательская логика для сортировки списка
Мы также можем реализовать вашу собственную логику для сортировки элементов списка.
В последнем примере мы использовали возраст как ключевой элемент для сортировки нашего списка.
Но есть такая поговорка: «Сначала дамы!». Итак, мы хотим отсортировать наш список таким образом, чтобы женский пол имел приоритет над мужским. Если пол двух человек совпадает, младший получает более высокий приоритет.
Итак, мы должны использовать ключевой аргумент в нашей функции сортировки. Но функцию сравнения нужно преобразовать в ключ.
Итак, нам нужно импортировать библиотеку под названием functools. Мы будем использовать функцию cmp_to_key(), чтобы преобразовать compare_function в key.
Список сначала сортируется по полу. Затем он сортируется по возрасту людей.
5. Сортировка списка объектов
Сортировка по умолчанию работает с числами и строками. Но это не будет работать со списком настраиваемых объектов. Посмотрим, что произойдет, когда мы попытаемся запустить сортировку по умолчанию для списка объектов.
В этом случае мы должны в обязательном порядке предоставить ключевую функцию для указания поля объектов, которое будет использоваться для сортировки.
Мы также можем использовать модуль functools для создания пользовательской логики сортировки для элементов списка.