1. timestamp 기준, 그리고 달력 계산 문제
프로그래밍 언어 내지 운영체제 API에서 현재 시각과 관련된 정보를 얻는 함수는 다음과 같은 두 그룹으로 나뉜다.
- 가변: 현재 프로그램이나 운영체제가 시작된 이래로 현재까지 경과한 시간을 밀리초나 그에 준하는 정밀한 단위로 되돌림. C언어의 clock() 함수, 또는 Windows API의 GetTickCount()가 이쪽에 속한다. 얘는 현재 날짜 시각을 얻는 용도가 아니라 그냥 짤막한 소요 시간 측정용이다.
- 고정: 특정 고정 시점 이래로 현재까지 경과한 시간을 초 정도의 정밀도로 되돌림. C언어의 time() 함수가 대표적인 예이며 timestamp 저장용으로 쓰인다. 단, 고정 시점 기반이면서 정밀도도 초보다 더 높은 물건도 있다.
- 날짜형: 애초에 출력 형식이 년-월-일-시-분-초가 따로 담긴 구조체이다. C언어에서는 time()의 결과값부터 구한 뒤에 gmtime이나 localtime을 호출해서 이렇게 변환해야 하지만, Windows API는 반대로 GetSystemTime/GetLocalTime을 이용해서 구조체부터 구한 뒤에 SystemTimeToFileTime을 호출하는 형태이다. 원론적으로는 C언어 방식의 순서가 더 자연스러울 것이다.
컴퓨터에서 특정 시각 timestamp를 저장하는 방식으로는 유닉스에서 유래된 "1970년 1월 1일 0시 이래로 경과한 초수"가 아주 널리 쓰인다.
하지만 그것 말고 NTP라고 네트워크 환경에서 통용되는 timestamp도 있는데, 얘는 10진법 계산의 편의를 염두에 둬서 그런지 1900년 1월 1일 0시가 기준이다. 두 timestamp는 70년이라는 격차가 존재하는 셈이다.
그런데 부호 있는 32비트 정수 자료형이 초 단위로 표현할 수 있는 기간, 즉 21억 5천만 초는 약 68년이어서 이 역시 공교롭게도 70년에 얼추 가깝다.
부호 있는 32비트 정수 기준으로 유닉스 timestamp는 2038년쯤에 overflow가 발생할 것으로 예상된다.
그 반면, 부호 없는 32비트 정수 기준으로 NTP는 2036년쯤에 overflow되어 숫자가 리셋될 예정이다.
본인은 직장에서 유닉스 timestamp를 네트워크 timestamp로 변환하는 함수를 구현할 일이 있었다.
기존 timestamp에다가 1900년 1월 1일부터 1970년 1월 1일까지의 초수라는 상수를 더해 주기만 하면 되니, 난 그 상수는 엑셀을 띄워서 간단히 구해서 썼다. 엑셀도 1900년 1월 1일이 기준이라는 걸 알고 있었기 때문이다.
그런데 이렇게 날수를 더해 줬더니, 계산 결과가 미묘하게 맞지 않고 하루 정도 오차가 났다.
그리고 그 원인은 alas... 엑셀은 1900년을 평년이 아닌 윤년으로 간주하고 하루를 더 집어넣었기 때문이었다.
현행 그레고리 태양력은 4의 배수인 해가 윤년이어서 2월이 29일까지 존재하게 되지만, 100의 배수인 해는 400의 배수인 해만 윤년으로 인정하고 나머지는 평년으로 간주한다.
하지만 이런 예외가 먼 197, 80년대의 스프레드 시트 프로그램에서는 구현하기가 너무 복잡했던 모양이다.
더구나 서기 1900년은 어차피 컴퓨터가 발명된 해 기준으로는 까마득한 옛날이어서 실용적인 의미가 없으니.. 윤년은 "그냥 4년 주기"라는 율리우스 달력 로직만 구현했던가 보다. 그리고 엑셀 역시 1900년 2월 29일이 존재할 수 있는 '버그'까지 똑같이 기존 프로그램(= Lotus 1-2-3 따위)과 호환성을 보장하기 위해.. 동일한 로직을 일부러 구현했다.
엑셀이 이렇게 윤년을 잘못 계산하는 건 1900년 하나뿐이니 걱정하지 않아도 된다. 미래의 서기 2100년이나 2200년은 평년으로 정확하게 계산하며, 2400년만을 윤년으로 계산한다.
이 동작이 영 껄끄러운지, 엑셀은 각 문서 파일에 대해 고급 옵션으로 "Use 1904 date system" 여부라는 걸 지정해 줄 수 있다. 논란의 여지가 있는 1900년이라는 걸 아예 삭제해 버리고 건너뛴 것 같은데.. 이러나 저러나 사용자에게는 큰 의미가 없고 널리 쓰이지는 않는 옵션으로 보인다.
어떤 경우건 엑셀에서 1899년 9월 18일 경인선 개통일을 날짜 타입으로 집어넣을 수는 없다. ㄲㄲㄲㄲㄲ 다른 날짜와 연계해서 연산을 할 수 없으며, 전화번호처럼 문자열로만 취급 가능할 뿐이다.
2. 핸들(포인터) 값을 대체하는 순서
GC가 없는 언어인 C++로 코딩을 하다 보면 각종 자원(메모리나 리소스, 객체)을 가리키는 포인터 및 핸들을 감싸는 wrapper 클래스를 만들 때가 많다.
그 클래스의 소멸자에는 if(_ptr) Free_Release_Close_Destroy(_ptr)처럼.. 핸들이 가리키는 자원을 해제하는 함수 호출이 들어가곤 한다. 그리고 객체 자체가 소멸되지는 않고 객체가 가리키는 핸들값만 바뀔 때도 기존 핸들에 대한 해제 작업이 자동으로 행해진다.
_ptr이라는 핸들 멤버를 갖고 있는 클래스에서 핸들값을 newVal로 변경하는 작업을 직관적으로 생각하면 다음과 같을 것이다. _ptr을 해제한 뒤 거기에다 바로 새 값을 대입하는 것이다.
if(_ptr && _ptr!=newVal) Free_Release_Close_Destroy(_ptr); //원래 핸들을 제거한 뒤
_ptr = newVal; //새걸로 대체
하지만 구조적으로 더 안전한 정석은 아래와 같이 임시 변수를 만들어서 두벌일을 좀 하는 것이다.
auto tmp = _ptr; _ptr = newVal; //새걸로 대체부터 한 뒤에
if(tmp && tmp!=newVal) Free_Release_Close_Destroy(tmp); //원래 핸들을 제거
핵심은 기존 핸들값을 다른 지역변수에다 옮긴 뒤, 자기 자신의 핸들을 먼저 새 값으로 바꿔 버리고, 지역변수에 대해서 해제 함수를 호출하는 것이다. 이거 무슨 swap 함수처럼 보이기도 하는데..
이렇게 해 주면.. 자기 자신이 해제되고 있는 중에 멀티스레드 등 모종의 이유로 인해서 해제 메소드가 또 호출됐을 때, 해제가 중복으로 행해지는 걸 막을 수 있다. 왜냐하면 자기의 핸들값은 대외적으로 이미 NULL 같은 딴 값으로 바뀌어 있기 때문이다.
실제로 C++의 스마트 포인터만 해도 unique_ptr::reset 같은 함수의 몸체를 보면 저렇게 임시 변수 대입, 멤버 변수 대입, 임시 변수에 대한 release 순으로 구현돼 있다.
분야가 좀 다르지만.. 전기 철도에서 팬터그래프는 안전을 위해 언제나 진행 방향 기준으로 최대한 뒤에 장착되는 것과 비슷한 이치로 보인다.
3. 이분 검색의 변종
모든 원소에 임의 접근이 가능한 배열의 경우, 원소들이 정렬돼 있다면 특성 원소를 찾을 때 '이분 검색'이 가능해서 O(n)이 아니라 O(log n)의 시간 복잡도로 작업을 수행할 수 있다. 비교를 한 번 할 때마다 후보군이 그거 하나만 없어지는 게 아니라 통째로 반토막이 나기 때문이다.
그런데 정렬된 배열에 대해서 원소 하나만 딱 정확하게 찾는 게 장땡이 아니고 다음과 같은 작업을 생각할 수 있다.
- "1, 4, 8, 11" 같은 배열에서 5나 2, 10, 15 같은 새로운 원소를 삽입해 넣고 싶은데 어느 지점이 좋을까? (당연히 정렬된 상태 유지)
- "1, 4, 8, 8, 8, 8, 11" 같은 배열에서 8이 정확하게 어느 오프셋부터 시작되어 어디에서 끝나는지 알고 싶다.
이런 것은 이분 검색의 변종이며, 이 역시 당연히 log n 시간 복잡도로 수행 가능하다. 정확한 이분 검색이 방정식이라면 이런 건 뭔가 부등식에 대응하는 것 같다. 날개셋 한글 입력기의 내부 동작에서도 종종 쓰이는 기능이다.
개인적으로는 타 비교 함수의 결과를 저런 용도대로 보정· 변조하는 2차 비교 콜백 함수를 만들어서 C의 bsearch 함수만으로 저런 기능을 구현했던 적이 있었다.
즉, 원래 사용하는 1차 비교 함수가 원소값이 동등하다는 0을 리턴했더라도, 바로 앞의 원소에 대해서 또 1차 비교를 했는데 걔가 또 0이라면.. 이 원소값에 대한 비교는 여전히 -1을 되돌리도록 보정하는 식이다. (탐색 지점을 앞으로 더 옮기게..)
그랬는데 C++에서는 사정이 더 좋아져서 이런 기본적인 동작은 algorithm이라는 라이브러리에 lower_bound, upper_bound, equal_range라고 내가 딱 원하던 함수들이 도입됐다. 포인터처럼 임의 접근이 가능한 iterator가 있다면 저 함수에다 바로 집어넣어 줄 수 있다.
하긴, 정렬도 qsort 하나뿐만 아니라 특별히 안정성 있는 stable_sort도 있고, 정렬되어 있는 두 컨테이너를 병합하는 함수도 있고.. 이런 것들이 algorithm의 섬세한 면모인 것 같다.
그런데 문제는 배열이 아닌 binary tree 형태로 정렬된 상태가 유지되는 컨테이너이다. set과 map..
얘들을 다룰 때 사용되는 iterator는 원소들의 임의 접근이 가능하지 않으며, 반대로 tree 노드의 좌우 이동 같은 게 iterator와 연계되지도 않는다.
물론 multiset도 아닌 이런 컨테이너에 equal_range이야 전혀 의미가 없을 것이고 새 원소 삽입 지점 같은 걸 찾아야 할 필요도 없을 것이다. 하지만 "들어있는 문자열 중에서 B로 시작하는 제일 첫 명칭은?" 같은 검색을 할 필요는 있다.
그렇기 때문에 set과 map에는 lower_bound와 upper_bound가 범용적인 함수가 아니라 클래스의 자기네 전용 멤버 함수로 구현되어 있다. 역시 C++ 라이브러리가 이런 걸 빠뜨리지는 않았고, 배열과 set/map에 대해서 대동소이한 형태로 동일 취지의 기능을 구현했다는 걸 뒤늦게나마 경험할 수 있었다.
Posted by 사무엘
