Sắp xếp dữ liệu lớn hơn kích thước RAM

Question

Đây là câu hỏi phỏng vấn của Google: Cho 2 máy, mỗi máy có RAM 64 GB, chứa tất cả số nguyên (8 byte), sắp xếp toàn bộ dữ liệu 128 GB. Bạn có thể giả định một lượng RAM nhỏ. Mở rộng điều này để sắp xếp dữ liệu được lưu trữ trong 1000 máy.

Tôi đã đưa ra sắp xếp bên ngoài. Trong đó chúng tôi chia toàn bộ dữ liệu thành các phần và sử dụng sắp xếp hợp nhất trên chúng. Đó là lần đầu tiên sắp xếp các khối và đặt chúng trở lại và nhận được chúng một lần nữa mảnh khôn ngoan và hợp nhất chúng. Có cách nào tốt hơn? Điều gì sẽ phức tạp?

Answer 1

Mỗi 64 GB có thể được sắp xếp bằng cách sử dụng một cách nhanh chóng và sau đó sử dụng bộ nhớ ngoài giữ con trỏ ở đầu của cả hai mảng 64GB, cho phép xem xét chúng tôi muốn RAM1 và RAM2 theo thứ tự đó để có toàn bộ dữ liệu, tiếp tục tăng con trỏ tại RAM1 nếu nó nhỏ hơn thì giá trị con trỏ tại RAM2 khác trao đổi giá trị với RAM2 cho đến khi con trỏ đến cuối RAM1.

lấy cùng một khái niệm để sắp xếp tất cả N RAM. Hãy cặp của họ và sắp xếp bằng cách sử dụng phương pháp trên. Bạn còn lại với N/2 RAM được sắp xếp. Sử dụng khái niệm tương tự ở trên đệ quy.

Answer 2

ChingPing đề xuất loại O (n log n) cho mỗi tập hợp con, theo sau là hợp nhất tuyến tính (bằng cách hoán đổi các phần tử). Vấn đề với Quicksort (và hầu hết các loại n đăng nhập, là chúng yêu cầu bộ nhớ n. Tôi khuyên bạn nên sử dụng một số SmoothSort sử dụng bộ nhớ không đổi, vẫn chạy trong O (n log n)

kịch bản trường hợp là nơi bạn có cái gì đó như:.

setA = [maxInt .. 1] 
setB = [0..minInt] 

nơi cả hai bộ được sắp xếp theo hướng ngược lại, nhưng sau đó sáp nhập là theo thứ tự ngược

The (IMO - rõ ràng hơn) giải thích về giải pháp ChingPing là :

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array 
While setA's pointer is not at the end 
    if (setA[pointerA] < setB[pointerB]) 
    then { pointerA++; } 
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; } 

Bây giờ cả hai bộ sẽ được sắp xếp.

Answer 3

Đã có câu trả lời cho trường hợp máy 2.

Tôi giả định rằng 128GB dữ liệu cần sắp xếp được lưu trữ dưới dạng một tệp duy nhất trên một ổ đĩa cứng (hoặc bất kỳ thiết bị ngoại vi nào). Không có vấn đề bao nhiêu máy hoặc ổ đĩa cứng được sử dụng, thời gian cần để đọc các tập tin 128GB ban đầu và ghi các tập tin 128GB được sắp xếp vẫn giữ nguyên. Các khoản tiết kiệm duy nhất xảy ra trong các loại ram dựa trên nội bộ để tạo ra các khối dữ liệu được sắp xếp. Thời gian cần để hợp nhất với ổ cứng n + 1 để thực hiện hợp nhất n-way thành một tệp 128GB được sắp xếp duy nhất trên ổ đĩa cứng còn lại vẫn giữ nguyên, bị giới hạn bởi thời gian cần để ghi tệp 128GB được sắp xếp vào phần còn lại ổ cứng.

Đối với máy n, dữ liệu sẽ được chia thành các khối 128GB/n. Mỗi máy có thể thay thế đọc các phần con, có thể là 64MB tại một thời điểm, để giảm chi phí truy cập ngẫu nhiên, do đó máy "cuối cùng" không chờ tất cả các máy trước đó đọc tất cả các khối của chúng trước khi nó bắt đầu .

Đối với các máy n (64GB ram mỗi) và n + 1 ổ đĩa cứng với n> = 4, loại bố cục với độ phức tạp thời gian O (n) có thể được sử dụng bởi mỗi máy để tạo 32GB hoặc khối nhỏ hơn trên n làm việc ổ đĩa cứng cùng một lúc, theo sau là một cách hợp nhất n-bit vào ổ cứng đích.

Có một điểm thu nhỏ làm giảm giới hạn lợi ích của n lớn hơn. Một nơi nào đó ngoài n> 16, thông lượng hợp nhất nội bộ có thể lớn hơn băng thông I/O đĩa.Nếu quá trình hợp nhất là cpu bị ràng buộc hơn là I/O bị ràng buộc, có một thương mại tắt trong cpu overhead cho thời gian cần để tạo ra các khối song song so với phí hợp nhất lớn hơn thời gian I/O.