※요약

인라인 함수는 프로그램의 실행 속도를 높이기 위해 추가된 기능이며 C언어의 매크로 함수와 비교된다.


(개발자 입장에서)일반 함수와 인라인 함수의 가장 큰 차이점은 함수의 호출 방식이다.

일반 함수의 호출 방법은 프로그램 실행 중 함수를 실행해야하면 해당 함수의 주소로 점프시켰다가, 함수의 처리가 종결되면 다시 원래의 자리로 돌아오는 것이다.

이렇게 앞뒤로 점프를 수행하고, 점프할 위치를 기억하려면 함수를 사용하는데 시간이 많이 걸린다.


인라인 함수는 컴파일된 함수 코드가 프로그램의 코드 안에 직접 삽입되어진다.

이 말은 컴파일러가 함수를 호출하는 대신, 그에 대응하는 함수 코드로 대체한다는 것을 의미하며 함수 호출없이 삽입된 함수 코드를 그 자리에서 처리하므로 해당 함수를 수행하기 위해 프로그램이 다른 주소로 점프했다가 되돌아 올 필요가 없어 속도면에서 유리하다.



일반 함수 어셈블리어


인라인 함수 어셈블리어



※특징

 - 인라인 함수를 사용하려면 함수 선언 앞에 inline이라는 키워드를 붙이거나 함수 정의 앞에 inline이라는 키워드를 붙인다.

 - 클래스 멤버 함수가 inline을 사용하려면, 함수 정의의 위치가 *.h에 있어야 한다. 안 그러면 확인할 수 없는 외부 참조라고 뜬다.

 - 프로그래머가 inline 선언을 해도 컴파일러가 인라인화를 거부할 수 있다.

 - 프로그래머가 inline 선언을 안 해도 컴파일러가 인라인화를 할 수 있다.

 - 함수의 덩치가 크거나 재귀호출이면 inline 요구를 거절하는 컴파일러도 있다.

 - 함수 코드의 수행 시간이 짧고 빈번하게 호출되는 함수가 아니라면, 인라인 함수로 인한 절대적인 시간 절약은 그다지 크지 않다.



※장점

 - 함수가 인라인화 되어 성능의 향상으로 이어질 수 있다.



※단점

 - 메모리 사용 측면에서는 인라인 함수가 일반 함수보다 불리하다.

   이유는 어떤 프로그램에서 인라인 함수를 열 번 호출한다면, 

   프로그램은 그 함수의 사본을 프로그램의 코드 안에 열 번이나 삽입해야 하기 때문이다.

 - 매크로 함수와 달리 자료형에 독립적이지 못 하다. 단, 템플릿을 이용하면 자료형에 독립적으로 사용할 수 있다.



※예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
using namespace std;
 
inline void Test( int nNum1 );
 
int main( )
{
    Test( 2 );
 
    return 0;
}
 
void Test( int nNum1 )
{
    int nResult = nNum1;
}


'Programing > C++' 카테고리의 다른 글

inline 함수  (0) 2016.04.12
stl 정렬 알고리즘(sort, stable_sort, partial_sort, nth_element)  (0) 2016.04.03

출처:  http://ohyecloudy.com/pnotes/archives/294/


컨테이너 정렬이 필요할 때, sort를 사용하고 순서가 유지돼야 하면 stable_sort를 사용했다. partial_sort와 nth_element는 한 번도 사용해본 적이 없는데, 일부분만 정렬이 필요하거나 몇 번째 원소를 뽑을 때 유용하게 사용할 수 있을 것 같다. 예를 들면 최고 작은 수 10개만 차례대로 혹은 차례 상관없이 뽑는다던지, 9번째로 작은 수만 뽑는다던지 할 때에 사용하면 좋을 거 같다. 구현하는데 시간을 추가로 쓰는 것도 아니고 이미 구현되어 있는데, 딱 필요한 만큼만 정렬해서 시간을 절약할 수 있다. 아무리 작은 시간이라 하더라도 그냥 낭비하는 건 죄를 짓는 거.

nth_element는 정렬 기준에 따라 몇 번째 원소만 정확히 뽑아준다. 원소를 기준으로 정렬 기준에 맞게 좌우를 나눠주기는 하는데, 그 원소들 사이에 정렬은 되어 있지 않은 상태이다. 

partial_sort는 시작점부터 지정한 위치까지만 정렬해준다. 나머지는 정렬되지 않은 상태로 놔둔다. sort와 stable_sort는 시작점에서 끝점까지 정렬하는데, 정렬되고 난 뒤 stable을 보장 여부가 다르다. 동일한 정렬 기준을 가진 녀석들의 순서가 정렬 후에도 바뀌지 않으면 stable하다고 하는데, 뒤에 소스 코드 예를 보면 단박에 이해된다. 참고로 merge sortinsertion sort가 대표적인 stable sort 알고리즘이고 unstable sort의 대표적인 알고리즘은 quicksort다.

수행 시간은 nth_element < partial_sort < sort < stable_sort 이다.

sort, stable_sort, partial_sort 테스트 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

////////////////////////////////////////////////////////////////////////////////
// Item
////////////////////////////////////////////////////////////////////////////////
struct Item
{
    int     num;
    char    tag;

    explicit Item(int n, char t = ' ') : num(n), tag(t) {}
};

inline bool operator< (const Item& lhs, const Item& rhs)
{
    return lhs.num < rhs.num;    // 숫자만 비교한다.
}

inline std::ostream& operator<< (std::ostream& ost, const Item& item)
{
    ost << item.num << item.tag;
    return ost;
}

정렬 알고리즘에서 호출해주는 operator < 는 숫자만 비교한다. tag는 stable하게 정렬되는지 확인하는 용도로 사용한다.

////////////////////////////////////////////////////////////////////////////////
// main
////////////////////////////////////////////////////////////////////////////////
int main()
{
    const Item itemArray[40] =
    {
        Item (-4, ' '), Item (16, ' '),
        Item (17, ' '), Item (-3, 's'),
        Item (14, ' '), Item (-6, ' '),
        Item (-1, ' '), Item (-3, 't'),
        Item (23, ' '), Item (-3, 'a'),
        Item (-2, ' '), Item (-7, ' '),
        Item (-3, 'b'), Item (-8, ' '),
        Item (11, ' '), Item (-3, 'l'),
        Item (15, ' '), Item (-5, ' '),
        Item (-3, 'e'), Item (15, ' '),
        Item (-4, ' '), Item (16, ' '),
        Item (17, ' '), Item (-3, 's'),
        Item (14, ' '), Item (-6, ' '),
        Item (-1, ' '), Item (-3, 't'),
        Item (23, ' '), Item (-3, 'a'),
        Item (-2, ' '), Item (-7, ' '),
        Item (-3, 'b'), Item (-8, ' '),
        Item (11, ' '), Item (-3, 'l'),
        Item (15, ' '), Item (-5, ' '),
        Item (-3, 'e'), Item (15, ' ')
    };

    typedef std::vector<Item> ItemVector;

    ItemVector v0(
        itemArray, itemArray + sizeof(itemArray) / sizeof(itemArray[0]));
    ItemVector v1(v0.begin(), v0.end());
    ItemVector v2(v0.begin(), v0.end());

    std::sort (v0.begin(), v0.end());
    std::stable_sort (v1.begin(), v1.end());
    std::partial_sort (v2.begin(), v2.begin() + 10, v2.end());

    std::cout << "### sort(begin, end)\n";
    std::copy (v0.begin(), v0.end(), std::ostream_iterator<Item>(std::cout, " "));
    std::cout << "\n\n### stable_sort(begin, end)\n";
    std::copy (v1.begin(), v1.end(), std::ostream_iterator<Item>(std::cout, " "));
    std::cout << "\n\n### partial_sort(begin, begin+10, end)\n";
    std::copy (v2.begin(), v2.end(), std::ostream_iterator<Item>(std::cout, " "));

    return 0;
}

20개 정도로 하니깐 sort로 정렬해도 결과가 stable해서 40개로 늘렸다. VS2005의 딩컴웨어 STL에서는 원소 개수가 32개 보다 작으면 insertion sort를 하기 때문에 20개로 sort를 호출하면 stable한 결과가 나온다. 정렬 알고리즘은 원소를 변경하기 때문에 복사해서 똑같은 원소를 가진 벡터를 3개 만들고 각각을 정렬한 다음 출력했다.

sort는 stablestable의 순서가 엉켜있고 stable_sort는 제대로 출력하고 있다.partial_sort는 [begin, begin+10) 까지만 정렬을 한다.

nth_element 테스트 소스 코드

nth_element 같은 경우는 위와 같은 예제로 하면 확인이 어려워 따로 테스트 코드를 만들었다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

int main()
{
    // VS 2005에서 원소 개수가 32개 이하면 Insertion sort를 한다.
    static const int INSERTION_SORT_THRESHOLD = 33;
    std::vector<int> v;
    v.reserve(INSERTION_SORT_THRESHOLD);

    for (int i = 0; i < INSERTION_SORT_THRESHOLD; ++i)    v.push_back(i);
    std::random_shuffle(v.begin(), v.end());

    std::cout << "### before\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    std::cout << "### nth_element(begin, begin+12, end)\n";
    std::nth_element(v.begin(), v.begin()+12, v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

VS 2005의 딩컴웨어 STL 구현을 보면 분할 정복 알고리즘(Divide and conquer algorithm)을 사용해서 구현했는데, 여기서도 sort와 같이 분할한 구역 원소 개수가 32개 이하이면 insertion sort을 한다. 그래서 출력해보면 12 앞에 숫자들이 정렬된 상태로 보인다. 처음에 원소를 10개로 잡아 놓고 테스트를 했는데, 전체가 정렬돼서 무척 의아했다. 궁금해서 소스코드를 보니 원소 개수가 32개 이하이면 insertion sort로 정렬하더라.

STLport 5.1.3 으로 돌려본 결과. insertion sort를 하는 threshold가 3이다.


'Programing > C++' 카테고리의 다른 글

inline 함수  (0) 2016.04.12
stl 정렬 알고리즘(sort, stable_sort, partial_sort, nth_element)  (0) 2016.04.03

+ Recent posts