Kiểm tra bộ so sánh trước khi tin vào kết quả sắp xếp

Thuật toán sắp xếp dựa vào bộ so sánh để mô tả một thứ tự nhất quán. Nếu bộ so sánh nói đá đứng trước kéo, kéo đứng trước giấy và giấy đứng trước đá, không dãy tuyến tính nào thỏa cả ba quan hệ. Với lập trình viên đang tìm nguyên nhân kết quả sắp xếp bất thường, kiểm tra bộ so sánh có thể phát hiện lỗi mà đổi thuật toán không sửa được.

Bộ so sánh ba kết quả trả số âm khi đối số đầu nên đứng trước đối số sau, 0 khi hai khóa tương đương để sắp xếp và số dương khi đối số đầu nên đứng sau. Chỉ dấu của kết quả khác 0 quyết định thứ tự; độ lớn không quan trọng. Hàm phải trả lời nhất quán trong suốt một lần sắp xếp.

Một chu trình có vẻ hợp lý khi xét từng cặp

Oẳn tù tì mô tả quan hệ thắng thua, không phải bảng thứ hạng có thể sắp xếp. Dùng chu trình đá trước kéo, kéo trước giấy, giấy trước đá. Mỗi cặp có một bên thắng, nhưng quan hệ không bắc cầu.

from functools import cmp_to_key

before = {('rock', 'scissors'), ('scissors', 'paper'), ('paper', 'rock')}


def cyclic_compare(a, b):
    if a == b:
        return 0
    return -1 if (a, b) in before else 1


ordered = sorted(['rock', 'scissors', 'paper'], key=cmp_to_key(cyclic_compare))
assert all(cyclic_compare(ordered[i], ordered[i + 1]) <= 0
           for i in range(len(ordered) - 1))
assert any(cyclic_compare(ordered[i], ordered[j]) > 0
           for i in range(len(ordered)) for j in range(i + 1, len(ordered)))

Phép xác nhận đầu kiểm tra các cặp kề nhau. Nó có thể đúng dù cùng bộ so sánh cho rằng một phần tử trước phải đứng sau một phần tử phía sau không liền kề. Với thứ tự bắc cầu, các cặp kề có thứ tự sẽ suy ra mọi cặp có thứ tự; chu trình làm mất suy luận ấy.

Dãy cụ thể mà thư viện tạo ra với bộ so sánh sai không phải hợp đồng có thể dựa vào trên mọi môi trường. Ví dụ chỉ thể hiện mâu thuẫn của quan hệ được yêu cầu. Không nên phụ thuộc vào một kết quả cụ thể từ một cài đặt sắp xếp cụ thể. Tài liệu hàm so sánh của Python giải thích cmp_to_key, bộ chuyển đổi hình thức gọi nhưng không sửa logic so sánh.

Mở ảnh kích thước đầy đủ ↗

Một bảng thứ hạng nhất quán cần quy tắc riêng, chẳng hạn điểm số, mức ưu tiên loại hoặc nhóm đồng hạng đã thống nhất. So sánh được mọi cặp không có nghĩa tất cả các cặp hợp lại thành một thứ tự.

Kiểm tra các luật trên miền nhỏ

Một giá trị phải so sánh bằng chính nó. Đảo hai đối số phải đảo dấu. Nếu A trước B và B trước C thì A phải trước C. Hai giá trị được xem là bằng nhau cũng phải có cùng quan hệ thứ tự với mọi giá trị thứ ba; nếu không, thay khóa tương đương này bằng khóa kia có thể đổi kết quả.

from itertools import product


def sign(number):
    return (number > 0) - (number < 0)


def audit_comparator(values, compare):
    values = tuple(values)
    failures = []
    for a in values:
        if compare(a, a) != 0:
            failures.append(('self', a))
    for a, b in product(values, repeat=2):
        if sign(compare(a, b)) != -sign(compare(b, a)):
            failures.append(('reversed-sign', a, b))
    for a, b, c in product(values, repeat=3):
        if compare(a, b) < 0 and compare(b, c) < 0 and compare(a, c) >= 0:
            failures.append(('transitivity', a, b, c))
        if compare(a, b) == 0 and sign(compare(a, c)) != sign(compare(b, c)):
            failures.append(('equivalent-keys', a, b, c))
    return failures

failures = audit_comparator(['rock', 'scissors', 'paper'], cyclic_compare)
assert sum(failure[0] == 'transitivity' for failure in failures) == 3
assert audit_comparator([-2, 0, 4], lambda a, b: (a > b) - (a < b)) == []
assert audit_comparator(iter(['rock', 'scissors', 'paper']), cyclic_compare) == failures

Hàm lưu miền hữu hạn vào một tuple duy nhất trước các lượt kiểm tra lặp. Cách này hỗ trợ iterator chỉ dùng được một lần và giữ O(k) tham chiếu tới các giá trị đã cho; nó không sao chép sâu nội dung của chúng. Đầu vào vô hạn nằm ngoài hợp đồng vì việc thu thập nó sẽ không kết thúc.

Kiểm tra này dùng O(k³) lời gọi so sánh cho miền có k giá trị, nên phù hợp với tập đại diện nhỏ hoặc việc xét hết một miền phân loại hữu hạn. Nó không chứng minh bộ so sánh đúng với bản ghi tùy ý, nhưng một bộ ba thất bại là phản ví dụ cụ thể để giữ làm kiểm thử hồi quy.

Hàm kiểm tra giả sử bộ so sánh trả về kết quả số hữu hạn thông thường. NaN không có dấu âm, không hoặc dương có ý nghĩa dưới những phép kiểm tra này và cần bị từ chối riêng. Bộ so sánh cũng phải đủ thuần để các lời gọi lặp với cùng đối số không đổi trả cùng đáp án; một lần quan sát chuỗi lời gọi không chứng minh tính chất đó trong mọi trường hợp.

Ưu tiên khóa tường minh khi thứ tự có nhiều thành phần

Với bản ghi sắp theo ưu tiên, thời gian rồi mã định danh, khóa tuple biểu diễn trực tiếp thứ bậc. Nó cũng cho phép tính trường dẫn xuất đắt tiền một lần trên mỗi bản ghi khi API lưu khóa, như các hàm sắp xếp của Python. Những nhánh so sánh lồng nhau viết tay dễ bỏ sót tình huống bằng nhau hoặc đảo chiều một trường.

Giá trị thiếu cần chính sách vị trí. Khóa như (value is None, value if value is not None else 0) đặt giá trị số thiếu ở cuối, đồng thời giữ các số hữu hạn theo thứ tự. NaN cần xử lý riêng vì nó không phải None và không tuân theo các luật so sánh số thông thường. Hãy quy định ứng dụng từ chối, phân nhóm hay coi nó là thiếu.

Đừng dùng bộ so sánh đọc một điểm số bên ngoài đang thay đổi trong lúc sắp xếp. Nếu hai lời gọi thấy hai điểm khác nhau, mỗi phép so sánh riêng có vẻ hợp lý nhưng chúng vẫn có thể mâu thuẫn. Hãy chụp khóa trước khi bắt đầu hoặc đồng bộ dữ liệu theo yêu cầu nhất quán của ứng dụng.

Tính ổn định không sửa được quan hệ mâu thuẫn

Phép sắp xếp ổn định giữ thứ tự đầu vào của các khóa tương đương. Nó vẫn cần các nhóm tương đương và thứ tự giữa chúng nhất quán. Ví dụ chu trình không có hai loại khác nhau được coi là bằng nhau, nên bảo đảm ổn định không có gì để giữ nhằm giải quyết chu trình.

JavaScript cũng yêu cầu bộ so sánh hợp lệ. Phần thảo luận của MDN cho thấy bộ so sánh sai có thể tạo kết quả khác nhau giữa các máy thực thi. Chỉ trả 1 hoặc 0 cho so sánh tăng dần là lỗi thường gặp vì đổi chỗ đối số không luôn đảo dấu.

Hãy kiểm thử các khóa bằng nhau có danh tính bản ghi khác nhau, từng trường tùy chọn và giá trị số cực trị. Với tập loại hữu hạn, xét mọi bộ ba. Khi có phản ví dụ, quyết định quy tắc thứ hạng mong muốn trước khi đổi mã. Thuật toán sắp xếp tổ chức được một thứ tự nhất quán; nó không thể thay ứng dụng chọn chính sách nhất quán.

Dung sai có thể phá ý nghĩa của bằng nhau

Bộ so sánh vẫn có thể sai khi không có chu trình oẳn tù tì. Giả sử nó coi hai số đo cách nhau không quá một đơn vị là bằng nhau. Giá trị 0 gần 0,75, và 0,75 gần 1,5, nhưng 0 không gần 1,5. Quan hệ gần nhau giữa từng cặp không chia các số đo thành những nhóm tương đương nhất quán.

def tolerance_compare(a, b):
    if abs(a - b) <= 1:
        return 0
    return (a > b) - (a < b)

measurements = [0.0, 0.75, 1.5]
assert tolerance_compare(0.0, 0.75) == 0
assert tolerance_compare(0.75, 1.5) == 0
assert tolerance_compare(0.0, 1.5) < 0
failures = audit_comparator(measurements, tolerance_compare)
assert any(failure[0] == 'equivalent-keys' for failure in failures)

Hai số đo đầu tự nhận có thể thay thế nhau khi sắp xếp, nhưng quan hệ của chúng với số đo thứ ba lại khác. Giá trị 0 phải đứng trước 1,5, còn 0,75 lại nhận là đồng hạng với nó. Phép sắp xếp ổn định không suy ra được yêu cầu mâu thuẫn nào nên được ưu tiên. Tăng hoặc giảm dung sai không loại bỏ vấn đề một cách tổng quát; các vùng lân cận chồng nhau vẫn có thể tạo mẫu này.

Mở ảnh kích thước đầy đủ ↗

Nếu sản phẩm thực sự cần các dải số đo cố định, hãy định nghĩa trực tiếp các dải. Với số hữu hạn, phép lấy sàn tạo khoảng [k, k + 1) mang nhãn số nguyên k. Các giá trị cùng khóa dải khi đó có cùng quan hệ với mọi dải khác. math.floor của Python trả số nguyên lớn nhất không vượt quá đầu vào, kể cả khi đầu vào âm.

from math import floor


def band_compare(a, b):
    ka, kb = floor(a), floor(b)
    return (ka > kb) - (ka < kb)

assert audit_comparator(measurements, band_compare) == []
assert sorted([1.5, 0.75, 0.0], key=floor) == [0.75, 0.0, 1.5]
assert floor(-0.1) == -1
assert floor(0.99) != floor(1.01)

Các bản ghi 0 và 0,75 giữ thứ tự đầu vào vì khóa dải bằng nhau. Kết quả có thứ tự theo dải, chưa chắc theo số đo gốc bên trong dải. Phép xác nhận cuối thể hiện đánh đổi: hai giá trị chỉ cách nhau 0,02 có thể nằm ở hai dải khác nhau khi chúng ở hai phía của biên. Dải cố định là chính sách nhất quán, nhưng không thực hiện phân nhóm từng cặp “cách nhau không quá một đơn vị”.

Giao diện cũng có thể sắp theo số đo gốc và chỉ làm tròn nhãn hiển thị. Hai hàng có thể hiện cùng nhãn đã làm tròn mà vẫn giữ thứ tự nền xác định. Việc đó có chấp nhận được hay không là quyết định trình bày, riêng với tính nhất quán toán học của bộ so sánh. Hãy chọn rõ thay vì giấu quy tắc gần bằng bên trong phép sắp xếp.

Để luyện tập, thử số âm quanh biên dải và bản ghi cùng dải nhưng khác danh tính. Kiểm tra các luật của bộ so sánh dải trên miền nhỏ ấy, rồi xác nhận phép sắp xếp khóa ổn định giữ thứ tự danh tính trong từng dải. Giữ chính sách từ chối hoặc xếp số không hữu hạn riêng: cả so sánh dung sai lẫn lấy sàn đều không tự cung cấp chính sách ứng dụng cho NaN.