SICP 썸네일형 리스트형 동시성 제어 - by 직렬화(serialization) 여러 스레드가 동시에 실행되는 프로그램을 만들 때는 공유변수에 대한 할당(assignment) 연산을 조심해서 사용해야 한다. 서로 다른 스레드들이 수행하는 할당 연산들의 순서를 제어할 수 없기때문이다. 다수의 할당 연산이 동시에 진행되는 상황이 발생할 수 있다면 시스템이 올바르게 행동하게 만드는 수단을 마련해야 한다. 다시 말해, 동시적 프로그램이 올바르게 행동하게 만들기 위한 약간의 제약이 필요하다. 동시성 제어를 위해 사용할 수 있는 전략 하나의 공유 변수에 대해 둘 이상의 연산이 동시에 적용될 수 없게 만든다. 즉, 한 번에 하나의 트랜잭션만 진행되게 한다. 스레드들이 프로그램을 동시에 실행할 때 그 실행순서가 어떻든 동일한 결과가 나오게 설계한다. 많은 수의 스레드가 부분 영역을 담당하게 하며,.. 더보기 다중표현이 존재하는 데이터 구조 설계(2) - 강제 형변환(Coercion) 앞선 포스팅에서 다중표현이 존재하는 데이터의 예시로 복소수 데이터 모델을 설계해 보았다. 2024.03.06 - [SICP] - 다중표현이 존재하는 데이터 구조 설계(1) - 복소수 모델 그런데 복소수의 사칙연산을 복소수뿐 아니라 실수, 정수, 유리수등의 데이터와의 연산으로 확장하려면 어떻게 해야 할까? 예를 들어 실수 + 복소수 덧셈연산을 정의한다고 해보자. 앞의 방식을 그대로 사용한다면 install 함수 내부에서 연산-형식 테이블에 해당 연산을 정의하면 될 것 같다. // 실수 연산 패키지 function install_real_package() { ... } // 복소수 연산 패키지 function install_complex_package() { ... function add_complex_re.. 더보기 허프먼 부호화 트리 구현과 복호화 컴퓨터에서 텍스트를 표현하는 데 쓰이는 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) 으로 치환할 때마다 필요한 단계수가 절반으.. 더보기 꼬리재귀(tail-recursion)와 꼬리 호출 최적화(TCO) 재귀함수를 사용할 때는 콜스택 증가로 인한 메모리 낭비, stack overflow 발생 위험을 조심해야 한다.이 때 재귀함수를 꼬리재귀 형태로 작성할 수 있다면 이 문제를 회피할 수도 있다. 몇몇 언어에서(특히 함수형 언어)는 꼬리 호출 최적화(TCO: Tail-Call Optimization)를 지원하기 때문이다.꼬리재귀(tail-recursion)재귀함수의 리턴값이 재귀호출의 반환값인 상황을 꼬리재귀라고 한다.꼬리 호출 최적화 (TCO: Tail call optimization)TCO(Tail call optimization)는 꼬리재귀 함수 호출시 스택 프레임을 재사용하는 최적화 방식이다. 스택에 쌓인 호출 정보를 새로운 호출에 대한 것으로 업데이트하여 메모리 사용량을 줄일 수 있다.꼬리 호출 최.. 더보기 프로그래밍 언어의 기본 요소 프로그래밍언어는 일련의 과정에 관한 생각들을 조직화하는 틀로써 작용할 수 있다. 단순한 아이디어(or 매커니즘)들을 조합해서 복잡한 아이디어를 조직하는 것이다. 강력한 컴퓨팅 언어들은 다음 세가지 매커니즘을 제공한다. 원시 표현식(primitive expression) 수단 언어와 관련한 가장 단순한 객체 조합(combination) 수단 여러개의 단순한 요소들을 이용하여 복합적인 요소를 만듦 추상화(abstraction) 수단 복합적 요소에 이름을 붙여 하나의 단위로 다룸 표현식 표현식은 원시표현식, 연산자 조합으로 구성될 수있다. 원시 표현식 number, bigint, string, null, undefined, boolean, Symbol 연산자 조합 피연산자 + 연산자 표현식 형태의 조합 이름 .. 더보기 이전 1 다음
