computing star: 2009

2009年9月1日

編輯blog使用的語法

我已經在blogger中設定好相關的語法，照內文的方式排版即可

在blog顯示的文章摘要
<span class="fullpost">
我的內文

<div class="code">
1、先至 HTML Encoder 將code中的特殊字元做轉換
2、至 Advanced Syntax highlighting將程式碼highlight 我的程式碼
</div>

</span>

修正：參考以下的做法
http://www.helperblogger.com/2012/06/how-to-add-syntax-highlighter-v3-to.html

test equations: Einstein's most famous equation is $E=mc^2$.

2009年2月14日

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

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

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

2009年2月8日

const的意義與使用時機

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

const value

const int value = 100;

value這個變數是read only，在程式當中不可以被修改。
許多書上建議使用這個方法加上inline來取代macro。
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];
};
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之值是可以改變的。
const member function

class A{
…
void print() const{…}
};

const member function是C++特有的語法，是指此member function不會改變任何member data，若是在 function中改變了member data，compile時會傳回error。
const references

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

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

const int value = 10;
void print(int val){…}
print(value);

可將const variable傳入non-const argument，會自動轉型。同理non-const variable傳入const argument也會自動轉型。
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以避免修改到資料。

2009年2月7日

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中使用。

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

//time complexity: O(nlogn)
void preprocess(int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
int i, j;
//initialize M for the intervals with length 1
for (i = 0; i < N; i++)
M[i][0] = i;
//compute values from smaller to bigger intervals
for (j = 1; 1 << j <= N; j++)
for (i = 0; i + (1 << j) - 1 < N; i++)
if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i + (1 << (j - 1))][j - 1];
}

//output: the index of the minimum value between index i and j
int RMQ(int i, int j, int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
if(i<0 || i>=N || j<0 || j>=N)
return -1;
if(i > j) //swap i, j
i ^= j, j ^= i, i ^= j;
int k = (int)(log(j-i)/log(2.0)),
rem = j-(1<<k) + 1;
return (A[M[i][k]] > A[M[rem][k]] ? M[rem][k] : M[i][k]);
}

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：

//one dimensional Hausdorff distance
clear;
function [dist] = hausdorff(A, B)
if(size(A, 'r') ~= 1 | size(B, 'r') ~= 1)
warning("must be one dimension array");
dist = [];
return;
end
dist = max(compute_dist(A, B), compute_dist(B, A));
endfunction
//compute distance from point to set
function [dist] = compute_dist(A, B)
m = size(A, 'c');
n = size(B, 'c');
for k=1:m
D = abs(B - A(k));
dist(k) = min(D);
end
dist = max(dist);
endfunction
function [dist,dist2] = minHausdorff(A, B, t)
if (size(A, 'r') ~=1 | size(B, 'r') ~= 1 | size(t, 'r') ~=1)
warning("must be one dimension array");
dist=[];
return;
end
m = size(A,'c');
n = size(B,'c');
len = size(t,'c');
for i=1:m
for j=1:len
dist(i, j) = compute_dist(A(i)+t(j), B);
end
end
subplot(1, 2, 1);
xlabel("t");
plot(t, dist);
for i=1:n
for j=1:len
dist2(i, j) = compute_dist(B(i), A+t(j));
end
end
subplot(1, 2, 2);
xlabel("t");
plot(t, dist2);
endfunction
A=[0, 0.5, 2, 3];
B=[0 0.3 1];
t=linspace(-3, 3, 500);
minHausdorff(A, B, t);

2009年1月31日

C++ Operator overloaded

Operator overloaded是C++獨特的功能，能夠把operator重新定義，符合class的需求，但是在定義的時候要注意是否違反class原本的意義。

Rule of thumb, if a class needs a destructor, it will also need the assignment operator and a copy constructor. C++ Primer P.485
If the operator often does the same work, the common work should be put in private utility functions.

#include <iostream>
#include <cstdlib>
using namespace std;
//////////////////////////////////////////////////////
class Point{
public:
//constructor
Point(double xval=0.0, double yval=0.0):
x(xval), y(yval){}
//copy constructor
Point(const Point &rhs):
x(rhs.x), y(rhs.y){}
//destructor
~Point(){}
//must return a new object
friend Point
operator+ (const Point &lhs, const Point &rhs){
Point ret(lhs);
//call overloaded operator +=
ret += rhs;
return ret;
}
//must return reference
Point& operator+= (const Point &rhs){
this->x += rhs.x;
this->y += rhs.y;
return *this;
}
//prefix operator,return a reference
Point& operator++ (){
this->x += 1.0;
this->y += 1.0;
return *this;
}
//posfix operator++, return a new object
Point operator++(int){
Point ret(*this);
++*this;
return ret;
}
friend inline bool
operator== (const Point &lhs, const Point &rhs){
return lhs.x == rhs.x && lhs.y == rhs.y;
}
friend inline bool
operator!= (const Point &lhs, const Point &rhs){
return !(lhs == rhs);
}
//input operators must deal with errors and EOF
friend istream&
operator>> (istream &in, Point &obj){
in>>obj.x>>obj.y;
if(!in)
obj = Point();
return in;
}
//IO operators must be nomember functions
//should not print a newline
friend ostream&
operator<< (ostream &os, const Point &obj){
os<<"("<<obj.x<<", "<<obj.y<<")";
return os;
}
private:
double x, y;
};
//////////////////////////////////////////////////////

2009年1月30日

C++ Class基本架構

常常在使用C++ Class，但是常常會忘記架構，以下使用個簡單的範例來展示class的基本結構。

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
////////////////////////////////////////////////////
class Base
{
public:
//constructor
Base(int num=0,string str=""):
base_id(num), base_name(str){
cout<<"Base construction\n";
}
//Destructor
//若Base class的destructor沒有設定為virtual
//則derived clss的destructor不會被呼叫，無法運作
virtual ~Base(){
cout<<"Base destroyed\n";
}
//overloading
virtual void print(){
cout<<"base id = "<<base_id
<<" name = "<<base_name<<endl;
}
//abstract method, 必須是virtual，否則無法compile
virtual void printall() = 0;
protected:
int base_id;
string base_name;
};
////////////////////////////////////////////////////
class Derived : public Base
{
public:
//constructor
Derived(int num=0, string str="", int val=0):
Base(num, str), derived_id(val){
cout<<"Derived construction"<<endl;
}
//Destructor
virtual ~Derived(){
cout<<"Derived destroyed\n";
}
virtual void print(){
cout<<"derived id = "<<derived_id<<endl;
}
//Derived class必須實作來自Base class的abstract method
//否則在程式中class無法被implementation
void printall(){
cout<<"hello world"<<endl;
}
protected:
int derived_id;
};
////////////////////////////////////////////////////
int main()
{
Base *ptr = new Derived(1, "derived", 2);
ptr->print(); //call Derived print()
ptr->printall();
delete ptr;
return EXIT_SUCCESS;
}

在建構Derived class時，會先呼叫Base class的constructor，再呼叫Derived class的constructor，而destroy object時是相反的方向。
當Base class的method全部為abstract method時，可將Base class視為Java的interface來使用。

訂閱：文章 (Atom)

2009年9月1日

編輯blog使用的語法

2009年2月14日

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

2009年2月8日

const的意義與使用時機

const value

const member value

const pointer

const member function

const references

argument passing

const_iterator, const_reverse_iterator