오늘 TIL은 KPT 회고 보단 자료구조의 회고를 할 예정이다. 그 주인공인 자료구조는 Map이다.

첫번째 MAP 사용법

프로젝트를 시작할 때 자료구조를 정하는 것이 중요하다는 걸 알았다.

내 인생에서 Map으로 코드를 짜본 기억이 파이썬 과제 할때라.. 단순 전화번호부 같은 전화번호, 이름처럼 중복이 가능할 수 없는 전화번호같은 key부분이랑 key로 접근하면 그 특정 value를 쓸 떄만 쓴다는 고정관념이 있었다.

어제 키오스크 개인과제 부분에서 튜터님이 객체지향적인 큰그림을 그려주실 떄 Map을 사용하여

Private Map<String,List<Menu>> menus;
private Map<String,List<Item>> meneItem;

이런 식으로 해당 List로 접근을 String key값으로 접근을 한게 너무 신박했었다.

나는 메뉴 또는 상품들을 불변이니깐 객체배열로 담았고

장바구니 기능을 ArrayList 자료구조를 사용해서 가변적으로 썼었다.

목적이 있는 자료구조 선택이라서 후회는 없지만... 더 좋을 수 있고 새로운 방식을 생각을 못 했던거에 좀 내 자신이 한심해 보였다!

나중에 시간이 나면 Map 자료구조를 사용해서 다시 키오스크 개인과제를 구현하고 싶다.

두번째의 Map 사용법

오늘 오전에 알고리즘 수업의 튜터님의 말씀을 빌리자면

Map이라는 자료구조는 현업에서도 많이 쓰이고 특히 캐시쪽에서 자주 쓰인다.

그래서 map이 어떻게 캐시에서 쓰이는지 적어볼려고 한다!

일단 캐시를 설명하기 전에 어떠한 데이터들은 프로그램이 실행되면서 reuse를 한다. 매번 데이터를 읽어들이거나, 네트워크를 통해 다운 받는건 상당히 비효율적이다. 그래서 reuse 가능성이 있는 데이터는 메모리에 유지하고 있다가 필요한 시점에 reuse하면 프로그램의 전체적인 성능을 높일수 있는데, 이러한 기법을 캐싱(caching)이라고 한다.

하지만 메모리는 한정되어 있고 무한적으로 캐시를 사용할 수 없으니 캐시의 어느정도 적당한 선에서 제한을 해야한다. 그래서 프로그램을 작동하다 보면 캐시가 가득차 새로운 캐시를 추가하기 위해선 이전 캐시된 항목을 제거해야하는데 제거할지 선택하는 기준에는 여러가지가 있을 수 있다.

그 중 하나로 LRU(Least Recently Used)캐시는 캐싱 알고리즘중 하나로, 캐시영역이 가득 찼을 떄 가장 오래전에 사용된 항목을 제거하는 방식이다.

통상 캐시를 구현할 떄에는 데이터를 찾는 기준이 되는 어떤 key 값을 사용하여 그에 상응하는 데이터를 빠르게 찾아야 한다.

구현의 핵심은 사전의 key중 어떤 것이 가장 최근에 사용되었고, 어떤 오래된 캐시인지 구별할 수 있는 정보나 방법이 필요하다.

LRU 구현은 map 또는 LinkedList로 구현이 가능하지만, 자바에는 LinkedHashMap이라는 강력한 아이가 있으니 사용해서 구현을 해볼까 한다!

@SuppressWarnings("serial")
class LRU<K, V> extends LinkedHashMap<K, V> {
    private int size;

    private LRU(int size) {
        super(size, 0.75f, true);
        this.size = size;
    }
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }
    public static <K,V> LRU<K,V> newInstance(int size) {
        return new LRU<K,V>(size);
    }
}

1. @SuppressWarnings("serial")은 클래스에 대한 serialVersionUID의 부재와 관련된 컴파일러 경고를 억제하는 데 사용된다.

2. LinkedHashMap을 상속을 받아 사용한 걸 볼수 있는데. super을 이용해서 생성을 한다

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

여기서 initialCapacity는 LinkedHashMap의 최초의 크기를 말하는데 우리가 구현할 건 cache이니깐 cache의 크기가 되는걸 알수 있다.

loadFactor는 hash 버킷의 크기를 동적으로 확장할 때의 임계점을 설정하는 부분이다.

accessOrder는 true로 설정할 경우 LinkedHashMap이 다르게 동작해서 cache로 사용할 수 있는 것이다.

true는 요소의 순서가 삽입 순서가 아닌 액세스(가져오기/넣기) 순서에 따라 결정되도록 한다.

3. removeEldestEntry는 가장 오래된 항목(가장 최근에 사용되지 않은 항목)을 제거해야 하는지 여부를 결정하기 위해 각 넣기 작업 후에 호출된다. 이 구현에서는 캐시 크기가 지정된 크기를 초과하면 true를 반환하므로 LRU 제거 정책이 적용됩니다.

4. newInstance(int size) 메서드는 지정된 크기로 LRU 캐시의 새 인스턴스를 생성하는 정적 팩터리 메서드이다. LRU 캐시를 인스턴스화하는 편리한 방법을 제공한다.

사용법

LRU<Integer, String> cache = LRU.newInstance(100);

cache는 일반 map처럼 캐시를 사용할 수 있으며 캐시 크기가 100을 초과하면 최근에 가장 적게 사용된 항목을 자동으로 제거를 한다.

LRU cache: https://leetcode.com/problems/lru-cache/
릿코드에서 문제도 있는데 medium이라 어려울듯하다... 나중에 시간 될 떄 풀어봐야할거 같다.

튜터님이 자료구조 책도 추천을 해주셨다
자바로 배우는 핵심 자료구조와 알고리즘

출처:https://blog.naver.com/gngh0101/221299269084
https://blog.naver.com/sooopd/223058424805