Sorteringstekniker

Författare:

Andrew Dalke och Raymond Hettinger

Python-listor har en inbyggd list.sort()-metod som modifierar listan på plats. Det finns också en inbyggd funktion sorted() som bygger en ny sorterad lista från en iterabel.

I det här dokumentet utforskar vi olika tekniker för att sortera data med hjälp av Python.

Sortering - grunderna

En enkel stigande sortering är mycket enkel: anropa bara funktionen sorted(). Den returnerar en ny sorterad lista:

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

Du kan också använda metoden list.sort(). Den ändrar listan på plats (och returnerar None för att undvika förvirring). Vanligtvis är det mindre bekvämt än sorted() - men om du inte behöver den ursprungliga listan är det något mer effektivt.

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

En annan skillnad är att metoden list.sort() endast är definierad för listor. Däremot accepterar funktionen sorted() vilken iterabel som helst.

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

Viktiga funktioner

Metoden list.sort() och funktionerna sorted(), min(), max(), heapq.nsmallest() och heapq.nlargest() har en key-parameter för att ange en funktion (eller annan anropsbar funktion) som ska anropas för varje listelement innan jämförelser görs.

Här är till exempel en strängjämförelse utan skiftlägeskänslighet med hjälp av str.casefold():

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

Värdet på parametern key bör vara en funktion (eller annan anropsbar funktion) som tar ett enda argument och returnerar en nyckel som kan användas för sortering. Den här tekniken är snabb eftersom nyckelfunktionen anropas exakt en gång för varje inmatad post.

Ett vanligt mönster är att sortera komplexa objekt med hjälp av några av objektets index som nycklar. Ett exempel:

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

Samma teknik fungerar för objekt med namngivna attribut. Till exempel:

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

Objekt med namngivna attribut kan skapas av en vanlig klass som visas ovan, eller så kan de vara instanser av dataclass eller en named tuple.

Operatormodulens funktioner och utvärdering av partiella funktioner

Mönstren key function ovan är mycket vanliga, så Python tillhandahåller bekvämlighetsfunktioner för att göra accessorfunktioner enklare och snabbare. Modulen operator har itemgetter(), attrgetter() och en methodcaller()-funktion.

Med hjälp av dessa funktioner blir exemplen ovan enklare och snabbare:

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

Operatormodulens funktioner tillåter flera sorteringsnivåer. Du kan till exempel sortera efter grad och sedan efter ålder:

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

Modulen functools tillhandahåller ett annat användbart verktyg för att skapa nyckelfunktioner. Funktionen partial() kan minska ariteten hos en funktion med flera argument, vilket gör den lämplig att använda som en nyckelfunktion.

>>> from functools import partial
>>> from unicodedata import normalize

>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()

>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

Stigande och fallande

Både list.sort() och sorted() accepterar en reverse parameter med ett booleskt värde. Detta används för att flagga nedåtgående sorteringar. Till exempel för att få studentdata i omvänd ålders ordning:

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

Sorteringsstabilitet och komplexa sorteringar

Sorteringar är garanterat stabila. Det innebär att när flera poster har samma nyckel bevaras deras ursprungliga ordning.

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

Lägg märke till hur de två posterna för blue behåller sin ursprungliga ordning så att ('blue', 1) garanterat kommer före ('blue', 2).

Med denna underbara egenskap kan du bygga upp komplexa sorteringar i en serie sorteringssteg. Om du t.ex. vill sortera elevdata efter fallande grad och sedan stigande ålder, gör du först ålder-sorteringen och sedan sorterar du igen med grad:

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

Detta kan abstraheras till en omslagsfunktion som kan ta en lista och tupler av fält och ordning för att sortera dem i flera omgångar.

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

Algoritmen Timsort som används i Python gör multipla sorteringar på ett effektivt sätt eftersom den kan dra nytta av all ordning som redan finns i en dataset.

Dekorera-Sortera-Undekorera

Detta idiom kallas Decorate-Sort-Undecorate efter sina tre steg:

  • Först dekoreras den ursprungliga listan med nya värden som styr sorteringsordningen.

  • För det andra sorteras den dekorerade listan.

  • Slutligen tas dekorationerna bort, vilket skapar en lista som endast innehåller de ursprungliga värdena i den nya ordningen.

Till exempel för att sortera studentdata efter klass med DSU-metoden:

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

Detta idiom fungerar eftersom tupler jämförs lexikografiskt; de första objekten jämförs; om de är desamma jämförs de andra objekten, och så vidare.

Det är inte alltid nödvändigt att inkludera index i i den dekorerade listan, men det finns två fördelar med att inkludera det:

  • Sorteringen är stabil - om två objekt har samma nyckel kommer deras ordning att bevaras i den sorterade listan.

  • De ursprungliga posterna behöver inte vara jämförbara eftersom ordningen på de dekorerade tuplerna kommer att bestämmas av högst de två första posterna. Den ursprungliga listan kan t.ex. innehålla komplexa tal som inte kan sorteras direkt.

Ett annat namn för detta idiom är Schwartzian transform, efter Randal L. Schwartz, som populariserade det bland Perl-programmerare.

Nu när Python-sortering tillhandahåller nyckelfunktioner behövs inte denna teknik så ofta.

Jämförelsefunktioner

Till skillnad från nyckelfunktioner som returnerar ett absolut värde för sortering, beräknar en jämförelsefunktion den relativa ordningen för två indata.

En balansskala jämför t.ex. två prover och ger en relativ ordning: lättare, lika eller tyngre. På samma sätt kommer en jämförelsefunktion som cmp(a, b) att returnera ett negativt värde för mindre än, noll om indata är lika, eller ett positivt värde för större än.

Det är vanligt att man stöter på jämförelsefunktioner när man översätter algoritmer från andra språk. Vissa bibliotek tillhandahåller också jämförelsefunktioner som en del av sitt API. Till exempel är locale.strcoll() en jämförelsefunktion.

För att tillgodose dessa situationer tillhandahåller Python functools.cmp_to_key för att omsluta jämförelsefunktionen så att den kan användas som en nyckelfunktion:

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Strategier för oordningsbara typer och värden

Ett antal typ- och värdeproblem kan uppstå vid sortering. Här är några strategier som kan hjälpa till:

  • Konvertera icke-jämförbara indatatyper till strängar före sortering:

>>> data = ['twelve', '11', 10]
>>> sorted(map(str, data))
['10', '11', 'twelve']

Detta behövs eftersom de flesta korsvisa typjämförelser ger upphov till ett TypeError.

  • Avlägsna särskilda värden före sortering:

>>> from math import isnan
>>> from itertools import filterfalse
>>> data = [3.3, float('nan'), 1.1, 2.2]
>>> sorted(filterfalse(isnan, data))
[1.1, 2.2, 3.3]

Detta behövs eftersom standarden IEEE-754 anger att ”Varje NaN ska jämföra oordnat med allt, inklusive sig själv.”

På samma sätt kan None också tas bort från dataset:

>>> data = [3.3, None, 1.1, 2.2]
>>> sorted(x for x in data if x is not None)
[1.1, 2.2, 3.3]

Detta behövs eftersom None inte är jämförbar med andra typer.

  • Konvertera mappningstyper till sorterade objektlistor före sortering:

>>> data = [{'a': 1}, {'b': 2}]
>>> sorted(data, key=lambda d: sorted(d.items()))
[{'a': 1}, {'b': 2}]

Detta behövs eftersom jämförelser mellan dikt och dikt ger upphov till ett TypeError.

  • Konvertera set-typer till sorterade listor före sortering:

>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> sorted(map(sorted, data))
[['a', 'b', 'c'], ['b', 'c', 'd']]

Detta behövs eftersom elementen i set-typer inte har en deterministisk ordning. Till exempel kan list({'a', 'b'}) producera antingen ['a', 'b'] eller ['b', 'a'].

Lite av varje

  • För lokalanpassad sortering, använd locale.strxfrm() för en nyckelfunktion eller locale.strcoll() för en jämförelsefunktion. Detta är nödvändigt eftersom ”alfabetiska” sorteringsordningar kan variera mellan olika kulturer även om det underliggande alfabetet är detsamma.

  • Parametern reverse upprätthåller fortfarande sorteringsstabiliteten (så att poster med lika nycklar behåller den ursprungliga ordningen). Intressant nog kan denna effekt simuleras utan parametern genom att använda den inbyggda funktionen reversed() två gånger:

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

  • Sorteringsrutinerna använder < när de gör jämförelser mellan två objekt. Det är alltså enkelt att lägga till en standardsorteringsordning i en klass genom att definiera en __lt__()-metod:

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

    Observera dock att < kan falla tillbaka till att använda __gt__() om __lt__() inte är implementerad (se object.__lt__() för detaljer om mekaniken). För att undvika överraskningar rekommenderar PEP 8 att alla sex jämförelsemetoderna implementeras. Dekoratorn total_ordering() tillhandahålls för att göra den uppgiften enklare.

  • Nyckelfunktioner behöver inte vara direkt beroende av de objekt som sorteras. En nyckelfunktion kan också komma åt externa resurser. Om t.ex. elevbetygen lagras i en ordbok kan de användas för att sortera en separat lista med elevnamn:

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

Partiell sortering

Vissa applikationer kräver att endast en del av datan ska sorteras. Standardbiblioteket innehåller flera verktyg som gör mindre arbete än en fullständig sortering:

  • min() och max() returnerar det minsta respektive det största värdet. Dessa funktioner gör en enda genomgång av indata och kräver nästan inget extra minne.

  • heapq.nsmallest() och heapq.nlargest() returnerar de n minsta respektive största värdena. Dessa funktioner gör en enda genomgång av data och behåller bara n element i minnet åt gången. För värden på n som är små i förhållande till antalet indata gör dessa funktioner mycket färre jämförelser än en fullständig sortering.

  • heapq.heappush() och heapq.heappop() skapar och upprätthåller ett delvis sorterat arrangemang av data som håller det minsta elementet på position 0. Dessa funktioner är lämpliga för att implementera prioritetsköer som ofta används för schemaläggning av uppgifter.