C 언어 표준 라이브러리에는 잘 알다시피 배열 데이터에 대해서 간단한 검색과 정렬 알고리즘을 구현해 놓은 함수가 존재한다.
정렬을 수행하는 qsort()가 대표적인 예이고, 이미 정렬된 배열에 대해서 이분 검색을 수행하는 bsearch()도 유용하다.

이들 검색과 정렬 함수는 비슷한 형태의 인자를 받아서 동작한다. 배열을 가리키는 포인터, 각 원소의 개수와 크기, 그리고 찾고자 하는 원소의 값, 그리고 비교 함수의 포인터이다. 비교 함수는 두 원소의 비교를 수행하여 대소 관계를 리턴값의 부호 또는 0 여부로 알려 주어야 한다. 이렇게 함으로써 int든 float든 그 어느 자료형이라도 범용적으로 검색하거나 정렬을 수행할 수 있다.

그런데 C 언어는 이분 검색뿐만 아니라 선형 검색을 하는 함수도 제공한다. 찾는 원소와 같은 값이 나올 때까지 배열을 처음부터 끝까지 단순히 뒤지기만 하는 알고리즘 말이다. 동작 방식은 단순하기 그지없지만, 이분 검색과 더불어 그냥 일관성을 위해서 선형 검색도 함수로 표준화한 듯하다. 선형 검색이 받아들이는 비교 함수는 두 값의 대소 비교를 할 필요가 없이 두 값이 단순히 같으면 0, 그렇지 않으면 nonzero만 되돌려도 된다.

그런데 본인은 C 언어가 제공하는 선형 검색 함수의 형태를 보고는 놀라지 않을 수 없었다.

1. 이분 검색이 bsearch이니 선형 검색은 응당 lsearch일 거라고 본인은 생각했다. 그런데 선형 검색 함수는 _lsearch와 _lfind로 나뉘어 있고, 어찌 된 이유인지 함수 이름 앞에 밑줄이 추가돼 있다. 이분 검색과 정렬 함수는 stdlib.h에도 선언이 되어 있는 반면, 선형 검색 함수는 거기에 없으며 반드시 생소한 search.h를 인클루드 해 줘야 한다. 왜 이런 차이가 존재하는지부터 의문이다.

2. _lsearch는 원소를 찾아서 이게 배열에 존재하지 않으면, 그 원소를 배열의 끝에다가 추가를 한다. 따라서 이 함수는 매개변수만 올바르다면, 원하는 원소가 배열에 없다고 하더라도 NULL을 리턴하지 않는다. 그 반면 _lfind는 read-only 함수로, 원하는 원소가 없으면 NULL을 되돌린다. 그러므로 정확하게 bsearch 함수의 동작 방식만 선형 검색의 형태로 원한다면 _lsearch가 아닌 _lfind를 써야 한다.

3. bsearch와는 달리, 선형 검색 함수는 배열 원소의 개수를 넘겨주는 인자가 포인터형이다. 그것도 size_t도 아닌 unsigned int의 포인터이기 때문에 64비트 환경에서도 여전히 32비트 값 전달만 가능하다는 한계마저 그대로 지닌다. ㅜ.ㅜ 왜냐하면 _lsearch의 경우, 원하는 원소가 배열에 존재하지 않아서 그 원소가 배열 뒤에 추가되었을 경우, 배열 원소 개수를 1 증가시켜 주기 위해서이다.

그러나 배열 원소 추가를 하지 않는 _lfind라면 배열 원소 개수 인자가 포인터여야 할 필요가 전혀 없고 bsearch처럼 size_t 값을 그대로 받기만 하면 된다. 왜 _lfind까지 _lsearch처럼 그렇게 포인터를 받게 해 놓았는지 모르겠다.

Posted by 사무엘

2010/08/13 09:18 2010/08/13 09:18
,
Response
No Trackback , 5 Comments
RSS :
http://moogi.new21.org/tc/rss/response/347

Trackback URL : http://moogi.new21.org/tc/trackback/347

Comments List

  1. 김 기윤 2010/08/13 14:52 # M/D Reply Permalink

    STL을 쓰는 저로써는 qsort() 는 한두번 써봤나? 싶고 그냥 sort() 함수 쓰는걸로 끝냅니다.. 훨씬 간편하고 쓰기도 쉽죠 -_-; 성능상으로도 sort 가 더 빠르다고 하는 글도 본 적이 있습니다. (아무래도 qsort 는 함수 포인터를 호출 해야 할 테니)

    1. 사무엘 2010/08/14 00:16 # M/D Permalink

      C++ 버전은 간단한 int 배열은 qsort처럼 매번 비교 함수를 호출 안 하고 바로 비교 연산만 수행하며 정렬하는 코드를 생성할 수도 있을 테니, 그 점에서는 유리하지요.
      비슷한 맥락에서, cout은 언제쯤 printf의 성능을 따라잡을지 모르겠습니다. 32비트와 64비트가 막 섞이면서 % 문자는 이식성 면에서 굉장히 골치 아픈 존재가 돼 있기도 하고요.

  2. 김재주 2010/08/14 01:23 # M/D Reply Permalink

    사실 fstream, iostream 같은 C++ 입출력 스트림은 C++ 표준 라이브러리 중에 가장 최적화 연구가 덜 된 분야이긴 합니다. 파싱 과정 없이 타입만 가지고 오버로딩된 함수 중에 어떤 걸 이용해야 되는지 결정할 수 있는 C++ 라이브러리가 C의 scanf, printf보다 더 빠른 속도로 동작하는 걸 기대해도 무리는 아닐 텐데요.

  3. 아라크넹 2010/08/14 04:58 # M/D Reply Permalink

    iostream 라이브러리의 가장 큰 문제는 (C 라이브러리 같은 데서도 흔히 볼 수 있는) locale 관련 처리가 지나치게 복잡하다는 데 있습니다. 정작 실제로 프로그래밍을 할 때 언어 차원에서 지원하는 locale 라이브러리는 거의 전혀 쓸모 없는 게 현실이라는 걸 감안하면 더더욱 큰 문제가 되지요. gettext 같은 매우 간단한 지역화 툴이나, 그걸로 부족하면 아예 ICU 같은 걸 쓰는 게 상식적입니다. (유닉스 계열에서는 POSIX locale의 존재 때문에 눈꼽만큼 상황이 낫습니다만, 결국 각자 구현해서 쓰게 되더군요.)

    보통 #include <iostream> 해서 cin과 cout을 받아 오면 정적 링크한 바이너리 크기가 급격히 불어나는 걸 볼 수 있는데 (상황에 따라 다르지만 200~500K 정도는 흔할 겁니다) 이 부분이 바로 locale 처리 코드가 들어 가서 그런 것입니다. 게다가 C++ locale의 구현은 locale 관련 정보를 제공하는 각종 클래스들(facet라고 합니다)의 "생짜 배열"로 구성되어 있어서 가독성을 좀 희생해서 모처럼 얻어낸 inline 가능한 구현을 망쳐버립니다. 차라리 이 부분을 최대한 템플릿으로 만들어서 컴파일 시간에 필요 없는 코드를 없애 버리는 쪽이 더 낫지 않을까 하는 망상까지 하게 되지요.

  4. 사무엘 2010/08/15 01:20 # M/D Reply Permalink

    김재주, 아라크넹: 그렇죠. % 문자를 해석하는 일도 만만한 작업이 아닐 텐데, C++ iostream은 지금보다 더 똑똑한 최적화가 아쉽습니다.
    하지만 현실에선... 속도는 그렇다 치더라도 code bloat도 말씀하셨듯이 너무 심해요. 복잡한 추상화 계층 때문이겠죠.

Leave a comment
« Previous : 1 : ... 1908 : 1909 : 1910 : 1911 : 1912 : 1913 : 1914 : 1915 : 1916 : ... 2204 : Next »

블로그 이미지

그런즉 이제 애호박, 단호박, 늙은호박 이 셋은 항상 있으나, 그 중에 제일은 늙은호박이니라.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2024/11   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

Site Stats

Total hits:
2967127
Today:
1113
Yesterday:
1514