External Sorting

Nghe thật bất khả thi, làm sao có thể mở được file to như vậy chứ, chắc chắn máy sẽ bị treo. Ồ không, có cách đó. Hôm nay mình sẽ hướng dẫn các bạn thực hiện sort 1 file lớn và demo trực tiếp bằng máy của mình với file nặng 11GB, giả định rằng mình chỉ có 1G RAM. Đảm bảo rằng các bạn sẽ tự tin trả lời câu hỏi này nếu được phỏng vấn. OK cùng bắt đầu nhé.

Phân tích

• Đầu tiên để sort được thì phải đọc được file đã. Nhưng làm sao mà có thể đọc được file lớn như thế? Thay vì đọc toàn bộ file một lúc thì ta có thể đọc file dưới dạng stream. Bằng cách này, ta không cần phải load toàn bộ file cùng một lúc lên RAM.

• Vậy thì nếu chỉ load 1 phần của file lên được, ta có thể chia 1 file gốc ban đầu thành n file nhỏ hơn sao cho có thể đọc được toàn bộ 1 file nhỏ đó rồi thực hiện sort. Khi sort xong ta có thể merge n file đó thành file ban đầu. Ví dụ file có 20GB, mình sẽ chia thành 20 file nhỏ hơn thành mỗi file 1GB, sort từng file một rồi ghép chúng lại với nhau.

  

  

• Merge các file đã sắp xếp y hệt thủ tục merge 2 array đã sắp xếp trong Merge sort

  

• Khi sort file nhỏ, các bạn nên xem xét dữ liệu đầu vào như thế nào để chọn thuật toán tương ứng. Nếu file random thì có thể chọn QuickSort. Ở đây do mình sinh test bằng random số nên chọn QuickSort là hợp lý

Demo

• File input của mình có 1 tỉ số int, mỗi số nằm trên 1 dòng. Tổng dung lượng của file khoảng 11GB

• Kết quả tổng thời gian hết khoảng 18 phút, với RAM sử dụng thời điểm cao nhất khoảng gần 800MB

  

Link

• github repo của mình: https://github.com/huynguyen411/External-Sort