-
Rust Crossbeam의 Epoch 기반 메모리 관리
서론 프로그래밍 언어는 다양한 방법을 통해 메모리를 관리합니다. 이러한 메모리 관리 방법은 크게 두 가지 방법으로 나눌 수 있습니다: GC(Garbage Collection)와 직접 메모리를 관리하는 방법입니다. GC는 메모리를 관리하는 방법 중 가장 편리한 방법이지만, GC가 동작하는 동안에는 프로그램이 멈추는 단점이 있습니다. 반면 직접 메모리를 관리하는 방법은 GC가 동작하지 않기 때문에 프로그램이 멈추지 않습니다. 하지만 직접 메모리를 관리하는 방법은 GC보다 훨씬 어렵습니다. Rust는 직접 메모리를 관리하는 방법을 사용합니다. Rust에서의 메모리 관리 방법은 예전 글인 Rust의 Borrow Checker을...
-
bound entanglement
서론 양자 얽힘 (quantum entanglement)는 크게 두 가지로 분류할 수 있다. 대부분의 entanglement는 free enntanglement이며, 일부가 bound entanglement이다. 특히, bound entanglement는 아직 한국에 잘 소개되지 않았으며, 한국어 명칭도 정착되지 않은 개념이다. 그리고 bound entanglement와 깊게 관련된 LOCC(Local Operations and Classical Communication)도 일반 사람들을 대상으로 많이 소개되지 않아 이에 대해 이번 글에서 간단히 소개해 보고자 한다. 양자 상태부터 설명을 시작해서 bound entanglement까지 설명하기에는 너무 긴 분량이 될 것이므로 초반부는 간략하게 설명하였으니 이 글을 읽고 흥미가 생긴...
-
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration 2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주...
-
Size of struct
서론 이 글은 구조체를 사용할 때 구조체가 차지하는 메모리가 어떻게 계산되는지를 다룬다. Problem Solving을 할 때 조금이나마 도움이 되기를 바란다. 구조체의 메모리 계산 예시 PS가 아닌 개발을 목적으로 한 프로그래밍을 할 때에는 보통 가독성을 중요하게 생각한다. 다음과 같은 c++ 코드를 생각해 보자. const int SIZE = 1000000; struct User{ char sex; short age; long long id; } db[SIZE]; 유저의 성별, 나이, 고유한 id를 설정해야 하는 상황이다. 우선 위와 같이 설정한 이유를 간략히 설명하겠다. 성별은 ‘M’...
-
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...