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

[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?

[helg]

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

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

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

Можно и так. Но это потребует преобразования трёх числел в ASCII строки, склеивания и парсирования полученной строки в число. Не очень накладно, но всё же операции string<->int - это, как минимум, циклы. С позиции дотошного оптимизатора это всё-таки затратнее для железки, чем простая арифметика.

[timeau]

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

А вот тут давайте поподробнее. Поскольку:
1. Лямбды в Питоне нетривиальными не бывают. Они все вида "x:return действие над х", потому вопрос с оптимизатором подвисает в воздухе.
2. Я больше чем уверен, что алгоритм сортировки один на все случаи жизни.
3. Генераторы, AFAIK, в сортировках недопустимы в принципе, по крайней мере в виде key=XXX функции.

Вы не верите, что получая за вопрос 64 бита информации можно найти ответ быстрее, чем получая только полтора бита за вопрос?

Я не не верю, я не понимаю, к чему это тут вообще. Это вообще к делу не относится, ИМО. Мы говорили о "троичном" флаге, Вы сказали о полутора битах. При чем тут возвращаемое 64-битовое число? С какого оно тут бока?

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

Можно и так. Но это потребует преобразования трёх числел в ASCII строки, склеивания и парсирования полученной строки в число. Не очень накладно, но всё же операции string<->int - это, как минимум, циклы. С позиции дотошного оптимизатора это всё-таки затратнее для железки, чем простая арифметика.

Нет, категорически. Переменная в нетипизированном языке типа Перла или Питона совсем не просто 64 int, это объекты (хэши), что подтверждается значениями типа None or undef. У Python так и вовсе парадигма "все есть объект". Отсюда и совершенно идиотские конструкции объединения массива

Code: Select all

','.join(list)

где в качестве объекта выступает объект константного разделителя, в данном случае запятой. Потому склеивание совсем не такое, как можно было бы ожидать из C/C++, etc.

[ALV00]

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

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

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

Можно и так. Но это потребует преобразования трёх числел в ASCII строки, склеивания и парсирования полученной строки в число. Не очень накладно, но всё же операции string<->int - это, как минимум, циклы. С позиции дотошного оптимизатора это всё-таки затратнее для железки, чем простая арифметика.

year*10000 + month*100 + day

[M. Ridcully]

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

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

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

Можно и так. Но это потребует преобразования трёх числел в ASCII строки, склеивания и парсирования полученной строки в число. Не очень накладно, но всё же операции string<->int - это, как минимум, циклы. С позиции дотошного оптимизатора это всё-таки затратнее для железки, чем простая арифметика.

year*10000 + month*100 + day

Ещё раз - а чего мешает tuple вернуть - year, month, day?

[ALV00]

Ещё раз - а чего мешает tuple вернуть - year, month, day?

Я думаю, по большому счету пофиг. Лишние несколько операций с памятью рояля не сыграют.