js 썸네일형 리스트형 동시성 제어 - by 직렬화(serialization) 여러 스레드가 동시에 실행되는 프로그램을 만들 때는 공유변수에 대한 할당(assignment) 연산을 조심해서 사용해야 한다. 서로 다른 스레드들이 수행하는 할당 연산들의 순서를 제어할 수 없기때문이다. 다수의 할당 연산이 동시에 진행되는 상황이 발생할 수 있다면 시스템이 올바르게 행동하게 만드는 수단을 마련해야 한다. 다시 말해, 동시적 프로그램이 올바르게 행동하게 만들기 위한 약간의 제약이 필요하다. 동시성 제어를 위해 사용할 수 있는 전략 하나의 공유 변수에 대해 둘 이상의 연산이 동시에 적용될 수 없게 만든다. 즉, 한 번에 하나의 트랜잭션만 진행되게 한다. 스레드들이 프로그램을 동시에 실행할 때 그 실행순서가 어떻든 동일한 결과가 나오게 설계한다. 많은 수의 스레드가 부분 영역을 담당하게 하며,.. 더보기 다중표현이 존재하는 데이터 구조 설계(2) - 강제 형변환(Coercion) 앞선 포스팅에서 다중표현이 존재하는 데이터의 예시로 복소수 데이터 모델을 설계해 보았다. 2024.03.06 - [SICP] - 다중표현이 존재하는 데이터 구조 설계(1) - 복소수 모델 그런데 복소수의 사칙연산을 복소수뿐 아니라 실수, 정수, 유리수등의 데이터와의 연산으로 확장하려면 어떻게 해야 할까? 예를 들어 실수 + 복소수 덧셈연산을 정의한다고 해보자. 앞의 방식을 그대로 사용한다면 install 함수 내부에서 연산-형식 테이블에 해당 연산을 정의하면 될 것 같다. // 실수 연산 패키지 function install_real_package() { ... } // 복소수 연산 패키지 function install_complex_package() { ... function add_complex_re.. 더보기 다중표현이 존재하는 데이터 구조 설계(1) - 복소수 모델 지난 두 포스팅에서 데이터를 사용하는 인터페이스와 구체적인 표현을 분리하는 방법으로 데이터 모델을 효과적으로 추상화하는 방법을 알아보았다. 2024.02.24 - [SICP] - 닫힘 성질을 충족하는 데이터 구조 설계(1) 2024.02.27 - [SICP] - 닫힘 성질을 충족하는 데이터 구조 설계(2) - 예제: 그림언어 데이터 설계 시 추상화 장벽을 세우는 것은 복잡한 시스템을 다스리는 데 있어 큰 위력을 발휘한다. 그런데 다중표현이 존재하는 데이터 모델을 설계하는 경우에는 이런 종류의 추상화 기법만으로는 부족할 수 있다. 어떤 데이터는 유용하게 표현하는 방식이 둘 이상일 수도 있으며, 다수의 표현을 다룰 수 있도록 설계되어야 하는 요구사항이 존재할 수 있기 때문이다. 그리고 이러한 케이스의 한 예.. 더보기 허프먼 부호화 트리 구현과 복호화 컴퓨터에서 텍스트를 표현하는 데 쓰이는 ASCII 코드는 각 문자를 7개의 고정된 비트열을 이용하여 부호화한다. 일곱개의 비트로는 총 128(2⁷)개의 서로 다른 문자를 표현할 수 있다. 이처럼 고정된 비트로 각 기호를 표현하는 부호를 가리켜 고정 길이 부호(fixed-length code)라고 한다. 한편, 각 기호를 서로 다른 개수의 비트로 표현하는 가변 길이 부호(varaible-length code)를 사용하는 것이 나을 때도 있다. 사용되는 빈도수가 높은 글자일수록 적은 수의 비트를 배정하면 데이터를 적게 사용하도록 부호화 할 수 있을 것이다. 모스 부호도 가변 길이 부호의 한 예시이다. 사용 빈도수가 높은 E, T, A, I 등의 문자에는 적은수의 비트를 배정하고, 사용 빈도수가 낮은 Q, X.. 더보기 닫힘 성질을 충족하는 데이터 구조 설계(2) - 예제: 그림언어 데이터 추상화와 닫힘 성질의 위력을 알아보기 위한 예시로 그림 언어(picture language)를 살펴보자. 참고로 이번 포스팅에서는 구체적인 벡터표현 방식이나 드로잉 함수등은 포함하지 않았다. 닫힘 성질을 충족하는 데이터 구조의 활용예시를 보면서 이 같은 추상화 방식이 얼마나 강력하고 유용한지만 알아볼 것이다. 그림 언어 그림 언어(picture language)는 간단한 그림 그리기용 언어이다. 화가 그림 언어에는 화가(painter)라는 딱 한 종류의 요소만 있는데, 이 화가요소는 주어진 액자(frame)에 들어맞게 기울이고 비례시킨 하나의 이미지를 그린다. 가령 화가요소 p, 액자객체 f가 있을 때, f를 인수로 하는 p를 호출하면 액자에 맞게 그린 이미지가 반환될 것이다 (참고로, 화가 요소.. 더보기 닫힘 성질을 충족하는 데이터 구조 설계(1) 데이터 추상화(data abstraction)란? 어떠한 복합 데이터 객체가 쓰이는 방식과 그 복합 데이터를 좀 더 기본적인 데이터 객체들로 구축하는 구체적인 방식을 분리할 수 있게 하는 방법론. 복합 데이터 객체를 사용하는 프로그램이 추상데이터에 대해 작동하도록 프로그램의 구조를 짜는 것이 핵심이다. 구체적 데이터 표현 데이터를 사용하는 프로그램간의 인터페이스는 선택자 함수와 생성자 함수의 집합으로 구성된다. 데이터 = 선택자함수 + 생성자함수 + 유효한 표현을 위해 그 함수들이 반드시 충족하는 조건들의 집합 데이터 추상화의 이득 데이터의 구체적인 표현 방식에 구애받지 않고 프로그램을 설계할 수 있다. 여러가지 대안 표현을 자유로이 실험할 수 있는 유연성이 생긴다. 위계적 자료구조 위계적(hierarc.. 더보기 거듭제곱, 최대공약수, 소수판정 최적화 (+ 확률에 의한 판정) 특정 산술 계산들에 적용할 수 있는 최적화 아이디어를 살펴보자. 거듭제곱 bⁿ 을 구하는 재귀함수는 다음과 같이 작성할 수 있다. function exp(b, n){ return n === 0 ? 1 : b * exp(b, n - 1); } 이 때의 증가차수는 O(n)이 될 것이다. 여기서 다음 연속제곱식을 이용하면 증가차수를 O(logn)으로 줄일 수 있다. bⁿ = (b½ⁿ)² : n = 짝수 bⁿ = b * bⁿ⁻¹ : n = 홀수 코드로 나타내면 다음과 같다. function exp(b, n){ return n === 0 ? 1 : n % 2 === 0 ? exp(b, n / 2) ** 2 : b * exp(b, n - 1); } exp(b, n / 2) 으로 치환할 때마다 필요한 단계수가 절반으.. 더보기 고차함수를 이용한 추상화 고차함수란? 동일한 프로그래밍 패턴이 서로 다른 여러 함수에 쓰이는 경우를 흔히 볼 수 있다. 이런 패턴을 하나의 추상적 개념으로 표현하기 위해 함수를 인수로 받거나 함수를 값으로 돌려주는 함수가 아주 유용하게 쓰일 수 있는데, 이러한 함수를 고차 함수(higher-order function)라고 한다. 고차함수는 추상의 관점에서 문제를 고찰하고, 그런 추상들을 프로그래밍 언어의 요소들로서 명시적으로 표현할 수 있게하여 추상들을 여타 계산 요소들과 마찬가지 방식으로 다룰수 있게 한다는 점에서 중요하다. 또, 자바스크립트에서는 함수에 일급요소 자격을 부여하기 때문에 고차함수를 유연하게 정의하고 사용할 수 있다. 일급요소란? 프로그래밍 언어는 계산적 요소들의 조작 방식에 이런저런 제약을 가하는데, 이 제약이.. 더보기 이전 1 2 다음
