Windows中使用MinGW編譯部份的C++ Boost Library

大部份Boost裡面的library，都只需要include header file就可以正確的編譯成執行檔，但有一些library需要先編譯出*.lib或是*.dll在link時才能夠正確的編譯成執行檔。在1.38.0中，Filesystem, IOstreams, ProgramOptions, Python, Regex, Serialization, Signals, Thread, Wave這些都是需要先編譯的library，以下以Thread為例。

• OS：Windows XP SP3
• Compiler：MinGW 3.4.2
• Boost library：1.38.0

1. 首先系統必需先安裝好MinGW，並且加入MinGW_HOME/bin至PATH中。
2. 將Boost的壓縮檔解開，並且加入Boost_HOME至PATH中。
   
3. 至網路上抓已經編譯好的bjam，解壓縮後放入BOOST_HOME中。
4. 執行cmd模式，切換至BOOST_HOME目錄中，輸入bjam --toolset=gcc –with-thread stage
   其中—with-thread表示只編譯thread這一個library。
   
5. 系統會只編譯thread library，並且將lib和dll檔放在Boost_HOME/stage/libs中。
   

接下來要開始寫程式時，只要記得在IDE(我的習慣是CodeBlocks和Eclipse)設定好include的路徑和link library就可以使用該library。

const的意義與使用時機

const在C++中是很常使用的修飾字，其原本的意義是指「不會被修改」也就是read only的意思。但是隨著其放在不同的地方，而有不同的功能。其中const pointer最容易被搞混，要特別注意。

1. const value

   const int value = 100;

   value這個變數是read only，在程式當中不可以被修改。
   許多書上建議使用這個方法加上inline來取代macro。

2. const member value

   class A{
       const int value;
       …
   };

   const member value只在object的生存期間是常數，而對於整個class而言是可變的，因為class可以創建多個instance，不同的instance其const member value可以為不同值。所以不能在class declaration初使化consta member value，因為在instance尚未被建立時，compiler不知道const member value之值。
   
   
   
   要初使用const int value，必須使用constructor：
   

   A(int val=0):value(val){}
   
   
   
   想要建立在所有instance都相同的常數，可使用enum或者static const來實作：
   class A{
       enum{size = 100};
       const int value = 200;
       int array[size];
       int array2[value];
   };

3. const pointer

   int value = 500;
   /*

     a, b兩種語法是相同的，因為const都在「*」的左邊，
      代表pointer所指向的值是常數，但是pointer可以指向其它不同的值，
       Ex: a=&another;
   */
   const int *a = &value;         
   int const *b = &value;
   /*
       const在「*」的右邊，代表pointer本身是常數，
      即pointer不可指向其它不同的  值，但是值本身是可變的。
      Ex:value = 300;
   */
   int* const c = &value;
   /*
      pointer所指向的值是常數，且pointer本身也是常數，兩者皆是read only
   */
   const int* const d= &value;

   this pointer本身不可指向其它不同的object，但是其指向的object之值是可以改變的。

4. const member function

   class A{
       …
       void print() const{…}
   };
   
   const member function是C++特有的語法，是指此member function不會改變任何member data，若是在 function中改變了member data，compile時會傳回error。

5. const references

   void function(const &value){...}

   使用const reference可以避免在傳遞argument使用call by value的方式，在傳遞物件時比較有效率且可以保證所傳遞的值在function中不會被修改。

6. argument passing

   const int value = 10;
   void print(int val){…}
   print(value);
   
   可將const variable傳入non-const argument，會自動轉型。同理non-const variable傳入const argument也會自動轉型。 

7. const_iterator, const_reverse_iterator

   vector<int> vec;
   vector<int>::const_iterator iter;
   vector<int>::const_reverse_iterator riter;
   
   當STL container的資料為read only時，應使用const iterator以避免修改到資料。

Range Minimum(Maximum) Query, RMQ

• Input：array A[0, N]
• Output： the index of minimum(maximum) value between two given indices.

RMQ的功能是若有一群資料放在array中，在經過preprocessing後，可在O(1)的時間內找出index i~j之間的最小(大)的元素。目前preprocessing最快是O(n)，也就是只需要O(n)的時間就可以處理完成。

以下介紹O(nlog(n))的preprocessing方法，O(n)的方法是由此法去改進，所以先了解此法相當重要且因程式碼容易撰寫，所以也相當適合在ACM中使用。

1. 假設array的長度2的n次方。
2. 建立一個大小為n x log(n)的矩陣M，用來存放RMQ的結果，其中M[i][j]是指以index i開頭，長度為2^j次方內最小元素的index。
3. 使用dynamic programming方法建立M，需O(nlogn) time。

 

1. //time complexity: O(nlogn)
2. void preprocess(int M[MAXN][LOGMAXN], int A[MAXN], int N)
3. {
4.     int i, j;
5.  
6.     //initialize M for the intervals with length 1
7.     for (i = 0; i < N; i++)
8.         M[i][0] = i;
9.     //compute values from smaller to bigger intervals
10.     for (j = 1; 1 << j <= N; j++)
11.         for (i = 0; i + (1 << j) - 1 < N; i++)
12.             if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
13.                 M[i][j] = M[i][j - 1];
14.             else
15.                 M[i][j] = M[i + (1 << (j - 1))][j - 1];
16. }

 

1. //output: the index of the minimum value between index i and j
2. int RMQ(int i, int j, int M[MAXN][LOGMAXN], int A[MAXN], int N)
3. {
4.     if(i<0 || i>=N || j<0 || j>=N)
5.         return -1;
6.  
7.     if(i > j) //swap i, j
8.         i ^= j, j ^= i, i ^= j;
9.  
10.     int k   = (int)(log(j-i)/log(2.0)),
11.         rem = j-(1<<k) + 1;
12.     return (A[M[i][k]] > A[M[rem][k]] ? M[rem][k] : M[i][k]);
13. }

Reference：

• Range Minimum Query and Lowest Common Ancestor

One dimension minimum Hausdorff distance

Hausdorff distance可以用來量測兩個sets之間的距離，如果將其中一個set的元素全部加(減)上t個單位，則兩個sets之間的Hausdorff distance可能會變小或變大。實際的應用，假設我們要做影像的比對，有一張影像為template，而另一張影像是準備要和template比對的圖片，若能夠讓兩張圖片儘量對齊，則能夠提高辨識的淮確度。

my meeting report

我在IPL Vol 106(2008)第一次看到這一篇A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation時，看了很久還是不懂演算法實際上是如何運作的，於是追蹤下去追到了源頭的兩篇論文。

源頭是Huttenlocher在1990年發表的Computing the Mimimum Hausdorff Distance for Point Sets Under Translation，這一篇提出的算法提供最初的想法，把sets中每一個元素移動t單位的軌跡的圖形找出來，再找出所有軌跡極大值中的最小值即為所求，時間複雜度是O(mnlog(mn))。

第二篇論文是Rote在1991年發表的Computing the mimimum Hausdorff distance between two point sets on a line under translation也是沿用了Huttenlocker的概念，只是他使用了一個lower bound來減少搜尋解答時所要檢查的解答數量，這個演算法的時間複雜度已經是Optimal (O(m+n)log(m+n))，所以一直以來大家都使用這個算法。

2008年的這一篇論文也是Optimal algorithm，但是所需要檢查的解答數量又更少了，時間複雜度仍然是O((m+n)log(m+n))，但實驗的結果比Rote’s algorithm快了將近15倍。

以下是我用來畫軌跡圖的Scilab script：

1. //one dimensional Hausdorff distance
2. clear;
3. function [dist] = hausdorff(A, B)
4.   if(size(A, 'r') ~= 1 | size(B, 'r') ~= 1)
5.     warning("must be one dimension array");
6.     dist = [];
7.     return;
8.   end
9.  
10.   dist = max(compute_dist(A, B), compute_dist(B, A));
11. endfunction
12.  
13. //compute distance from point to set
14. function [dist] = compute_dist(A, B)
15.   m = size(A, 'c');
16.   n = size(B, 'c');
17.    
18.   for k=1:m
19.     D = abs(B - A(k));
20.     dist(k) = min(D);
21.   end
22.   dist = max(dist);
23. endfunction
24.  
25. function [dist,dist2] = minHausdorff(A, B, t)
26.     if (size(A, 'r') ~=1 | size(B, 'r') ~= 1 | size(t, 'r') ~=1)
27.         warning("must be one dimension array");
28.         dist=[];
29.         return;
30.     end
31.  
32.     m = size(A,'c');
33.     n = size(B,'c');
34.     len = size(t,'c');
35.    
36.     for i=1:m
37.         for j=1:len
38.             dist(i, j) = compute_dist(A(i)+t(j), B);
39.         end
40.     end
41.     subplot(1, 2, 1);
42.     xlabel("t");
43.     plot(t, dist);
44.    
45.     for i=1:n
46.         for j=1:len
47.             dist2(i, j) = compute_dist(B(i), A+t(j));
48.         end
49.     end
50.     subplot(1, 2, 2);
51.     xlabel("t");
52.     plot(t, dist2);
53. endfunction
54.  
55.  
56. A=[0, 0.5, 2, 3];
57. B=[0 0.3 1];
58. t=linspace(-3, 3, 500);
59. minHausdorff(A, B, t);