Гарантируется ли стабильность функции sorted() в python?

документация не гарантирует этого. Есть ли другое место, где это задокументировано?

Я предполагаю, что это может быть стабильно, поскольку метод сортировки в списках гарантированно быть стабильным (Примечание 9-й пункт: «Начиная с Python 2.3, метод sort() гарантированно будет стабильным»), и sorted функционально аналогичен. Тем не менее, я не могу найти какой-либо окончательный источник, который говорит об этом.

Цель: мне нужно отсортировать на основе первичного ключа, а также вторичного ключа в случаях, когда первичный ключ равен в обеих записях. Если sorted() гарантированно стабильна, я могу отсортировать по вторичному ключу, затем отсортировать по первичному ключу и получить нужный мне результат.

PS: Чтобы избежать путаницы, я использую стабильный в том смысле, что «сортировка является стабильной, если она гарантирует, что относительный порядок элементов, сравниваемых равными», не изменится.


python stable-sort sorted
person sundar - Remember Monica    schedule 16.12.2009    source источник

Ответы (5)


arrow_upward
140
arrow_downward

Да, цель руководства действительно состоит в том, чтобы гарантировать, что sorted стабилен и действительно использует тот же алгоритм, что и метод sort. Я понимаю, что документы не на 100% ясны в отношении этой личности; doc патчи всегда принимаются с радостью!

person Alex Martelli    schedule 16.12.2009
comment
Я обнаружил, что если я сортирую кортежи или списки, всякий раз, когда первичные ключи сортировки равны, сортировка заканчивается вторичным ключом. Например, sorted([(1, 2), (1, 1)]) возвращает [(1, 1), (1, 2)] вместо возврата исходного ввода в той же последовательности/порядке. Разве гарантия стабильности не должна означать, что он должен возвращать исходный ввод [(1, 2), (1, 1)]? В этом случае вы должны быть откровенны и сказать sorted([(1, 2), (1, 1)], key=lambda t: t[0]) - person code_dredd; 01.09.2017
comment
Разве это не то, что ожидается в этом случае? Python по умолчанию будет сравнивать кортежи по всем элементам, а не только по первому первичному. Если вы хотите отсортировать только первый элемент, вы можете явно указать параметр key. - person Matias Grioni; 30.11.2017
comment
@code_dredd это ожидаемое поведение. Точка стабильной сортировки — это сортировка с использованием ключа сортировки, но два разных элемента с одинаковым ключом сортировки будут в одном и том же порядке. Ключ сортировки по умолчанию для кортежа — это все элементы кортежа. - person Guy; 05.11.2018

arrow_upward
32
arrow_downward

Они стабильны.

Кстати: иногда можно не знать, стабильны ли sort и sorted, комбинируя многопроходную сортировку в однопроходной.

Например, если вы хотите отсортировать объекты по их атрибутам last_name, first_name, вы можете сделать это за один проход:

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

используя сравнение кортежей.

Этот ответ, как есть, охватывает исходный вопрос. Ответы на дополнительные вопросы, связанные с сортировкой, см. в инструкции по сортировке Python.

person tzot    schedule 28.12.2009
comment
Это может иметь нежелательный эффект, если вы хотите изменить сортировку на противоположную. Например, при сортировке товаров вы можете сначала отсортировать по рейтингу (по возрастанию), а затем по цене (также по возрастанию). Если вы измените это, вы хотите отсортировать по рейтингу в порядке убывания, но по цене в порядке возрастания. Это не работает с этим решением. - person Remco Wendt; 08.03.2012
comment
@RemcoWendt: то, что вы описываете, не требовалось. В любом случае рассмотрите вариант key= lambda item: (-item.rating, item.price) или аргумент cmp вместо аргумента key. Однако я все еще не уверен в цели вашего комментария. - person tzot; 09.03.2012
comment
На самом деле это не было требованием, но я хотел указать на эту тонкую разницу, когда другие люди прочитают это и сделают выбор между вашим решением или использованием функции стабильной сортировки Python. - person Remco Wendt; 13.03.2012
comment
Понимаю. Другими словами, сортировка по парам понятнее и поэтому предпочтительнее, если только вы не заботитесь о производительности. Я полагаю, что две стабильные сортировки несколько быстрее, чем одна сортировка по парам, хотя разница может быть незначительной - ? - person Sergey Orshanskiy; 03.12.2013
comment
@tzot Я хочу отметить, что всегда есть такие требования для стабильной сортировки. Например, у меня есть список кортежей (рейтинг, комментарий), комментарии сохраняются в порядке их создания, и я хочу отсортировать по рейтингу и сохранить временной порядок, однако я не сохранил метка времени в списке. Короче говоря, я просто хочу отсортировать список по рейтингу и сохранить комментарии в том же порядке. - person wsysuper; 07.04.2015
comment
Документация 3.6 по сортировке прямо говорит вам, что стабильность — замечательное свойство, и дает пример сложной сортировки. Поэтому я прошу не согласиться с этим ответом на не нужно знать. Кодирование информации в индексном порядке, как упоминает @wsysuper, также распространено и требует стабильности. - person Wolfgang Kuehn; 11.06.2018

arrow_upward
4
arrow_downward

За это время изменилась документация (соответствующая фиксация) и текущая документация sorted явно гарантирует это:

Встроенная функция sorted() гарантированно работает стабильно. Сортировка является стабильной, если она гарантирует неизменный относительный порядок элементов, которые сравниваются равными — это полезно для сортировки в несколько проходов (например, сортировка по отделам, а затем по уровням заработной платы).

Эта часть документации была добавлена ​​в Python 2.7 и Python 3.4(+), поэтому любая совместимая реализация этой языковой версии должна иметь стабильную версию sorted.

Обратите внимание, что для CPython list.sort был стабильным, начиная с Python 2.3.

  • Тим Питерс переписал свою реализацию list.sort() — это «стабильная сортировка» (одинаковые входные данные появляются в том же порядке на выходе) и быстрее, чем раньше.

Я не уверен на 100% в sorted, в настоящее время он просто использует list.sort, но я не проверял историю на предмет этого. Но вполне вероятно, что он «всегда» использовал list.sort.

person MSeifert    schedule 16.05.2017

arrow_upward
2
arrow_downward

В документе Python 3.6 по сортировке теперь говорится, что

Сорта гарантированно стабильны

Кроме того, в этом документе есть ссылка на стабильный Timsort, в котором говорится, что

Timsort является стандартным алгоритмом сортировки Python, начиная с версии 2.3.

person Wolfgang Kuehn    schedule 11.06.2018

arrow_upward
0
arrow_downward

В документах "Что нового" для Python 2.4 эффективно подчеркивается, что sorted( ) сначала создает список, а затем вызывает для него sort(), предоставляя вам необходимую гарантию, хотя и не в «официальных» документах. Вы также можете просто проверить источник, если вы действительно обеспокоены.

person Peter Hansen    schedule 16.12.2009
comment
Не могли бы вы указать, где это сказано? В нем говорится, что sorted() работает так же, как list.sort() на месте, и вновь сформированная копия сортируется, но я не вижу, чтобы в нем говорилось, что он внутри использует sort(). - person sundar - Remember Monica; 16.12.2009
comment
Сформированная копия представляет собой список (это то, что вы получаете в качестве возвращаемого значения), и .sort() вызывается для этого списка перед возвратом. КЭД. Нет, это не неопровержимое доказательство, но пока у Python нет официального стандарта, вы его не получите. - person Peter Hansen; 16.12.2009