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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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