'$ SaVvY'에 해당되는 글 55건

  1. 2013.07.09 Red-Black Tree flow diagram
  2. 2013.07.05 GDBM User Reference
  3. 2013.07.01 SyncMaster TA531 with Mac OS X 1
  4. 2013.06.21 UDP Maximum message size
  5. 2013.06.20 가변매크로 __VA_ARGS__ 2

산술비교가 가능한 대용량 데이터에 대해 삽입/삭제/검색을 해야하는 경우 적용할 알고리즘.  C++의 std::map을 사용하면 굳이 몰라도 되긴하지만, C에서는 없으니까, 오픈소스를 가져다 이용한다.



 Red / Black  지정에 대한 규칙은 다음과 같다.

    1. 하나의 노드는  Black  아니면   Red 로 한다.
    2. Root 노드는 반드시  Black 이다.
    3. 모든 Leaf 노드는  Black 이다.
    4.  Red  노드의 Child 노드 양쪽(left/right)은 항상 모두  Black 이다. 그러므로,  Black  노드만  Red  노드의 Parent 노드가 될 수 있다.
    5. 어떤 노드로부터 시작되어 Leaf 노드에 도달하는 모든 경로에는 Leaf 를 제외하고 모두 같은 개수의  Black 노드가 있다.


위와 같은 다섯가지 조건을 만족하게끔 알고리즘이 구성되어 있다.  그러다보니, Root 노드로부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두배보다 항상 작게 된다. 그래서 대략 균형잡힌 트리라고 볼 수 있겠다. 삽입/삭제/검색에 대해 최악의 경우에도 시간복잡도가 보통의 이진트리와 비교해보면 훨씬 효율적이라고 볼 수 있다.  삽입/삭제/검색에 대한 시간복잡도면에서 AVL 알고리즘이 이와 유사하긴 하지만, Red/Black 알고리즘이 효율성에서 훨씬 앞서고 있으며 보다 많이 사용되고 있다.(거의 대부분)



Download document (RedBlack Tree.pdf)

'$ SaVvY > » computer' 카테고리의 다른 글

Building ACE framework on Mac OS X Mountain Lion.  (0) 2013.07.10
Public DNS server  (0) 2013.07.10
GDBM User Reference  (0) 2013.07.05
SyncMaster TA531 with Mac OS X  (1) 2013.07.01
UDP Maximum message size  (0) 2013.06.21
Posted by Jason Ryu
,

GDBM(GNU Database Manager) 사용자 매뉴얼을 iBooks Author로 정리해봤다.

목적은 iBooks Author로 퍼블리싱까지 해보는거였는데, 퍼블리싱을 위해 입력해야할 필수 항목들이란게 꽤 귀찮지만, 일단 <Delivery>까진 성공!!

iPad나 iPhone에서 보기엔 편해서 좋긴하다. 요약본 만들때 약간의 수고를 더해서 전자책으로 만들어두면 괜찮을듯하다.

[PDF] GDBM User Reference.pdf

[iBooks] GDBM.iba



'$ SaVvY > » computer' 카테고리의 다른 글

Public DNS server  (0) 2013.07.10
Red-Black Tree flow diagram  (0) 2013.07.09
SyncMaster TA531 with Mac OS X  (1) 2013.07.01
UDP Maximum message size  (0) 2013.06.21
가변매크로 __VA_ARGS__  (2) 2013.06.20
Posted by Jason Ryu
,

싱크마스터 TA531을 맥북에 연결하여 사용할때 늘 화면이 엉망 이었다.

모니터의 PC연결설정부분을 [HDMI1/DVI]로 맞추고 맥북에는 HDMI로 연결했는데 화질이 영 구리다.

구글링으로 관련 글들을 검색해보니 [HDMI1/DVI]로 맞추면 잘된다는 글만 있고, 그밖에는 아예 유사한 얘기 조차 없었다.

혹시나해서 RGB 케이블로 연결해봤는데, 이번엔 화질은 깨끗해졌는데 화면이 우측으로 지나치게 치우쳐있어서 모니터 메뉴상의 옵션으로는 화면위치를 맞출수가 없었다.

또다시 혹시나해서 [HDMI2]로 연결을 시도했더니, 이번엔 위치도 맞고 화질도 제대로 나온다.

(근 6개월을 그냥 푸르딩딩한 화면을 사용해왔는데.... 오늘에서야 -.-;;)


집에 있는 또다른 모니터 LG꺼는 그런 걱정없이 어느 포트로 연결하든 깨끗하게 잘나온다.


내 기억속에 각인된 선입견을 다시 바꿔줄 일이 생기지 않는한 '삼성제품'은 가능한 불매할 생각.

이 모니터가 아마 마지막 제품이지 싶다.


관련글: http://mtsparrow.blogspot.kr/2011/08/syncmaster-ta531-review.html


'$ SaVvY > » computer' 카테고리의 다른 글

Red-Black Tree flow diagram  (0) 2013.07.09
GDBM User Reference  (0) 2013.07.05
UDP Maximum message size  (0) 2013.06.21
가변매크로 __VA_ARGS__  (2) 2013.06.20
맥용 어플 추가...  (0) 2013.06.10
Posted by Jason Ryu
,

예전 자료들을 살펴보면, UDP 소켓에 대해서 getsockopt(...,  SO_MAX_MSG_SIZE,...)를 이용하면 최대메시지크기를 구할 수 있다고 나와있다.

하지만, 현재는 SO_MAX_MSG_SIZE란 옵션이 아예 없다. 적어도, Mac OS X 10.8과 Redhat EL6에 기본설치되는 라이브러리 헤더파일에는 존재하지 않는다. 그래서 컴파일이 안된다.

error: 'SO_MAX_MSG_SIZE' undefined.

언제부터 그 옵션이 사라졌는지는 모르겠지만, 중요한건 이식성문제때문에라도 사용하지 않아야겠다.

왜 없어졌는지 곰곰이 생각해보다, 구글링을 통해 자료를 좀 수집/정리 해보니 대강 다음과 같다.


UDP 패킷의 경우에는 TCP와 달리 전송할 패킷의 크기에 대해 신경써야 한다. 과거에 설령 getsockopt()로 구했다쳐도 그 크기를 마음대로 사용하기엔 무리가 있다. 즉, 중요한건 IP계층에서의 MTU에 대한 정의부분이다.  IPv4와 IPv6가 각각 576바이트, 1500바이트로 차이가 있다.

예를들어, 577바이트 데이터그램(UDP패킷)을 전송했을때 이 패킷이 목적지에서 수신될 수 있을지는 확신할 수 없게 된다.  MTU보다 큰 패킷은 MTU단위로 쪼개져서 전송이 일어나는데, 이 중 하나라도 전송에 실패하면 UDP는 그냥 전송에러로 끝나고, TCP는 재전송이 발생하게 된다.

결국 UDP를 사용하려면 가능한 MTU보다 작은 메시지를 전송하는 것으로 고려하는게 좋다는 것이다.

다만, 동영상과 같은 스트리밍을 전송할때 사용하는 UDP의 경우처럼 일부 유실되는 패킷이 전체 서비스에 미치는 영향이 미미한 정도로 판단된다면 사용해도 무방하다.

그렇다면, App 레이어에서 전송할 메시지의 크기는 대략 다음과 조건에 맞춰 계산하여 사용하는게 좋겠다.

    • IP 헤더크기 : IPv4의 경우 최소 20바이트, IPv6의 경우 최소 40바이트, 그리고, 최대크기는 60바이트가 된다.

    • UDP 헤더크기: 8바이트.

    • MTU 크기: 인터넷표준은 576바이트, IPS들이 종종 제시하는 값은 1500이다. 네트워크따라 천차만별!!!

App 레이어 메시지크기는 MTU 크기에 따라 결정되므로,

Maximum UDP packet size < (MTU - 68)

를 만족하는 작은 App메시지를 사용하도록 소스코드상에서 조정이 필요하겠다.

대략 계산은 나오지만 그렇다고 큰 기대는 하기 어렵다. 왜냐하면 네트워크 경로상의 가장 작은 MTU를 확인하기도 쉽지 않은데다, 언제든지 바뀔 수 있기 때문이다.

따라서, 전송성공율이 높아야 한다면 가능한 TCP를 사용하는 것이 바람직하고, 그렇지 않다면 UDP를 이용해도 무방하겠다. 역시나 필요성에 따라 선택!!!


'$ SaVvY > » computer' 카테고리의 다른 글

GDBM User Reference  (0) 2013.07.05
SyncMaster TA531 with Mac OS X  (1) 2013.07.01
가변매크로 __VA_ARGS__  (2) 2013.06.20
맥용 어플 추가...  (0) 2013.06.10
Mac에서 Office 문서 사용하기.  (0) 2012.06.13
Posted by Jason Ryu
,

C/C++에서 가변인자 함수를 사용하기 위해서는 어느 표준을 따라 컴파일하느냐가 중요하다.


C99 표준 이전에는 이런식이었다.

#ifdef    DEBUG

#define    TRACE(a)    print a

#else

#define    TRACE(a)

#endif /* DEBUG */

결국 사용할 때에는

TRACE(("result = %d\n", value));

위와 같이 "((", "))"를 사용하였고, 결국 printf("result = %d\n", value);라고 작성한것과 같은 결과를 만들어낸다.

gcc를 이용한다면 위의 매크로는 좀 더 간결해지긴 한다.

#define    TRACE(args...)    fprintf(args)

괄호를 하나만 쓰는것 빼곤 좋은점이 보이진 않는다. 더구나 "비표준"이라 다른 컴파일러에서 동작된다는 보장이 없다.


그래서 C99 표준에서 도입된 것이 가변매크로 정의방법이고, 그것이 __VA_ARGS__ 이다.

이를 이용하여 위 매크로를 만들어보면

#define    TRACE(other, fmt, ...)    my_function(other, fmt, ##__VA_ARGS__)

차이점은 "fmt"와 "..." 사이에 ","가 포함되어 있다는 것과 __VA_ARGS__로 대치되는것, 그리고 괄호는 하나만 사용한다는 것이다.

그리고, "##"을 사용하였는데 그건 다음과 같은 이유때문이다. 예를 들어,

TRACE(1, "one argument");

처럼 사용할 경우, 인자가 하나이므로 확장하면

my_function(1, "one argument", );

가 되어 ","가 문제를 일으킨다. 결국 "##"을 사용함으로써 이부분을 해결할 수 있다는 것이다.

많은 컴파일러들이 C99 표준을 따라주기때문에, 가변매크로를 사용하는데 지장은 없지만 여전히 C99표준을 따르지 않는 컴파일러들도 존재하고 있기때문에 주의해야 한다. 특히 Visual C++!!!



'$ SaVvY > » computer' 카테고리의 다른 글

SyncMaster TA531 with Mac OS X  (1) 2013.07.01
UDP Maximum message size  (0) 2013.06.21
맥용 어플 추가...  (0) 2013.06.10
Mac에서 Office 문서 사용하기.  (0) 2012.06.13
IMS(IP Multimedia Subsystem)  (1) 2012.05.05
Posted by Jason Ryu
,