Hee's Blog

최근 정렬알고리즘을 공부하면서 STL의 함수와 내가 구현한 알고리즘의 엄청난 속도차이를 느꼈다.
결론부터 말하자면 STL의 알고리즘을 분석하고 나만의 HSort를 구현하는 것이 목표이다.
HSort구현에 앞서 기존의 알고리즘들을 구현해보고 비교 분석해보았다. 
결과는 아래와 같다.(오름차순 정렬을 기준으로 비교하였다.)

각각의 구현된 알고리즘 및 분석 내용은 링크를 걸겠다.

추가

2015/12/28 - 비주얼스튜디오에서는 실행시간이 많이 차이난다. 특히 <algorithm>의 sort는 함수 구현이 완전 다른듯 하다. 이유는 모르겠다. 참고로 위의 시간은 맥OS의 Xcode에서 실행한 결과이다. 윈도우에서 전반적으로 시간이 느려졌으니 내컴퓨터의 성능 문제라고 할수 있겠지만 stl qsort의 경우 오히려 10, 10, 9의 시간으로 역순일때 더빠른 속도를 냈기 때문에 STL함수는 구현이 다르다고 할수 있을 것 같다.

LValue란 

LeftValue, 단일 표현식을 넘어가도 존재하는 값을 의미한다. (영속성)

예를들어 

int i = 0; 

char* Name = "홍길동";

++i;

위에서 볼드체로 된 값들은 문장이 넘어가도 존재한다. 

RValue란 

RightValue, 단일 표현식이 넘어가면 없어지는 값을 의미한다. (비영속성)

예를들어

int a = 10; 

int b = 20;

char* Name = "홍길동";

​int c = a + b;

​c++;

위에서 붉은색 글씨로 된 값들은 그 당시에만 있는 임시값이다.

다른 것들은 쉽게 이해가 된다. 하지만 ++i와 c++는 쉽사리 이해 되질 않는다.

차근차근 알아보자 ++i의 경우에는 연산자오버로딩을 해보면 

이렇게 자기자신을 리턴한다. 이는 영속한 데이터이다. 하지만 c++의 경우 연산자오버로딩에서 보면

이렇게 복사본을 리턴한다. 때문에 연산후에도 값이 그대로이며 다음식에서 ++되는 것을 알수있다.

또한 복사본이기 때문에 비영속적이다. 

이것이 ++i가 LValue이고 c++가 RValue인 이유라 할 수 있다.

위의 내용이 어렵다면 단순히 해당 식에서 주소를 알아낼 수 있다면 lvalue 불가능하다면 rvalue라 할수도 있다. 예를들어 

&i는 가능하지만 &(a + b)는 불가능하다.

서론이 길었는데 원래 포스트의 주제는 RValue를 참조하는 방법에 관한 것이었음으로 이제 본론으로 들어가겠다. 예를 들어

Print(const char& a) //알파벳 하나를 넘겨받아서 출력함 

이라는 함수가 있다. 잠시 설명을 하자면 a는 레퍼런스로 매개변수를 넘겨받는다.

레퍼런스이니 당연히 메모리가 할당되지 않으며 변수에 별명을 붙이는 형식이므로 마치 포인터처럼 사용이 가능하다.(값 복사 없이 참조가 가능하다는 뜻) 

또한 const로 선언되어 있기에 값을 변경할 수 없다.

즉 const든 non_const든 영속적인 LValue가 저장 가능하다.

결과적으로 a로 넘어오는 파라미터 값이 무엇이든 char형 변수일때 출력이 가능하다.

하지만 위의 함수는 print('a');와 같이 RValue를 파라미터로 호출할 수 없다.

(영속적인 데이터만 저장가능한 변수이기에 파라미터로 넘겨 받을 수 없다.)

때문에 RValue를 저장할 수 있는 레퍼런스가 필요하며 그것이 바로 && 이다.

print(const char&& a); 

이와 같이 정의하면 const든 non_const든 비영속적인 RValue가 저장가능하다.

때문에 print('a');와 같은 호출이가능하다.

결과

원리는 0x80 과 문자배열의 요소의 &연산(1000.0000 & 111.1111)으로 해당 문자가 1 ~ 127  범위안 (아스키 코드)인지 판단하여 범위 안이면 1바이트 밖이면 3바이트 로 계산하여 제한 길이까지의 바이트 수를 저장한다. 

그후 구한 바이트 수가 문자열의 총 바이트 수보다 작다면 문자열을 자른후 [...]을 붙인다.

아스키코드표의 문자들을 제외하면 전부 3바이트로 처리하니 정확한 것은 아니지만 UTF-8인코딩 에서 3바이트로 처리되는 언어들에서는 충분히 사용가능할 것이다.