알고리즘

나이브 문자열 검색

긴 문자열에서 부분 문자열을 검색하는 것과 관련있다.
시간복잡도 O(n^2)

구현 코드

const long = 'i love korea, i love apple';
const short = 'love';

const SearchNaiveString = (long, short) => {
	let count = 0;
	for(let i = 0; i < long.length; i++){
		for(let j = 0; j < short.length; j++){
			if(long[i+j] !== short[j]) break;
			if(j === short.length-1) count++;
			// 이렇게 하면 반복 조금이라도 덜 돌긴함 ㅎ ... 복잡도로는 의미가 없긴하다..
			// count++;
			// i = i+j;
		}
	}
	return count;
}

하나씩 비교해가며 문자열에서 키워드가 얼마나 나오는지 카운트 하는 것이다.

가비지 콜렉션이란?

자바스크립트의 메모리 관리

가비지 콜렌션에 대해 알아보기 전에 자바스크립트의 메모리 관리부터 알아보겠다.

C, C++ 같은 경우는 메모리 관리를 개발자가 직접 해야하지만 자바, 자바스크립트 등의 언어는 메모리 할당과 해제를 자동으로 하여 개발자가 직접 관리를 하지 않는다. 이러한 자동 메모리 관리는 잠재적으로 혼란의 원인인데, 개발자가 메모리 관리에 대해 고민할 필요가 없다고 잘못된 인식을 할 수 있기때문이다. → 내 얘기임(WeakMap 할 때 ㅋㅋㅋㅋ)

메모리 생존 주기

1. 필요할 때 할당한다.
2. 할당된 메모리를 사용한다. (읽기, 쓰기)
3. 더 이상 사용하지 않으면 해제한다.

2번은 모든 언어가 같지만 1, 3 번은 C, C++ 등과 같은 언어에서는 명시를 해여하고, 자바스크립트, 자바 같은 언어는 암묵적으로 자동수행한다.

가비지 콜렉션

자바스크립트는 가비지콜렉션 이라는 자동 메모리 관리 방법을 사용한다.

가비지 컬렉터의 목적은 메모리 할당을 추적하고 할당된 메모리 블록이 더이상 필요하지 않게 되었는지 판단하여 회수하는 것이다.

“더 이상 필요하지 않은” 모든 메모리를 찾는건 힘든 일이다. 가비지 콜렉션 알고리즘과 그 한계를 이해하는데 필요한 개념을 알아보고 깊게 이해해보장

참조

가비지 콜렉션 알고리즘의 핵심 개념은 참조이다. A라는 메모리를 통해 B라는 메모리를 접근할 수 있다면 “B는 A에 참조된다.” 라고 한다. 모든 자바스크립트 오브젝트는 암시적으로 prototype을 참조하고 오브젝트의 속성을 명시적으로 참조한다.

참조 세기(Reference-counting) 가비지 콜렉션

현 최신 브라우저는 더 이상 이 방식을 사용하지 않는다. 가장 단순하게 구현되었고, 이 알고리즘은 어떤 오브젝트도 참조하지 않는 오브젝트를 더 이상 필요없는 오브젝트 라고 여긴다. 오브젝트 - 가비지라하고 이를 참조하는 다른 오브젝트가 없으면 수집한다.

이 알고리즘의 한계점으로 인해 순환 참조는 메모리 누수의 흔한 원인이다. 아래 코드로 보장

function f() {
  var x = {};
  var y = {};
  x.a = y;         // x는 y를 참조합니다.
  y.a = x;         // y는 x를 참조합니다.

  return "azerty";
}

f();

이런식으로 되면 사용하지 않음에도 불구하고 가비지 컬렉팅 대상이 되지 않는걸 확인할 수 있다.