[TIL]20220526

CS 스터디

챕터 15: 캐시가 뭔가요?

캐시

• 컴퓨터의 성능을 향상시키기 위해 사용되는 용량은 작고 속도가 빠른 메모리.
• 주 기억 장치와 CPU사이에 위치하고, 자주 사용하는 데이터들을 기억한다.
• 캐시는 캐시의 접근 시간에 비해 원래 데이터에 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우에 사용한다.
• 캐시에 데이터를 미리 복사해 놓으면 계산이나 접근 시간 없이 더 빠른 속도로 데이터에 접근할 수 있다.
• 프로세서에서 캐시는 용량이 작고 속도가 빠른 메모리로, 용량이 더 크지만 훨씬 느린 주 기억 장치에 매번 접근하는 것을 피하고자 최근에 사용된 정보를 저장하는 데 사용
• 일반적인 프로세서에는 캐시가 2~3개가 있는데, 흔히 L1, L2, L3 레벨이라고 부르고 뒤로 갈수록 용량은 크지만 속도가 더 느림
• 단, 캐시 용량이 무한정 커질 수는 없으므로, 새 데이터를 위한 공간을 만들기 위해 오래된 항목부터 조용히 제거한다.

캐싱

• 속도가 느린 디스크의 데이터를 속도가 빠른 메모리로 가져와서 메모리 상에서 읽고 쓰는 작업을 수행하는 것을 말한다.
•  효과적인 이유는 최근에 사용된 정보가 곧 다시 사용될 가능성이 크기 때문. 즉, 캐시에 정보를 포함하고 있다는 사실은 메모리 작업을 기다리는데 시간을 덜 쓴다는 것을 뜻한다. 
• 대게 정보를 블록 단위로 동시에 불러온다.

캐시의 지역성

• 캐시가 효율적으로 동작하려면, 캐시의 적중율(Hit-rate)를 극대화 시켜야 한다.
• 캐시에 저장할 데이터가 지역성(Locality)을 가져야 한다.
• 지역성이란, 데이터 접근이 시간적, 혹은 공간적으로 가깝게 일어나는 것을 의미한다.
• 지역성의 전제 조건으로 프로그램은 모든 코드나 데이터를 균등하게 Access하지 않는다는 특성을 기본으로 한다.
• 즉, 지역성(Locality)이란
  기억장치 내의 정보를 균일하게 Access하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성이다.
• 지역성에는 1. 시간적 지역성(Temporal Locality)과 2.공간적 지역성(Spatial Locality)이 있다.

시간적 지역성

• 특정 데이터에 한 번 접근해서 가져온 경우, 그 데이터가 가까운 미래에 또 한번 접근할 가능성이 높은 것을 시간적 지역성이라고 한다. 즉, 한 번 가져왔던 데이터를 또 쓸 일이 있다는 의미이다.

• 그런 경우 캐시에 한 번 가져와서 저장을 해 놓고 여러 번 사용하게 되면 메모리에 접근하는 횟수가 줄어들게 된다. 따라서 캐시는 반복으로 사용되는 데이터가 많을수록 높은 효율성을 낼 수 있다.

공간적 지역성

• 필요한 데이터가 모여 있다면, 한번만 메모리에 접근해도 필요한 데이터들을 가져올 수 있다. 만약 데이터들이 여기저기 흩어져 있다면, 캐시 미스가 날 확률이 높아지고 메모리에 여러 번 접근해 효율성이 떨어진다.
• 특정 데이터와 가까운 주소가 순서대로 접근 되었을 경우 공간적 지역성이라고 한다. 즉, 앞으로 사용할 데이터들이 가져올 블록 안에 많이 모여있는 것을 의미한다.
• 특정 데이터와 가까운 주소가 순서대로 접근되었을 경우. CPU 캐시나 디스크 캐시의 경우 한 메모리 주소에 접근할 때 그 주소뿐 아니라 해당 블록을 전부 캐시에 가져오게 된다.
• 이때 메모리 주소를 오름차순이나 내림차순으로 접근한다면, 캐시에 이미 저장된 같은 블록의 데이터를 접근하게 되므로 캐시의 효율성이 크게 향상된다.

 

---

알고리즘 

정렬(1)

버블 정렬 (Bubble Sort)

def bubblesort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    iters = len(lst) - 1
    for iter in range(iters):
        # 이미 구한 최댓값은 범위에서 제외한다.
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

선택 정렬 (Selection Sort)

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

삽입 정렬 (Insertion Sort)

def insertionsort(lst):
    # 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst


def insertionsort_2(lst):
    for idx in range(1, len(lst)):
        val = lst[idx]
        cmp = idx - 1

        while lst[cmp] > val and cmp >= 0:
            lst[cmp + 1] = lst[cmp]
            cmp -= 1

        lst[cmp + 1] = val

    return lst

---

알고리즘 문제

 

Largest Number, Insertion Sort List, 전화번호 목록 - 백준

---