Làm thế nào Cache Sắp xếp nhanh chóng Sắp xếp là?

Question

Trong Burst sort tác giả giấy tuyên bố rằng sắp xếp nhanh chóng không phải là thuật toán phân loại rất hiệu quả của bộ nhớ cache. Như tác giả đề cập

Tuy nhiên, một số trong những nhược điểm của quicksort vẫn còn nhân vật present.Each được kiểm tra nhiều lần, cho đến khi nó nằm trong một bằng trục chuỗi partition.Each được tái truy cập mỗi lần một nhân vật trong nó được kiểm tra, và sau khi phân vùng đầu tiên các truy cập này là ngẫu nhiên hiệu quả. Đối với một tập hợp lớn các chuỗi, tỷ lệ bộ nhớ cache số lần bỏ lỡ có khả năng cao.

Tôi cũng thấy ppt mà nói loại nhanh chóng và hợp nhất loại là bộ nhớ cache thuật toán Quên đi nhưng Wikipedia và few paper tuyên bố rằng loại nhanh là rất nhớ cache hiệu quả.

Tôi không thể hiểu các trường hợp trong đó sắp xếp nhanh có được bộ nhớ cache bỏ lỡ ngoài việc bỏ lỡ bắt buộc cho dữ liệu số nguyên. Có ai giải thích bộ nhớ cache sắp xếp nhanh bỏ sót chi tiết không?

Answer 1

Đoạn bạn trích dẫn chủ yếu nói về các vấn đề khi sắp xếp chuỗi. Nếu một chuỗi các chuỗi trong quicksort được lưu trữ như một mảng như con trỏ (mà về cơ bản là cách dễ dàng nhất để làm điều đó), thì sau khi vượt qua đầu tiên của quicksort có thể con trỏ được lưu trữ ở các vị trí lân cận trong mảng sẽ trỏ đến bộ nhớ vị trí cách xa nhau, ngay cả khi chuỗi ban đầu của chuỗi được cấp phát trong bộ nhớ liên tiếp. Có vẻ hợp lý khi phân loại các chuỗi có thể được coi là một vấn đề đặc biệt và các thuật toán chuyên biệt cho nó có thể là bộ nhớ cache hiệu quả hơn.

Nếu thay vào đó, bạn sắp xếp một mảng các số nguyên, thì bạn thực sự so sánh và trao đổi xung quanh dữ liệu trong mảng trong quicksort, và vì vậy khi bạn truy cập các vị trí lân cận trong mảng, bạn sẽ nhận được các lợi ích bộ nhớ cache. Trong trường hợp này, sự hiểu biết của tôi là giống như những gì bạn tìm thấy trên wikipedia và ở nơi khác, cụ thể là, quicksort là khá cache hiệu quả. Về cơ bản điều này là bởi vì mỗi pass của quicksort xử lý phần của mảng trong một thời trang rất địa phương.