제목 보고 당했다.

"새표준 C C99" C99 표준 번역서 인줄 알고 냉큼 샀는데, C 기초 프로그래밍 책이다.

이런,.

All about unicode

(korean) 진숙의 유니코드 입문서 

Backtracking

백트래킹은 주어진 어떤 집합에 대해 조건을 만족하는 모든 부분집합(subset)을 구하는 정형화된 알고리즘이다.

/*
  a[] : 답중 하나가 되는 부분 집합을 저장할 공간
  n : 전체 집합의 크기
  k : 현재 집합의 크기
  candidates[] : 조건들 (예, 포함되거나 안되거나)
*/
void process_solution(int a, int k)
{
  for (int i = 1; i <= k;)
    if (a[i] == 1) printf ("...", i);
}
void construct_candidates( ... c, *nc)
{
  c[...] = condition
  ...
  *nc = X; // number of conditions
  return;
}
backtrack(a[], k, n)
{
  if (k == n)
    process_solution(a, k);
  else
    k++;
    construct_candidates(c, &nc);
    for (int i = 0; i < nc; i++)
      a[k] = c[i]; // set condition
      backtrack(a, k, n);
}
int main()
{
  a = arr[MAXSIZE];
  backtrack(a, 0, n);
}

Minimizing Memory Cost

프로그램이 사용하는 메모리를 절약하기 위한 방법들에 대해 정리해 보자.

• 일단 단순해져야 한다.
  메모리의 구조를 단순하게 하면 크기도 줄어들고 실행속도도 빨리질 수 있다. (세금 계산 테이블을 메모리에 넣는 대신 이를 표현하는 하나의 함수를 사용할 수 있다)
• 메모리 절약을 위해 사용되는 기법들은 아래와 같다.
  
  • Sparse data structure
    는 대부분의 엔트리가 같은 값을 가지는 데이터 구조를 의미하는데, 이를 리스트와 같은 자료구조를 사용하면 메모리를 절약할 수 있다. 혹은 같은 값을 가지는 부분만 떼어 내어 별도로 저장하므로 같은 값을 중복으로 저장하는 overhead를 줄일 수 있다.
  • 데이터 압축
    은 말그대로 압축을 하거나, 한 자료 타입안에 여러 데이터를 동시에 넣는 방법이다. (두 지점사이의 거리를 나타내는 행렬, 좌표 등)
  • 할당 정책의 변경
    을 통해 메모리를 절약할 수 있다. 공간을 정적으로 미리할당하지 않고 필요할 때 동적으로 할당해주는 것을 예로 들 수 있다.
• 물론 메모리 절약에서도 Amdahl's law 가 적용된다. 특정 데이터 구조가 전체 메모리 공간의 대부분을 차지하는 경우를 찾아 개선하면 효율적으로 메모리를 절약할 수 있다.
• 때로는 메모리 절약을 위해 성능을 희생해야하는 Trade-off 가 발생한다.
  

Using Macro is not always faster.

함수 콜하는 부분을 매크로로 치환하면 일반적으로 성능이 빨라진다. 그러나 항상 그렇지는 않다.

#define MAX(a,b) ((a) > (b) ? (a) : (b))

float arrmax(int n)
{
 if (n == 1)
     return x[0];
 else
 {
         return MAX(x[n-1], arrmax(n-1));
 }
}

위 코드는 매우 느리다. 배열의 최대값을 리턴하는 코드인데, 배열의 크기가 30개만 넘어가도 실행 속도가 수초이상 걸리게 된다. 왜냐하면 매크로 부분이 x[n-1] > arrmax(n-1) ? x[n-1] : arrmax(n-1) 로 치환되면서 수행시간이 (함수가 호출되는 횟수가) 매크로 대신 함수로 구현할 때 보다 O(n) 에서 O(2^n) 이 되기 때문이다. 재귀적 호출에서 이런 실수는 상당한 성능저하를 낳게 되니 주의 하자.

Code Tuning

코드 튜닝은 기본적으로 구조에 적합한 효율성을 얻는데서 만족해야지 지나친 최적화나 그 반대의 경우로 치우치면 곤란하다.

1. Hotspot (병목) 찾아내기
2. 그 부분 최적화 하기

의 식으로 진행하는데, 코드 튜닝의 팁&예를 들면 아래와 같다.

나눗셈은 다른 연산보다 비용이 많이 든다. 그래서 가능한 경우 아래처럼 할 수 있다고 한다.

k = (a+b) % n; // 요거 대신
k = a + b; if (k>=n) k -=n; // 요렇게

경우에 따라 2배의 성능 차이가 있다고 한다.

메모리 접근 빈도나 계산 시간 중 오래 걸리는 것을 개선해라

매크로가 항상 성능을 개선시키는 것은 아니다. recursive하게 호출되는 경우 책에서는 경우에 따라 1,000배까지 느려진다고 한다. 이건,.. 테스트 해봐야 겠다. (물론 매크로를 써서 성능이 향상된 경우도 있다.)

for loop 의 비교횟수를 줄여 5% 성능향상을 가져올 수도 있다. 좀, 심하긴 한데,

int search(int t) {
 hold = x[n];
 x[n] = t;
 for (i = 0; ;i++) {
   if (x[i] == t)
     break;
 x[n] = hold;
 if (i == n)
   return -1;
 else
   return i;
}

요렇게 해서 for 루프에서 매번하던 비교연산을 줄일 수 있다.

그리고, loop unrolling으로 속도를 개선할 수 있다. loop를 말그대로 조금 펼쳐서 pipeline이나 Multicore 에서 돌아가는 점을 살려 병렬로 실행시킬 수 있다. (요건 컴파일러에서도 어느정도 지원해줄 것 같다.)

위에서 소개된 방법들의 이름으로 정리를 해보면,

• Exploit common cases 자주쓰이는 경우를 캐시하는 것과 비슷한 방법이고,
• Exploit an algebric identity 요건 대수적인 최적화를 한다는 것이고,
• Collapsing procedure hierarchy 는 함수콜 대신 매크로, 인라인 쓰는 것이고
• Loop unrolling 은 아까 했고.
• Data structure augmentation 은,. 설명하기 귀찮다. ㅡ.ㅡ;.

Dijkstra Algorithm

다익스트라 알고리즘은 가중치를 가지는 양방향 그래프에서 특정 정점에 대한 나머지 정점들로의 최단거리를 구하는 알고리즘이다.
가중치를 가지는 간선을 가지는 그래프를 G[V,E] 라하고 정점들의 집합을 S, Q두개로 가질 수 있다고 할때 알고리즘은 아래와 같이 기술될 수 있다.

while Q is not empty
 S = empty
 Q = G[V,E]
 u = extract_min(Q);
 for edge from u
   relax(edge, u)

간단히 기술하면, 먼저 시작점 s 로부터 걸리는 경로 값을 각 정점에 기록할 수 있다고 할때, 모든 정점에 infinite 값 (아주 큰값)을 넣은 후 모든 정점들을 Q에 넣는다(s 에는 값 0을 넣는다). 그리고 Q 에서 최소 값을 가지는 정점을 하나 꺼내어 이 정점이 가지는 모든 간선들에 대해 relax를 수행한다. relax 란 간선들과 연결된 정점들에 최단 경로값을 갱신해 넣어주는 것을 말한다(이미 Q에서 빠져나온 노드들에 대해서도 갱신한다). 이 과정을 Q에 정점이 없을 때까지 반복한다.