Điều gì thúc đẩy mô hình RAM?
Có vẻ như hầu hết các phân tích thuật toán ngày nay được thực hiện trong các mô hình có quyền truy cập ngẫu nhiên theo thời gian không đổi, chẳng hạn như mô hình RAM từ. Tôi không biết nhiều về vật lý nhưng từ các nguồn phổ biến, tôi đã nghe nói rằng có giới hạn về lưu trữ thông tin trên mỗi ổ đĩa và tốc độ truyền thông tin, vì vậy RAM dường như không thể thực hiện được. Máy tính hiện đại có tất cả các mức bộ nhớ cache này mà tôi muốn nói là khiến chúng không giống RAM. Vậy tại sao các thuật toán lý thuyết phải được thiết lập trong RAM?
Trả lời
Hãy để tôi nói về nó khác với vonbrand. Tất cả những gì bạn nói đều đúng: mô hình RAM không thực tế vì một số lý do, và trong khi có thể bảo vệ các khía cạnh khác nhau của nó, việc bảo vệ như vậy không thực sự đi vào trọng tâm của vấn đề.
Trọng tâm của vấn đề - và câu trả lời cho câu hỏi của bạn - là mẫu RAM là thứ tốt nhất mà chúng tôi có. So với các mô hình khác được chấp nhận, nó mô hình hóa chính xác hơn việc tính toán trong đời thực. Đặc biệt, lý do chúng tôi áp dụng mô hình RAM chủ yếu là phản ứng với máy Turing, vì chúng tôi nhận thấy rằng việc sử dụng máy Turing dẫn đến các vấn đề khó giải quyết một cách giả tạo về độ phức tạp về thời gian. Mô hình RAM rõ ràng đã giải quyết được vấn đề chói sáng này và do đó nó đã được chấp nhận, mặc dù nó vẫn chưa hoàn hảo.
Một ví dụ cổ điển minh họa vấn đề khó hiểu với máy Turing là vấn đề bình đẳng chuỗi: đầu vào đã cho
$$ w_1 \# w_2$$
Ở đâu $w_1, w_2$ là các chuỗi nhị phân và $\#$ là một dấu phân cách, xác định xem $w_1 = w_2$. Có thể chứng minh rằng bất kỳ máy Turing nào cho bài toán bình đẳng đều có$O(n^2)$thời gian. Điều này thật khó chịu, bởi vì máy Turing là thứ mà mọi người coi là mô hình tính toán phổ biến - nhưng không một kỹ sư phần mềm hoặc nhà nghiên cứu thuật toán nào tin rằng bình đẳng chuỗi thực sự có$O(n^2)$thời gian. Vì vậy, những gì cho? Bình đẳng chuỗi phải là tuyến tính, vì vậy chúng tôi phát minh ra một mô hình mới ở đó và giải pháp tốt nhất hiện có là máy RAM từ.
Có lẽ một ngày nào đó trong tương lai, chúng ta sẽ nghĩ ra một mô hình tốt hơn - một mô hình đơn giản, rõ ràng về mặt khái niệm và cải thiện RAM trong khả năng mô hình độ phức tạp tính toán trong đời thực. Hiện tại, chúng tôi chỉ có thể làm bằng những gì tốt nhất mà chúng tôi có.
Như một phép gần đúng, đầu tiên, bạn có thể dành thời gian để truy cập một từ trong bộ nhớ dưới dạng hằng số, độc lập với các lần truy cập trước đó. Tức là mô hình RAM.
Bạn nói đúng, máy móc ngày nay khá không có RAM, nó trả công (thậm chí rất tốt) để tổ chức truy cập dữ liệu sao cho tuần tự nhất có thể hoặc phát ra bit thông tin cuối cùng từ một đoạn bộ nhớ (ngắn!) Trước khi xử lý tiếp theo. Nhưng bạn hiếm khi có đủ thời gian để làm như vậy, việc truy cập bộ nhớ của bạn về cơ bản là ngẫu nhiên và mô hình không xa sự thật. Thêm vào đó, máy móc ngày nay có nhiều hơn một CPU, kiểu máy chỉ có một. Và sau đó là xử lý vectơ (thực hiện cùng một hoạt động trên một vectơ dữ liệu, không phải từng cái một) như "hướng dẫn đa phương tiện" (và thậm chí nhiều hơn nữa bằng cách sử dụng card đồ họa để xử lý).
Một chút thảo luận được đưa ra ví dụ bởi Khoung's Binary search là một trường hợp bệnh lý cho bộ nhớ đệm . Như bạn thấy, việc phân tích các thuật toán đơn giản, dễ hiểu theo các mô hình thời gian truy cập bộ nhớ thực tế hơn là một điều khó khăn.
Mô hình RAM được thúc đẩy bởi phân tích tiệm cận của các thuật toán được thiết kế như các phép tính đơn luồng trong bộ nhớ.
Tối ưu hóa hiệu suất cho tập hướng dẫn cụ thể, bộ nhớ đệm và những gì không phải là một điều. Điều còn lại là chuẩn bị cho sự phát triển của quy mô vấn đề. Để ước tính tỷ lệ thuật toán trong bộ nhớ của bạn tốt như thế nào, bạn có thể muốn bỏ qua các yếu tố nhỏ và tập trung vào$\mathcal{O}$ký hiệu. Lớn$\mathcal{O}$ sẽ không tối ưu hóa mọi thứ cho bạn, nhưng ít nhất nó có thể cho bạn biết rằng giải pháp của bạn có quy mô tốt (hoặc bạn nên thử một cái gì đó khác).
RAM giả định tập lệnh cố định nhỏ, trong đó mỗi thao tác hoạt động trong $\mathcal{O}(1)$. Lưu ý rằng đây là một mô hình tốt nếu chúng ta chỉ quan tâm đến tăng trưởng tiệm cận:
Bộ lệnh của một CPU hiện đại không nhỏ, nhưng chúng ta có thể giả vờ rằng nó thực sự là như vậy. Những mã op bổ sung đó không tạo ra sự khác biệt lớn$\mathcal{O}$ ký hiệu.
CPU có thể có các lệnh mà thời gian chạy của chúng phụ thuộc vào đầu vào. Một lần nữa, chúng ta có thể bỏ qua chúng, bởi vì chúng ta có thể lập mô hình chúng bằng các hướng dẫn đơn giản hơn mà không ảnh hưởng đến$\mathcal{O}$sự phức tạp. Điều tương tự đối với các mức bộ nhớ cache: hiệu suất của chúng vẫn bị giới hạn bởi một số hằng số nhỏ, do đó hoạt động trong$\mathcal{O}(1)$ theo định nghĩa.
Có, bạn không thể truy cập bộ nhớ trong thời gian liên tục nếu nó tiếp tục phát triển. May mắn thay, điều này không bao giờ được yêu cầu nhờ vào lẽ thường. Không ai lập chỉ mục toàn bộ Internet vào bộ nhớ không liên tục của một cỗ máy đơn luồng cô đơn.