Сортировка в Python 3

[timeau]

Здорово, отцы!
Ситуация довольно необычная: не могу врубиться в идеологию сортировки на этом, мягко скажем, странном языке. Конкретно говорю о sorted(), еще конкретнее - о custom функции сортировки в этом sorted(...,key=myfunc). То есть на вопрос "как" мне ответили, меня интересует "зачем так?"
Подробнее.
В привычных мне языках программирования функция сортировки возвращает троичный флаг, если так можно выразиться: -1 or 0 or 1. Фсё! Просто и понятно. Саму функцию языка (не мою! стандартную!) не интересует структура моих данных: только флаг. Но в Python 3 предлагается возвращать значение, которое и будет сортироваться.
Простой пример: мне надо отсортировать даты, состоящие из дня, месяца и года. Я понимаю, что пример притянут за уши, чисто для пояснения идеи. Мне предлагается вернуть что-то такое, что и будет отсортировано, например, в терминах Perl,

Code: Select all

return sprintf("%s%s%s",$year,$month,$day)

И я вынужден формировать такую строку каждый раз, вместо тривиальных трех (в худшем случае!) опрераторов "if"
Если же объекты более сложные, то мне снова придется генерить некие промежуточные строки (или числа) только для сортировки.
Вот объясните мне, ради бога, зачем это надо было делать? Что этим вообще достигли как в идедологическом, так и в техническом плане?
Или я чего-то не догоняю? В общем, заранее благодарен.

P.S. Я уже не задаю вопрос, какому идиоту пришло в голову вместо списка ключей хэша (словаря) возвращать iterator. Что этим достигли? Ничего более разумного, чем экономия памяти, в голову не приходит.

P.P.S. Нэнавижю!

[Alexander Troyansky]

Здорово, отцы!
Ситуация довольно необычная: не могу врубиться в идеологию сортировки на этом, мягко скажем, странном языке. Конкретно говорю о sorted(), еще конкретнее - о custom функции сортировки в этом sorted(...,key=myfunc). То есть на вопрос "как" мне ответили, меня интересует "зачем так?"
Подробнее.
В привычных мне языках программирования функция сортировки возвращает троичный флаг, если так можно выразиться: -1 or 0 or 1. Фсё! Просто и понятно. Саму функцию языка (не мою! стандартную!) не интересует структура моих данных: только флаг. Но в Python 3 предлагается возвращать значение, которое и будет сортироваться.
Простой пример: мне надо отсортировать даты, состоящие из дня, месяца и года. Я понимаю, что пример притянут за уши, чисто для пояснения идеи. Мне предлагается вернуть что-то такое, что и будет отсортировано, например, в терминах Perl,

Code: Select all

return sprintf("%s%s%s",$year,$month,$day)

И я вынужден формировать такую строку каждый раз, вместо тривиальных трех (в худшем случае!) опрераторов "if"
Если же объекты более сложные, то мне снова придется генерить некие промежуточные строки (или числа) только для сортировки.
Вот объясните мне, ради бога, зачем это надо было делать? Что этим вообще достигли как в идедологическом, так и в техническом плане?
Или я чего-то не догоняю? В общем, заранее благодарен.

P.S. Я уже не задаю вопрос, какому идиоту пришло в голову вместо списка ключей хэша (словаря) возвращать iterator. Что этим достигли? Ничего более разумного, чем экономия памяти, в голову не приходит.

P.P.S. Нэнавижю!

По-моему, очень хорошо здесь объяснено:
https://developers.google.com/edu/python/sorting

Например:

Code: Select all

strs = ['ccc', 'aaaa', 'd', 'bb']
print sorted(strs, key=len)  ## ['d', 'bb', 'ccc', 'aaaa']

отсортирует:

Code: Select all

d
bb
ccc
aaaa

[Alexander Troyansky]

Причём есть и то, что вы хотите, тоже:

To use key= custom sorting, remember that you provide a function that takes one value and returns the proxy value to guide the sorting. There is also an optional argument "cmp=cmpFn" to sorted() that specifies a traditional two-argument comparison function that takes two values from the list and returns negative/0/positive to indicate their ordering.

[Pantigalt]

Причём есть и то, что вы хотите, тоже:

To use key= custom sorting, remember that you provide a function that takes one value and returns the proxy value to guide the sorting. There is also an optional argument "cmp=cmpFn" to sorted() that specifies a traditional two-argument comparison function that takes two values from the list and returns negative/0/positive to indicate their ordering.

https://docs.python.org/3/howto/sorting.html

In Py3.0, the cmp parameter was removed entirely (as part of a larger effort to simplify and unify the language, eliminating the conflict between rich comparisons and the __cmp__() magic method).

[Alexander Troyansky]

Причём есть и то, что вы хотите, тоже:

To use key= custom sorting, remember that you provide a function that takes one value and returns the proxy value to guide the sorting. There is also an optional argument "cmp=cmpFn" to sorted() that specifies a traditional two-argument comparison function that takes two values from the list and returns negative/0/positive to indicate their ordering.

https://docs.python.org/3/howto/sorting.html

In Py3.0, the cmp parameter was removed entirely (as part of a larger effort to simplify and unify the language, eliminating the conflict between rich comparisons and the __cmp__() magic method).

кое чего добавили в 3.2:

Transform an old-style comparison function to a key function.
https://docs.python.org/3/library/funct ... cmp_to_key

[timeau]

По-моему, очень хорошо здесь объяснено:
https://developers.google.com/edu/python/sorting

Александр,
Я нисколько не хочу показаться грубым, но все же вынужден спросить: Вы вопрос-то исходный читали? Я не спрашивал, как это сделать. Это сделано. Я спросил: "Вот объясните мне, ради бога, зачем это надо было делать? Что этим вообще достигли как в идедологическом, так и в техническом плане?"

Причём есть и то, что вы хотите, тоже:

В Python 3 параметр "cmp" отсутствует. И я так и не понял, почему Вы решили, что я этого я хочу. Я категорически не хочу возвращать "the proxy value to guide the sorting". Это глупость, ИМО, по сравнению с "троичным флагом" -1, 0, 1.

In Py3.0, the cmp parameter was removed entirely (as part of a larger effort to simplify and unify the language, eliminating the conflict between rich comparisons and the __cmp__() magic method).

Да пофигу, что они "cmp" убрали. Зачем вместо флага требовать значение?

[Alexander Troyansky]

По-моему, очень хорошо здесь объяснено:
https://developers.google.com/edu/python/sorting

Александр,
Я нисколько не хочу показаться грубым, но все же вынужден спросить: Вы вопрос-то исходный читали? Я не спрашивал, как это сделать. Это сделано. Я спросил: "Вот объясните мне, ради бога, зачем это надо было делать? Что этим вообще достигли как в идедологическом, так и в техническом плане?"

Ну типа, упростили. Собсно я вашу точку зрения ("зачем?!") понимаю и разделяю. Просто я вам ответил в духе Why Men Shouldn’t Write Advice Columns

[ALV00]

Почему? Потому что так захотела левая пятка великого Гвидо. А почему они убрали в третьем Питоне команду print? Кому она мешала? Я, подустав от этих странностей, отошел взад на Python 2.7

[Palych]

Я а питоне не силен, но в Java чтобы в Map/Set вставлять нужно чтобы были реализованы как equals(), так и hashCode()
Я по-моему сделал именно так: строил строку, а из неё получал оба значения.

[timeau]

Почему? Потому что так захотела левая пятка великого Гвидо.

Да, иного разумного объяснения я не вижу. Могу быть неправ, но у меня впечатления от Питона исключительно "украинские": "усе не как у всих", да простят меня соседи. Отступы вместо фигурных скобок или begin/end (идиотизм!), невозможность активизировать режим обязательного описания переменных (типа use strict в Перле) и т.д и т.п.

А почему они убрали в третьем Питоне команду print? Кому она мешала? Я, подустав от этих странностей, отошел взад на Python 2.7

У меня нет выбора Запрещено-с. Да и смысл учить с нуля то, с чего придется вскоре мигрировать?..

[helg]

В случае key() у алгоритма сортировки сильно больше возможностей для оптимизации процесса, чем в случае cmp().

Доб. В рассматриваемом случае я бы сделал примерно так (чтобы не задумываться: с нуля нам отсчёт или с единицы)
key = (13*(year-1900) + month)*32 + day
целые числа и готовятся и сравниваются быстрее, чем строки.

[M. Ridcully]

Простой пример: мне надо отсортировать даты, состоящие из дня, месяца и года.

Не обязательно пытаться придумать какое-то _одно_ / интегральное значение.
Верните tuple - (год, месяц, день) - и будет счастье.

[M. Ridcully]

А если про "лирику" - в-принципе, в Питоне 3 можно ко всему привыкнуть, кроме идиотизма UNICODE: нахрена было выдумывать для unicode новый _тип_, когда всё, что нужно - итератор по байтам?!

[timeau]

В случае key() у алгоритма сортировки сильно больше возможностей для оптимизации процесса, чем в случае cmp().

Это почему же?

Доб. В рассматриваемом случае я бы сделал примерно так (чтобы не задумываться: с нуля нам отсчёт или с единицы)
key = (13*(year-1900) + month)*32 + day

Ну и надо вот это для простейшей сортировки? На Perl это бы выглядело как

Code: Select all

$year1 <=> $year2 || $month1 <=> $month2 || $day1 <=> $day2 

Фсё.
До третьего сравнения дойдет только в самом крайнем случае, если равны месяц и год.

целые числа и готовятся и сравниваются быстрее, чем строки.

Ну, я бы начал с того, что о такого рода оптимизации на Python смешно даже говорить, поскольку более тормозного языка и поискать придется. Раза в 3-4 медленнее того же самого Perl, который написан на таком же C, что и Python. А во-вторых, я не уверен, что такое нагромождение умножений и сдвигов при конвертации в число сильно эффективнее того же strcmp(), лежащего под сравнением строк. Нет, не убедил, от слова "совсем".

Не обязательно пытаться придумать какое-то _одно_ / интегральное значение.
Верните tuple - (год, месяц, день) - и будет счастье.

Вернуть tuple для

Code: Select all

sorted(list, key=mysort)

Вы ничего не перепутали?

[M. Ridcully]

Я имел в виду:

Доб. В рассматриваемом случае я бы сделал примерно так (чтобы не задумываться: с нуля нам отсчёт или с единицы)
key = (13*(year-1900) + month)*32 + day

key = year, month, day


Всё.

[timeau]

key = year, month, day
Всё.

Будьте добры, взгляните на мой самый первый оригинальный пост. Там разве что-то иное?

[M. Ridcully]

key = year, month, day
Всё.

Будьте добры, взгляните на мой самый первый оригинальный пост. Там разве что-то иное?

Да.
У вас строка.
У меня - tuple.
Если у вас каждый компонент - год, месяц, день - сравниваем, то можно вернуть tuple из этих компонентов, принимая во внимание lexicographic сравнение tuples.

[helg]

В случае key() у алгоритма сортировки сильно больше возможностей для оптимизации процесса, чем в случае cmp().

Это почему же?

Не всем современным алгоритмам сортировки достаточно функции попарного сравнения. Гляньте в поисковике "Non comparison sorting algorithms". Они могут быть быстрее чем N*ln(N).

Та же карманная (bucket) сортировка, где элементы одним O(N) проходом распихиваются по карманам в соответствии с их значениями, не работает с cmp(), но замечательно работает с key().

[timeau]

У вас строка.
У меня - tuple.
Если у вас каждый компонент - год, месяц, день - сравниваем, то можно вернуть tuple из этих компонентов, принимая во внимание lexicographic сравнение tuples.

Да, согласен, Вы правы, разница есть.

Не всем современным алгоритмам сортировки достаточно функции попарного сравнения. Гляньте в поисковике "Non comparison sorting algorithms". Они могут быть быстрее чем N*ln(N).Та же карманная (bucket) сортировка, где элементы одним O(N) проходом распихиваются по карманам в соответствии с их значениями, не работает с cmp(), но замечательно работает с key().

Нет, не согласен. Карманная сортировка - лишь частный случай, сильно зависящий от "удачности" или "неудачности" данных. К тому же я не верю, что именно этот алгоритм взят за основу в Python.
Опять же, то, что не всем современным алгоритмам достаточно троичного флага - это "фича" алгоритма, но не более того. Это не показатель его, алгоритма, качества.

Подводя некоторые итоги, я бы сказал, что если в Python тот же самый карманный метод выбран в качестве основного (по тем или иным причинам), это могло бы быть аргументом в пользу отказа от cmp. Иначе это блажь, ИМО, ничем не подтвержденная. Как и итератор вместо списка ключей словаря (хэша). Разумности в последнем ноль, если смотреть с точки зрения языка, а не его технической реализации (временный массив требует дополнительную память).

[helg]

Карманная сортировка - лишь частный случай, сильно зависящий от "удачности" или "неудачности" данных.

Карманная сортировка - лишь один из алгоритмов, не работающих через бинарное сравнение.

В современных комьютерах операции с полутора возвращёнными битами от cmp() и с 64 битами от key() занимают одинаковое время. А вот информации в 64 битах сильно больше. То есть без лишних расходов получаем больше информации, соответственно, шире возможности. Я не стал бы настаивать, что сравнение - наилучший метод для обеспечения сортировки во веки веков.

[M. Ridcully]

В случае key() у алгоритма сортировки сильно больше возможностей для оптимизации процесса, чем в случае cmp().

Это почему же?

Не всем современным алгоритмам сортировки достаточно функции попарного сравнения. Гляньте в поисковике "Non comparison sorting algorithms". Они могут быть быстрее чем N*ln(N).

Та же карманная (bucket) сортировка, где элементы одним O(N) проходом распихиваются по карманам в соответствии с их значениями, не работает с cmp(), но замечательно работает с key().

Чтобы говорить о применимости bucket sort vs comparison algorithms нужны доменные знания / семантика ключа. Для динамического языка как-то определить это только на основе исходного кода - ИМХО нереально.

Но key-based сортировка действительно может быть быстрее из-за того, что key функция вызывается ровно 1 раз для каждого элемента, а cmp - может вызываться несколько раз. Учитывая, что в Питоне вызов функции - относительно дорогая операция, это может быть существенно.

Но вообще, это всё дело вкуса. Мне, может, тоже, cmp функция изначально ближе и интуитивнее была. Но я понимаю, что это просто определяется тем, с какими языками раньше работал. В каждом языке какие-то свои идиомы.

Вот Тимо выше пишет про "троичный" флаг для cmp. А кому-то, быть может, это покажется странным - нафига троичный, если можно двоичным обойтись?

[timeau]

В современных комьютерах операции с полутора возвращёнными битами от cmp() и с 64 битами от key() занимают одинаковое время. А вот информации в 64 битах сильно больше. То есть без лишних расходов получаем больше информации, соответственно, шире возможности.

Я что-то не улавливаю этот тезис...

[helg]

Чтобы говорить о применимости bucket sort vs comparison algorithms нужны доменные знания / семантика ключа. Для динамического языка как-то определить это только на основе исходного кода - ИМХО нереально.

Да в этом питоне сортируются не только овеществлённые коллекции, но и вполне себе виртуальные, сгенерированные. Метрики генераторов, особенно тривиальных, коих так много в питонокоде, известны безо всяких проходов по элементам. Да и лямбды для key() обычно тоже немудрёные, так что оптимизатор может их понять. А раз всё известно заранее, можно выбрать правильный алгоритм сортировки. Более того, оптимизатор может даже решить, что не надо громоздить паровоз из генератора и сортировщика, а достаточно просто воткнуть какой параметр в существующий генератор.

[helg]

В современных комьютерах операции с полутора возвращёнными битами от cmp() и с 64 битами от key() занимают одинаковое время. А вот информации в 64 битах сильно больше. То есть без лишних расходов получаем больше информации, соответственно, шире возможности.

Я что-то не улавливаю этот тезис...

Вы не верите, что получая за вопрос 64 бита информации можно найти ответ быстрее, чем получая только полтора бита за вопрос? Ну давайте поиграем в "угадай число". Оба загадаем по целому числу. Я буду отвечать только на вопросы словами "больше-меньше-угадал". Мои же вопросы будут сформулированы так, что ответ на них - 64 битное число. Я с меньшего количества вопросов угадаю, верно? Потому что за один вопрос я получаю больше информации.

[Serguei666]

В случае key() у алгоритма сортировки сильно больше возможностей для оптимизации процесса, чем в случае cmp().

Доб. В рассматриваемом случае я бы сделал примерно так (чтобы не задумываться: с нуля нам отсчёт или с единицы)
key = (13*(year-1900) + month)*32 + day
целые числа и готовятся и сравниваются быстрее, чем строки.

А почему просто не возвращать конвертированное в int строчное значение даты в формате YYYYMMDD?