JSON
JSON이란?
Javascript Object Notation
자바스크립트 객체를 범용적으로 읽을 수 있는 문자열 형태로 변환하기 위해
JSON.stringify()라는 메서드를 활용한다.
serialize(marshalling)
자바스크립트에서 해석할 수 있는 객체인 object에 저장된 내용을 데이터 스트림으로 변환하는 것이다. 자바스크립트가 아닌 다른 매개체를 활용해서 해당 객체를 전송하기 위해서는 serialize과정이 필요하다. 일반적으로 어디서나 해석가능한 string으로 serialize하고, 이를 해주는 자바스크립트 내장 메서드가 JSON.stringify다. Stringify, Serialize 모두 S로 시작하므로 헷갈리지 않게 기억해두자
오브젝트를 직렬화하는 것은 마셜링(marshalling)이라고도 한다. hyperldeger fabric의 체인코드를 golang으로 작성할때 marshalling 관련 메서드를 활용했었다.
deserialize
직렬화된 데이터 스트림을 오브젝트로 변환하는 작업이다. 범용적인 데이터인 string을 자바스크립트에서 쉽게 이용하기 위한 객체로 변환하기 위해 deserialize 한다. JSON.parse()메서드로 deserialize 한다.
JSON.stringify 구현하기
Tree menu ui 구현하기
tail recursion in js
https://homoefficio.github.io
https://velog.io/@yesdoing
https://exploringjs.com/es6/ch_tail-calls.html#sec_checking-for-tail-calls
여러 글을 읽으면서 이해하는 중... 아직 어렵다.
maximum callstack exceeded
- 재귀함수를 계속 호출하면 콜스택에 순차적으로 함수가 쌓여 결국 콜스택이 가득차게되어 오류 발생
tail position
해야 할 일이 남겨져 있지 않은 포지션
The last action in a function
마지막으로 반환되는 값?
아래의 함수에서 return 문은 tail position이 아니다. 곱하기 연산자가 사용되었으므로, 함수의 반환값을 추후 연산에 활용해야 하므로 스택에 계속 남기게 된다.
const factorial(num) {
if (num === 1) return num;
return num * factorial(num - 1);
}tail position optimization(=tail call 방식)
Tail Call 방식으로 짜여지면 Stack을 새로 만들지 않고 이미 있는 Stack 속의 값만 대체해서 Stack을 재사용하는 방식으로 동작하도록 최적화 할 수 있다. 이러한 최적화를 Tail Call Optimization(또는 Tail Call Elimination)이라고 하며 언어의 실행 환경에서 지원해줘야 한다.
return에서 연산자를 사용하면 optimization이 안된다.
(단, 언어 스펙에서 스택에 메모리를 쌓지 않는 연산자는 가능)
optimization을 위해선 서브루틴의 내부 연산에 필요한 상태는 값은 전부 인자로 넘겨야 하므로. accumulator가 필수적이다.
const factorial(num, acc=1) {
if (num === 1) return acc;
return factorial(num - 1, acc * num);
}결국 테일 포지션 최적화는 서브루틴의 반환지점을 caller에게 되돌아가지 않아도 되도록 수정하는 것이다. 따라서 스택을 계속 쌓지 않고, 결괏값(acc)을 인자로 전달하므로 함수가 되돌아가지 않고 바로 반환되는 것.
재귀호출을 반복으로 변환하는 과정엔 accumulator가 필수적이다.
non-tail-recursive and tail-recursive
A function is tail-recursive if the main recursive calls it makes are in tail positions.
For example, the following function is not tail recursive, because the main recursive call in line A is not in a tail position:
function factorial(x) {
if (x <= 0) {
return 1;
} else {
return x * factorial(x-1); // (A)
}
}factorial() can be implemented via a tail-recursive helper function facRec(). The main recursive call in line A is in a tail position.
function factorial(n) {
return facRec(n, 1);
}
function facRec(x, acc) {
if (x <= 1) {
return acc;
} else {
return facRec(x-1, x*acc); // (A)
}
}That is, some non-tail-recursive functions can be transformed into tail-recursive functions.
A function is tail-recursive if the main recursive calls it makes are in tail positions.
결론?
- 만약 실행 환경에서 Tail Call Optimization을 지원해주지 않으면 사실상 유일한 해결책은 반복문 뿐이다.
- 재귀 호출을 반복이나 Tail Recursion 방식으로 구현하려면 다음의 사항을 꼭 기억하자.
반복이나 꼬리 호출 단계별 계산 결과를 어딘가에 계속 저장한다.
js combination with recursion
한번에 이해가 안되면 외우자. 🤣
배열의 크기가 5일때, 3개의 조합을 구하는 것은
5개에서 한개의 원소를 택한 뒤, 4개의 나머지 배열에서 2개의 원소를선택한 것을 합친것과 같다.
rest는 나머지 배열을 의미한다.
restCombinations 는 나머지 배열에서 n-1 개의 원소를 택한 결과이다.
merged는 fixed된 원소와 나머지 배열을 합친 것이다. 주의할 점은 restCombinations의 결과는 배열이므로 map을 활용해서 배열에 담아주고,
마지막 result에 담을때도 ...연산자를 활용해서 원소를 하나하나 각각 최종 결과에 담아줘야된다.
const getCombinations = (arr, n) => {
if (n === 1) return arr.map(elem => [elem]);
const results = [];
arr.forEach((fixed, idx) => {
const rest = arr.slice(idx + 1);
const restCombinations = getCombinations(rest, n - 1);
const merged = restCombination.map(elem => [fixed, ...elem]);
result.push(...merged);
});
return result;
}js permutation with recursion
생각?
순열은 조합과 유사하다. 따라서 5개의 배열에서 n개로 이루어진 순열을 구하는 경우는
1. 5개의 배열에서 1개의 원소를 뽑는다.
2. 뽑은 원소와, 나머지 4개의 원소가 남아있는 배열에서 n - 1개의 원소를 뽑는 순열을 구하고 이를 합치는 과정을 반복하는 것이다.
가장 중요한 차이점은 rest다. 앞에서 뽑았던 원소라도 다시 rest에 포함해야 된다. 조합의 경우 한번이라도 이전에 뽑았던 원소는 rest에 넣어줄 필요가 없지만, 순열은 순서가 중요하므로 현재 뽑은 그 원소 이외에는 rest에 다시 포함해줘야 한다.
const getPermutations = (arr, n) => {
if (n === 1) return arr.map(elem => [elem]);
const results = [];
arr.forEach((fixed, idx) => {
const rest = [...arr.slice(0, idx), ...arr.slice(idx + 1)];
const restPermutations = getPermutations(arr, n - 1);
const merged = restPermutations.map(elem => [fixed, ...elem]);
results.push(...merged);
});
return results;
}