Jak sortować za pomocą wyściełanego atrybutu string w pythonie za pomocą funkcji klawiszy - python, sortowanie

Załóżmy, że l jest listą obiektów klasy c zAtrybut String x. l należy sortować według następujących kryteriów: Dla dowolnych dwóch elementów: podziel x przy ostatnim znaku ukośnika, weź przyrostek, dodaj dopełnienie zer przed nimi, aby były one równe długości i porównaj je alfabetycznie. Czytałem, że należy użyć funkcji klucza do sortowania w Pythonie. Jednak nie mogę znaleźć żadnego sposobu na osiągnięcie wymaganych kryteriów sortowania w ten sposób. Jeśli kluczowe funkcje nie są właściwym sposobem na osiągnięcie wymaganego sortowania, cieszę się z rozwiązań wykorzystujących „poprawny” sposób.

Odpowiedzi:

Jest to trochę trudne do wykonania przy użyciu funkcji klucza; łatwiej byłoby użyć niestandardowej funkcji porównania. Python 2 obsługuje niestandardowe funkcje porównania dla sort, ale Python 3 nie. Jednak sortowanie z kluczową funkcją to dużo bardziej wydajne niż użycie niestandardowej funkcji porównania: funkcja klucza jest wywoływana tylko raz dla każdego elementu na liście, podczas gdy niestandardowa funkcja porównania musi być wywoływana każdy porównanie dokonane.

„Kluczem” do rozwiązania tego problemu jest realizacjaże nie ma znaczenia, ile zer jest dodawanych do każdego ciągu, o ile długość dwóch porównywanych ciągów jest równa. Musimy więc określić długość najdłuższego ciągu w danych i umieścić wszystkie ciągi długość.

Aby określić tę długość, możemy użyć stosunkowo prostego wyrażenia generatora, które używa rsplit aby uzyskać długość części ciągu po ostatnim cięciu i przekazuje te długości do wbudowanego max funkcjonować. Możemy wtedy wykorzystać tę maksymalną długość w naszej kluczowej funkcji.

Poniższy kod jest przeznaczony dla Pythona 2, ale będzie działał na Pythonie 3, jeśli poprawisz instrukcje print w show funkcjonować.

#!/usr/bin/env python

data = [
"a/bc/this",
"a/bc/is",
"a/bc/a",
"a/bc/short",
"a/bc/test",
"a/bc/123",
"a/bc/24",
"a/bc/5",
]

#Simple sequence printer
def show(seq):
for row in seq:
print row
print

#Get maximum length of the string after the last slash in each data string
maxlen = max(len(s.rsplit("/", 1)[1]) for s in data)

#Key function that pads the string after the last slash
key = lambda s: s.rsplit("/", 1)[1].rjust(maxlen, "0")

#Test the key function
show([(s, key(s)) for s in data])

new_data = sorted(data, key=key)
show(new_data)

wydajność

("a/bc/this", "0this")
("a/bc/is", "000is")
("a/bc/a", "0000a")
("a/bc/short", "short")
("a/bc/test", "0test")
("a/bc/123", "00123")
("a/bc/24", "00024")
("a/bc/5", "00005")

a/bc/5
a/bc/a
a/bc/24
a/bc/is
a/bc/123
a/bc/test
a/bc/this
a/bc/short

Nie znam dokładnych szczegółów sortowania Timsort przy użyciu funkcji klucza, ale jest to odpowiednik:

1. Zmień listę elementów na listę krotek (klucz, element).
2. Posortuj listę krotek, sortując tylko klucz i ignorując element.
3. Przebuduj nową listę elementów, usuwając je z krotek na posortowanej liście.

Jest to tylko przybliżony przewodnik, ponieważ Timsort jest napisany w C.