[CS] Quick Sort, ArrayList/LinkedList, Concurrency/Parallelism, Critical Section/Mutex 정리

Quick Sort(퀵 정렬)

• 결정론적 알고리즘(Deterministic Algorithm) : 매번 똑같은 방식으로 각 단계를 거쳐가는 알고리즘
• 무작위 알고리즘(Randomized Algorithm) : 난수 생성

Partitioning -> 분할 작업. 기준이 되는 값은 pivot이 된다. pivot 보다 작은 수는 왼쪽에, 큰 숫자는 오른쪽에 위치하면서 정렬이 된다. 항상 첫 번째 요소를 선택할지, 랜덤으로 요소를 선택할지 달라질 수 있다.

 

Quick Sort에 의한 시간 복잡도

-Best Case: 가장 좋은 케이스는 중간 값을 골라서 밸런스 있게 정렬을 나눌 때이다.

-Average Case

-Worst Case: 매우 불균형한 파티션으로 나눠지거나 가장 작은 값 또는 가장 큰 값이 선택 될 때이다. 이럴 경우 중간 값에 가까운 수를 고르거나 Randomized Quicksort를 사용한다.

 

Quick Sort의 장점

-큰 데이터 셋에 효과적이다.

-오버헤드가 적고 적은 양의 메모리를 필요로한다.

Quick Sort의 단점

-작은 데이터 셋이 적합하지 않다.

-가장 최악의 시간 복잡도를 가질 수 있다.

-일반적으로 안정적이지 않고 같은 수가 있을 때 상대 순서가 유지되지 않는다.

 

 

---

 

 

ArrayList

-ArrayList는 동적 배열로 그 크기가 변할 수 있다.

-랜덤 접근이 매우 빠르지만 데이터 추가와 제거가 느리다.

-오직 객체만을 리스트에 저장하기 때문에 메모리에 효율적이다.

 

LinkedList

-ArrayList와 동일하게 선형적 데이터 구조이다. 마찬가지로 크기를 구체화하지 않아도 된다.

-LinkedList는 노드들로 구성되어 있다.

-데이터 추가와 제거가 빠르지만 랜덤 접근은 느리다.

-객체와 다음/이전의 노드도 함께 저장하기 때문에 메모리에 비효율적이다.

 

ArrayList vs LinkedList

-데이터를 읽는 것보다 데이터의 추가/제거가 빈번할 경우 LinkedList를 사용하는 것이 좋다.

-반대로, 데이터의 추가/제거보다 데이터를 읽는 시나리오가 더 일반적일 경우, ArrayList를 사용하는 것이 좋다.

-ArrayList가 LinkedList보다 더 컴팩트하게 저장되므로 cache-friendly하다. 반면, LinkedList는 분산된 데이터 저장으로 cache-locality가 더 좋지 않다.

 

 

---

 

 

Concurrency

-간단하게는 동시에 처리되는 '것처럼' 보이는 프로세싱이다.

-여러 계산을 동시에 진행되고 관리하는 작업이다.

-Concurrency의 동시성은 CPU의 context switching에 의해서 작동한다.

-싱글 코어를 이용해서 수행될 수 있다.

-동기화 문제는 Parallelism 뿐만 아니라 Concurrency에서도 발생할 수 있다.

 

Parallelism

-'실제로' 여러 계산을 동시에 수행하는 작업이다.

-여러 CPU를 통해서 작동한다.

-싱글 코어에서 수행될 수 없고 멀티 코어에서 수행되어야 한다.

-더욱 향상된 성능을 보여줄 수 있지만 동기화 문제가 발생할 수 있다.

 

 

---

 

 

Critical Section과 Mutex는 다중 스레드 환경에서 동기화를 달성하기 위해 사용되는 개념

Critical Section(임계 구역)

- 여러 스레드가 동시에 접근해서는 안 되는 공유 자원에 대한 코드 영역

- 보통 공유 자원을 보호하기 위해 잠금 메커니즘이나 동기화 기법을 사용하여 안전하게 접근하도록 보장한다.

- 다중 스레드 환경에서 발생할 수 있는 경쟁 조건이나 데이터 불일치 문제를 방지하기 위해 사용

 

Mutex(상호 배제)

- 상호 배제 메커니즘의 일종으로, Critical Section의 진입을 제어하는 동기화 객체

- 한 번에 하나의 스레드만이 Critical Section에 접근할 수 있도록 보장한다.

- 여러 스레드가 Mutex에 대한 잠금을 요청하면 오직 하나의 스레드만이 잠금을 획득하고 Critical Section에 접근할 수 있습니다. 다른 스레드들은 Mutex가 해제될 때까지 대기한다.

- 일반적으로, Mutex는 운영 체제 수준에서 제공되는 동기화 도구이다.

 

Critical Section과 Mutex

- Critical Section은 코드 영역을 나타내는 개념이고, Mutex는 이러한 Critical Section에 대한 접근을 제어하는 동기화 도구이다.

- Critical Section은 프로그래머가 직접 구현해야 하지만 Mutex는 운영 체제에서 제공된다.

- Critical Section은 더욱 추상적인 개념이며 Mutex는 구체적인 구현체이다.