Làm thế nào để sắp xếp hàng triệu dòng dữ liệu trong một tập tin với ít/ít ỏi nhớ

Question

(Từ here)

tôi đã tham dự một cuộc phỏng vấn vào tuần trước và câu hỏi này đã được hỏi:

Làm thế nào để bạn sắp xếp một tỷ hàng dữ liệu trong một tệp chỉ có 640KB bộ nhớ trong máy xử lý dựa trên 8080? Không có bộ nhớ ảo, không có đĩa ngoài.

Tôi đã hỏi người phỏng vấn một cách rõ ràng nếu tôi có thể sử dụng ổ đĩa cứng, vì vậy tôi có thể sắp xếp hàng loạt cây khi tôi sắp xếp chúng và sau đó kết hợp ở cuối. Anh ấy nói không. Tôi đã thử nhiều cách, các thuật toán khác nhau. Không có gì anh đồng ý.

Tôi đã từ bỏ và hỏi anh ta một cách lịch sự, "bạn sẽ làm điều đó như thế nào?" Anh thẳng thừng nói, "Tôi sẽ không nói với bạn." (Cuộc phỏng vấn kết thúc ngay sau đó. Tôi không có ý xúc phạm anh ta, với tư cách là một nhà phát triển, tôi tò mò. Hơn nữa, đó là một câu hỏi theo bản năng, giống như tôi sẽ hỏi bất cứ ai tại nơi làm việc của tôi.)

Cuộc phỏng vấn này là một ngân hàng thực sự lớn.

Vậy, làm cách nào để mọi người tiếp cận vấn đề này?

Answer 1

Nếu tốc độ không phải là yêu cầu, bạn có thể bubble sort hàng tại chỗ trong tệp. Điều này chỉ yêu cầu xem xét hai hàng dữ liệu cùng một lúc, không yêu cầu thông tin hoặc bộ nhớ ngoài.

Answer 2

Tôi sẽ không làm điều đó trong C#, để bắt đầu. Bạn có chắc chắn rằng bạn có quyền được gắn thẻ này không? Đây là một vấn đề C, nếu nó có thể được giải quyết.

640K chỉ cung cấp cho bạn 640 * 1024 * 8 bit để không có cách nào giải quyết vấn đề này được đóng khung. Có lẽ đó là câu trả lời anh/cô ấy đang tìm kiếm. Những cuộc phỏng vấn của Ngân hàng Đầu tư này đôi khi là một cái gì đó.

Answer 3

Heapsort sẽ là lời khuyên của tôi. Nó tương đối nhanh khi n là lớn, và bạn chỉ cần nhìn vào ba yếu tố với sự phân biệt rõ ràng cùng một lúc.

Điều đó đang được nói, trực giác của tôi nói với tôi rằng sắp xếp một tỷ hàng trên một 8080 ngay cả trong C sẽ không thể xảy ra chậm.

Answer 4

Tôi muốn sử dụng GPU! Ngay cả trên máy tính nhanh, the GPU is often faster at sorting. Và tôi không biết các "hàng" lớn như thế nào, nhưng không khó để tìm các thẻ video 1GB, do đó cũng trả lời câu hỏi lưu trữ.

Bên cạnh đó, nếu tôi phải làm việc trên một chiếc 8080, tôi chắc chắn muốn đặt chiếc cạc đồ họa ngọt nhất mà tôi có thể tìm thấy trên đó.

Bạn chỉ cần sẵn sàng cho câu hỏi tiếp theo: "Làm thế nào để bạn có được 8080 để nói chuyện với một thẻ PCI Express 2.0 x16 hiện đại?". Tôi đã khám phá ra một phương pháp thật kỳ diệu, nhưng vùng văn bản này quá hẹp để chứa nó.

Answer 5

Knuth có toàn bộ phần trên external sorting; điều này đã được phổ biến trở lại khi không có ổ cứng & không có nhiều bộ nhớ, và ổ đĩa băng là tiêu chuẩn. Nhìn vào trang wikipedia, và/hoặc vol. 3 của nghệ thuật lập trình máy tính của Knuth.

Tôi đồng ý với bình luận Robusto của:

Nơi nào bạn nhận được các tập tin từ nếu bạn không thể sử dụng ổ đĩa? Nó chắc chắn sẽ không được giữ trong ký ức.

Không đủ định nghĩa sự cố.

Answer 6

Tôi càng nghĩ về điều này, tôi nghĩ rằng sắp xếp hợp nhất sẽ hoạt động rất tốt trong cửa sổ bộ nhớ mà chúng tôi đưa ra.

Giả sử bạn có bộ nhớ x. Chia hàng tỷ mục thành tỷ/x + 1 phần và heapsort chúng (heapsort vì không có bộ nhớ thêm là cần thiết và nó O (2n (log n)) thời gian). Khi tất cả các phần được heapsorted, làm một sắp xếp hợp nhất bắt đầu trên các yếu tố đầu tiên của tất cả các phần. Điều này sẽ làm việc miễn là bạn có nhiều hơn sqrt (tỷ) bộ nhớ để làm việc với được sử dụng bộ nhớ cơ bản 8080 hệ điều hành.

Làm phép tính, điều này giả định rằng mỗi hàng dữ liệu nhỏ hơn 165 bit.

Answer 7

Một câu hỏi khác được đặt ra là "Bản chất của các hàng là gì?" Nếu số lượng giá trị khác biệt đủ thấp, thì câu trả lời có thể là pigeon hole sort.

Ví dụ: giả sử tệp chỉ được sắp xếp chứa các hàng chứa số từ 0 đến 100. Tạo một mảng gồm 101 số nguyên không bit 32 bit hoặc 64 bit với giá trị bằng 0. Khi bạn đọc một hàng, hãy sử dụng nó để lập chỉ mục mảng và tăng số đếm của phần tử đó. Khi tập tin được đọc, bắt đầu từ 0, đọc số lượng các số không đọc và nhổ ra nhiều, đi đến 1, lặp lại. Mở rộng kích thước mảng khi cần để xử lý tập hợp các số đi qua. Tất nhiên có giới hạn, nói rằng các giá trị có thể được nhìn thấy khoảng từ -2e9 đến + 2e9. Điều đó sẽ yêu cầu 4e9 thùng, mà sẽ không phù hợp với 640K RAM.

Nếu thay vào đó các hàng là chuỗi, nhưng bạn vẫn đang xem một tập hợp đủ nhỏ giá trị khác biệt, sau đó sử dụng mảng kết hợp hoặc bảng băm để giữ số lượng.

Answer 8

Rõ ràng bạn phải có khả năng đọc và ghi vào tệp hàng tỷ. Ràng buộc không có đĩa bên ngoài có nghĩa là bạn phải hạn chế chính xác thuật toán tại chỗ hoặc đưa ra một số giả định về điều kiện bắt đầu và phân phối dữ liệu để bạn có thể giữ dữ liệu được sắp xếp khi nó được thêm vào tệp (ví dụ: sử dụng khóa làm chỉ mục và tạo một tệp đủ lớn để giữ số khóa dự kiến).

Nếu bạn phải bắt đầu với một tệp chưa phân loại và sắp xếp nó, bạn có thể sử dụng hợp nhất sắp xếp hợp nhất sắp xếp hoạt động trên các phần rất nhỏ của tệp. Vì không có ràng buộc nào được thực hiện vào thời gian truy cập của phương tiện lưu trữ, nó có thể rất nhanh.

Answer 9

Bạn có thể tìm thấy các cuộc thảo luận về một vấn đề tương tự trong Jon BentleyPearls trìnhColumn. 1. đây Bentley giao dịch với một vấn đề phân loại hàng triệu mã vùng mà chắc chắn sẽ rất độc đáo bằng cách sử dụng một bitset cấu trúc dữ liệu.