7

В недавно заданном вопросе зашла речь об обратной сортировке алфавитного порядка.
В именно этом случае вопрос решается просто - по числам изначально отсортировать наоборот, а потом развернуть результат в обратном порядке. Однако, вероятно, таким образом можно решить вопрос не всегда.

Мне показалось, что именно это обсуждение уже мало относится к теме вопроса, и его стоит выделить в отдельный.


Суть вопроса:
Есть некоторый набор данных:

data = [
  ('Ехал', 1), 
  ('Грека', 3), 
  ('Через', 1), 
  ('Реку', 2), 
  ('Видит', 1), 
  ('В', 2), 
  ('Реке', 1), 
  ('Рак', 2), 
  ('Сунул', 1), 
  ('Руку', 2), 
  ('За', 1), 
  ('Греку', 1), 
  ('Цап', 1)
]

Стоит задача: сначала отсортировать этот список по второму элементу (числу) в порядке убывания, а в случае совпадения числа - внутри группы отсортировать в обратном лексикографическом порядке.


Решение задачи о сортировке в прямом лексикографическом порядке сводится к одной строке:

sorted(data, key=lambda x: (-x[1], x[0]))

Конкретно эта задача также может быть решена в одну строку:

reversed(sorted(data, key=lambda x: (x[1], x[0])))
# или же
sorted(data, key=lambda x: (x[1], x[0]), reverse=True)

И это решение действительно даст правильный результат. Однако, не всегда можно обойтись простым разворотом списка (особенно если ключей сортировки больше двух, или же оба ключа - строки)

Обратная сортировка по числу задаётся с помощью унарного отрицания: -key.
Есть ли подобная возможность для строк?


UPD

Ответ на вопрос из комментариев про reverse=True:
В некоторых случаях использование этого атрибута не поможет, ровным счётом, ничем.

Входные данные:

data_hard = [
  ('Иванов', 'Сергей', 'Фёдорович'),
  ('Петров', 'Александр', 'Владимирович'),
  ('Иванов', 'Алексей', 'Евгеньевич'),
  ('Афанасьев', 'Артём', 'Григорьевич'),
  ('Иванов', 'Иван', 'Иванович'),
  ('Петров', 'Сергей', 'Викторович'),
  ('Петров', 'Сергей', 'Владимирович'),
  ('Пушкин', 'Александр', 'Сергеевич'),
  ('Иванов', 'Сергей', 'Петрович'),
  ('Гоголь', 'Николай', 'Васильевич'),
]

Задача:

Отсортировать список в прямом порядке по фамилиям. В случае совпадения фамилии отсортировать группу в обратном порядке по имени. В случае совпадение фамилии и имени отсортировать подгруппу в обратном порядке по отчеству.

Результат прямой сортировки:

>>> sorted(data_hard, key=lambda x: (x[0], x[1], x[2]))
[('Афанасьев', 'Артём', 'Григорьевич'), 
 ('Гоголь', 'Николай', 'Васильевич'), 
 ('Иванов', 'Алексей', 'Евгеньевич'), 
 ('Иванов', 'Иван', 'Иванович'), 
 ('Иванов', 'Сергей', 'Петрович'), 
 ('Иванов', 'Сергей', 'Фёдорович'), 
 ('Петров', 'Александр', 'Владимирович'), 
 ('Петров', 'Сергей', 'Викторович'), 
 ('Петров', 'Сергей', 'Владимирович'), 
 ('Пушкин', 'Александр', 'Сергеевич')]

Результат обратной сортировки:

>>> sorted(data_hard, key=lambda x: (x[0], x[1], x[2]), reverse=True)
[('Пушкин', 'Александр', 'Сергеевич'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Афанасьев', 'Артём', 'Григорьевич')]

Как видно, оба варианта не соответствуют поставленным условиям. Т.е. атрибут reverse не всегда является актуальным решением для обратной сортировки строк.

2
  • sorted(..., reversed=True) 1 мая 2020 в 12:01
  • @КириллМалышев как я уже упоминал, если ключей много, и по каким-то нужно сортировать в прямом порядке, а по каким-то - в обратном, этот параметр будет неудобен. Особенно, если в сортировке несколько строковых ключей/ключей-списков. 1 мая 2020 в 12:02

3 ответа 3

7
+100

В сложных случаях сортировать нужно в несколько проходов. Аналогом

sorted(data, key=lambda x: (-x[1], x[0]))

работающим не только с числами, будет

sorted(sorted(data, key=lambda x: x[0]), key=lambda x: x[1], reverse=True)

или для лучшей читаемости

from operator import itemgetter

sorted(sorted(data, key=itemgetter(0)), key=itemgetter(1), reverse=True)

Upd

Пояснение:

Берем вашу таблицу

[('Иванов', 'Сергей', 'Фёдорович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Афанасьев', 'Артём', 'Григорьевич'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Гоголь', 'Николай', 'Васильевич')]

И упорядочиваем ее по имени

[('Петров', 'Александр', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Афанасьев', 'Артём', 'Григорьевич'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Иванов', 'Сергей', 'Петрович')]

Заметьте, что записи с одинаковыми ключами (именами в данном случае) остались в прежнем порядке относительно друг друга, например, Иванов Сергей Фёдорович стоит раньше Петрова Сергея Векторовича. Это не совпадение, такое поведение гарантируется.

Теперь по фамилии в обратном порядке

data_hard.sort(key=itemgetter(0), reverse=True)
[('Пушкин', 'Александр', 'Сергеевич'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Афанасьев', 'Артём', 'Григорьевич')]

И, опять же, Петров Александр Владимирович идет раньше Петрова Сергея Викторовича, как и в предыдущей таблице. Это значит что результаты предыдущей сортировки не пропали даром. И несмотря на то, что многие записи сменили порядок, потому, что порядок фамилий важнее порядка имен, те записи, порядок которых не нуждался в изменении остались на своих местах.

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


Еще одним (менее производительным) решением будет создание собственного класса-обертки, меняющего операнды сравнения местами.

from functools import total_ordering

@total_ordering
class Reverse:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return other.value < self.value

    def __eq__(self, other):
        return other.value == self.value
sorted(data, key=lambda x: (Reverse(x[1]), x[0]))

Upd

Пояснение:

Reverse здесь играет ту же роль, что и минус для числел, т.е. является некоторой функцией f такой, что

если x < y, то f(y) < f(x)
если x = y, то f(y) = f(x)

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

7
  • 2
    этот вариант не только более читабельный, он еще и быстрее! браво! :) 1 мая 2020 в 15:04
  • 1
    @MaxU по моим тестам этот вариант получается даже быстрее чем в один проход c key=lambda x: (-x[1], x[0]) там где это применимо, правда незначительно быстрее.
    – extrn
    1 мая 2020 в 15:29
  • 1
    неожиданный результат, возьму себе на заметку! 1 мая 2020 в 15:30
  • Ответ довольно интересный и уж очень в стиле python. Однако, мне кажется, его стоило бы дополнить пояснением о том, как именно он работает. А вообще идея сортировки по возрастанию приоритетов, а не по их убыванию очень интересна 4 мая 2020 в 15:20
  • 1
    @Евгений, мне кажется данный ответ гораздо больше заслуживает быть отмеченным как верный ответ. А пояснять тут особо и нечего - сначала сортируем по нужным признакам в одном направлении, а потом сортируем результат сортирвки по другим признакам в обратном направлении. За счет того, что алгоритм TimSort - стабильный все правильно отработает. 4 мая 2020 в 16:13
5

Поскольку для строк операции отрицания нет, мы можем прибегнуть к хитрости: перевести строку в массив чисел, где каждое число - порядковый номер буквы в этом слове:

sorted(data, key = lambda x: (-x[1], [-o for o in map(ord, x[0])]))

Если более наглядно, вот числовое представление слова Ехал:

>>> list(map(ord, data[0][0]))
[1045, 1093, 1072, 1083]

Соответственно, сортировка происходит в обратном порядке. Всё, что остаётся сделать - развернуть все числа в последовательности:

>>> [-o for o in map(ord, x[0])]
[-1045, -1093, -1072, -1083]

В таком случае сортировка будет происходить в обратном лексикографическом порядке.
Результат работы:

>>> sorted(data, key = lambda x: (-x[1], [-o for o in map(ord, x[0])]))
[('Грека', 3),
 ('Руку', 2),
 ('Реку', 2),
 ('Рак', 2),
 ('В', 2),
 ('Через', 1),
 ('Цап', 1),
 ('Сунул', 1),
 ('Реке', 1),
 ('За', 1),
 ('Ехал', 1),
 ('Греку', 1),
 ('Видит', 1)]

Как и было заявлено - список отсортирован в порядке убывания по числу, а внутри групп с одинаковым числом - в обратном лексикографическом порядке.


UPD

Результат сортировки данных из дополнения:

>>> sorted( 
...   data_hard,
...   key = lambda x:
...   (x[0], [-o for o in map(ord, x[1])], [-o for o in map(ord, x[2])])
... )
[('Афанасьев', 'Артём', 'Григорьевич'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич')]

Такой метод задания ключа вполне подходит для решения подобных задач

5

Ваше решение можно немного сократить:

In [22]: sorted(
    ...:   data_hard,
    ...:   key = lambda x: ([-ord(c) for c in x[0]], x[1], x[2]),
    ...:   reverse=True
    ...: )
Out[22]:
[('Афанасьев', 'Артём', 'Григорьевич'),
 ('Гоголь', 'Николай', 'Васильевич'),
 ('Иванов', 'Сергей', 'Фёдорович'),
 ('Иванов', 'Сергей', 'Петрович'),
 ('Иванов', 'Иван', 'Иванович'),
 ('Иванов', 'Алексей', 'Евгеньевич'),
 ('Петров', 'Сергей', 'Владимирович'),
 ('Петров', 'Сергей', 'Викторович'),
 ('Петров', 'Александр', 'Владимирович'),
 ('Пушкин', 'Александр', 'Сергеевич')]

Кроме того можно воспользоваться тяжелой артиллерией Pandas:

import pandas as pd

df = pd.DataFrame(data_hard, columns=["last_name", "first_name", "mid_name"])

In [35]: df.sort_values(df.columns.to_list(), ascending=[True, False, False])
Out[35]:
   last_name first_name      mid_name
3  Афанасьев      Артём   Григорьевич
9     Гоголь    Николай    Васильевич
0     Иванов     Сергей     Фёдорович
8     Иванов     Сергей      Петрович
4     Иванов       Иван      Иванович
2     Иванов    Алексей    Евгеньевич
6     Петров     Сергей  Владимирович
5     Петров     Сергей    Викторович
1     Петров  Александр  Владимирович
7     Пушкин  Александр     Сергеевич

в виде списка списков:

In [36]: df.sort_values(df.columns.to_list(), ascending=[True, False, False]).to_numpy().tolist()
Out[36]:
[['Афанасьев', 'Артём', 'Григорьевич'],
 ['Гоголь', 'Николай', 'Васильевич'],
 ['Иванов', 'Сергей', 'Фёдорович'],
 ['Иванов', 'Сергей', 'Петрович'],
 ['Иванов', 'Иван', 'Иванович'],
 ['Иванов', 'Алексей', 'Евгеньевич'],
 ['Петров', 'Сергей', 'Владимирович'],
 ['Петров', 'Сергей', 'Викторович'],
 ['Петров', 'Александр', 'Владимирович'],
 ['Пушкин', 'Александр', 'Сергеевич']]

UPDATE: сравнение разных вариантов по скорости на списке из 10.000 списков:

In [48]: data_big = data * 1000

In [49]: len(data_big)
Out[49]: 10000

In [50]: %%timeit
    ...: sorted(
    ...:   data_big,
    ...:   key = lambda x:
    ...:   (x[0], [-o for o in map(ord, x[1])], [-o for o in map(ord, x[2])])
    ...: )
    ...:
    ...:
53.8 ms ± 220 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [51]: %%timeit
    ...: sorted(sorted(data_big, key=itemgetter(0)), key=itemgetter(1), reverse=True)
    ...:
    ...:
3.66 ms ± 504 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [53]: %%timeit
    ...: sorted(
    ...:   data_big,
    ...:   key = lambda x:
    ...:   (x[0], [-o for o in map(ord, x[1])], [-o for o in map(ord, x[2])])
    ...: )
    ...:
    ...:
54.4 ms ± 797 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [54]: %%timeit
    ...: df = pd.DataFrame(data_big, columns=["last_name", "first_name", "mid_name"])
    ...: df.sort_values(df.columns.to_list(), ascending=[True, False, False]).to_numpy().tolist()
    ...:
    ...:
8.91 ms ± 2.86 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1
  • "Ваше решение можно немного сократить" - технически это просто уточнение. При равном количестве прямых и обратных сортировок реверс не будет иметь значения, а если прямых больше - только сделает решение массивнее. В своём ответе мне было интересно рассказать именно про метод приведения строки к списку порядковых номеров. А решение через pd - полезное дополнение =) 1 мая 2020 в 13:05

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.