Tôi tin rằng trong một số ngôn ngữ khác ngoài Ruby, tra cứu Array là O (1) bởi vì bạn biết nơi dữ liệu bắt đầu, và bạn nhân chỉ mục theo kích thước của dữ liệu mà mảng đang giữ, và sau đó truy cập vị trí bộ nhớ đó .Tại sao tra cứu trong một mảng O (1)?
Tuy nhiên, trong Ruby, một mảng có thể có các đối tượng từ các lớp khác nhau, vậy làm cách nào để quản lý tra cứu độ phức tạp O (1)?
gì @Neil Slater nói, với một chi tiết nhỏ hơn ...
Về cơ bản có hai cách tiếp cận hợp lý để lưu trữ một mảng của các đối tượng không đồng nhất của các kích cỡ khác nhau:
Store đối tượng như một đơn lẻ - hoặc gấp đôi - linked list, với dung lượng lưu trữ cho từng đối tượng riêng lẻ đi trước bởi (các) con trỏ đến các đối tượng trước và/hoặc sau. Cấu trúc này có lợi thế là làm cho nó rất dễ dàng để chèn các đối tượng mới tại các điểm tùy ý mà không cần di chuyển xung quanh phần còn lại của mảng, nhưng nhược điểm lớn là tìm kiếm một đối tượng theo vị trí của nó thường là O(N), vì bạn phải bắt đầu từ một cuối danh sách và nhảy qua nút từng nút cho đến khi bạn đến vị trí thứ n.
Lưu trữ bảng hoặc mảng con trỏ có kích thước không đổi cho các đối tượng riêng lẻ. Vì bảng tra cứu này chứa các mục có kích thước không đổi trong một bố cục được sắp xếp liền kề, hãy tra cứu địa chỉ của các objec riêng lẻ O(1); bảng chỉ là một mảng kiểu C, trong đó tra cứu chỉ mất một vài lệnh máy, ngay cả trên các kiến trúc CPU RISC.
(Các chiến lược phân bổ để lưu trữ các đối tượng cá nhân cũng là thú vị và phức tạp, nhưng không phải ngay lập tức có liên quan đến câu hỏi của bạn.)
ngôn ngữ động như Perl/Python/Ruby khá nhiều tất cả các lựa chọn cho # 2 cho danh sách/loại mảng có mục đích chung của chúng. Nói cách khác, chúng giúp tra cứu hiệu quả hơn chèn các đối tượng tại các vị trí ngẫu nhiên trong danh sách, đây là lựa chọn tốt hơn cho nhiều ứng dụng.
Tôi không quen với các chi tiết triển khai cho Ruby, nhưng chúng có thể khá giống với kiểu của loại list của Python, có hiệu suất và thiết kế được giải thích chi tiết tuyệt vời tại effbot.org.
Việc triển khai của nó có thể chứa một mảng địa chỉ bộ nhớ, trỏ đến các đối tượng thực tế. Do đó nó vẫn có thể tra cứu mà không lặp qua mảng.
Đối với MRI Ruby và Rubinius: Nội bộ * tất cả * Đối tượng Ruby là cùng loại cơ sở trong C (được gọi là '# define' được gọi là' VALUE', vì vậy nó có thể thay đổi trong một số triển khai). Đôi khi, 'VALUE' được coi là con trỏ, đôi khi (ví dụ: đối với số nguyên nhỏ) là giá trị được mã hóa của mục. Đó là những thuật ngữ 'VALUE' có độ dài cố định được lưu trữ trong một mảng mặc dù. Nếu bạn bao gồm chi tiết đó, bạn có thể thả * có thể *. –
@NeilSlater Đặt nhận xét của bạn là câu trả lời đúng: D Tôi sẽ xóa câu trả lời phỏng đoán của mình. – lulalala
Đoạn đầu tiên của bạn mâu thuẫn với đoạn thứ hai của bạn, vì vậy tôi đã chỉnh sửa để làm cho nó không mâu thuẫn. Nếu bạn có ngôn ngữ cụ thể trong tâm trí mà bạn đã không đề cập đến, sau đó làm cho rõ ràng. – sawa
sawa, bạn có nhiều quyền hơn. Cảm ơn bạn đã chỉnh sửa. – blackghost