Sorting HOW TO

Автор

Andrew Dalke та Raymond Hettinger

Release

0.1

Списки Python мають вбудований метод list.sort(), який змінює список на місці. Існує також вбудована функція sorted(), яка створює новий відсортований список із ітерованого.

У цьому документі ми досліджуємо різні техніки сортування даних за допомогою Python.

Основи сортування

A simple ascending sort is very easy: just call the sorted() function. It returns a new sorted list:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

Ви також можете використовувати метод list.sort(). Він змінює список на місці (і повертає None, щоб уникнути плутанини). Зазвичай це менш зручно, ніж sorted(), але якщо вам не потрібен оригінальний список, це трохи ефективніше.

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

Ще одна відмінність полягає в тому, що метод list.sort() визначено лише для списків. На відміну від цього, функція sorted() приймає будь-яку ітерацію.

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

Ключові функції

І list.sort(), і sorted() мають параметр key для вказівки функції (або іншого виклику), яка буде викликана для кожного елемента списку перед проведенням порівнянь.

Наприклад, ось порівняння рядків без урахування регістру:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

Значення параметра key має бути функцією (або іншою можливістю виклику), яка приймає один аргумент і повертає ключ для використання в цілях сортування. Ця техніка є швидкою, оскільки ключова функція викликається рівно один раз для кожного вхідного запису.

Загальним шаблоном є сортування складних об’єктів за допомогою деяких індексів об’єктів як ключів. Наприклад:

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Така ж техніка працює для об’єктів з іменованими атрибутами. Наприклад:

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Operator Module Functions

The key-function patterns shown above are very common, so Python provides convenience functions to make accessor functions easier and faster. The operator module has itemgetter(), attrgetter(), and a methodcaller() function.

Використовуючи ці функції, наведені вище приклади стають простішими та швидшими:

>>> from operator import itemgetter, attrgetter

>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Функції модуля оператора дозволяють сортувати кілька рівнів. Наприклад, щоб відсортувати за класом, а потім за віком:

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

Висхідний і спадний

І list.sort(), і sorted() приймають параметр reverse із логічним значенням. Це використовується для позначення сортування за спаданням. Наприклад, щоб отримати дані про студентів у зворотному порядку віку:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Стійкість сортування та складні сорти

Сортування гарантовано буде стабільним. Це означає, що коли кілька записів мають однаковий ключ, їхній початковий порядок зберігається.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Зверніть увагу, як два записи для blue зберігають свій початковий порядок, тому ('blue', 1) гарантовано передує ('blue', 2).

Ця чудова властивість дозволяє вам створювати складні сорти за допомогою серії кроків сортування. Наприклад, щоб відсортувати дані студента за зменшенням оцінки, а потім за зростанням віку, спочатку виконайте сортування за віком, а потім знову за допомогою оцінки:

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Це можна абстрагувати у функцію-обгортку, яка може брати список і кортежі полів і впорядковувати їх, щоб сортувати їх за кілька проходів.

>>> def multisort(xs, specs):
...     for key, reverse in reversed(specs):
...         xs.sort(key=attrgetter(key), reverse=reverse)
...     return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Алгоритм Timsort, що використовується в Python, ефективно виконує багаторазове сортування, оскільки він може використовувати будь-яке впорядкування, яке вже є в наборі даних.

The Old Way Using Decorate-Sort-Undecorate

Ця ідіома називається Decorate-Sort-Undecorate після трьох кроків:

• По-перше, початковий список прикрашається новими значеннями, які контролюють порядок сортування.

• По-друге, оформлений список сортується.

• Нарешті, декорації видаляються, створюючи список, який містить лише початкові значення в новому порядку.

Наприклад, щоб відсортувати дані студента за класом за допомогою підходу DSU:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated]               # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Ця ідіома працює, тому що кортежі порівнюються лексикографічно; порівнюються перші предмети; якщо вони однакові, то порівнюються другі елементи і так далі.

Не обов’язково в усіх випадках включати індекс i в оформлений список, але це дає дві переваги:

• Сортування є стабільним — якщо два елементи мають однаковий ключ, їхній порядок буде збережено у відсортованому списку.

• Оригінальні елементи не обов’язково мають бути порівнянними, тому що порядок оформлених кортежів визначатиметься щонайбільше першими двома елементами. Так, наприклад, вихідний список може містити комплексні числа, які неможливо відсортувати безпосередньо.

Інша назва цієї ідіоми — перетворення Шварца, на честь Рендала Л. Шварца, який популяризував її серед програмістів на Perl.

Тепер, коли сортування Python надає ключові функції, ця техніка не часто потрібна.

The Old Way Using the cmp Parameter

Many constructs given in this HOWTO assume Python 2.4 or later. Before that, there was no sorted() builtin and list.sort() took no keyword arguments. Instead, all of the Py2.x versions supported a cmp parameter to handle user specified comparison functions.

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).

In Py2.x, sort allowed an optional function which can be called for doing the comparisons. That function should take two arguments to be compared and then return a negative value for less-than, return zero if they are equal, or return a positive value for greater-than. For example, we can do:

>>> def numeric_compare(x, y):
...     return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) 
[1, 2, 3, 4, 5]

Or you can reverse the order of comparison with:

>>> def reverse_numeric(x, y):
...     return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) 
[5, 4, 3, 2, 1]

When porting code from Python 2.x to 3.x, the situation can arise when you have the user supplying a comparison function and you need to convert that to a key function. The following wrapper makes that easy to do:

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

To convert to a key function, just wrap the old comparison function:

>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

In Python 3.2, the functools.cmp_to_key() function was added to the functools module in the standard library.

Odd and Ends

• For locale aware sorting, use locale.strxfrm() for a key function or locale.strcoll() for a comparison function.

• Параметр reverse усе ще підтримує стабільність сортування (щоб записи з однаковими ключами зберігали вихідний порядок). Цікаво, що цей ефект можна моделювати без параметра, використовуючи двічі вбудовану функцію reversed():

  >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
  >>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
  >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
  >>> assert standard_way == double_reversed
  >>> standard_way
  [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
  

• The sort routines use < when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method:

  >>> Student.__lt__ = lambda self, other: self.age < other.age
  >>> sorted(student_objects)
  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  

  However, note that < can fall back to using __gt__() if __lt__() is not implemented (see object.__lt__()).

• Ключові функції не повинні безпосередньо залежати від об’єктів, які сортуються. Ключова функція також може отримувати доступ до зовнішніх ресурсів. Наприклад, якщо оцінки студентів зберігаються в словнику, їх можна використовувати для сортування окремого списку імен студентів:

  >>> students = ['dave', 'john', 'jane']
  >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
  >>> sorted(students, key=newgrades.__getitem__)
  ['jane', 'dave', 'john']