함수형 프로그래밍 ~ 시간 복잡도

함수형 프로그래밍

함수형 패러다임

• 패러다임은 프로그램의 순차, 분기, 반복, 참조를 어떻게 이용할 것인가를 다룸.

• 객체지향 추상화의 최소 단위가 객체인 것처럼 함수형은 함수가 최소 단위임.

• 함수 단위로 나눠지므로 재사용성이 높음.

• 데이터의 불변성을 지향하기 때문에 동작 예측이 쉽고 사이드 이펙트를 방지(스레드 등의 동시성 문제 해결)함.

• 객체 지향 : 제어 흐름의 간적접인 전환에 부과되는 규율, 함수형 : 변수 할당에 부과되는 규율.

//각 숫자를 더해주는 프로그램

const stringNumber = "12345";

//절차지향
let sum = 0;
for(let i=0; i<stringNumber.length; i++) {
    sum += stringNumber[i] -"0";
}

//함수형
stringNumber
    .split('')
    .map(x => parseInt(x))
    .reduce((x, y) => x + y, 0);

//객체지향
function StringNumber(string) {
    this.string = string;
}
StringNumber.prototype.calculate = function() {
    this.sum = 0;
    for(let i = 0; i<stringNumber.length; i++) {
        this.sum += stringNumber[i] -'0';
    }
};

const stringNumber = new StringNumber("12345");
const printer = new printer();
stringNumber.calculate();
printer.log(stringNumber.sum);

장단점

• 상태가 없기 때문에 사이드 이펙트가 없음. → 변수 조작이 되지 않음. 변수를 조작하려면 객체지향보다 메모리나 성능을 더 사용해야 함.

• 함수단위로 나누어지기 때문에 재사용성이 높음. → 함수를 너무 잘게 자르면 오히려 코드가 복잡해짐.

• 함수의 조합을 통해 코드가 짧고 간결함. → 많은 숙련도를 요구함.

선언형 프로그래밍

• 기존 명령형 프로그래밍은 문제를 어떻게 해결해야 하는지 컴퓨터에게 명령을 내리는 방법.

• 선연형 프로그래밍은 무엇을 해결해야 할지에 집중하고 해결 방법은 컴퓨터에게 위임하는 방법.

//명령형 (control flow)
let a = [1,2,3,4,5];
for(let i = 0; i < 5; i += 1) {
    if(a[i] % 2 === 0) {
        console.log(a[i]);
    }
}

//선언형 (data flow)
[1,2,3,4,5]
    .filter((item) => item % 2 === 0)
    .forEach((item) => console.log(item));

객체지향과 프로토타입

객체

객체지향

• 객체 위주로 설계하고 프로그래밍하는 패러다임.

• 최소 단위는 객체임.

• 각각의 객체는 메시지를 주고받을 수 있음.

프로토타입

• JS 객체는 클래스 기반 언어처럼 속성과 행위를 정의할 수 있음.

• JS에선 객체 리터럴, Object, 생성자 함수 세 가지 방법을 이용할 수 있음.

//객체 리터럴
const person = {
    name : "임효성",
    age : 24,
    move : function(destination) {
        console.log(`${destination}(으)로 이동합니다.`)
    }
}

//object 생성자 함수
const person = new Object();
person.name = '임효성';
person.age = 24;
pserson.move = function(destination) {
    console.log(`${destination}(으)로 이동합니다.`) 
}

//생성자 함수
function Person(name, company, move) {
    this.name = name;
    this.age = age;
    this.move = function(destination) {
        console.log(`${destination}(으)로 이동합니다.`)
    }
}

• 프로토타입 : 기존의 객체를 복사하여 새로운 객체를 생성하는 방식.

• 부모 객체를 이용하여 프로토타입 함수 정의하기, 부모 생성자, object.create(기존 객체 재활용)

모듈

• JS 파일이 많아짐에 따라 스크립트 파일 관리가 필요함.

• 예전 JS는 즉시 실행 함수 등을 통해 전역 스코프가 어느정도 오염되는 걸 막을 순 있지만, 스크립트 파일 간 의존도를 확인하기 힘들고 실행 순서를 제어해야 한다는 단점이 있음.

• 모듈은 의존도 확인 및 실행 순서 제어가 용이함. import와 export를 통해 수행할 수 있음.

모듈의 특징

• 항상 엄격 모드로 실행됨. ex) let, const를 생략하면 변수를 선언할 수 없음.

• 모듈 레벨 스코프가 있음. import를 해주지 않으면 서로 참조할 수 없음.

• 단 한 번만 평가됨. 2번 import해도 한 번만 실행됨.

• 지연 실행됨. 일반 스크립트는 body 태그 순서에 따라 실행되는 순서가 결정되지만 모듈은 deeper 옵션을 넣지 않아도 자동으로 지연 실행되기 때문에 모든 DOM 생성 후 실행.

이벤트 루프

브라우저에서 실행되는 스크립트는 어떻게 비동기 동작을 할까?

• 그림과 같이 JS에 이벤트 루프가 포함되지 않음. 이벤트 루프는 브라우저, nodejs에서 자체적으로 관리하기 때문에 싱글 스레드인 JS가 비동기적으로 처리할 수 있음.

• Web APIs(브라우저에서 제공하는 API, DOM 이벤트) → 브라우저에 위임 → web api에서 콜백함수 반환 → 콜백함수는 비동기 작업 후 task queue(call back queue)로 이동 → 순차적으로 call stack에 push함.

• 이 과정은 멀티 스레드로 동작함. JS가 싱글 스레드지만 브라우저가 멀티 스레드이기 때문에 비동기 처리가 가능한 것임.

이벤트 루프 동작 방법

유니코드

문자가 웹에 그려지는 과정

문자를 알기위한 문자 시스템 기본 개념

• CCS(Coded Character Set) : 문자들을 code point(character의 식별자, 정의된 정수 값)에 대응시켜 만든 코드화된 문자들의 집합. ex) KS C 5601, US-ASCII

• CES(Character Encoding Scheme) : CCS를 octet(8bit) 집합에 대응시키는 것(1:1 대응됨). Character를 시스템이 인식할 수 있는 값으로 변환하는 인코딩이 해당됨. ex) UTF-8

• TES(Transfer Encoding Syntax) : 인코딩한 문자가 특정 프로토콜을 타고 전송되도록 변환하는 것. URL에서 공백을 사용할 수 없는 등 통신 프로토콜에 제약이 있기 때문. ex) URL Encoding

그래서 유니코드란

• 전 세계 문자를 컴퓨터에서 다룰 수 있도록 만든 표준 시스템.

• 유니코드가 없을 땐 다양한 나라가 서로 다른 인코딩 방식을 사용함으로써 호환성, 확장성 문제를 일으킴.

• 문자를 포함하여 이모티콘도 포함됨.

정규표현식

• 패턴을 이용하여 문자 검색, 대체, 추출을 하기 위해 사용.

• 성능은 느리지만 대체로 짧은 문자열에서 사용함.

JS에서 생성하기

// new RegExp(표현식)
const regExp1 = new RegExp('^\d+');

// new RegExp(표현식, 플래그)
const regExp2 = new RegExp('^\d+','gi');

// 리터럴 방식
const regExp3 = /^\d+/;

정규표현식 객체의 기능

• test() : 입력받은 문자열에 패턴을 찾은 후 true, false를 반환함.

const message = "010-1234-5678";
const message2 = "no number";

const regExp = /\d{3}-\d{3,4}-\d{4}/;

console.log(regExp.test(message)); //true
console.log(regExp.test(message2)); //false

• exec() : 입력받은 문자열에 패턴을 찾은 후, 일치한 패턴 정보를 반환하고 없으면 null 반환 (문자추출).

const message = "010-1234-5678";
const message2 = "no number";

const regExp = /\d{3}-\d{3,4}-\d{4}/;

console.log(regExp.exec(message));
console.log(regExp.exec(message2));

/*console 값
[ '010-1234-5678',
  index: 0,
  input: '010-1234-5678',
  groups: undefined ]
 null*/

• match() : exec 함수와 동일하나 matchAll을 통해 매칭된 모든 케이스를 볼 수 있음.

const regexp = /t(e)(st(\d?))/g;
const str = 'test1test2';

const array = [...str.matchAll(regexp)];

console.log(array)

/*console 값
[ [ 'test1',
    'e',
    'st1',
    '1',
    index: 0,
    input: 'test1test2',
    groups: undefined ],
  [ 'test2',
    'e',
    'st2',
    '2',
    index: 5,
    input: 'test1test2',
    groups: undefined ] ]*/

• replace() : 정규표현식 객체를 파라미터로 받아 패턴이 있다면 원하는 문자열로 대체함.

const p = 'dog Dog cat';

const regex = /Dog/i;
console.log(p.replace(regex, 'ferret'));

//ferret Dog cat

• search() : 정규표현식 객체를 파라미터로 받아 패턴이 있다면 해당 정보의 위치를 반환함.

const paragraph = 'The quick brown fox jumps over the lazy dog. If the dog barked, was it really lazy?';

// any character that is not a word character or whitespace
const regex = /[^\w\s]/g;

console.log(paragraph.search(regex));
// expected output: 43

console.log(paragraph[paragraph.search(regex)]);
// expected output: "."

• capture - 괄호로 표현 문자의 그룹과 범위를 나타냄.

반복적인 알파벳 개수 알아내기

const raw = "AAAAAABBBDFFFFFFFKK";

const regExp = /(.)\1*/g;
const result = raw.match(regExp).reduce((a,b) => a + `${b.length}${b.slice(0,1)}`,"");

console.log(result) //6A3B1D7F2K

쿠키, 세션, 웹 스토리지

HTTP 통신

• HTTP request는 기본적으로 상태가 존재하지 않기 때문에 서버는 어떤 브라우저에서 요청이 온 건지 알 수 없음.

• 하지만 헤더에 쿠키를 담으면 서버가 쿠키를 읽어 어디서 온 것인지 알 수 있음.

Cookie

• 클라이언트에서 저장, 관리하는 데이터.

• 브라우저를 닫아도 데이터를 유지함.

• 서버에서 Set-cookie를 응답 헤더로 내려주면 클라이언트는 받아서 저장함.

Set-Cookie

• 키=값;옵션의 형태로 저장됨.

• 응답 헤더에 담으면 브라우저가 알아서 저장함.

• 각 데이터엔 여러 옵션 존재.
• Expires : 쿠키 만료 날짜를 지정함.
• Secure : HTTPS에서만 쿠키를 전송함.
• HttpOnly : JS에서 쿠키에 접근 못하도록 막음.
• Max-Age : 쿠키 수명을 정함. 이때 Expires는 무시됨.
• Domain : 도메인이 일치하는 요청만 쿠키가 전송됨.
• Path : 패스와 일치하는 요청만 쿠키가 전송됨.

Cookie의 취약점

• XSS(Cross-Site Script) 공격을 당할 수 있음. JS를 이용하거나 쿠키를 암호화하지 않고 보내면 쿠키값을 탈취 당할 가능성이 있음. → HTTPS를 통해 해결할 수 있음.

Session

• 서버 자체적으로 클라이언트를 기억하기 위해 등장 (서버는 쿠키 클라이언트를 모름).

• 서버는 HTTP Session Id를 식별자로 사용자를 구분함.

• 클라이언트는 HTTP Session Id를 쿠키 형태로 저장함.

Session의 문제점

• 세션은 서버에 파일로 저장됨. 만약 사용자가 엄청 많아진다면?

• 서버가 만약 2대라면 세션은 어떻게 관리해야할까? 각 인증정보가 퍼져있어 제대로된 값을 응답하지 못할 수 있음.

• 따라서 서버와 클러이언트간 인증은 JWT등의 별도 토큰을 사용하고 쿠키는 클라이언트 자체적인 지속적 데이터 관리 용도로 많이 사용됨.

웹 스토리지

• HTML5부터 등장한 클라이언트에 데이터를 저장하기 위한 새로운 방법. 쿠키의 한계를 보완.

• 로컬 스토리지와 세션 스토리지가 있음.

로컬 스토리지

• 반영구적으로 데이터가 저장되기 때문에 브라우저를 종료해도 데이터가 유지됨.

• 저장했던 도메인과 이용하는 도메인이 다른 경우 접근 불가.

• 쿠키와 마찬가지로 Key-Value 형태로 저장.

세션 스토리지

• 새 창을 생성할 때마다 개별적으로 저장되는 데이터를 관리.

• 브라우저를 닫으면 사라짐.

• 같은 도메인어도 세션이 다르면 데이터에 접근 불가.

• 쿠키와 마찬가지로 Key-Value 형태로 저장.

시간 복잡도

• 상수항은 무시함.

• 가장 큰 항 외엔 무시함. ex) O(n^2+n)이지만 O(n^2)로 표기함

성능 측정 방법

console.log("start")
const start = new Date().getTime();
const N = 100000000;

let total = 0;
for(let i =0; i<N; i++) {
    total += i;
}

const end = new Date().getTime();
console.log(end - start);
console.log('Finish')

/*start
1695
Finish*/

Follow Up Tasks