Cho số nguyên 100 GB Dữ liệu trên đĩa cứng có RAM lên đến 2 GB, cách sắp xếp các số nguyên với hoạt động đĩa tối thiểu. Ở đây lấy một số từ đĩa được coi là một hoạt động đĩa (mặc dù trong thực tế một khối dữ liệu có thể được lấy).Sắp xếp số lượng lớn các số nguyên từ đĩa cứng
Chúng tôi có thể sử dụng thêm dung lượng trên đĩa để lưu trữ tạm thời và không cần xem xét các hoạt động làm sạch các khoảng trống tạm thời được sử dụng.
Như những người khác đã lưu ý, bạn có thể sử dụng O (n) counting sort. Tuy nhiên có một số vấn đề khác mà bạn cần xem xét. Giả sử bạn đang lưu trữ các số nguyên 32 bit, vì vậy inte 100GB ~ 27e9.
Nếu tất cả các số nguyên đều giống nhau, thì nó sẽ xuất hiện ~ 27e9 lần, lớn hơn 32 bit int. Do đó, bộ đếm của bạn sẽ phải là số nguyên 64 bit.
Với 2GB RAM, bạn chỉ có thể lưu trữ ~ 125e6 bộ đếm trong RAM cùng một lúc. Nếu chúng ta không thể thực hiện bất kỳ giả định về sự phân bố của số nguyên, chúng ta sẽ có thể sở để:
Tôi nghĩ tùy chọn thứ hai tốt hơn. Vì chúng tôi cần ~ 4e9 bộ đếm 64 bit và chỉ có thể lưu trữ 2GB, chúng tôi sẽ cần phải chạy toàn bộ mảng ~ 16 lần. Tùy chọn đầu tiên rõ ràng là không tốt nếu chúng ta xem xét việc gặp phải một chuỗi các số nguyên như 0,1 < < 31,0. Các bộ đếm này sẽ không được lưu trữ trong RAM cùng một lúc và do đó ít nhất phải ghi 2 HD.
Bởi vì điều này, tôi nghĩ về kích thước cụ thể của vấn đề (100GB), sắp xếp N-way merge sẽ tốt hơn, vì điều này chỉ yêu cầu đọc toàn bộ log_2 (100) ~ 8 lần.
Tuy nhiên, nếu người phỏng vấn ngay lập tức thay đổi câu hỏi thành "mảng 10TB, vẫn còn 2GB RAM", thì việc đếm sắp xếp sẽ dễ dàng giành chiến thắng.
Điều gì sẽ xảy ra nếu mảng lớn hơn 16 Exabyte? –
Merge Sort là một phương pháp phổ biến khi nói đến bộ nhớ hạn chế
Trên thực tế không có, bất lợi chính của loại sáp nhập trên quicksort và heapsort là yêu cầu của bộ nhớ bổ sung, mà khoảng bằng gấp đôi so với bộ nhớ dữ liệu nguồn. –
Pháo thủ, thực sự, không :) bạn có lẽ đang nghĩ về các thuật toán sắp xếp bộ nhớ chính, đó không phải là cuộc thảo luận ở đây. –
100GB dữ liệu số nguyên có nghĩa là bạn sẽ có một số lượng lớn các dữ liệu trùng lặp. Cá nhân tôi chọn phương pháp tiếp cận (bucketsort/selection)/mergesort làm bản năng đầu tiên của tôi nếu tôi đang cố gắng giảm thiểu I/O đĩa.
Đầu tiên đọc một chút dưới 1 Gig dữ liệu vào bộ nhớ, hợp nhất dữ liệu đó trong bộ nhớ. Xả vào đĩa. Lặp lại cho mỗi đoạn bộ nhớ. Sau đó, bạn có thể đi từng đoạn dữ liệu và lấy tất cả các số 0, lặp lại cho mỗi số nguyên. Nó sẽ mất một thời gian dài, nhưng đó chỉ là 203GB Đọc và 200GB viết trường hợp xấu nhất (lý thuyết).
Nếu bạn có RAM 2GB, tại sao chỉ đọc 1GB mỗi lần? – Gabe
Sắp xếp hợp nhất yêu cầu O (n) bộ nhớ bổ sung. – OmnipotentEntity
Bạn đang cố gắng giảm thiểu hoạt động của đĩa và không có giới hạn về hoạt động của CPU. Bạn có thể thực hiện hợp nhất trong O (1) khoảng trống bổ sung nếu bạn hợp nhất trong thời gian CPU O (n^2). Cá nhân, mặc dù, tôi sẽ chỉ đọc trong 2GB và QuickSort nó. – Gabe
Tôi nghĩ rằng đối với thuật toán nhanh, 100 GB không gian HDD miễn phí khác là điều kiện tiên quyết.
Chỉ cần sử dụng bất kỳ loại nào trên khối 2GB và đặt chúng trở lại. Bây giờ bạn có 50 khối được sắp xếp trong tập tin, và bạn cand sử dụng sắp xếp hợp nhất theo đề xuất của Mihir trên chúng. Ghi bộ đệm đầu ra khi nó điền vào tệp đầu ra. Bạn sẽ chỉ cần tinh chỉnh kích thước bộ đệm đầu vào và đầu ra.
Có một số giải pháp có tính. Nó không thể được sử dụng trên phạm vi rộng lớn như vậy và số lượng tối đa có thể. Bạn chỉ có thể lưu trữ các bộ đếm QWORD trên đĩa, nhưng điều này có nghĩa là nhiều truy cập ngẫu nhiên, điều đó chắc chắn sẽ chậm hơn so với làm việc với các bộ đệm lớn hơn.
Câu trả lời đầu tiên đến với tâm trí tôi thực sự là câu trả lời này. Nhưng, bây giờ có vẻ như, các giải pháp dựa trên truy cập thuận tiện hơn. –
@Gunner nhưng làm cách nào? – ruslik
Xem bài đăng của Mark Synowiec. –
Đối với tôi câu trả lời cho câu hỏi này tùy thuộc vào sự phân bố dự kiến của các số trong tệp.
Có 12 tỷ tỷ int trong 100 Biểu đồ dữ liệu int. Cũng chỉ có ~ 4,3 tỷ ints riêng biệt.
Phân phối hoàn toàn đồng đều trên tất cả các int có thể bạn mong đợi mỗi int hiển thị khoảng 3 lần cho hoặc nhận. Mức độ trùng lặp thấp này không đảm bảo thay đổi từ một thường trình sắp xếp tiêu chuẩn (một loại sắp xếp các khối tại một thời điểm và sau đó kết hợp các khối với nhau).
Tuy nhiên, nếu chúng tôi hạn chế "tệp ints" thành tất cả là không âm thì chúng tôi ngay lập tức mong đợi mỗi int hợp lệ xuất hiện khoảng 6 lần. Điều này đang tiến tới một mức độ trùng lặp có thể đảm bảo một sự thay đổi trong thói quen phân loại. Vì vậy, tôi nghĩ bạn nên hỏi người phỏng vấn xem liệu có thể giả định thêm bất cứ điều gì về việc phân phối các int trên đĩa. Xét cho cùng, sẽ thật kỳ quặc nếu có 100GB giá trị dữ liệu và không biết liệu nó có thể hiển thị bất kỳ mẫu có thể đoán trước nào hay không.
Đây thực sự là câu hỏi phỏng vấn và người phỏng vấn có lẽ quan tâm đến việc xem cách tiếp cận vấn đề. Vì vậy, chúng ta không nên mong đợi một số loại mẫu trong dữ liệu. Về vấn đề này, tôi tự hỏi nếu có bao giờ cần phải sắp xếp một số lượng lớn dữ liệu trong cuộc sống thực. –
Vâng, tôi hiểu rằng bạn đã viết ra câu hỏi phỏng vấn thực tế. Nhưng bạn nên hỏi trong cuộc phỏng vấn nếu các con số trong tập tin đến từ phân phối này hay phân phối khác. Bởi vì có kiến thức đó (hay không) có ý nghĩa quan trọng - bạn nên chứng minh rằng bạn nhận ra điều đó. – Ivan
Điểm tốt, hầu hết người phỏng vấn thực sự mong đợi người được phỏng vấn hỏi vài câu hỏi làm rõ. Những biểu hiện rất nhiều về cách người đó suy nghĩ và giải quyết các vấn đề được trình bày. –
Vì dữ liệu được sắp xếp là loại số nguyên (4 byte) và lượng dữ liệu là 100 GB (trong đó GB là 2^30), bạn có 26,843,545,600 số nguyên để sắp xếp. Vì bạn có 4,294,967,296 giá trị số nguyên có thể, bạn có thể biểu diễn dữ liệu này dưới dạng một chuỗi các thời gian phục vụ như các bộ đếm, sẽ tiêu tốn khoảng 34 GB dung lượng đĩa. Đọc qua 100 GB dữ liệu một lần, tăng các bộ đếm riêng cho mỗi giá trị nguyên có thể (tổng dung lượng đĩa tổng cộng 300 GB để đọc giá trị, đọc bộ đếm, viết bộ đếm tăng), sau đó đọc các bộ đếm theo thứ tự, viết số các giá trị mà bạn đã đọc của mỗi giá trị (tổng dung lượng truy cập đĩa là 134 GB).
Điều này sẽ sắp xếp dữ liệu bằng cách sử dụng tổng cộng 434 GB quyền truy cập đĩa.Nếu bạn sử dụng RAM để lưu trữ một phần phạm vi của các bộ đếm giá trị nguyên, bạn có thể hạ thấp kỹ thuật truy cập đĩa hơn nữa.
Điều này có vẻ là một câu trả lời hay. Đọc tất cả các yếu tố và đếm chúng và viết kết quả trở lại. Tôi đoán đếm sắp xếp là con đường để đi nếu chúng ta muốn giảm quyền truy cập đĩa. –
Có 2^32 số nguyên 32 bit và 8 byte trong một thời gian dài, vì vậy sẽ mất * chính xác * 32 GB (trong đó GB là 2^30) để lưu trữ tất cả các bộ đếm. Tuy nhiên, mỗi bộ đếm chỉ yêu cầu 35 bit để lưu trữ lên đến 26,843,545,600, vì vậy bạn cần 2^32 * 35/8 byte hoặc dưới 18 GB để giữ các bộ đếm. Hơn nữa, bạn có thể sử dụng 2GB bộ nhớ RAM để bộ nhớ cache thường xuyên sử dụng quầy, giảm sử dụng đĩa của bạn nhiều hơn. – Gabe
@Gabe: Có, giữ một số giá trị trong bộ nhớ cũng sẽ cải thiện hiệu suất. Một khả năng khác có thể là thực sự giữ các quầy trong bộ nhớ cho đến khi chúng ta đạt đến một điểm mà chúng ta sẽ không thể chứa thêm nữa. Trong trường hợp đó, chúng ta sẽ xóa chúng và cập nhật các bộ đếm trên đĩa. –
đây có phải là một loại Bài tập về nhà không? và đặt một số mã mà bạn đã thử? – FosterZ
có thể trùng lặp của [Cách sắp xếp chuỗi giá trị 100 GB.] (Http://stackoverflow.com/questions/2566459/how-to-sort-100gb-worth-of-strings) – Gabe
Xem thêm http: // stackoverflow. com/questions/134158/how-would-you-sort-1-triệu-32-bit-số nguyên-in-2mb-of-ram/3961223 và http://stackoverflow.com/questions/3961245/how-to- phân loại-hàng-of-hàng-of-data-in-a-file-với-ít-ít-bộ nhớ – Gabe