Hai bản sao của cùng dãy chưa sắp xếp
Đọc dãy A từ tệp trước khi đo. Với mỗi lượt, tạo B=A.copy() và C=A.copy() trước đoạn tính thời gian; không dùng kết quả đã sắp xếp của thuật toán đầu làm đầu vào thuật toán sau.
Dùng perf_counter lấy thời điểm trước và sau từng thuật toán. Bản trộn trả dãy nên cần giữ kết quả; bản chèn sửa C nên kiểm C sau khi gọi. Cả hai kết quả cần khớp dãy sắp xếp đúng, đồng thời giữ đủ phần tử.
Trong tệp thực hành, benchmark thực hiện các bước ấy và trả thời gian trung bình ms/lần. Tạo bản sao, đọc tệp và kiểm kết quả đều ở ngoài hai đoạn đo.
Thực hiện và đọc bảng số đo
Chạy với tệp mẫu:
```text
python3 g11-cs-sap-xep-tron.py do g11-cs-day-can-sap-xep.inp --repeat 100
```
Bảng có số phần tử n, số lần đo, thời gian trộn và chèn tính bằng ms/lần. Cột nào nhỏ hơn thì thuật toán đó nhanh hơn trong lượt đo này. Có thể đổi dữ liệu thành dãy tăng, giảm hoặc có giá trị trùng và đo lại với cả hai bản trên cùng dữ liệu mới.
Tệp mẫu chỉ có 6 phần tử nên chưa đủ đại diện cho dãy lớn. Số đo phụ thuộc dữ liệu, máy, phiên bản Python và nhiễu thời gian; không dùng một lượt nhỏ để kết luận thuật toán luôn nhanh hơn. Trong trường hợp xấu nhất, chèn có O(n²), trộn có O(n log n); chèn có thể chạy tốt khi dãy đã gần hoặc đúng thứ tự.
Bài luyện
Cách chuẩn bị nào giúp so sánh hai thuật toán trên cùng dữ liệu?
Hai đoạn đo sẽ không cùng phạm vi công việc.
Hai thuật toán nhận cùng số lượng, giá trị và thứ tự ban đầu.
Đã thay đổi thứ tự đầu vào của thuật toán thứ hai.
Khác dữ liệu làm phép so sánh thiếu căn cứ.
Lời giải
Đọc dữ liệu và tạo B,C ngoài đoạn đo. Mỗi thuật toán nhận một bản sao giống dãy gốc, giúp khác biệt số đo gắn với cách sắp xếp trong cùng điều kiện.
Bài luyện
Một lượt đo 6 phần tử cho chèn nhanh hơn trộn. Kết luận nào phù hợp?
Không thể khái quát từ một dãy nhỏ.
Tốc độ chỉ có ý nghĩa khi kết quả đúng.
Số đo có phạm vi theo dữ liệu và môi trường thực nghiệm.
Bậc tăng khi n lớn không quyết định mọi dãy nhỏ.
Lời giải
Dãy nhỏ chịu ảnh hưởng của chi phí gọi hàm và điều kiện máy. Kết quả mô tả lượt đo đã làm; cần thêm dữ liệu/kích thước trước khi nhận xét rộng hơn.
Bài luyện
Vì sao cần giữ result=mergeSort(B) trong phép đo?
Đó không phải hợp đồng của bản mergeSort này.
Thuật toán giữ đủ phần tử trùng.
Hàm vẫn chạy nhưng kết quả có thể bị bỏ mất.
Kết quả trả về cần được đối chiếu, không chỉ đo thời gian.
Lời giải
Bản mergeSort trả dãy kết quả và không sửa B. Phép gán không quyết định hàm có chạy hay không, nhưng cần để xác nhận kết quả sau đoạn đo là đúng.
Đang học