캐시와 정렬 알고리즘간 관계

'The Influences of Caches on the Performance of Sorting '리뷰 O(nlogn) 정렬 알고리즘이 O(n)정렬 알고리즘보다 빠르다??1. Introduction:Cache miss penalty의 문제가 performance에 큰 영향을 미침 & instruction count를 최소화 하기 위한 알고리즘이 필요.ex) radix sort는 lowest instruction count가 있으나, poor cache performance로 인해 merge sort, quicksort에 비해 성능이 떨어진다.이 논문의 목적은 4개의 정렬 알고리즘: heapsort, mergesort, quicksort, radixsort 를 cache의 측면에서 개선(메모리 최적화를..

2024.07.02