10

Giả sử chúng tôi có một mảng chưa được sắp xếp và danh sách được liên kết. Trường hợp xấu nhất khi tìm kiếm phần tử cho cả hai cấu trúc dữ liệu sẽ là O (n), nhưng câu hỏi của tôi là:Mảng và Danh sách được Liên kết theo địa phương

Liệu mảng có còn nhanh hơn do sử dụng không gian trong bộ nhớ cache hay không cache làm cho việc sử dụng địa phương chi nhánh cho phép các danh sách liên kết được nhanh như bất kỳ mảng nào?

Sự hiểu biết của tôi về mảng là nếu một phần tử được truy cập, khối bộ nhớ đó và nhiều khối xung quanh được đưa vào bộ nhớ cache cho phép truy cập bộ nhớ nhanh hơn nhiều.

Sự hiểu biết của tôi về danh sách được liên kết là vì đường dẫn sẽ được thực hiện để đi qua danh sách có thể dự đoán được, bộ nhớ cache sẽ khai thác và vẫn lưu trữ các khối bộ nhớ phù hợp ngay cả khi các nút trong danh sách có thể ở xa ngoài heap.

+0

"Địa phương chi nhánh" này bạn nói đến là gì? Làm thế nào có thể bộ nhớ cache có được xung quanh độ trễ của bộ nhớ chính? Vui lòng mô tả những gì bạn nghĩ rằng bộ nhớ cache thực hiện với các nút danh sách được liên kết. – delnan

+0

@delnan Bạn có thể đọc về địa phương chi nhánh tại đây: http://en.wikipedia.org/wiki/Locality_of_reference Tôi không biết câu trả lời cho câu hỏi thứ 2 của bạn. Tôi giải thích những gì tôi nghĩ rằng bộ nhớ cache có thể làm với các nút ở phần cuối của câu hỏi của tôi. – Kacy

+1

Mô tả về địa phương chi nhánh có vẻ là về một tập hợp nhỏ các lựa chọn thay thế, như mục tiêu của lệnh chi nhánh (do đó tên). Ngược lại, nút tiếp theo của danh sách được liên kết có thể là * ở bất kỳ đâu *. Đối với câu hỏi thứ hai của tôi: Vấn đề lưu trữ sửa chữa không phải là chủ yếu giới hạn băng thông nhưng hạn chế độ trễ. Việc tải một khối liên tục lớn vào bộ nhớ cache cùng một lúc (vì nó xảy ra đối với mảng/mảng không gian) là một sự cải tiến vì bộ nhớ cache chỉ phải trả chi phí thời gian chờ một lần. Vì vậy, câu hỏi của tôi là, làm thế nào có thể bộ nhớ cache tải n nút của một danh sách liên kết mà không phải trả chi phí độ trễ n lần? – delnan

Trả lời

11

Sự hiểu biết của bạn về trường hợp mảng chủ yếu là chính xác. Nếu một mảng được truy cập tuần tự, nhiều bộ xử lý sẽ không chỉ tìm nạp khối chứa phần tử đó, mà còn tìm nạp trước các khối tiếp theo để giảm thiểu các chu kỳ dành cho việc chờ cache. Nếu bạn đang sử dụng bộ xử lý Intel x86, bạn có thể tìm thấy chi tiết về điều này trong tối ưu hóa Intel x86 manual. Ngoài ra, nếu các phần tử mảng đủ nhỏ, việc tải một khối chứa phần tử có nghĩa là phần tử tiếp theo có khả năng trong cùng một khối.

Thật không may, đối với danh sách được liên kết, tải mẫu không thể đoán trước được từ quan điểm của bộ xử lý. Nó không biết rằng khi tải một phần tử tại địa chỉ X là địa chỉ tiếp theo là nội dung của (X + 8).

Ví dụ cụ thể, chuỗi địa chỉ tải cho truy cập mảng tuần tự là tốt và có thể dự đoán được. Ví dụ, 1000, 1016, 1032, 1064 vv

Đối với một danh sách liên kết nó sẽ trông giống như: 1000, 3048, 5040, 7888, vv Rất khó để dự đoán địa chỉ tiếp theo.

Các vấn đề liên quan