星期五, 1月 16, 2009

有關File I/O的兩三事(2) - Binary FIle

有趣問題: 電腦的資訊是由0和1組成,當塞了一堆0和1時,電腦如何得知要執行什麼動作?

這個問題從我學電腦的第一年到現在為止都是一個很有趣的問題XD 我在大學才給了一個自己比較滿意的解答,我所認為的答案是,Instruction Set Architecture(ISA) 會解釋比較基本的答案,也就是說,只要塞入一道道的instructions,電腦就會依序執行,當然,這中間還有很多事要做,我們就暫時略過。

有趣問題: 電腦如何判斷且讀取一個檔案?

這個問題其實更有趣,最常見的方法是,判斷副檔名。當然,如果自己把副檔名改掉,而電腦就會用另外一個程式來開啟時,當然我們不確保能打的開XD 那麼怎麼讀取? 通常每個File都會有一個header,而每個header有其固定的format,例如說我這學期處理過的wav file,讀取了前面這麼多bytes之後,我們才能判斷如何讀取接下來的資料(於是就有許許多多的file format document需要閱讀XD)。

那麼我們回到(1)的有趣問題,我們要怎麼寫入一個binary tree? 假設我們把每個node data structure如下(以下以C++為例)。

typedef struct _node{
unsigned int node_number;
unsigned int data;
unsigned int left_number, right_number;
struct _node* left; /* 理論上不用寫入檔案XD */
struct _node* right; /* 理論上不用寫入檔案XD */
}Node;

那麼當我們在C++中寫入Node array時,可能是這樣子寫的

    std::size_t list_size = 20;
Node* list = new Node[list_size];
/* ... */

std::ofstream outfile;
outfile.open("test.out", std::ofstream::out | std::ofstream::binary);
outfile.write(static_cast<char*>(static_cast<void*>(list)), sizeof(Node)*list_size);
當然,寫進去的檔案在linux下嘗試用more觀看時,應該會看到一堆亂碼XD

可是這樣子寫入我們會有一個問題,root node number為何,而總共又有幾個node,方法也很簡單,我們也一併寫入file,於是我們現在的File Format就變成

0~34~7...
total node sizeroot node numbernode data

所以我們的寫入檔案的方法就變成...

    unsigned int root_number;
std::size_t node_size;
std::size_t list_size = 20;
Node* list = new Node[list_size];

std::ofstream outfile;
outfile.open("test.out", std::ofstream::out | std::ofstream::binary);
outfile.write(static_cast<char*>(static_cast<void*>(&root_number)), sizeof(unsigned int));
outfile.write(static_cast<char*>(static_cast<void*>(&node_size)), sizeof(std::size_t));
outfile.write(static_cast<char*>(static_cast<void*>(list)), sizeof(Node)*list_size);
於是我們就把檔案寫完啦,那麼讀檔的時候,我就不另外寫啦(用std::ifstream XD)。


那麼這樣子的設計缺失在那? 第一個是,我們一定要寫入root node number嗎? 其實可以不用,如果在設計list時,我們強制把list[0]設為root,我們就不用另外寫入檔案(因此省了4 byte),第二個是,total nodes的數目只能是2^32-1個,其實非常大,足以應付一般日常生活所需,但在數學模型上,還是不能支援無限多個是有點可惜的事。

那麼這樣子寫入檔案有什麼好處? 答案是,非常的快以及容易撰寫(不論是讀取或寫入),而且,其實每個node size是固定的(24 bytes),也就是說,可以配合seekp, seekg任意跳及讀取,大部分的狀況,如果資料不夠大會一次讀進來,如果資料很大的時候,我們會利用buffered I/O來讀取,或者是跳到檔案某處只讀取我們所需要的資料(有時候,你只會需要檔案的某個部分。),至於讀進來之後要做什麼事,這就不是我要關心的了XD。

---
下回繼續分解XD

星期四, 1月 15, 2009

有關File I/O的兩三事(1) - 不算開始的開始

這篇是技術文,不想看的可以跳了XD 這篇是寫給初學者看的,也是我這幾天寫程式的心得,所以高手可以改錯XD。會想寫這樣子的文字是從SmallPig及cllee老師中所提及的File I/O方式,做一個論述。

大部分的書本都會提及如何在記憶體中操作程式,但是對於File I/O僅提及如何讀取,寫入,其實也相當正常,因為換作是我來寫,我也不知道要寫什麼額外的,然而在實作呢?

重要問題: 為什麼File I/O如此重要?
有趣的問題: 如何把binary tree寫入檔案,又從檔案中讀取建立binary tree呢?

先回答重要問題,回到基本計算機概論本身,常識會告訴你,記憶體中的資料只要一斷電就消失,而硬碟不會(但是硬碟容易壞XD),如果你要保留你的程式某些資訊,勢必是要寫入檔案中的,在有趣的問題中,binary tree小的話,每次重算倒也沒有什麼,但是如果是相當大量的資料呢,不寫入是不行的,而我想把有趣的問題拖到晚一點再回答。

那麼一般狀況下怎麼寫檔案?

  • 直接寫
    號稱人類最直覺的做法XD,想寫什麼就寫什麼,通常人看的懂,電腦很難看懂XD

  • binary file
    其實我也不知道怎麼稱呼XD,將C/C++中的struct直接以binary的方法寫入檔案(人看不懂,電腦很容易看懂XD),在一般狀況下稱為fixed file format,一般常見的檔案格式都是採用此方法,會有一個header在檔案的一開始,做為檔案的描述。

  • XML
    用一堆tag組成的檔案(人看的懂,電腦也看的懂,可是...XD),只要程式中具有XML parser,就可以慢慢的得到檔案想要傳遞的訊息,其實XML最常用的是在於網路中的訊息交換,在近期的檔案格式也相當常見。

先來慢慢討論第二項吧,這邊以C語言為範例(yen3 <- 不擅長C),假設今天struct如下。

typedef struct _Node{
int n;
char s;
} Node;
如果我們寫了這樣子的程式碼
    print("%d", sizeof(Node));  //output: 8
從這邊得到一個非常有趣的結果,結果是8 bytes而不是5 bytes,原因很簡單,因為要align memory,一個word是4 bytes,如果只有char時無妨,還是只有1 bytes,但是如果加入int時,那麼就要變成2個words為8 bytes,所以其實這個struct寫成
typedef struct _Node{
int n;
char s;
char unused[3];
} Node;

效果是一模一樣的。


利用這個例子,我想說明的是,如果要寫binary file,就要對每個byte斤斤計較放在檔案的那個位置,倒也不是為了節省記憶體(雖然某部分原因也是),而是為了支援File Random Access,Binary FIle的最大好處是,由於format固定,相當容易做到random access(在C中使用lseek(不過這是Unix System Call),在C++中使用std::ifstream::tellg(), std::ofstream::tellp()),只要每筆資料size固定,只要算出檔案相對的byte即可存取,相當方便。

那binary file壞處為何? 如果當初設計的File format不足以支援現有需求時,該如何因應? 有些File format會設計一些保留bytes,或者是延伸檔案格式,總而言之,如果要擴充時還蠻不方便的。


---
下回分解XD

星期二, 1月 13, 2009

Mac OSX 上的 vim 安裝 taglist


今天心血來潮想要在vim上裝一個taglist,發現一直裝失敗,後來才成功了XD

方法如下


  1. 下載taglist,之後把相關檔案對應複製到/usr/share/vim/vim72/ 下,兩個檔案複製到各別的資料夾

  2. 安裝最新的ctags直接安裝即可

  3. sudo rm /usr/bin/ctags (移掉,這是舊版,新版裝在/usr/local/bin 下)
    sudo ln -s /usr/local/bin/ctags /usr/bin/ctags (然後重新連結到新版去)

  4. 在vim中開原始檔試著打:TlistToggle 理論上可以用了XD


---
一波三折XD