Balanced graph와 unbalanced graph

이미지
사람과 사람 사이의 관계를 그래프로 나타내보자. 그렇다면 사람은 node로 표현될 것이고, 두 사람이 서로를 알고 있다면 두 node 사이의 edge를 그릴 수 있다. 실제로는 내가 모르는 사람이 나를 알고 있을 수도 있고, 내가 아는 사람이 나를 모를 수도 있지만, 그런 복잡한 경우는 생각하지 않고 서로 간에 알고 있는 경우만을 고려하도록 하자. 1) 이때 두 사람은 친구이거나 적일 것이다. 현실적으로는 그냥 아는 사람이고 적인지 친구인지 별생각 없을 수도 있거나, 내가 친구라고 생각하는 사람이 나를 적으로 생각할 수 있지만, 이런 경우 문제가 복잡해지니 생각하지 않도록 하자. 그러면 친구인 사람 사이의 edge에는 +사인을, 적인 사람 사이의 관계에는 -사인을 추가하여 signed undirected graph 2) 로 표현할 수 있다. 사람 사이의 관계를 signed graph로 표현한다면, 이는 아래의 4가지 모습 중 하나일 것이다. 만약 친구일 확률과 적일 확률이 똑같이 1/2로 랜덤하게 그래프를 생성하였다면, 모두가 친구로 생각하거나 모두가 적으로 생각할 확률은 각각 1/8이고, 한 명은 다른 두 명을 적이라고 생각하는데 두 사람은 서로 친구라고 생각하거나, 친구로 생각하는 두 사람이 서로 적일 확률은 각각 3/8으로 나타날 것이다. 하지만 실제 인간관계를 그래프로 그렸을 때는 첫 번째나 세 번째 삼각형이 나올 확률은 기대했던 것보다 높게 나오고, 두 번째나 네 번째 삼각형이 나올 확률은 기대했던 것보다 낮게 나온다. 이 두 삼각형은 다른 삼각형으로 쉽게 변하기 때문이다. 내가 친구라고 생각하는 두 사람이 서로를 적으로 생각하는 경우를 보자. 이 경우 나에게 압박이 가해져서 한쪽 관계를 끊거나, 적으로 돌아서기 쉽다. 3명이 서로를 모두 적으로 생각하는 경우도 쉽게 변한다. 이런 경우 공동의 적을 상대하기 위해 적이었던 두 사람이 손을 잡기 쉽다. 이렇게 변하기 쉬운 삼각형을 unbalanced triangle이라고 부르고

OSI 모델은 무엇인가

OSI 모델 은 추상화를 위해 프로토콜을 여러 계층의 layer로 나누고, 각 layer에서 자신이 책임진 일만 하도록 설계한 네트워크 모델이다. 각 layer는 완전히 독립되어 있으며, 각 layer에서 수행해야 하는 일만 제대로 된다면 그 구현은 다른 구현으로 대체 될 수 있도록 설계되어야 한다. OSI 7 layer OSI layer는 보통 7계층으로 나누어지기 때문에 OSI 7 layer라고 불리기도 한다. 각 layer의 이름은 가장 아래부터 physical layer , data link layer , network layer , transport layer , session layer , presentation layer , application layer 다. 이를 다시 크게 둘로 나누어서 network layer까지의 아래 3개 layer는 media layer라고 하고, transport layer부터 위의 4개 layer를 host layer라고 한다. media layer는 네트워크상에서 원하는 머신을 찾아 데이터를 보내는 역할을 하고, host layer는 전송된 데이터를 안전하게 사용하는 방법에 대한 역할을 한다. 그러면 이제부터 각 layer에 대해 자세한 설명을 할 것인데 명심해야 할 것은 어떤 네트워크 프로토콜을 만들 때 OSI 모델을 지키는 것이 필수적인 것은 아니라는 것이다. 실제로 많이 사용되는 네트워크 프로토콜 중에서도 완벽하게 OSI의 원칙에 따라 설계된 프로토콜도 거의 없고, 7개 계층을 전부 구현하여 사용하는 것도 본 적이 없다. 그냥 네트워크 프로토콜은 이러한 역할이 필요하고, 그것은 이러한 순서로 지켜지는 게 안전하다는 가이드 정도로 생각하는 것이 좋다. physical layer 우선 가장 아래 계층은 physical layer 다. physical layer에서는 전달 매체를 통해 전달된 신호를 어떻게 0과 1로 바꾸는지를 담당한다. 데이터의 전달 매체에 따라서 0과 1이 반드시 bit일 필요도 없

[Android] AsyncTask - UI 스레드에서는 시간이 오래 걸리는 일을 하면 안 된다

안드로이드는 메인 스레드에서 UI와 관련된 일을 처리한다. 그래서 메인 스레드를 UI 스레드라고 부르기도 한다. 그런데 UI 스레드에서 오랫동안 CPU를 점유하는 일을 하게 되면, " Application Not Responding "이라는 메시지가 나온다. 이러면 앱에 대한 컨트롤을 잃게 되며, 응답할 때까지 기다리거나 강제종료할 수밖에 없다. 이런 일을 방지하기 위해서는 새로운 스레드를 생성하여 다른 스레드에 시켜야 한다. 하지만 로우레벨의 스레드를 바로 사용하면 동기화하는 과정에서 쉽게 실수할 수 있으므로 실수 없이 쉽게 스레드를 사용할 수 있게 하려고 안드로이드는 AsyncTask 라는 클래스를 지원한다. AsyncTask 는 UI 스레드에서 잠시 동안 백그라운드로 일을 호출하고 싶을 때 사용된다. 잠시 동안이라는 것을 문서상 으로는 should ideally be used for short operations (a few seconds at the most.) 1) 라고 표현하고 있다. 만약 길게 실행되는 일을 백그라운드에서 실행하고 싶으면 스레드를 직접 사용하거나 다른 방법을 이용해야 한다. 그 이유는 몇 가지 있다. 대표적인 문제는, AsyncTask 가 Activity 에 종속되지 않기 때문에, AsyncTask 를 호출했던 Activity 가 먼저 죽었을 경우 처리가 복잡해진다. 또 다른 문제는 백그라운드 스레드를 점유해버린다는 것이다. AsyncTask 는 AsyncThread 가 새로 만들어질 때마다 스레드를 생성하지 않는다. 고정된 크기의 스레드 풀이 있고 이 스레드 풀을 모든 AsyncTask 가 공유한다. API 버전에 따라서 1개의 태스크만 실행될 수도 있고, 여러 개의 태스크가 병렬적으로 동시에 수행될 수도 있는데, 최신 버전은 1개만 실행되며 모든 태스크는 순차적으로 실행하게 되어 있다. 따라서 어떤 태스크가 데 시간이 오래 걸린다면 다른 태스크가 실행되지 못한다. AsyncTask 를 사용하는

멀티 쓰레드 환경에서 fork는 조심해야 한다.

리눅스나 유닉스 같은 POSIX 시스템에서는 fork 를 이용해서 자신과 똑같은 프로세스를 만들 수 있다. 이때 fork 를 호출한 프로세스를 부모 프로세스 라고 하고, 새로 생성된 프로세스를 자식 프로세스 라고 부르는데, 자식 프로세스는 부모 프로세스의 모든 메모리를 복사한다. fork 는 그 뒤 exec 을 해서 다른 바이너리를 실행시키는 fork-exec 이 일반적인 사용법이다. 하지만 자식 프로세스 는 부모 프로세스 와 완전히 같은 메모리를 가지기 때문에, 스레드가 존재하지 않던 시절에는 exec 을 하지 않고 병렬 처리를 하기 위해서도 자주 사용되었다. 지금은 스레드를 사용하는 것이 더 사용하기 쉽고 가벼운 방식이기에 스레드를 병렬처리를 위해 스레드를 주로 사용하지만, 스레드보다 서로 간에 독립적이기 때문에 일을 분리하기 위해서 사용하기도 한다. 분명히 fork 는 없어서는 안 될 기능이지만 fork 에는 태생적 한계가 있다. 애초에 fork 는 스레드라는 개념이 존재하지 않던 시절에 만들어졌기 때문에 thread-safe 하지 않다. 따라서 멀티스레드 환경에서 사용하려면 조심해서 사용해야 한다. fork 가 멀티스레드 환경에서 문제를 일으키는 이유는 fork 가 부모 프로세스 의 메모리를 전부 복사하지만, fork 를 호출한 스레드를 제외한 나머지 스레드들은 죽어버리기 때문이다. 따라서 fork 를 호출한 스레드 이외의 스레드에서 획득한 자원은 아무것도 해제되지 않는다. 메모리 릭도 충분히 문제지만, 이는 단순한 메모리 릭만을 의미하지 않는다. fork 가 복사한 메모리에는 힙이나 스택 이외에 mutex 나 condition variable 들도 포함된다. 만약 mutex 나 condition variable 이 다른 스레드에서 사용된 채로 fork 된다면 해당 변수로 보호되는 critical section에는 다시는 진입할 수 없게 된다. 특히나 malloc 같은 thread-safe 한 함수는 대부분 내부적으로 글로벌한 m

Flow vs TypeScript - 왜 나는 아직 타입스크립트를 쓰는가

나는 개인적으로 동적 타입 언어보다 정적 타입 언어를 선호한다. 아니 동적 타입 언어를 싫어한다. 정확히 말하면 동적 타입 언어이기에 생기는 실수에 의한 버그들과 그로 인해 사고에 걸리는 부하를 싫어한다. 그래서 웹 개발을 몇 년을 했지만 여전히 동적 타입 언어인 자바스크립트로 코딩하는 것은 싫어한다. 그 때문에 어지간히 간단한 일이 아니라면, 자바스크립트를 사용할 때 반드시 다른 툴을 붙여 정적분석을 한다. 자바스크립트의 정적 분석을 위해 사용되는 도구는 크게 2가지로 나뉜다. 마이크로소프트에서 만든 타입스크립트 와 페이스북에서 만든 플로우 다. 한때는 구글이 타입스크립트를 기반으로 만든 AtScript라는 것도 있었지만, 이는 다시 TypeScript로 합쳐지면서 사라지게 되었다. 타입스크립트와 플로우는 둘 다 자바스크립트를 정적 타입 검사가 가능하도록 만들어주었다. 하지만 접근하는 방향은 완전 다른 방향으로 접근하였다. 우선 타입스크립트는 2012년에 첫 버전 이 나왔다. 타입스크립트의 목표는 자바스크립트로 변환되는 더 쓰기 편하고 안전한 언어를 만드는 것이었다. 어디까지나 자바스크립트로 변환되는 언어를 만드는 것이었기에 문법적 기반을 자바스크립트에 두었다. 다시 말해서 타입스크립트의 문법은 자바스크립트 문법의 슈퍼 셋이다. 자바스크립트의 문법을 기반으로 하여 그 위에 추가적인 기능을 더했다. 추가된 기능에는 class 나 enum 처럼 사용성을 올리기 위한 기능도 있고, private 이나 타입 어노테이션 처럼 안전한 코드를 만들기 위해 추가된 기능도 있다. 반면에 페이스북의 플로우는 새로운 언어를 정의하지 않는다. 플로우는 ECMAScript 6 (a.k.a. ES6) 의 타입 검증 도구일 뿐이다. 이미 타입스크립트의 많은 기능이 ES6에 표준으로 들어왔기 때문에 새로운 언어를 만들 필요가 없었다. 플로우는 새로운 언어를 정의하지 않기 때문에 이미 자바스크립트로 작성된 프로그램을 바로 분석할 수 있다. 타입이 모호한 경우에는 어노테이션을 추

reflection과 introspection

Reflection 은 실행 시간에 객체의 메타 데이터에 접근하여 원래라면 접근할 수 없는 타입 정보, 프로퍼티, 멤버 함수 등을 수정하는 행위를 말한다. 이는 프로그래머에게 기존의 제약을 넘어서 더 많은 것을 할 수 있게 해준다. Reflection 중 실행 시간에 메타 데이터를 읽는 기능 만을 구분해서 introspection 이라고 부르기도 한다. 하지만 reflection이라고 하면 당연히 introspection을 포함해서 말하는 것이기 때문에, 특별한 이유가 없으면 그냥 전부 reflection이라고 부르기도 한다. Reflection은 매우 유용한 도구로 보인다. 하지만 개인적으로 좋아하는 기능은 아니다. 오히려 싫어하는 기능이다. Reflection이 주는 힘은 너무 과한 힘이고 대부분의 경우 득보다 실이 더 많다. Reflection은 기본적으로 실행 시간에 실행되기 때문에 컴파일 타임에 당연히 잡힐 문제를 잡지 못한다. 게다가 컴파일러가 코드 최적화를 하지 못하기 때문에 성능이 느려지는 등 여러 문제를 일으킨다. 그래서 reflection을 사용해야 하는 일이 생기면, 일단 다른 방법이 없는지 알아보고, reflection을 사용하지 않을 방법이 알아보고, 그래도 방법이 없을 때만 사용한다. 지금까지 그래야 했던 경우는 디펜던시 인젝션을 하는 라이브러리를 이용하거나, 디버깅 로그를 찍기 위해 보통은 접근할 수 없는 정보가 필요하거나, 임의의 객체를 시리얼라이즈를 하는 함수를 만들거나, 내가 건드릴 수 없는 라이브러리에서 제공한 객체의 정보를 가져오는 등의 일이었다. 전부 수정할 수 없어서 어쩔 수 없이 쓴 경우다.

[ECMAScript 6] class 선언하기

JavaScript는 훌륭한 객체 지향 언어다. 하지만 프로토타입 기반 객체지향 이라는 독특한 개념과 특유의 verbose한 문법 때문에 다른 언어에서 넘어온 사람들은 쉽게 적응하지 못하였고, 객체 지향스럽지 않은 코드를 작성하였다. 그럼에도 프로토타입은 다른 객체 지향 언어가 제공하는 class 에 비해서 더 유연한 확장성 지원하기 때문에 많은 JavaScript 개발자들은 class 가 필요 없다는 입장을 고수해왔다. 하지만 프로토타입이 코드를 verbose 하게 만들고, 가독성을 떨어뜨린다는 주장은 꾸준히 제기되었고, 결국 ECMAScript 6에 드디어 class 키워드가 추가되어 보다 쉽게 객체 지향적 코드를 작성할 수 있게 되었다. 여기서 중요한 것은 class 키워드가 ES6에 추가되었다고 해서 클래스 기반 객체지향 이라는 개념이 추가된 것은 아니라는 것이다. ES6도 여전히 프로토타입 기반의 객체 지향 언어이다. class 는 프로토타입 기반 객체를 만드는 syntactic sugar 일 뿐이다. 즉, 위와 같은 코드는 ES5를 기준으로 보면 아래와 같이 해석된다. 1) class 스타일의 간결성과 prototype 의 유연성을 동시에 갖기 위한 선택이었다. 1) 완전히 일치하는 것은 아니다. ES5에는 생성자로 쓸 수 없는 함수 가 존재하지 않기 때문에 method를 완벽히 재현할 수 없다.

이 블로그의 인기 게시물

[C++] enum class - 안전하고 쓰기 쉬운 enum

Log Aggregator 비교 - Scribe, Flume, Fluentd, logstash

RAII는 무엇인가

[Python] cache 데코레이터로 최적화하기

[Web] SpeechSynthesis - TTS API