Sắp xếp một tập tin 20GB với một chuỗi mỗi dòng

Question

Trong câu hỏi 11,5 của cuốn sách Gayle Laakman của, Cracking Phỏng vấn kỹ thuật,

"Hãy tưởng tượng bạn có một tập tin 20GB với một chuỗi trên mỗi dòng. Giải thích làm thế nào bạn sẽ sắp xếp các tập tin" Phản ứng ban đầu của tôi chính xác là giải pháp mà cô ấy đề xuất - chia nhỏ tệp thành các phần nhỏ hơn (megabyte) bằng cách đọc trong dữ liệu của X mb, phân loại và sau đó ghi nó vào đĩa. Và cuối cùng, hợp nhất các tập tin.

Tôi quyết định không theo đuổi phương pháp này vì hợp nhất cuối cùng sẽ liên quan đến việc lưu giữ tất cả dữ liệu trong bộ nhớ chính - và chúng tôi giả định rằng điều đó là không thể. Nếu đó là trường hợp, giải pháp này giữ chính xác như thế nào?

Cách tiếp cận khác của tôi dựa trên giả định rằng chúng tôi có dung lượng đĩa gần như không giới hạn hoặc ít nhất là đủ để giữ 2X dữ liệu chúng tôi đã có. Chúng ta có thể đọc trong dữ liệu của X mb và sau đó tạo ra các khóa băm cho chúng - mỗi khóa tương ứng với một dòng trong một tệp. Chúng tôi sẽ tiếp tục làm điều này cho đến khi tất cả các giá trị đã được băm. Sau đó, chúng ta chỉ cần ghi các giá trị của tập tin đó vào tập tin gốc.

Hãy cho tôi biết suy nghĩ của bạn.

Answer 1

http://en.wikipedia.org/wiki/External_sorting cung cấp giải thích chi tiết hơn về cách sắp xếp bên ngoài hoạt động. Nó giải quyết mối quan tâm của bạn cuối cùng phải đưa toàn bộ 20gB vào bộ nhớ bằng cách giải thích cách bạn thực hiện kết hợp cuối cùng của N được sắp xếp khối bằng cách đọc trong khối của các khối được sắp xếp như trái ngược với đọc trong tất cả các khối được sắp xếp cùng một lúc.