그중, 흔히 말하는 시간 복잡도 O(n²) 정렬들은 구현도 간단하여 자주 사용하는 편인데, 정작 각 정렬에 대한 차이를 명확하게 답변하지 못할때가 종종 있어서 복습 겸 정리를 좀 할까 싶다.
1. 해당 문서의 예시 코드는 C/C++ 기반으로 작성되었습니다.
2. 모든 설명은 오름차순을 기준으로 합니다.
삽입 정렬
삽입정렬은 "맨 처음부터 진행하면서 내 위치일 것 같은곳으로 삽입" 하는 정렬이다.
예를들어, [5 3 2 1 4] 의 순서로 자료가 있다고 하면
시작 - [5 3 2 1 4]
1회차 - [5 3 2 1 4] --> [3 5 2 1 4]
2회차 - [3 5 2 1 4] --> [2 3 5 1 4]
3회차 - [2 3 5 1 4] --> [1 2 3 5 4]
4회차 - [1 2 3 5 4] --> [1 2 3 4 5]
종료 - [1 2 3 4 5]
의 방식으로 정렬이 이루어진다.
삽입 정렬의 특징이자 문제점이, "삽입" 방식으로 이루어지다보니 중간에 데이터를 삽입하면 뒤로 밀어버려야 한다는 특징이 있는데..
코드를 보면서 설명하도록 하겠다.
void Insertion_Sort(int *data, int n) //data = int 동적배열, n = 배열 길이
{
int i, j;
int temp; //임시 기억용 변수
for (i = 1 ; i < n ; i++) //2번째 원소부터 검사하므로 index가 1부터 시작함.
{
j = i;
temp = data[i];
while (--j >= 0 && data[j] > temp) //검사중인 원소부터
{ //0번 인덱스 원소까지
data[j+1] = data[j]; //한칸씩 뒤로 당김
} //* while문 최초 실행때 [j+1] 원소는 temp에 들어간 원소와 같다.
data[j+1] = temp; // j = i = 1일때, j + 1은 0이 될 수 있다.
}
}
흐름은 다음과 같다.
시작을 i 번 원소부터 했을때
1. [i - 1] 원소가 [i] 보다 클때 = i 원소의 값을 [i - 1]로 바꾼다.
2. [i - 1] 원소가 [i] 보다 작을때 = 값을 바꾸지 않고 종료한다.
3. while 루프 종료시 = 최종 위치에 임시값을 삽입한다. (1, 2번을 수행하면서 생긴 "중복 값" (=빈 자리) 에 삽입)
여기 나오는 모든 정렬들이 그렇겠지만, 삽입정렬도 N번째 값 정렬 시 N-1만큼의 순회를 돌아야 하므로, 시간 복잡도는 O (N(N-1)) = O(n² - n) = O(n²) 로 수렴한다.
구현이 간단하고, 나름 빠른 편 (선택 정렬과 버블정렬은 순수하게 O(n²) 의 시간 복잡도를 가진다) 이나, 배열이 길어질수록 효율이 떨어진다는 단점이 존재한다.
이미 정렬이 되어있는 경우에는 비교를 제외한 추가적인 연산이 필요 없으므로 최선의 케이스가 나오며, 이때 시간 복잡도는 O(n) 이 나온다.
선택 정렬
선택 정렬은 "리스트의 최소값부터 정렬하는" 알고리즘이다.
삽입정렬과 헷깔릴 수 있는데, 선택정렬은 N번째 자료를 정렬시에 N-1번까지는 이미 정렬이 완전히 끝난 상태라는것이 가장 큰 차이. (위에도 언급했지만 삽입정렬은 N번째 자료 정렬시 정렬이 끝난다는 보장을 할 수 없다.)
선택 정렬은 다음과 같이 작동한다.
시작 - [5 3 2 1 4]
1회차 - [532 1 4] --> [1 3 2 5 4]
2회차 - [1 3 2 5 4] --> [1 23 5 4]
3회차 - [1 2 3 5 4] --> [1 2 3 5 4] // 이미 순서가 맞으므로 추가 정렬 X
4회차 - [1 2 3 54] --> [1 2 345]
종료 - [1 2 3 4 5]
선택 정렬은 N번째 자료 정렬시 그 앞까지 (N-1까지)는 정렬이 완료되었다는 보장을 할 수 있는데, 현재 값이 "어느 위치인지" 알기 위해서 결국 모든 자료를 검사해야한다는 불상사가 발생한다.
이게 무슨소리냐면... 시간 복잡도가 어떤 상황에서든 O(n²) 라는 것이다.
삽입 정렬이나 버블정렬의 경우에는, 비교하는 대상과 본인이 정렬이 되어있다면 추가적인 연산을 하지 않는데 선택정렬은 그런거 모르겠고 이미 끝난 정렬도 함수 안에서 정렬을 수행한다는 뜻이다.
선택정렬은 "다음 최소값"이 어떤 값인지 알아야 하는 문제가 있어, 삽입정렬이나 버블정렬보다는 로직이 조금 복잡한 편이다.
void SelectionSort(int *data, int n)
{
int i, j, indexMin, temp; //최소값 인덱스와 임시값 변수 2종이 추가로 필요함.
for (i = 0 ; i < n-1 ; i++)
{
indexMin = i;
for (j = i+1 ; j < n ; j++)
{
//해당 for문은 정렬되지 않은 구역에서 "최소값"을 찾는 로직이다.
if (data[j] < data[indexMin])
{
indexMin = j;
}
}
temp = data[indexMin]; //찾아낸 최소값을 temp에 저장.
data [indexMin] = data[i]; //위치 교환
data[i] = temp; //temp값을 위치에 저장
}
}
흐름은 다음과 같다.
시작을 i 번 원소부터 했을때
1. i번 부터 N번까지 데이터 중 최소값을 찾는다.
2. 최소값이 발견되면 해당 값의 인덱스를 기록한다.
3. 최소값을 임시 변수에 저장한다.
4. i번 값과 최소값이 위치한 인덱스의 값을 교체한다.
5. i번 값에 임시 변수에 저장된 값을 집어넣는다.
해당 과정은 값이 이미 정렬이 되어있던, 아니던 상관없이 작동한다. 그러니까 시간 복잡도가 그모양이지
- 짐벌락 이슈에 대응하기 위해, 회전 정보 획득시 GetActorRotation이 아닌 GetComponentRotation 함수를 Root Component를 대상으로 호출하여 이용함.
라는 문장에 대한 질문이었는데, 내가 답변을 좀 에매모호하게 한거 같아서 정리를 좀 하고자 한다.
짐벌락?
짐벌락(Gimbal lock) 은 말 그대로 짐벌 (물체가 회전 가능하도록 중심축을 가진 물체)에 락이 걸린 상황을 의미한다.
보통, 3D 회전은 오일러 좌표계 (혹은 오일러 각 / Eular Angle)을 따르는데, 이때 3개의 축을 이용한다.
각각을 Roll, Pitch, Yaw로 표현하고, 보통은 각각의 수치가 X축 회전, Y축 회전, Z축 회전에 대응한다.
그래서 짐벌락은 언제, 왜 생기는가.
간단히 요약하는 짐벌락
간단히 요약하면, 축이 겹쳐서 발생하는 현상이다.
물체가 회전할때 명심해야 할 것이 있는데, 회전축이 회전할때는 다른 축의 회전에 영향을 받는다.
특히, 명심해야 하는 사항이 회전에는 순서가 있고, 순서에 따라 다른 결과값을 갖고온다는 점이다.
이러다보니 발생하는 문제가 바로 짐벌락. 임의의 축을 기준으로 회전했을때 회전한 축이 아닌 다른 축이 겹치는 현상이 발생하는데, 이렇게 되면 특정 축이 연산에 전혀 영향을 못주게 되면 문제가 발생한다.
예시로, X = 빨강, Y = 초록, Z = 파랑이라 생각해보자.
예를들어, X, Y축이 겹치는 현상이 발생했다면, X축을 회전하던, Y축을 회전하던 결국 Z축을 기준으로 똑같이 빙빙 도는 결과가 발생한다.
짐벌락이 문제가 되는 경우는, 해당 상황과 같이 특정 축이 락이 걸려버린경우 해당 축의 연산값이 전혀 영향을 못 미치게 된다는것인데, 이로 인해 정상적인 회전을 보장할 수가 없게된다.
쿼터니언
선형대수학에서는 오일러 각을 이용할때 생기는 이러한 문제를 해결하기 위해 4개의 축을 이용하는 쿼터니언 이라는것을 이용하여 연산을 한다.
쿼터니언 표현식이 좀 많은데, 제일 많이 쓰는 식은
q = xi + yj + zk + w
의 식으로 기억하고 있다. 표현대로 각각 x축, y축, z축과.. 가상의 w축을 포함하여 4개의 축을 이용한다.
이를 이용해서 회전 처리를 할때 짐벌락이 걸리지 않도록 하는것인데... 쿼터니언 설명 자체는 다음에 필요하면 하도록 하겠다.
언리얼에서는
언리얼에서도 당연히 짐벌락을 막기 위해 많은 방법을 선택한다.
주로 사용되는 방식은 2가지인데,
첫번째. 회전시 쿼터니언을 사용한다.
두번째. 회전값 표현시 축 분리를 한다.
우선 첫번째부터 설명하면, 언리얼에서 물체의 회전 및 위치, 스케일을 가지고 있는 "FTransform" 구조체를 뜯어보면 바로 답이 나온다.
protected:
/** Rotation of this transformation, as a quaternion */
TPersistentVectorRegisterType<T> Rotation;
/** Translation of this transformation, as a vector */
TPersistentVectorRegisterType<T> Translation;
/** 3D scale (always applied in local space) as a vector */
TPersistentVectorRegisterType<T> Scale3D;
public:
/**
* The identity transformation (Rotation = TQuat<T>::Identity, Translation = TVector<T>::ZeroVector, Scale3D = (1,1,1))
*/
CORE_API static const TTransform<T> Identity;
그냥 대놓고 쿼터니언으로 변환해서 쓴다고 얘기를 한다.
언리얼에선 TQuat라는 쿼터니언 자료형이 있는데, 내부적으로는 해당 값을 사용하고, 오일러 좌표계로 표현되는 FRotator 값이 내부 함수에서 쿼터니언으로 변환되어 들어온다.
두번째가 조금 설명하기 까다로운데, 우선 설명해야할것은, 쿼터니언 회전값은 해당 식만 보고는 이게 어떤 회전값을 가지고 있는지 바로 알기가 힘들다. 물론, FQuat와 FRotator를 변환해주는 함수가 없다는 뜻은 아니고, 쿼터니언 값만 가지고 원하는 오일러 각으로 변환하기가 쉽지 않다는 뜻이다. (물론, 지금은 시키면 할 수 있을거 같긴한데)
아무튼 그런 이유로, 언리얼 에디터에서는 회전값을 쿼터니언이 아닌 오일러 좌표계로 표현한다.
하지만, 오일러 좌표계를 이용하면 짐벌락을 피하기가 쉽지 않은데, 이를 "자동으로" 각도를 분할시키는 방식으로 해결하려고 했다.
무슨소리냐
예를들어, 멀쩡한 물체의 각도를 회전시키면
처음에는 0,0,0임
Y축 (Pitch)를 회전시키려고 하면
짜잔! 건들지도 않은 Yaw도 바뀌어버려요!
이처럼, 짐벌락을 피하기 위해 임의의 각을 연산하여 추가로 회전시키는 로직이 들어간다.
이러한 연산이 일반적인 회전 처리에서는 당연히 도움이 되지만...
회전이 들어간 이후 "인위적으로 회전값을 변경해야 하는 경우"에 문제가 발생했다.
그래서 뭐 한건데?
문제가 뭐였나면요...
위에서 말한것에서 이어서, 언리얼에서는 짐벌락을 피하기 위해 임의의 각 회전을 추가로 하는 경우가 있다고 했다.
하지만, 다음과 같은 경우에서 문제가 발생했었다.
예를들어, 특정 이동에서 X축값 (Roll)이 회전이 들어간 경우, Roll값을 0으로 만들고싶으면 Roll을 0으로 만드는 회전값 오버라이드를 하면 그만일것이다.
처음엔 당연히 그렇게 생각했다. 하지만 Roll을 회전 시킨 결과가 과연 Roll에만 있을까?
여기서 해당 회전 수치를 보장 할 수 없는 문제가 생겨버린다. 내가 임의의 축을 0으로 돌렸을때, 나머지 회전값은 내가 원하던 회전이 맞는가?
여기서 의문이 들 수 있다.
첫번째. "그냥 모든 축을 0으로 바꾸면 안됐나요?"
두번째. "내가 필요한 회전축을 제외하고 0으로 만들면 안되나요?"
둘다 답은 X다. 당연히 첫번째는 말도 안되고, 두번째의 경우, 처음 회전한 Yaw 값을 유지하는것이 목적이었는데 (언리얼에서 캐릭터를 조금이라도 만져보면 알겠지만, 서 있는 상태에서 회전은 Yaw값을 사용하여 움직인다)
임의의 축에서 회전이 발생 -> 짐벌락을 피하겠다고 언리얼에서 자체적으로 회전 처리 -> Yaw값에 손상 -> 나머지 회전값을 처리해도 Yaw값이 원하는 회전값이 아니게 되는 문제가 발생
이라는 문제가 발생해버리고 있었다.
해결방안
우선, Actor에서 회전값을 받아오는 GetActorRotation() 함수는 다음과 같은 구조로 작동한다.
template<class T>
static FORCEINLINE FRotator TemplateGetActorRotation(const T* RootComponent)
{
return (RootComponent != nullptr) ? RootComponent->GetComponentRotation() : FRotator::ZeroRotator;
}
//---
/** Return rotation of the component, in world space */
FORCEINLINE FRotator GetComponentRotation() const
{
return WorldRotationCache.NormalizedQuatToRotator(GetComponentTransform().GetRotation());
}
보통은 RootComponent의 회전값을 갖고와서 리턴해주는 방식인데, 당연히 대체로는 문제가 없다.
그런데 갖고오는 부분 어딘가에서 문제가 생기는지, RootComponent의 회전값과 다른 무언가를 갖고오는 현상이 있었는데, 이를 막기 위해 RootComponent에서 갖고오는 (정확히는 엔진 코멘트에 "해당 값은 RootComponent의 값과 동일함" 이라는 코멘트가 있는 부분이 있었다...) 방안을 선택했는데...
.....근데 분명 작업할때는 그런 코멘트를 본 기억이 있는데 (심지어 내부 문서에도 다 기록해놨다) 지금와서 찾으려니까 안보인다...???
C++에 들어오면서, "기존의 로우 포인터(=Raw Pointer) 에서 발생할 수 있는 문제들을 해결하기 위한 포인터"를 만들겠다는 명목하에 스마트 포인터라는 포인터가 추가되었다.
Raw Pointer 를 쓰면 생기는 문제점은 크게
1. 메모리를 사용했는데 해제 안한 경우 = 메모리가 낭비되는 현상 (=메모리 누수 / Memory Leak) 가 발생
2. 메모리를 사용하던 중에 해제한 경우, 해제한 메모리를 접근하는 경우
= 잘못된 참조 (Dangling Pointer) 발생으로 크래시 위험
둘다 문제가 많은 상황인데,
해제를 안한 경우가 "언제 터질지 모르는 시한폭탄" 이라면, 해제된 메모리 접근은 "지뢰" 라고 볼 수 있다.
둘다 터지면 머리아픈건 매한가지지만
주요 이론은, "객체는 (특별한 문제가 없는 한) 사라질때 소멸자가 반드시 호출되며, 이때 자원 해제를 하게 되면 자원 해제와 관련된 문제가 해결되지 않을까?" 라는 마인드에 입각하여(*1) 포인터를 포인터 객체로 만들어서, 해당 객체가 소멸시 데이터까지 같이 delete 하도록 하여 각종 포인터 예외를 대응하고자 한것이다.
다양한 스마트 포인터가 있고, 각자 다양한 목적을 위해 사용하는데 각각에 대한 정보를 정리를 한번 해야할것 같아 스스로 이해한 부분에 대해 정리를 해보고자 한다.
물론, 이미 Duplicated 된 Auto_Ptr은 생략한다...
해당 문서에는 각 스마트포인터의 사용법보단, 구조 및 원리에 대해 주로 설명합니다.
사용법이 필요하다면 적당히 찾아보시거나 직접 연구해보시는것을 추천합니다.
1) 해당 내용과 관련된 디자인 패턴이 RAII 라고 불리는 객체를 통한 자원 획득 디자인 패턴임. RAII : Resource Acquisition Is Initialization
Unique_Ptr
unique_ptr은 특정 객체에 대한 유일한 소유권을 가지는 스마트 포인터이다.
대체로, 유일한 소유권을 가지는 경우에 대해 "이걸 왜 쓰냐" 라는 의문을 가질때가 종종 있는데
다음과 같은 경우에 주로 문제가 발생한다.
Data* data1 = new Data();
Data* data2 = data1;
delete data1;// = data1 에 연결된 객체 소멸 (=new data() 로 선언한 객체)
delete data2;// = data2 에 연결된 객체 소멸 (=data1 (= new data()로 선언한 객체)
간단히 설명하면, data1 포인터에 새로운 data 객체를 만들어줬고, 이를 data2에서도 참조할 수 있도록 해놨는데,
수행 이후 data1 포인터를 통해 객체를 소멸시켰으나, data2에서도 연결된 객체를 소멸시키려고 하는 상황이다.
이때, 이미 삭제된 객체를 삭제하려고 시도해서 메모리 오류가 발생하며 Crash가 발생하게 된다.
"그럼 객체 소멸을 한가지 포인터만 하게 하면 되지 않나요?" 란 의문에서 나온것이 바로 unique_ptr 되시겠다.
특정 객체의 소유권을 지정하여 해당 포인터에서만 객체 접근 및 소멸을 담당하게 하면, 다른 포인터가 임의로 객체를 파괴시키는 현상은 일어나지 않게 될것이다. 또한, 위에서 설명한 문제중 "포인터를 쓰고 해제 하지 않는 문제"를 RAII 패턴에 입각하여 대응을 한것이 unique_ptr이고, 이는 일반적인 포인터처럼 사용할 수 있으나 다음과 같은 특징을 가지고 있다.
1. 특정 객체 (= 특정 클래스로 이루어진 메모리 영역) 에 대해 유일한 소유권을 가진다.
2. 함수 스택에 포함된 객체로, 함수가 끝나면 소멸자가 호출되며 메모리를 자동으로 해제한다.
사실, 2번에 대해서는 이해하기가 쉬운데, 1번은 "그걸 어떻게 알 수 있는데?" 라는 의문이 생길 수 있다.
안그래도 궁금해서 좀 찾아보았는데, unique_ptr 구현부에 다음과 같은 항목이 있었다.
/** Takes ownership of a pointer.
*
* @param __p A pointer to an object of @c element_type
* @param __d A reference to a deleter.
*
* The deleter will be initialized with @p __d
*/
template<typename _Del = deleter_type,
typename = _Require<is_copy_constructible<_Del>>>
unique_ptr(pointer __p, const deleter_type& __d) noexcept
: _M_t(__p, __d) { }
/** Takes ownership of a pointer.
*
* @param __p A pointer to an object of @c element_type
* @param __d An rvalue reference to a (non-reference) deleter.
*
* The deleter will be initialized with @p std::move(__d)
*/
template<typename _Del = deleter_type,
typename = _Require<is_move_constructible<_Del>>>
unique_ptr(pointer __p,
__enable_if_t<!is_lvalue_reference<_Del>::value,
_Del&&> __d) noexcept
: _M_t(__p, std::move(__d))
{ }
위는 할당, 아래는 "이동" 연산
여기서 보면 _M_t_ 라는 변수가 보이는데, 이는 __uniq_ptr_data 라는 구조체 변수이고, 해당 변수는 내부에 "__unique_ptr_impl" 라는 변수를 가지고 있다.
즉, 일반적인 복사 생성자나 대입 연산자는 삭제되어있으니, 당연히 접근하면 오류가 발생하는것이다.
'std::unique_ptr<A,std::default_delete<_Ty>>::unique_ptr(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)': attempting to reference a deleted function
오류 메시지는 다음과 같이 나온다. 삭제된 함수 (= 여기서는 복사, 대입 연산자)에 접근하려고 했다는 뜻.
이와 같은 방법으로 unique_ptr 간의 소유권을 지정할 수 있게 되었으며 (정확히는 조금.... 눈가리고 아웅 같긴 하지만) RAII 패턴에 힘입어 안전한 해제까지 보장되게 된 것이다.
p.s -
주의사항 : 물론, 설명에 없는것에서 눈치챘을수도 있지만 소유권이 이전된 빈 포인터가 된 unique_ptr에 포인터 연산을 시도 시 댕글링 포인터 문제로 인해 런타임 오류가 발생한다.
Shared_Ptr
근데 내가 특정 객체를 여러번 써야하는 경우가 있다면?
사실 이런 경우가 굉장히 흔하다. (오히려 unique_ptr을 쓰는 경우는 되게 드물었던것으로 기억한다.)
그렇다면 요구사항은 다음과 같이 정리된다.
1. 나는 한개의 객체를 여러개의 포인터로 접근하고 싶다.
2. 하지만, 그러면서 스마트 포인터의 특징 (= 안전한 해제)를 보장받고 싶다.
이를 위해 만들어진것이 바로 shared_ptr 되시겠다.
shared_ptr은 같은 객체를 다수의 스마트 포인터가 가리킬 수 있고, 내부적으로 레퍼런스 카운팅을 통해 몇번 참조중인지를 알 수 있는 스마트 포인터다.
레퍼런스 카운터가 0이 되면, 자동으로 해제되는 형태의 스마트 포인터로 알려져있는데.....
그럼 그 레퍼런스 카운터는 어떻게 되는가... 하면
__shared_count라는 서브 클래스가 따로 있고, (해당 클래스 내부에는 "_Sp_counted_base" 라는 클래스가 있다) 해당 클래스에서 카운트를 실시하는 스타일이다.
해당 정보는 같은 포인터를 가리키는 shared_ptr 끼리 공유하며 해당 공유 정보를 Control Block이라고 부른다.
즉, 레퍼런스 카운트 정보를 동일한 Control Block이 소유하고, 이를 각각의 shared_ptr이 공유하면서 사용하면 굳이 각 포인터에서 각자 카운터를 조작할 필요가 없게 되는것...
물론, 이를 위해서는 최초의 shared_ptr에서 접근을 늘려가야 하며 (즉, 최초의 shared_ptr을 제외한 N번째 shared_ptr은 최초의 shared_ptr을 가리켜야 한다), 1개의 raw pointer에서 다수의 shared_ptr을 새로 선언하면 shared_ptr이 자랑하는 레퍼런스 카운트 기능이 딱히 의미가 없어진다.
즉, shared_ptr에 raw pointer (=주소값)이 전달되면, 해당 shared_ptr은 본인이 해당 주소값을 최초로 소유한것으로 인지하게 된다는 것이다.
우선, std::sort를 검색하면 std::__sort 라는 inner func가 나온다.
/**
* @brief Sort the elements of a sequence using a predicate for comparison.
* @ingroup sorting_algorithms
* @param __first An iterator.
* @param __last Another iterator.
* @param __comp A comparison functor.
* @return Nothing.
*
* Sorts the elements in the range @p [__first,__last) in ascending order,
* such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
* range @p [__first,__last-1).
*
* The relative ordering of equivalent elements is not preserved, use
* @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
typename iterator_traits<_RandomAccessIterator>::value_type,
typename iterator_traits<_RandomAccessIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
// sort
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}
해당 함수에서는, 시작과 끝이 일치하지 않을때 introSort 재귀함수를 진행하고, 종료 시점에 삽입 정렬을 수행한다.
introsort_loop (Instro sort 재귀함수) 에서는, 미리 정해진 threadhold 상수값을 기준으로 정렬을 선택해서 사용한다.
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
_S_threadhold 라는 상수가 문제의 상수인데, 파일을 조금 뒤져보니 "16" 이란 값으로 임의로 박혀있었다.
왜 하필 16인지에 대해서는.... 더 찾아봐야할거같긴 한데 일단은 16이라니까 16이라고 보자.
Introsort_loop 의 로직은,
1. 리스트의 길이가 16 초과 일때 로직을 수행하고
2. depth limit가 0이 아니라면 -> depth limit를 1 줄이고, 임의 pivot을 선택한 후 instroSort를 반복해서 선택한다.
3. 여기서, depth limit는 함수 시작 시 2⌈ log₂(length) ⌉ (log 연산값의 정수 올림) 의 값을 가지고 시작한다.(해당 연산을 N번 반복하므로 정렬의 평균 속도가 O(n log₂n) 이 나오는것..)
4. 연산을 반복하다, depth limit가 0이 되었고 (= 연산의 깊이가 2⌈ log₂(length) ⌉ 돌파시), 길이가 16이상일 시 힙 정렬을 수행한다.
2. 해당 작업은 임시 연동을 위해 작업되었으며, 타 환경 (네트워크 환경 등)에서는 정상 작동을 보장하지 않습니다.
3. 필요시, 코드를 적당히 수정해서 사용해주세요!
(아마 기억이 맞다면) 언리얼 5.3에 들어오면서 큰 변화가 몇가지 생겼다.
그중에 프로그래머 입장에서 유의미하게 볼것이 바로 EnhancedInput의 정식 사용 시작 및 AbilitySystem의 공식 플러그인 화 일것이다.
근데 웃긴게, 이 두가지가 하나는 정식기능, 다른 하나는 플러그인이라서 그런가 공식적으로 지원하는 연동 코드가 없다.....
물론, 진짜 하나도 없진 않다. 대신, LyraStarterGame에 포함되어있을뿐...
LyraStarterGame에서는 해당 기능을 HeroComponent라는 연동 컴포넌트와, EnhancedInput을 위한 LyraInputComponent를 만들어서 사용하는데, 해당 컴포넌트 및 Lyra 식 사용에 대한 분석은 다음에 하기로 하고, 우선은 조금 빠른 사용법을 익혀보도록 하자.
* 해당 코드의 일부는 EpicGames에서 제공하는 Lyra Starter Game에서 발췌했습니다.
우선, 이전 글을 참고하여 AbilitySystemComponent를 정상적으로 사용할 수 있는 상태를 기준으로 한다.
Lyra에서는 (EditDefaultsOnly, BlueprintReadOnly) 조건으로 사용중이나, 적당히 필요한대로 쓰시면 될것같다.
그 다음부터는 선택지가 갈리는데, EnhancedInputComponent 및 PanwComponent를 상속받아서 Lyra와 같이 InputComponent + HeroComponent를 만들어서 사용하거나, 간략하게 AbilitySystemComponent를 상속하여 구현해주는 방법 등이 있다.
여기서는 AbilitySystemComponent 을 상속하여 추가 함수를 만들어주는 방식으로 구현하고자 한다.
Lyra 방식은... 공부도 하실겸 Lyra 코드를 열어보시는걸 추천드립니다.
첫번째. UAbilitySystemComponent를 상속받은 컴포넌트를 추가한다.
두번째. 위에서 만든 DataAsset Class를 헤더에 추가한다. (단순히 전방선언으로 사용하면 구조체의 사이즈를 알 수 없어 오류가 발생한다)
세번째. 다음과 같이 (혹은 적당히 수정하여) 헤더를 작성한다.
UCLASS()
class PROJECTCLOUD_API UCLAbilitySystemComponent : public UAbilitySystemComponent
{
GENERATED_BODY()
public:
//인풋 액션을 세팅하는 함수 (return bool인 이유는 오류 검출 용도)
bool BindInputActions(const UCLAbilityInputConfig* InputConfig, UEnhancedInputComponent* EnhancedInputComponent);
//인풋 액션을 호출하는 바인딩 함수
void TryActiveAbilityFromInputAction(const FInputActionInstance& Value);
private:
//인풋 액션 리스트
TMap<TObjectPtr<const UInputAction>, FGameplayTag> InputactionList;
};
네번째. cpp 파일에 필요한 헤더들을 추가한다. EnhancedInput관련, GameplayTag 관련 헤더를 추가해주면 된다.
