Thuật toán phân loại từng phần

Question

Giả sử tôi có 50 triệu đối tượng địa lý, mỗi tính năng đến từ đĩa.

Khi bắt đầu chương trình, tôi xử lý từng tính năng và tùy thuộc vào một số điều kiện, tôi áp dụng một số sửa đổi cho một số điều kiện.

Điểm này trong chương trình của tôi, tôi đang đọc một tính năng từ đĩa, xử lý và viết lại, vì tôi không có đủ ram để mở tất cả 50 triệu tính năng cùng một lúc.

Bây giờ nói rằng tôi muốn sắp xếp 50 triệu tính năng này, có bất kỳ thuật toán tối ưu nào để làm điều này vì tôi không thể tải tất cả mọi người cùng một lúc không?

Giống như thuật toán phân loại từng phần hoặc một cái gì đó tương tự?

Answer 1

Nói chung, loại thuật toán bạn đang tìm kiếm được gọi là external sorting. Có lẽ ví dụ nổi tiếng nhất về thuật toán phân loại như vậy được gọi là Merge sort.

Ý tưởng của thuật toán này (phiên bản bên ngoài) là bạn chia dữ liệu thành các phần mà bạn có thể sắp xếp tại chỗ trong bộ nhớ (nói 100 nghìn) và sắp xếp từng khối một cách độc lập (sử dụng một số thuật toán chuẩn như Quick sort) . Sau đó, bạn lấy các khối và hợp nhất chúng (vì vậy bạn hợp nhất hai khối 100k thành một khối 200k) có thể được thực hiện bằng cách đọc các phần tử từ cả hai khối vào bộ đệm (vì các khối đã được sắp xếp). Cuối cùng, bạn hợp nhất hai khối nhỏ hơn thành một khối sẽ chứa tất cả các phần tử theo thứ tự đúng.

Answer 2

Nếu bạn đang ở trên Unix, sử dụng sort;)

Nó có vẻ ngu ngốc nhưng công cụ dòng lệnh đã được lập trình để xử lý trường hợp này và bạn sẽ không cần phải lập trình lại nó.