크래프톤 정글 WEEK5 Day42 - Counter 모듈 / malloc lab 구현 / 힙 정렬

📆24.02.19

1. 프로그래머스 - Counter 모듈
2. malloc - next fit
3. heap sort

 

 

오랜만에 프로그래머스 문제 풀었다. 원래 기초 풀고 있었는데 입문 다 풀려고 다시 입문으로 돌아왔다.. 

 

풀면서 알게 된 점에 대해 정리!

---

프로그래머스 - 최빈값 구하기

 

Counter 클래스 

• 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common() 메서드 제공

최빈값은 주어진 값 중에서 가장 자주 나오는 값을 의미

from collections import Counter

def solution(array):
    answer = Counter(array)
    modes =[]
    max_count = max(answer.values())
    
    for k, v in answer.items():
        if v == max_count:
            modes.append(k)
        
    if len(modes) == 1:
        return modes[0]
    else:
        return -1

 

• items() - 딕셔너리의 키, 값 쌍 얻음
• keys() - 딕셔너리의 키만 얻음
• values() - 딕셔너리의 value만 얻음

---

Malloc

 

First Fit으로 구현한 결과 총점이 44(util) + 12 (thru) = 56 점이 나왔다.

• Space Utilization - 공간을 얼마나 잘 활용하는가
• Throughput - 할당 속도가 얼마나 빠른가

 

더 높은 점수를 만들기 위해서는 first-fit을 next-fit으로 바꿔서 Throughput을 개선해야 한다!

• first-fit은 매 할당마다 처음부터 메모리를 쭉 보다가 알맞은 자리가 있다면 할당하는 것
• next fit은 시작 위치를 처음부터가 아닌 이전 할당 위치부터 탐색해서 할당하는 것

 

그렇게 때문에 최근에 할당한 블록의 위치를 기억하는 전역 포인터 last_bp를 만들어 탐색하면 된다!!

//last_bp 전역 포인터 선언
static void *last_bp;   //next fit

 

mm_init

int mm_init(void)
{
    //4워드 빈 가용 리스트 만들 수 있도록 초기화
    if((heap_listp = mem_sbrk(4*WSIZE)) == (void*)-1)
        return -1;

    PUT(heap_listp, 0);     //정렬 패딩(unused)
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1)); //프롤로그 헤더 8바이트
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1)); //프롤로그 풋터 8바이트
    PUT(heap_listp + (3*WSIZE), PACK(0,1)); //에필로그 블록, 헤더만으로 구성된 크기가 0으로 할당된 블록
    heap_listp += (2*WSIZE);    //프롤로그 블록(힙의 시작점)을 가리킴 -> 힙의 시작 위치 쉽게 알 수 있음

    //힙을 CHUNKSIZE 바이트로 확장하고 초기 가용 블록 생성(힙 확장) (워드 단위로 변환)
    if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;

    last_bp = heap_listp;       //next_fit에서 사용하기 위해 초기 포인터 위치를 넣어준다.
    return 0;
}

 

last_bp에 힙(heap) 영역의 시작 주소를 가리키는 초기 포인터 위치를 넣어준다.

 

mm_malloc

void *mm_malloc(size_t size)
{
    size_t asize;     /*조정된 블록 사이즈*/
    size_t extendsize;  /*적합하지 않은 경우, 힙 확장할 사이즈*/
    char *bp;

    if(size == 0)
        return NULL;

    //더블 워드 정렬 제한 조건 만족 위해 더블 워드 단위로 크기 설정
    if(size <= DSIZE)
        asize = 2*DSIZE;    //최소 블록 크기 16바이트 할당(헤더 4 + 푸터 4 + 저장공간 8)
    else    
        asize = ALIGN(size + DSIZE); //8배수로 올림 처리

    //적절한 가용 블록 검색
    if ((bp = find_fit(asize)) !=NULL)
    {
        place(bp,asize);
        last_bp = bp;
        return bp;  //새롭게 할당한 블록 리턴
    }

    //적합한 블록이 없을 경우 힙 확장
    extendsize = MAX(asize,CHUNKSIZE);
    if((bp = extend_heap(extendsize/WSIZE))==NULL)
        return NULL;
    place(bp,asize);
    last_bp = bp;
    return bp;
}

 

find_fit (next_fit) 

#elif defined(NEXT_FIT)
static void *find_fit(size_t asize)
{
    void *bp = last_bp;

    //next_fit 포인터에서 탐색 시작
    for(bp = NEXT_BLKP(bp); GET_SIZE(HDRP(bp))> 0; bp =NEXT_BLKP(bp))
    {
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            last_bp = bp;
            return bp;
        }
    }

    //끝까지 갔는데 할당가능한 free block이 없으면 다시 처음부터 last_bp전까지 탐색
    bp = heap_listp;
    while(bp <last_bp)
    {
        bp = NEXT_BLKP(bp);
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            last_bp = bp;
            return bp;
        }
    }
    return NULL;
}

 

만일 last_bp부터 탐색하고, 할당할 곳을 못 찾았다면 처음부터 한번 더 탐색한다. 

앞에 빈 공간 없이 할당되어있을 경우에는 동작 시간 저하를 유발하겠지만, 조금이라도 빈 공간이 있다면 훨씬 효율적으로 동작할 수 있을 것이다.

 

 

thr가 개선되었다! 근데 왜 util은 줄었을까..

 

그리고! 

기존 mm_realloc 함수를 다른 분의 개선된 realloc 코드로 돌려봤더니...!!

 

기존 mm_realloc

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;

    /* 새 블록에 할당*/
    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;

    /* 데이터 복사 */
    copySize =GET_SIZE(HDRP(oldptr));
    if (size < copySize)    
        copySize = size;  

    memcpy(newptr, oldptr, copySize);   //새 블록으로 데이터 복사
    mm_free(oldptr);

    return newptr;
}

 

개선된 realloc

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t originsize = GET_SIZE(HDRP(oldptr));
    size_t newsize = size + DSIZE;
    
    if (newsize <= originsize) {
        return oldptr;
    }
    else {
        size_t addSize = originsize + GET_SIZE(HDRP(NEXT_BLKP(oldptr)));
        if (!GET_ALLOC(HDRP(NEXT_BLKP(oldptr))) && (newsize <= addSize))
        {
            PUT(HDRP(oldptr), PACK(addSize, 1));
            PUT(FTRP(oldptr), PACK(addSize, 1));
            return oldptr;
        }
        else
        {
            newptr = mm_malloc(newsize);
            if (newptr == NULL)
                return NULL;
            memcpy(newptr, oldptr, newsize);
            mm_free(oldptr);
            return newptr;
        }
    }
}

 

 

 

무려 util과 thru가 개선된 86점 점수가 떴다.

 

이건 내일.. 분석하도록 하겠다..

 

---

힙 정렬

 

오케이 이론 이해했다.

자 코드 봐보자~ 엥?? 에엥??? 해서 디버깅 돌리면서 복보고보고보고하면서 이해했다................!!!!!!!!

[알고리즘] 힙 정렬(Heap Sort)

 

 

 

---

참고

https://olive-su.tistory.com/428

Malloc Lab 구현