Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다.
나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

가장 먼저 구현한 자료구조는 아니지만 가장 간단하여 첫 게시물로 어울릴 것이라 생각한 pair 입니다.
문제 풀이에 활용도가 매우 높으며 header 내에 있습니다.

This is short(?) summary of the textbook “Art of Multiprocessor Programming” by Maurice Herlihy & Nir Shavit.
A complete set of lecture slides & sample code is available at the textbook’s companion page
This work is licensed under a Attribution-ShareAlike 3.0.

Wait-free Bounded Queue는 atomic fetch_add() 함수를 사용하여 bounded된(사이즈가 정해진) 배열 내에서 값을 enqueue, dequeue 함으로서 작동하는 자료 구조입니다.
여러 enqueue/dequeue 요청이 병렬적으로 들어왔을 때에도 순차적인 처리를 위하여 배열 내부의 원소는 flag를 두고 있으며 해당 flag를 사용하여 enqueue/dequeue 요청을 순차적으로 처리할 수 있기 때문에 wait-free의 성질을 가지고 있습니다.

문제보기

• LIS (Longest Increasing Subsequence) : 최장 증가 부분수열
  LIS란 임의의 수열이 주어졌을 때, 해당 수열에서 몇 개의 수들을 뽑아 만든 부분수열 중 오름차순으로 정렬된(strictly increasing) 가장 긴 수열을 뜻합니다.

이 때 LIS의 길이를 구하는 방법은 크게 세가지가 있습니다.

• DP O(n²)
• Binary Search O(nlogn)
• Segment Tree O(nlogn)

오늘은 이 중 Binary Search, 즉 이분 탐색을 이용해 LIS의 길이와 수열을 찾는 방법을 알아보겠습니다.

현재 OpenBwTree에는 Update가 구현되어 있지 않습니다.
그렇기에 테스트 케이스 생성에 앞서 BwTree를 위한 Update를 제작해야 했습니다.

Test Case 생성기

instruction, thread 갯수와 insert ratio를 받아서 테스트 케이스가 적혀있는 tmp[num].txt 생성 (tmp1.txt, tmp2.txt …)

각 텍스트 파일에는 매 행마다 i num 혹은 d num 으로 입력, 삭제 할 키 값이 들어있음.

키 값은 랜덤으로 생성.

Open Bw Treed Benchmark 코드 흐름 따라가면서 파악하기.