phép nói rằng tôi có một mảng như:tại sao truy cập phần tử trong một mảng có thời gian không đổi?
int a [] = {} 4,5,7,10,2,3,6
khi tôi truy cập vào một yếu tố, chẳng hạn như một [3] , điều gì thực sự xảy ra đằng sau hiện trường? Tại sao nhiều sách thuật toán (chẳng hạn như sách Cormen ...) nói rằng phải mất một thời gian không đổi?
(Tôi chỉ là một Noob trong cấp thấp lập trình vì vậy tôi muốn tìm hiểu thêm từ các bạn)
Chỉ cần hoàn thành, "cấu trúc nào được truy cập trong thời gian tuyến tính?" Cấu trúc Linked List được truy cập trong thời gian tuyến tính. Để có được yếu tố n, bạn phải di chuyển qua các phần tử trước đây n-1. Bạn biết đấy, giống như máy ghi âm hoặc băng VHS, nơi để đi đến cuối băng/VHS, bạn phải chờ một thời gian dài :-)
Một mảng tương tự như một đĩa cứng: mọi điểm là có thể truy cập trong thời gian "không đổi" :-)
Đây là lý do RAM của máy tính được gọi là RAM: Bộ nhớ truy cập ngẫu nhiên. Bạn có thể đi đến bất kỳ vị trí nào nếu bạn biết địa chỉ của nó mà không đi qua tất cả bộ nhớ trước vị trí đó.
Một số người nói với tôi rằng truy cập HD không thực sự trong thời gian liên tục (khi truy cập tôi có nghĩa là "thời gian để định vị đầu và đọc một phần của HD"). Tôi phải nói rằng tôi không chắc chắn về nó. Tôi đã googled xung quanh và tôi đã không tìm thấy bất cứ ai nói về nó. Tôi biết rằng thời gian không tuyến tính, bởi vì nó vẫn được truy cập ngẫu nhiên. Cuối cùng, nếu bạn nghĩ rằng truy cập HD không đủ liên tục cho bạn (nhưng sau đó, điều gì là không đổi? Truy cập RAM? Xem xét Cache, Prefetching, Data Locality và Compiler optimizations?), Hãy cân nhắc câu như Một mảng tương tự như một thanh đĩa USB: mỗi điểm có thể truy cập trong thời gian "không đổi" :-)
ổ đĩa cứng là một ví dụ không tốt cho bộ nhớ truy cập ngẫu nhiên, vì đó chính xác là những gì chúng không có. Có thể sử dụng một thanh USB hoặc một đĩa trạng thái rắn làm ví dụ thay thế? – blubb
Có và không ... Về mặt kỹ thuật, phần "bên ngoài" của HD nhanh hơn phần bên trong, nhưng chúng tôi sẽ bỏ qua điều này. Truy cập một tập tin trên HD được thực hiện trong thời gian không đổi (hoặc ít nhất là không phải trong thời gian tuyến tính). Nếu bạn có một tệp trên HD hoặc một triệu tệp trên HD, việc truy cập một trong số chúng sẽ mất cùng một lúc (không chính xác, nhưng đó là mô hình lý thuyết hơn thực tế phisical chúng ta đang sống trong :-)). – xanatos
Có thể giải thích -1 không? Tôi đã suy nghĩ lại một chút. Thời gian truy cập HD trong thời gian không đổi. Với HD, bạn có thời gian tìm kiếm trung bình. Vì vậy, tìm kiếm sự khởi đầu của một tập tin sẽ mất thời gian đó. – xanatos
Mảng, có hiệu quả, được biết đến bởi một vị trí bộ nhớ (một con trỏ). Truy cập a[3] có thể được tìm thấy trong thời gian không đổi vì nó chỉ là location_of_a + 3 * sizeof (int).
Trong C, bạn có thể thấy điều này trực tiếp. Hãy nhớ rằng, a[3] giống với *(a+3) - điều này rõ ràng hơn một chút về những gì nó đang làm (dereferencing con trỏ "3 mục" trên).
Và vì '* (a + 3)' là giống như '* (3 + a)', chúng ta có thể viết 'a [3]' cũng như '3 [a]', một thực tế luôn luôn có ích trong IOCCC và những thứ tương tự. :-) – ShreevatsaR
@ShreevatsaR: Có, nhưng ... viết '3 [a]' không có nhiều cách sử dụng thực tế - nhưng việc sử dụng '* (a + 3)' thường hữu ích trong các tình huống thực tế .. –
Giải thích của bạn thậm chí sẽ giữ khi chỉ mục được sử dụng cũng sẽ là một biến. Nhưng vì ở đây nó là một hằng số ('3') tất cả các tính toán thậm chí có thể được thực hiện bởi trình biên dịch trước khi bàn tay và tại thời gian chạy chương trình có thể truy cập bộ nhớ trực tiếp. Vì vậy, trên thực tế nó không chỉ liên tục, mà là một cái thực sự nhỏ. –
Do mảng được lưu trữ trong bộ nhớ tuần tự. Vì vậy, thực sự, khi bạn truy cập mảng [3] bạn đang nói với máy tính, "Lấy địa chỉ bộ nhớ của phần đầu của mảng, sau đó thêm 3 vào nó, sau đó truy cập vào vị trí đó." Kể từ khi thêm mất thời gian liên tục, do đó, không truy cập mảng!
"thời gian liên tục" thực sự có nghĩa là "thời gian không phụ thuộc vào 'kích thước vấn đề'" . Đối với 'vấn đề' "có được một cái gì đó ra khỏi một container", 'kích thước vấn đề' là kích thước của container. Việc truy cập phần tử mảng cơ bản là cùng một khoảng thời gian (đây là cách đơn giản) bất kể kích thước vùng chứa, vì một bộ các bước cố định được sử dụng để lấy phần tử: vị trí của nó trong bộ nhớ (đây cũng là một sự đơn giản hóa) được tính toán, và sau đó giá trị tại vị trí đó trong bộ nhớ được lấy ra. Ví dụ:
Danh sách được liên kết không thể thực hiện điều này vì mỗi liên kết chỉ ra vị trí của vị trí tiếp theo. Để tìm một yếu tố bạn phải làm việc qua tất cả các phần tử trước đó; trung bình, bạn sẽ làm việc thông qua một nửa container, vì vậy kích thước của container rõ ràng là quan trọng.
một mảng của 10 biến số nguyên, với chỉ số từ 0 đến 9, có thể được lưu dưới dạng 10 từ tại các địa chỉ bộ nhớ 2000, 2004, 2008, ... 2036, do đó các phần tử với chỉ số i có địa chỉ 2000 + 4 × i . quá trình này mất một nhân và một Ngoài Kể từ khi hai hoạt động chăm time.so liên tục chúng ta có thể nói rằng truy cập có thể được thực hiện trong thời gian liên tục
Đây chính xác là những gì tôi muốn. Nó là hằng số nhưng toán học đằng sau điều này là gì ---- bạn đã giải thích rất rõ. –
Một mảng là tuần tự, có nghĩa là, địa chỉ phần tử tiếp theo trong mảng là bên cạnh hiện tại. Vì vậy, nếu bạn muốn lấy phần tử thứ 5 của một mảng, bạn tính toán địa chỉ của phần tử thứ 5 bằng cách tổng hợp địa chỉ cơ sở của mảng với 5. Địa chỉ trực tiếp này hiện được sử dụng trực tiếp để lấy phần tử tại địa chỉ đó.
Bây giờ bạn có thể hỏi thêm một câu hỏi tương tự tại đây- "Làm cách nào máy tính biết/truy cập địa chỉ được tính toán trực tiếp?" Đây là bản chất và nguyên tắc bộ nhớ máy tính (RAM). Nếu bạn quan tâm hơn đến cách RAM truy cập vào bất kỳ địa chỉ nào trong thời gian không đổi, bạn có thể tìm thấy nó trong bất kỳ văn bản tổ chức máy tính nào hoặc bạn chỉ có thể google nó.
Mảng là tập hợp các loại dữ liệu tương tự. Vì vậy, tất cả các yếu tố sẽ mất cùng một lượng memory.Therefore nếu bạn biết địa chỉ cơ sở của mảng và kiểu dữ liệu nó giữ bạn có thể dễ dàng có được yếu tố Array [i] trong thời gian liên tục sử dụng công thức nêu dưới đây:
int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];
Do đó, rõ ràng của nó có thể nhìn thấy bạn có thể nhận được phần tử thứ i trong thời gian không đổi nếu bạn biết địa chỉ cơ sở và loại dữ liệu mà nó nắm giữ. Vui lòng truy cập vào liên kết this để biết thêm về cấu trúc dữ liệu mảng.
Nếu chúng tôi biết vị trí bộ nhớ cần truy cập thì quyền truy cập này là không đổi. Trong trường hợp mảng, vị trí bộ nhớ được tính bằng cách sử dụng con trỏ cơ sở, chỉ mục của phần tử và kích thước của phần tử. Điều này liên quan đến phép tính nhân và phép cộng, phải mất thời gian liên tục để thực thi. Do đó truy cập phần tử bên trong mảng mất thời gian không đổi.
tại sao điều này lại được giảm giá? Vui lòng cung cấp giải thích? – pixelearth
tôi không biết tại sao nó lại bị bỏ phiếu –
Chỉ 10 phiếu bầu. Điều này xứng đáng chú ý –