Sắp xếp tệp 1TB trên máy có RAM 1GB

Question

Câu hỏi này có vẻ dễ dàng, nhưng tôi không thể hiểu được công việc thực sự đằng sau nó. Tôi biết mọi người sẽ nói, chia nhỏ thành các khối 512 Megs và sắp xếp chúng như sử dụng Merge Sort bằng cách sử dụng Map reduce.

Vì vậy, đây là câu hỏi thực tế tôi có:

Giả sử tôi phá vỡ các tập tin vào 512 Megs đoạn và sau đó gửi đến các máy chủ khác nhau để sắp xếp chúng. giả sử các máy này sử dụng Sắp xếp Hợp nhất. Bây giờ, tôi đã có 2000 máy được phân loại 2000, 512 megabyte. Bây giờ khi tôi hợp nhất chúng lại, nó hoạt động như thế nào? Sẽ không phải là kích thước tiếp tục tăng trở lại? Ví dụ kết hợp hai 512 megs sẽ làm cho 1024Megs là kích thước của bộ nhớ RAM của tôi như thế nào sẽ làm việc này? Bất kỳ máy nào không thể hợp nhất đoạn lớn hơn 512 megabyte với một đoạn khác vì sau đó kích thước> 1 GB.

Làm cách nào để kết thúc quá trình hợp nhất, tôi có thể hợp nhất hai đoạn 0,5 TB với đoạn 0,5 TB khác. Khái niệm về Bộ nhớ ảo có được phát ở đây không?

Tôi ở đây để làm rõ những điều cơ bản của tôi và tôi hy vọng tôi đang yêu cầu câu hỏi này rất quan trọng (chính xác) một cách chính xác. Ngoài ra, những người nên làm điều này hợp nhất (sau khi phân loại)? Máy của tôi hoặc một vài trong số 2000 máy đó?

Answer 1

Đây là một cách lý thuyết nên hoạt động. Giả sử bạn đã có các tệp 2000 512MB của mình, sẵn sàng tạo một tệp 1TB.

Nếu bạn chỉ cần lặp qua mọi tệp, hãy tìm giá trị nào có giá trị FIRST thấp nhất, sau đó chuyển giá trị đó vào tệp đích và lặp lại sau đó bạn sẽ kết thúc với mọi thứ theo thứ tự. Việc sử dụng RAM sẽ rất nhỏ vì bạn sẽ không bao giờ cần phải mở nhiều hơn một dòng tại một thời điểm.

Rõ ràng bạn sẽ có thể tối ưu hóa điều này - giữ dòng đầu tiên của mọi tệp trong RAM khi bạn đi và nó sẽ nhanh hơn một chút.

Answer 2

Phiên bản ngắn gọn về cách bạn hợp nhất như thế này:

1) Bạn tạo bảng có một vị trí cho mỗi máy bạn đang hợp nhất.

2) Bạn yêu cầu mỗi máy cho mục nhập thấp nhất mà chúng có mà chúng chưa cung cấp cho bạn.

3) Bạn xóa mục nhập có giá trị thấp nhất khỏi bảng, xuất ra và yêu cầu máy đó nạp chậm với mục nhập thấp nhất mà nó chưa cung cấp cho bạn, để trống nếu máy không có mục nhập .

4) Bạn lặp lại bước 3 cho đến khi bảng trống.

Điều này cho phép bạn hợp nhất từ ​​các máy N chỉ lưu trữ N mục tại một thời điểm. Tất nhiên, bạn có thể tối ưu hóa trivially nó để giữ M mục từ mỗi máy. Trong trường hợp đó, bạn cần lưu trữ các mục N * M và khi một vùng trống, hãy yêu cầu máy đó cho các mục M nạp tiền vào nó.

Answer 3

Điều tuyệt vời về sắp xếp hợp nhất là bạn không cần quyền truy cập ngẫu nhiên; truy cập tuần tự sẽ làm. Đó là những gì làm cho nó một giải pháp hoàn hảo khi tập dữ liệu sẽ không phù hợp trong bộ nhớ.

Một lần nhập hợp nhất yêu cầu 2 (hoặc nhiều) đầu vào và tạo ra một đầu ra. Bạn chỉ cần tiếp tục kết hợp đầu vào vào đầu ra cho đến khi chỉ còn lại một tệp.

Answer 4

Bây giờ, tôi có 2000 máy được sắp xếp 2000, 512 megabyte đoạn.Bây giờ khi tôi hợp nhất chúng lại, nó hoạt động như thế nào? Sẽ không kích thước tiếp tục trên tăng trở lại? Ví dụ, việc kết hợp hai 512 megabyte sẽ làm cho 1024Megs kích thước bộ nhớ RAM của tôi sao cho nó hoạt động như thế nào? Bất kỳ máy nào cũng không thể hợp nhất đoạn lớn hơn 512 megabyte với một đoạn khác vì rồi kích thước> 1 GB.

Đó không phải là cách triển khai thực hiện hợp nhất thực tế. Điều thú vị về mergesort (và các thuật toán sắp xếp liên quan) là bạn không cần phải có toàn bộ tập dữ liệu trong bộ nhớ để làm cho nó hoạt động. Khi hợp nhất bạn chỉ cần đọc vào bộ nhớ một phần nhỏ của tập tin tại một thời điểm, sau đó sẽ được viết ra sau đó.

Nói cách khác, bạn không cần truy cập ngẫu nhiên để hợp nhất. Nếu nó không được cho tài sản tốt đẹp này sẽ là không thể sort the data on tape drives với công nghệ có sẵn tại thời điểm đó. Ổ đĩa băng tất nhiên không phải là phương tiện truy cập ngẫu nhiên và RAM sau đó được đo bằng kilobyte.

Answer 5

Sự cố này có thể bị giảm xuống một vấn đề đơn giản hơn. Vấn đề này được thiết kế để buộc bạn phải tiếp cận. Dưới đây là:

• Chọn khối = ~ 1GB, sắp xếp & lưu trữ chúng dưới dạng tệp được phân loại riêng biệt.
• Bạn kết thúc với 1000 tệp được sắp xếp 1 GB trên hệ thống tệp.

• Bây giờ, vấn đề đơn giản là sáp nhập các mảng được sắp xếp k thành một mảng mới.

  Việc hợp nhất các mảng được sắp xếp theo thứ tự k cần bạn duy trì một phút (Hàng đợi ưu tiên) với các phần tử k tại một thời điểm.

ví dụ k = 1.000 (file) trong trường hợp của chúng tôi. (1GB ram có thể lưu trữ 1000 số)

Vì vậy, hãy giữ nguyên tố từ hàng đợi ưu tiên và lưu vào đĩa.

Bạn sẽ có tệp mới, sắp xếp kích thước 1TB.

Tham khảo: http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Cập nhật

PS: có thể được thực hiện trên một máy duy nhất với GB RAM 1 với một cấu trúc dữ liệu tốt hơn

Merge có thể được thực hiện trong vòng chưa đầy O (N) không gian với Hàng đợi ưu tiên tức là Không gian O (K) tức là trung tâm của vấn đề.