Kỹ thuật sắp xếp

tác giả:

Andrew Dalke và Raymond Hettinger

Danh sách Python có phương thức list.sort() tích hợp sẵn để sửa đổi danh sách tại chỗ. Ngoài ra còn có một hàm tích hợp sorted() để xây dựng một danh sách được sắp xếp mới từ một lần lặp.

Trong tài liệu này, chúng ta khám phá các kỹ thuật khác nhau để sắp xếp dữ liệu bằng Python.

Sắp xếp cơ bản

Việc sắp xếp tăng dần đơn giản rất dễ dàng: chỉ cần gọi hàm sorted(). Nó trả về một danh sách được sắp xếp mới:

>>> được sắp xếp([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

Bạn cũng có thể sử dụng phương pháp list.sort(). Nó sửa đổi danh sách tại chỗ (và trả về None để tránh nhầm lẫn). Thông thường, nó kém tiện lợi hơn sorted() - nhưng nếu bạn không cần danh sách gốc thì nó hiệu quả hơn một chút.

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

Một điểm khác biệt nữa là phương thức list.sort() chỉ được xác định cho danh sách. Ngược lại, hàm sorted() chấp nhận bất kỳ lần lặp nào.

>>> được sắp xếp({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

Chức năng chính

Phương thức list.sort() và các hàm sorted(), min(), max(), heapq.nsmallest() và heapq.nlargest() có tham số key để chỉ định một hàm (hoặc có thể gọi khác) được gọi trên mỗi thành phần danh sách trước khi thực hiện so sánh.

Ví dụ: đây là so sánh chuỗi không phân biệt chữ hoa chữ thường bằng str.casefold():

>>> được sắp xếp("Đây là chuỗi thử nghiệm từ Andrew".split(), key=str.casefold)
['a', 'Andrew', 'từ', 'là', 'chuỗi', 'kiểm tra', 'Cái này']

Giá trị của tham số key phải là một hàm (hoặc có thể gọi khác) nhận một đối số duy nhất và trả về một khóa để sử dụng cho mục đích sắp xếp. Kỹ thuật này nhanh vì hàm khóa được gọi chính xác một lần cho mỗi bản ghi đầu vào.

Một mẫu phổ biến là sắp xếp các đối tượng phức tạp bằng cách sử dụng một số chỉ mục của đối tượng làm khóa. Ví dụ:

>>> sinh viên_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
...]
>>> sắp xếp(student_tuples, key=lambda sinh viên: sinh viên[2]) # sort theo độ tuổi
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Kỹ thuật tương tự áp dụng cho các đối tượng có thuộc tính được đặt tên. Ví dụ:

>>> Sinh viên lớp:
... def __init__(bản thân, tên, lớp, tuổi):
... self.name = tên
... self.grade = điểm
... self.age = tuổi
... def __repr__(self):
... return Repr((self.name, self.grade, self.age))

>>> sinh viên_objects = [
... Sinh viên('john', 'A', 15),
... Sinh viên('jane', 'B', 12),
... Sinh viên('dave', 'B', 10),
...]
>>> sắp xếp(student_objects, key=lambda sinh viên: sinh viên.age) # sort theo độ tuổi
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Các đối tượng có thuộc tính được đặt tên có thể được tạo bởi một lớp thông thường như được hiển thị ở trên hoặc chúng có thể là phiên bản của dataclass hoặc named tuple.

Chức năng mô-đun toán tử và đánh giá chức năng một phần

Các mẫu key function được hiển thị ở trên rất phổ biến, vì vậy Python cung cấp các hàm tiện lợi để làm cho các hàm truy cập trở nên dễ dàng và nhanh hơn. Mô-đun operator có chức năng itemgetter(), attrgetter() và methodcaller().

Sử dụng các hàm đó, các ví dụ trên trở nên đơn giản và nhanh hơn:

>>> từ toán tử nhập itemgetter, attrgetter

>>> đã sắp xếp(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

>>> được sắp xếp(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Các chức năng của mô-đun vận hành cho phép nhiều cấp độ sắp xếp. Ví dụ: để sắp xếp theo grade rồi theo age:

>>> đã sắp xếp(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

>>> được sắp xếp(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

Mô-đun functools cung cấp một công cụ hữu ích khác để tạo các chức năng chính. Hàm partial() có thể giảm arity của hàm nhiều đối số, khiến nó phù hợp để sử dụng làm hàm khóa.

>>> từ functools nhập một phần
>>> từ nhập unicodedata bình thường hóa

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

>>> được sắp xếp(tên, key=một phần(chuẩn hóa, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

>>> được sắp xếp(tên, key=partial(chuẩn hóa, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']

Tăng dần và giảm dần

Cả list.sort() và sorted() đều chấp nhận tham số reverse có giá trị boolean. Điều này được sử dụng để gắn cờ các loại giảm dần. Ví dụ: để lấy dữ liệu học sinh theo thứ tự age ngược:

>>> được sắp xếp(student_tuples, key=itemgetter(2), Reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

>>> được sắp xếp(student_objects, key=attrgetter('age'), Reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Sắp xếp ổn định và sắp xếp phức tạp

Các loại được đảm bảo là stable. Điều đó có nghĩa là khi nhiều bản ghi có cùng khóa, thứ tự ban đầu của chúng được giữ nguyên.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> đã sắp xếp(dữ liệu, key=itemgetter(0))
[('xanh', 1), ('xanh', 2), ('đỏ', 1), ('đỏ', 2)]

Lưu ý cách hai bản ghi cho blue giữ nguyên thứ tự ban đầu của chúng để ('blue', 1) được đảm bảo đứng trước ('blue', 2).

Thuộc tính tuyệt vời này cho phép bạn xây dựng các kiểu sắp xếp phức tạp theo một loạt các bước sắp xếp. Ví dụ: để sắp xếp dữ liệu học sinh theo grade giảm dần rồi tăng dần age, hãy thực hiện sắp xếp age trước rồi sắp xếp lại bằng grade:

>>> s = được sắp xếp(student_objects, key=attrgetter('age')) # sort trên khóa phụ
>>> được sắp xếp (s, key=attrgetter('grade'), Reverse=True) # now sắp xếp theo khóa chính, giảm dần
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Điều này có thể được trừu tượng hóa thành một hàm bao bọc có thể lấy danh sách và các bộ dữ liệu của trường rồi sắp xếp chúng theo nhiều lần.

>>> def multisort(xs, thông số kỹ thuật):
... đối với khóa, đảo ngược trong đảo ngược(thông số kỹ thuật):
... xs.sort(key=attrgetter(key), đảo ngược=đảo ngược)
... trả lại xs

>>> multisort(list(student_objects), (('lớp', Đúng), ('tuổi', Sai)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Thuật toán Timsort được sử dụng trong Python thực hiện nhiều loại hiệu quả vì nó có thể tận dụng mọi thứ tự đã có trong tập dữ liệu.

Trang trí-Sắp xếp-Không trang trí

Thành ngữ này được gọi là Trang trí-Sắp xếp-Không trang trí sau ba bước:

  • Đầu tiên, danh sách ban đầu được trang trí bằng các giá trị mới kiểm soát thứ tự sắp xếp.

  • Thứ hai, danh sách trang trí được sắp xếp.

  • Cuối cùng, phần trang trí được loại bỏ, tạo ra một danh sách chỉ chứa các giá trị ban đầu theo thứ tự mới.

Ví dụ: để sắp xếp dữ liệu học sinh theo grade bằng phương pháp DSU:

>>> trang trí = [(student.grade, i, sinh viên) cho i, sinh viên trong enumerate(student_objects)]
>>> trang trí.sort()
>>> [học sinh lớp, i, học sinh trang trí] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Thành ngữ này có tác dụng vì các bộ dữ liệu được so sánh theo từ điển; các mục đầu tiên được so sánh; nếu chúng giống nhau thì các mục thứ hai sẽ được so sánh, v.v.

Trong mọi trường hợp, không nhất thiết phải đưa chỉ mục i vào danh sách được trang trí, nhưng việc đưa chỉ mục này mang lại hai lợi ích:

  • Việc sắp xếp ổn định -- nếu hai mục có cùng khóa, thứ tự của chúng sẽ được giữ nguyên trong danh sách đã sắp xếp.

  • Các mục ban đầu không cần phải so sánh được vì thứ tự của các bộ dữ liệu được trang trí sẽ được xác định nhiều nhất bởi hai mục đầu tiên. Vì vậy, ví dụ: danh sách ban đầu có thể chứa các số phức không thể sắp xếp trực tiếp.

Một tên khác cho thành ngữ này là Schwartzian transform, theo tên Randal L. Schwartz, người đã phổ biến nó trong giới lập trình viên Perl.

Giờ đây, việc sắp xếp Python đã cung cấp các hàm chính nên kỹ thuật này thường không cần thiết.

Hàm so sánh

Không giống như các hàm chính trả về giá trị tuyệt đối để sắp xếp, hàm so sánh tính toán thứ tự tương đối cho hai đầu vào.

Ví dụ: balance scale so sánh hai mẫu và đưa ra thứ tự tương đối: nhẹ hơn, bằng hoặc nặng hơn. Tương tự, hàm so sánh như cmp(a, b) sẽ trả về giá trị âm cho giá trị nhỏ hơn, bằng 0 nếu đầu vào bằng nhau hoặc giá trị dương cho giá trị lớn hơn.

Người ta thường gặp phải các hàm so sánh khi dịch thuật toán từ các ngôn ngữ khác. Ngoài ra, một số thư viện còn cung cấp chức năng so sánh như một phần của API. Ví dụ: locale.strcoll() là một hàm so sánh.

Để phù hợp với những tình huống đó, Python cung cấp functools.cmp_to_key để bọc hàm so sánh để làm cho nó có thể sử dụng được như một hàm chính

được sắp xếp(từ, key=cmp_to_key(strcoll)) thứ tự sắp xếp # locale-aware

Chiến lược cho các loại và giá trị không thể sắp xếp

Một số vấn đề về loại và giá trị có thể phát sinh khi sắp xếp. Dưới đây là một số chiến lược có thể giúp ích:

  • Chuyển đổi các loại đầu vào không thể so sánh thành chuỗi trước khi sắp xếp:

>>> dữ liệu = ['mười hai', '11', 10]
>>> đã sắp xếp(map(str, data))
['10', '11', 'mười hai']

Điều này là cần thiết vì hầu hết các so sánh giữa các loại đều đưa ra TypeError.

  • Xóa các giá trị đặc biệt trước khi sắp xếp:

>>> từ nhập toán isnan
>>> từ itertools nhập filterfalse
>>> data = [3.3, float('nan'), 1.1, 2.2]
>>> đã sắp xếp(filterfalse(isnan, data))
[1.1, 2.2, 3.3]

Điều này là cần thiết vì IEEE-754 standard chỉ định rằng "Mọi NaN sẽ so sánh không có thứ tự với mọi thứ, kể cả chính nó."

Tương tự, None cũng có thể bị xóa khỏi bộ dữ liệu:

>>> dữ liệu = [3.3, Không, 1.1, 2.2]
>>> được sắp xếp(x cho x trong dữ liệu nếu x không phải là Không)
[1.1, 2.2, 3.3]

Điều này là cần thiết vì None không thể so sánh được với các loại khác.

  • Chuyển đổi các loại ánh xạ thành danh sách mục được sắp xếp trước khi sắp xếp:

>>> dữ liệu = [{'a': 1}, {'b': 2}]
>>> được sắp xếp(dữ liệu, key=lambda d: được sắp xếp(d.items()))
[{'a': 1}, {'b': 2}]

Điều này là cần thiết vì so sánh dict-to-dict sẽ tăng TypeError.

  • Chuyển đổi các loại tập hợp thành danh sách được sắp xếp trước khi sắp xếp:

>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> đã sắp xếp(bản đồ(đã sắp xếp, dữ liệu))
[['a', 'b', 'c'], ['b', 'c', 'd']]

Điều này là cần thiết vì các phần tử chứa trong các kiểu tập hợp không có thứ tự xác định. Ví dụ: list({'a', 'b'}) có thể tạo ra ['a', 'b'] hoặc ['b', 'a'].

Tỷ lệ cược và kết thúc

  • Để sắp xếp nhận biết ngôn ngữ, hãy sử dụng locale.strxfrm() cho hàm chính hoặc locale.strcoll() cho hàm so sánh. Điều này là cần thiết vì thứ tự sắp xếp "theo bảng chữ cái" có thể khác nhau giữa các nền văn hóa ngay cả khi bảng chữ cái cơ bản giống nhau.

  • Tham số reverse vẫn duy trì độ ổn định sắp xếp (để các bản ghi có khóa bằng nhau vẫn giữ nguyên thứ tự ban đầu). Điều thú vị là hiệu ứng đó có thể được mô phỏng mà không cần tham số bằng cách sử dụng hàm reversed() dựng sẵn hai lần:

    >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> tiêu chuẩn_way = đã sắp xếp(dữ liệu, key=itemgetter(0), đảo ngược=True)
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
>>> khẳng định tiêu chuẩn_way == double_reversed
>>> đường tiêu chuẩn
[('đỏ', 1), ('đỏ', 2), ('xanh', 1), ('xanh', 2)]

  • Các thủ tục sắp xếp sử dụng < khi thực hiện so sánh giữa hai đối tượng. Vì vậy, thật dễ dàng để thêm thứ tự sắp xếp tiêu chuẩn vào một lớp bằng cách xác định phương thức __lt__():

    >>> Sinh viên.__lt__ = lambda self, other: self.age < other.age
>>> đã sắp xếp(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

    Tuy nhiên, lưu ý rằng < có thể quay lại sử dụng __gt__() nếu __lt__() không được triển khai (xem object.__lt__() để biết chi tiết về cơ chế). Để tránh những điều bất ngờ, PEP 8 khuyến nghị nên thực hiện tất cả sáu phương pháp so sánh. Trình trang trí total_ordering() được cung cấp để thực hiện công việc đó dễ dàng hơn.

  • Các chức năng chính không cần phụ thuộc trực tiếp vào các đối tượng được sắp xếp. Một chức năng chính cũng có thể truy cập các tài nguyên bên ngoài. Ví dụ: nếu điểm của học sinh được lưu trữ trong từ điển, chúng có thể được sử dụng để sắp xếp một danh sách tên học sinh riêng biệt:

    >>> sinh viên = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> đã sắp xếp(sinh viên, key=newgrades.__getitem__)
['jane', 'dave', 'john']

Sắp xếp một phần

Một số ứng dụng chỉ yêu cầu một số dữ liệu được sắp xếp. Thư viện tiêu chuẩn cung cấp một số công cụ thực hiện ít công việc hơn so với một loại đầy đủ:

  • min() và max() lần lượt trả về giá trị nhỏ nhất và lớn nhất. Các hàm này thực hiện một lần chuyển qua dữ liệu đầu vào và hầu như không cần bộ nhớ phụ.

  • heapq.nsmallest() và heapq.nlargest() lần lượt trả về giá trị nhỏ nhất và lớn nhất của n. Các hàm này thực hiện một lần chuyển dữ liệu chỉ giữ các phần tử n trong bộ nhớ tại một thời điểm. Đối với các giá trị của n nhỏ so với số lượng đầu vào, các hàm này thực hiện so sánh ít hơn nhiều so với sắp xếp đầy đủ.

  • heapq.heappush() và heapq.heappop() tạo và duy trì sự sắp xếp dữ liệu được sắp xếp một phần để giữ phần tử nhỏ nhất ở vị trí 0. Các chức năng này phù hợp để triển khai các hàng đợi ưu tiên thường được sử dụng để lập lịch tác vụ.