알고리즘지역성 (1) 썸네일형 리스트형 [Arm프로세서] 알고리즘 지역성 공간 지역성과 시간 지역성을 활용해 캐시 알고리즘을 구성할 수 있다고 소개했습니다. 그런데 데이터 구조나 알고리즘을 사용할 때 메모리에 접근하는 패턴을 관찰하면 시간 지역성이나 공간 지역성을 확인하기 어려운 경우가 있습니다. 예를 들어, 링크드 리스트로 데이터를 관리할 때 메모리에 접근하는 패턴을 관찰하면 특정 위치에 있는 데이터에 다시 접근할 확률이 높지 않아 시간 지역성과 같은 특징을 지니지 않습니다. 또한 링크드 리스트는 배열과 달리 인접한 메모리 주소 공간에 접근하지 않아 공간 지역성에도 맞지 않습니다. 그런데 코드를 유심히 분석하면 프로그램은 함수의 호출과 자료구조로 구성돼 있다는 사실을 알 수 있습니다. 자주 사용하는 자료 구조나 알고리즘은 어느 정도 정해져 있습니다. 예를 들어, 링크드 리스.. 이전 1 다음