Chuyển đến nội dung
MINH VO Ghi chép từ công việc
của một kỹ sư tại Việt Nam
Cơ bản9 phút đọc

Dùng hai con trỏ để trộn danh sách điểm danh đã sắp

Trộn bản ghi đã sắp với quy tắc hòa ổn định, giữ đủ bản ghi trùng và mở rộng sang generator đọc dần mà không nhầm với phép hợp tập hợp.

Đồ thị vẽ bằng bút chì trên giấy màu be, với các đường màu ô liu nối những đỉnh

Trộn hai danh sách đã sắp chỉ cần đi qua mỗi danh sách một lần vì phần tử nhỏ nhất còn lại luôn nằm ở hai vị trí hiện tại. Nếu đang học thuật toán hai con trỏ, bạn có thể dùng ID điểm danh làm ví dụ, miễn là nêu rõ quy tắc đối với giá trị trùng. Phiên bản này giữ mọi bản ghi đầu vào, kể cả ID lặp lại.

Giả sử một buổi xuất [2, 4, 4, 9], buổi khác xuất [1, 4, 7]. Trộn có thứ tự cho [1, 2, 4, 4, 4, 7, 9]. Kết quả không khẳng định có bảy người khác nhau. Ba số bốn có thể là sự kiện riêng, dữ liệu xuất trùng hoặc bản ghi cần làm sạch sau. Xác định ý nghĩa bản ghi trùng là thao tác khác với sắp mọi bản ghi theo thứ tự.

Mỗi bước lấy đúng một bản ghi kế tiếp

Giữ chỉ số i trong danh sách trái và j trong danh sách phải. So hai giá trị chưa dùng kế tiếp rồi thêm giá trị nhỏ hơn vào đầu ra. Nếu bằng nhau, chọn bên trái trước. Chỉ tăng con trỏ của giá trị vừa thêm.

def merge_sorted(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

assert merge_sorted([2, 4, 4, 9], [1, 4, 7]) == [1, 2, 4, 4, 4, 7, 9]
assert merge_sorted([], [1, 1]) == [1, 1]
assert merge_sorted([], []) == []

Hai vòng sao chép phần đuôi chỉ chạy sau khi một bên đã hết. Các giá trị còn lại của bên kia đã có thứ tự, nên có thể thêm mà không cần so sánh chéo hai danh sách nữa. Cài đặt không đổi hai danh sách nguồn và tạo danh sách kết quả mới.

Trong ví dụ, một được lấy trước hai, rồi hai trước bốn. Sau đó so bốn với bốn nên số bốn đầu tiên bên trái được thêm. Số bốn thứ hai bên trái cũng thắng khi hòa. Bốn và bảy bên phải đi tiếp; chín còn lại bên trái được sao chép bởi vòng phần đuôi.

Trộn dãy trái hai, bốn, bốn, chín với dãy phải một, bốn, bảy; đầu ra giữ ba số bốn và ghi nguồn của từng bản ghiMở ảnh kích thước đầy đủ ↗

Hình đánh dấu nguồn của mỗi bản ghi đầu ra. Với giá trị bằng nhau, bản ghi trái đứng trước bản ghi phải; thứ tự bên trong từng nguồn được giữ nguyên. Đó là quy tắc xử lý hòa ổn định của ví dụ.

Phần đầu có thứ tự là bất biến

Trước mỗi lượt vòng chính, kết quả chứa đúng các phần đầu đã dùng của hai nguồn, theo thứ tự tăng. Mọi giá trị còn chờ đều không nhỏ hơn giá trị cuối đầu ra. Ban đầu kết quả và hai phần đã dùng đều rỗng nên các điều kiện đúng.

Vì từng đầu vào đã sắp, giá trị chưa dùng đầu tiên là giá trị nhỏ nhất còn lại của đầu vào đó. Giá trị nhỏ hơn trong hai ứng viên vì vậy là giá trị nhỏ nhất còn lại ở cả hai nơi. Thêm nó giữ thứ tự và bổ sung đúng một bản ghi vào các phần đầu đã dùng. Con trỏ được chọn tiến lên nên không lần xuất hiện nào bị thêm hai lần.

Khi một danh sách hết, mọi lần xuất hiện bên đó đã được tính đủ. Phần đuôi còn lại của bên kia đứng sau phần đầu đã tạo và có thể sao chép trực tiếp. Kết quả cuối dài len(left) + len(right), chứa mọi lần xuất hiện đầu vào và có thứ tự.

Lập luận này là bước trộn trong merge sort. Phần mergesort của Princeton giải thích cách trộn lặp các đoạn đã sắp tạo thuật toán sắp xếp đầy đủ. Trong bài này, nguồn đã sắp là điều kiện bên gọi cung cấp, nên chi phí tạo các nguồn đó nằm ngoài thao tác trộn.

Đếm số lần tiến trước khi đo thời gian

Nếu độ dài hai bên là m và n, con trỏ i tiến m lần, còn j tiến n lần. Mỗi lần thêm dùng một bản ghi. Tổng thời gian là Θ(m + n), nếu so sánh có chi phí hằng số và thêm cuối có chi phí khấu hao hằng số.

Khi cả hai đầu vào không rỗng, vòng chính thực hiện nhiều nhất m + n - 1 lần so sánh chéo. Đến đó ít nhất một danh sách phải hết, để lại phần tử cuối cho vòng phần đuôi. Có đầu vào cần ít so sánh hơn, chẳng hạn mọi giá trị trái đều nhỏ hơn giá trị phải đầu tiên.

Danh sách trả về giữ m + n tham chiếu, nên bộ nhớ đầu ra là Θ(m + n). Bản thân hai con trỏ chỉ cần O(1) bộ nhớ phụ. Nếu bên nhận xử lý từng bản ghi, generator có thể phát dần thay vì giữ toàn bộ kết quả. heapq.merge của Python hỗ trợ trộn lười các nguồn đã sắp và xử lý được hơn hai nguồn.

Trộn bản ghi mà chưa tạo toàn bộ đầu ra

Khóa sắp xếp và định danh bản ghi là hai việc khác nhau. Muốn quan sát tính ổn định, hãy gắn nhãn riêng cho những bản ghi có cùng ID và chỉ so ID. Generator dưới đây còn đổi cách trả kết quả: nó phát từng bản ghi khi bên gọi yêu cầu, thay vì xây ngay một danh sách đầy đủ.

def merge_records(left, right, key):
    left_iter, right_iter = iter(left), iter(right)
    missing = object()
    a = next(left_iter, missing)
    b = next(right_iter, missing)
    while a is not missing and b is not missing:
        if key(a) <= key(b):
            yield a
            a = next(left_iter, missing)
        else:
            yield b
            b = next(right_iter, missing)
    while a is not missing:
        yield a
        a = next(left_iter, missing)
    while b is not missing:
        yield b
        b = next(right_iter, missing)

seen = []
def observed(source, records):
    for record in records:
        seen.append((source, record[1]))
        yield record

left = [(4, 'L1'), (4, 'L2'), (9, 'L3')]
right = [(4, 'R1'), (7, 'R2')]
merged = merge_records(observed('left', left), observed('right', right),
                       key=lambda record: record[0])
assert seen == []
first = next(merged)
assert first == (4, 'L1')
assert seen == [('left', 'L1'), ('right', 'R1')]
assert [first, *merged] == [
    (4, 'L1'), (4, 'L2'), (4, 'R1'), (7, 'R2'), (9, 'L3'),
]

Lần yêu cầu đầu tiên chỉ đọc L1 và R1 cùng có ID bốn, phát L1 theo quy tắc ưu tiên trái và để L2, L3, R2 chưa được đọcMở ảnh kích thước đầy đủ ↗

Như tài liệu biểu thức yield của Python giải thích, tạo generator chưa làm phần thân chạy. Lần yêu cầu đầu đọc một bản ghi ở mỗi nguồn để so khóa, rồi phát L1. Bộ lặp trái chỉ tiến thêm khi mã tiếp tục sau lệnh phát đó. Các nhãn trong seen cho thấy việc đọc mà không cần đo thời gian. Cả hai nguồn đều phải đưa ứng viên tiếp theo trước khi hàm trộn có thể chọn an toàn.

Đối tượng đánh dấu riêng biểu diễn việc nguồn đã hết. Dùng một đối tượng riêng tránh nhầm nguồn cạn với bản ghi hợp lệ có giá trị None; bản ghi như vậy chỉ được chấp nhận nếu hàm khóa biết cách xếp nó. Dữ liệu thực tế của ví dụ là tuple ID-nhãn và hàm khóa yêu cầu đúng dạng này.

Generator giữ lượng trạng thái nhìn trước không đổi cho hai đầu vào và phát mỗi lần xuất hiện đúng một lần. Điều đó không giới hạn bộ nhớ mà bộ lặp đầu vào đã giữ hoặc bên gọi tiếp tục lưu. Chuyển generator thành danh sách vẫn cấp phát bộ nhớ tỷ lệ với tổng đầu ra. Lấy khóa cũng là một phần chi phí so sánh; nếu tính khóa tốn kém, hãy lưu khóa của bản ghi hiện giữ thay vì tính lại nhiều lần.

Quy tắc hòa ổn định giữ L1 và L2 trước R1, đồng thời giữ thứ tự từng nguồn. Sắp cả tuple sẽ đưa nhãn vào quy tắc thứ tự và tạo giao diện khác. Ví dụ giả định nguồn hữu hạn, đã sắp và có cách so khóa nhất quán. Hàm không vừa đọc vừa sắp, loại trùng hoặc kiểm tra lại các bên tạo dữ liệu.

Hãy lấy chỉ bản ghi đầu và xem nhật ký đọc, rồi dùng hết generator. Lặp lại với một nguồn rỗng và các ID bằng nhau có nhãn mà thứ tự chữ cái đi ngược thứ tự nguồn. Kiểm thử chỉ nhìn ID số không phát hiện được quy tắc hòa sai. Kiểm thử luôn chuyển hết thành danh sách cũng không chứng minh việc đọc dần.

Đổi yêu cầu một cách tường minh

Phép hợp tập hợp sẽ bỏ ID lặp. Phép giao giữ ID có mặt ở cả hai nguồn, nhưng vẫn cần quyết định giữ bao nhiêu lần xuất hiện. Các hàm đó cũng có thể dùng hai con trỏ, song nhánh bằng nhau và số lượng đầu ra khác. Dùng hàm trộn này rồi mặc nhiên coi nó đã loại trùng điểm danh sẽ cho kết quả nghiệp vụ sai.

Đầu vào chưa sắp phá vỡ chứng minh ngay. Trộn [4, 2] với [1, 3] có thể tạo [1, 3, 4, 2], vì thuật toán không tìm phía sau vị trí hiện tại để lấy giá trị nhỏ hơn. Có thể kiểm tra thứ tự bằng một lượt tuyến tính hoặc giao trách nhiệm bảo đảm cho bên tạo dữ liệu. Với bản ghi, so cùng khóa và cùng chiều mà cả hai nguồn đã dùng.

Các ca kiểm thử cần có bên rỗng, toàn bộ một bên đứng trước bên kia, giá trị xen kẽ và giá trị trùng qua cả hai nguồn. Muốn kiểm tra ổn định, gắn nhãn nguồn rồi chỉ so khóa số; số nguyên bằng nhau đứng riêng không cho biết thứ tự gốc có được giữ hay không. Kiểm tra lại danh sách đầu vào sau lời gọi nếu không thay đổi dữ liệu là một phần giao diện công khai.

Nguồn tham khảo & đọc thêm

  1. Python documentation, heapq.merge
  2. Princeton Algorithms, Mergesort
  3. Python language reference, Yield expressions
← Về trang bài viết

Hình minh họa

100%