Czy Python śledzi, kiedy coś zostało posortowane, wewnętrznie?

Question

Na przykład, jeśli zadzwonię

L = [3,4,2,1,5] 
L = sorted(L) 

dostaję posortowaną listę. Teraz, w przyszłości, jeśli chcę przeprowadzić jakiś inny rodzaj sortowania na L, Python automatycznie wie, że "ta lista została posortowana przed i nie zmodyfikowana, ponieważ możemy przeprowadzić pewne wewnętrzne optymalizacje, w jaki sposób wykonujemy ten inny rodzaj sortować "takie jak sortowanie odwrotne itp.?

Answer 1

Nie, nie ma. Algorytm sortowania ma na celu wykorzystanie (częściowo) posortowanych danych wejściowych, ale sama lista nie "pamięta", że jest sortowana w jakikolwiek sposób.

(W rzeczywistości jest to szczegół implementacji CPython, a przyszłe wersje/różne implementacje mogą buforować fakt, że lista została właśnie posortowana, ale nie jestem przekonany, że można to zrobić bez spowalniania wszystkich operacji, które modyfikują listę , takie jak append.)

Answer 2

Niektóre z nich, przynajmniej specyficzna odwrotnej sortowania pytanie, można to zrobić za pomocą numpy:

import numpy as np 
L = np.array([3,4,2,1,5]) 
a = np.argsort(L) 
b = L[a] 
r = L[a[::-1]] 

print L 
[3 4 2 1 5] 

print b 
[1 2 3 4 5] 

print r 
[5, 4, 3, 2, 1] 

Oznacza to, że tu po prostu zrobić coś w rodzaju raz (w celu utworzenia a procesu sortowania indeksów), a następnie możemy manipulować a, aby wykonać inne różne rodzaje, takie jak sortowanie zwykłe b i sortowanie odwrotne r. I wielu innych byłoby równie łatwo, jak każdy inny element.

Answer 3

Jak zauważyli komentatorzy, normalne listy Pythona są z natury uporządkowane i wydajnie sortowane (dzięki, Timsort!), ale nie pamiętam ani nie utrzymuję statusu sortowania.

Jeśli potrzebujesz list, które zawsze zachowują swój posortowany status, możesz zainstalować pakiet SortedContainers z PyPI.

>>> from sortedcontainers import SortedList 
>>> L = SortedList([3,4,2,1,5]) 
>>> L 
SortedList([1, 2, 3, 4, 5]) 
>>> L.add(3.3) 
>>> L 
SortedList([1, 2, 3, 3.3, 4, 5]) 

Uwaga normalny append metoda staje add, ponieważ przedmiot nie jest dodawana na końcu. Jest dodawany wszędzie tam, gdzie jest to odpowiednie, biorąc pod uwagę kolejność sortowania. Istnieje również typ SortedListWithKey, który pozwala jawnie ustawić klucz/porządek sortowania.