Memoization과 WeakMap

WeakMap

Map vs WeakMap

1. Map vs WeakMap 차이점

• Map은 키와 값의 쌍을 강하게 참조하므로, 명시적으로 삭제하지 않는 한 메모리에 계속 유지됩니다.

• WeakMap은 키를 약하게 참조하므로, 키로 사용된 객체가 가비지 컬렉터에 의해 수집될 수 있습니다. 즉, 객체가 더 이상 참조되지 않으면 WeakMap에서 자동으로 제거됩니다.

2. WeakMap 사용의 장점

• 메모리 관리: WeakMap은 키를 약하게 참조하므로, 키로 사용된 객체가 더 이상 필요 없을 때 자동으로 가비지 컬렉터에 의해 정리됩니다. 이는 특히 객체 키가 많고, 메모리 관리가 중요한 상황에서 유용합니다.

3. WeakMap의 단점

• Primitive 키 사용 불가: WeakMap의 키는 반드시 객체여야 합니다. 문자열, 숫자 같은 프리미티브 값은 사용할 수 없습니다.

• 모든 캐시 상황에 적합하지 않음: WeakMap은 피보나치와 같은 숫자 인수를 기반으로 하는 함수에 적용하기 어렵습니다. 숫자는 객체가 아니기 때문에 WeakMap에서는 키로 사용할 수 없기 때문입니다.

Memoization 함수

function fibonacci(n: number): number {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

function memoize<T extends (...args: any[]) => any>(fn: T): T {
	const cache = new Map<string, ReturnType<T>>();
	return function (...args: Parameters<T>): ReturnType<T> {
		const key = JSON.stringify(args);
		if (cache.has(key)) {
			return cache.get(key) as ReturnType<T>;
		}
		const result = fn(...args);
		cache.set(key, result);
		return result;
	} as T;
}

• fn의 인수를 문자열 형태로 변환해서 cache에 저장

• 인수에 대해 기존 캐시에 값이 있으면 그 값을 반환, 없으면 계산하여 캐시에 저장 후 반환

const fibonacci = memoize((n: number): number =>  {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
});

console.log(fibonacci(40)); // 처음 시도 시 시간이 걸림
console.log(fibonacci(40)); // 두번째 시도 시 캐싱된 값을 가져오기 때문에 빠르게 출력

LRU(Least Recently Used) Cache

1. LRU (Least Recently Used) 캐싱 개념

• 페이지 네이션이 자주 발생하는 웹 애플리케이션.

• 큰 데이터를 로딩하는 애플리케이션에서 최근 데이터만 캐시에 보관.

2. LRU 캐시 구현 방법

• 최신 항목을 맨 앞으로 이동하는 것.

• 가장 오래된 항목을 쉽게 제거하는 것.

class LRUCache<K, V> {
    private capacity: number;
    private cache: Map<K, V>;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key: K): V | undefined {
        if (!this.cache.has(key)) {
            return undefined; // 캐시에 없는 경우
        }
        const value = this.cache.get(key);
        // 가장 최근에 사용된 키로 갱신 (삭제 후 다시 삽입)
        this.cache.delete(key);
        this.cache.set(key, value as V);
        return value;
    }

    put(key: K, value: V): void {
        // 이미 존재하는 키일 경우 갱신 (삭제 후 다시 삽입)
        if (this.cache.has(key)) {
            this.cache.delete(key);
        }
        // 용량을 초과할 경우 가장 오래된 항목 삭제
        if (this.cache.size >= this.capacity) {
            const oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey);
        }
        this.cache.set(key, value);
    }
}

// 사용 예시
const lruCache = new LRUCache<string, number>(3);
lruCache.put("a", 1);
lruCache.put("b", 2);
lruCache.put("c", 3);
console.log(lruCache.get("a")); // 1
lruCache.put("d", 4); // 용량 초과로 가장 오래된 "b" 제거
console.log(lruCache.get("b")); // undefined (삭제됨)

3. LRU 캐시의 장단점

• 장점:
• 자주 사용되는 항목을 우선적으로 캐시에 보관해 성능을 최적화합니다.
• 메모리 사용을 제한하여, 캐시가 메모리 부족 문제를 일으키지 않도록 제어할 수 있습니다.

• 단점:
• 캐시 용량이 제한적이므로, 용량보다 많은 항목을 캐시에 보관할 수 없습니다.
• 연결 리스트와 해시맵을 사용하면 메모리는 효율적으로 관리되지만, 복잡도가 약간 증가합니다.

4. 기타 캐시 관리 전략

• LFU (Least Frequently Used): 가장 적게 사용된 항목을 삭제하는 방식입니다. 접근 빈도가 낮은 항목을 캐시에서 삭제하므로, 접근 빈도가 중요한 경우에 유용합니다.

• FIFO (First In, First Out): 먼저 캐시에 들어온 항목을 먼저 삭제하는 방식입니다. 고정된 시간 동안만 데이터를 보관해야 할 때 유용합니다.

• TTL (Time-To-Live): 캐시에 항목이 추가된 후 일정 시간이 지나면 삭제하는 방식입니다. 최신 데이터만 필요한 경우 유용합니다.

Set

• 특징: 중복을 허용하지 않는 값을 저장하는 컬렉션입니다.

• 장점: 값의 존재 여부를 빠르게 확인할 수 있으며, 유일한 값들만 관리할 때 유용합니다.

• 단점: 키-값 쌍으로 데이터를 저장하지 않기 때문에, 특정 값을 기준으로 매핑해야 하는 경우 부적합합니다.

const uniqueValues = new Set<number>();
uniqueValues.add(1);
uniqueValues.add(2);
uniqueValues.add(1); // 중복된 값은 추가되지 않음
console.log(uniqueValues); // Set { 1, 2 }

WeakSet

• 특징: 객체만 저장할 수 있으며, WeakMap처럼 객체가 가비지 컬렉터에 의해 정리될 수 있습니다.

• 장점: 메모리 관리가 필요하거나, 객체만 다루는 경우 유용합니다.

• 단점: 프리미티브 값을 저장할 수 없으며, 반복할 수 없습니다.

const weakObj1 = { id: 1 };
const weakObj2 = { id: 2 };

const weakSet = new WeakSet<object>();
weakSet.add(weakObj1);
weakSet.add(weakObj2);

console.log(weakSet.has(weakObj1)); // true

Set vs Map

1. 기본 구조와 목적

• Set: 중복 없는 고유한 값들의 집합을 저장하는 컬렉션입니다. 같은 값을 여러 번 추가하려고 하면, 중복 없이 하나의 값만 유지됩니다.

• Map: 키-값 쌍을 저장하는 컬렉션입니다. 키는 고유해야 하며, 각 키에 대해 하나의 값을 저장할 수 있습니다.

2. 데이터 저장 방식

• Set: 값만 저장합니다. 각 값은 컬렉션 내에서 유일해야 하며, 키-값 쌍의 구조가 없습니다.

• Map: key와 value의 쌍으로 데이터를 저장합니다. key는 고유하며, 각 키에 매핑된 값을 가지고 있습니다.

// Set 예제
const set = new Set();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복된 값은 무시됨
console.log(set); // Set { "apple", "banana" }

// Map 예제
const map = new Map();
map.set("name", "Alice");
map.set("age", 30);
map.set("name", "Bob"); // 동일한 키에 대한 값 덮어쓰기
console.log(map); // Map { "name" => "Bob", "age" => 30 }

3. 데이터 접근 방식

• Set: 인덱스나 키를 통해 접근할 수 없으며, forEach나 for...of 구문으로 순회하며 값을 접근할 수 있습니다.

• Map: 키를 통해 직접 접근할 수 있습니다. map.get(key)를 사용하여 특정 키에 매핑된 값을 반환받을 수 있습니다.

// Set 순회 예제
set.forEach(value => console.log(value));

// Map 값 접근 예제
console.log(map.get("name")); // "Bob"
console.log(map.get("age")); // 30

4. 중복 허용 여부

• Set: 중복된 값을 허용하지 않습니다. 동일한 값을 여러 번 추가해도 한 번만 저장됩니다.

• Map: 키는 중복되지 않지만, 다른 키와 동일한 값을 가질 수 있습니다. 따라서 여러 키가 같은 값을 가질 수 있습니다.

// Set 중복 예제
set.add("banana");
console.log(set); // Set { "apple", "banana" } (중복된 "banana"는 무시됨)

// Map 중복 값 예제
map.set("nickname", "Bob");
console.log(map); // Map { "name" => "Bob", "age" => 30, "nickname" => "Bob" }

5. 특정 값 확인

• Set: set.has(value)를 사용하여 특정 값이 존재하는지 확인합니다.

• Map: map.has(key)를 사용하여 특정 키가 존재하는지 확인합니다.

console.log(set.has("apple")); // true
console.log(map.has("name")); // true

6. 크기 확인

• Set: set.size로 Set의 항목 개수를 확인할 수 있습니다.

• Map: map.size로 Map의 키-값 쌍의 개수를 확인할 수 있습니다.

console.log(set.size); // 2
console.log(map.size); // 3

7. 사용 예시

• Set: 중복을 허용하지 않는 유일한 값들의 목록을 관리할 때 적합합니다. 예를 들어, 사용자 ID 목록, 고유 태그 목록 등.

• Map: 특정 키에 매핑된 값을 빠르게 찾을 수 있는 상황에 적합합니다. 예를 들어, 이름과 연락처가 매핑된 전화번호부, 사용자 설정 등의 데이터를 저장할 때 유용합니다.

요약