Mảng và Danh sách được Liên kết theo địa phương

Question

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à:

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.

Answer 1

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.