Edison.X. Blog

給  (初學   --->  進階)  的觀念問題而已，高手涵之。

一般 C/C++ 在做檔案讀取範例時，會有幾個「假設」性存在，且此「假設」性與實際上之情況很可能有所差異。我們以一個例子而言：讀入學生的成績，計算，排序，輸出。此時都會假設欄位是「姓名  國文  英文  數學」等類似欄位，但第一個問題便是：檔案裡面的資料有幾筆？也就是說到底有幾個學生資料？目前沒看到一個能兼具速度與相容性、準度之作法。我們來探討一下這方面問題。

檔案開頭時，第一個數字便告知有幾筆資料

這是少數的做法，檔案第一行直接告知接下來有幾筆有效資料 (cnt)，接下來直接做 for(i=0; i<cnt; ++i) fscanf(....) 動作即可。但實際上這存在之情形非常少，一般實際應用之情況，並不會有這情形產生。

計算檔案之行數

一般而言，計算檔案行數當作是資料個數，是大多情況之做法，這種方法必須將檔案讀二次，第一次是計算行數(得知資料個數)，再配置所需記憶體大小；第二次再重頭讀一次資料，塞進記憶體裡面。

見過最慢的方式是用 fgetc，去統計 '\n' 有幾個，便知道有幾行，實際上可直接用 fgets 去完成，一次讀完一行即可。

用 fgets 是一般人認為最快的方式，實際上不然。可想一下， fgets 還是必須以 '\n' 為斷點，如果一行只有 20 個 character 的話，實際上 IO 次數還是很多次。

讀檔速度要增快其中一個要訣，就是減少檔案讀取次數，將在磁碟上之運作，盡可能搬到記憶體裡面去運作，這是其中一門要訣 (是有一些所謂的例外沒錯)。更快、更穩、較難一點實作之方式，是先用 fread 讀取一定的大小到字串 buffer 裡面去，再直接對字串 buffer 做 strchr /strcspn 之動作，如此一來便是將原本在磁碟上之動作，挪到記憶體裡面下來做，有興趣可自行實作看看。以成績單的那份例子而言，若採 1000 筆資料，速度比 fgets 快上 2~10 倍真的不是問題。

回歸 fscanf

從以前幾份實驗數據出來之結果，fscanf 速度其實真的非常慢，應是 parse 那裡慢很多，程式語言有一點水準的人都可以寫得比 fscanf 還要快，但它的便利性是無庸致疑的。

這種情況也曾見過幾次：文件檔本身，最後一筆資料並不會有 '\n' ，也就是說，若用計算檔案行數之方法，會少一行資料，這情況尤其是在從 excel 轉存 csv 或 txt 時會遇到。甚至較窘的情況是，文件檔本身，資料已結束，還多了好多的無意義換行 (多個二、三行，或多個快百行)，這些原始資料若是由程式產生，久了之後這些 (bug) 也成了 (spec.) [真是不好的習慣]；然而若是由人為之 excel 轉存產生，實在是不可控制之因素。

最後我還是建議了初學者：還是使用 fscanf 慢慢 parse ，算到底有幾筆資料吧！雖然速度慢很多，但避開了許多莫名奇妙的「例外」狀況，而這些「例外」狀況，久而久之竟變成了「使用規範」，實在也沒必要這麼搞下去。

fscanf 的慢，應已是眾所皆知，但想想為了使得程式碼變「快」，而必須再考慮其他的可能例外，延伸下去的開發時間，評估下來，或許可知道該怎麼做會較佳 (當然前提會是，對 string library 及 file io 有到熟練的地步)。

我需要更好的作法

這想法源自於 script language，當然也只是 script language 之冰山一角，同時這也不是適用於所有的解法。但一般在教別人寫演化式演算法時，若對方有一點基礎，我會用這種方式。

我也建議，如果覺得書本裡面的讀檔寫得不夠清楚，這是一個好的練習。

我舉 ga 演算法解 tsp 問題為例，此問題之 ga 的必設參數為群體大小、選擇方式、突變方式、突變率、交配方式、交配率、最大迭代次數(含在收斂條件裡面)、染色體長度。而同時染色體長度本身就等於是資料的筆數，於是會額外去讀 ga_tsp.set，而最後還有可能因為 tsp 的原始資料不同，所以也會在 ga_tsp.set 裡面再設定 city 座標的來源檔案，故 ga_tsp.set 長得大致如此

-----

ga_tsp.set

; 這是抬頭註解文字
; 分號以後視為註解
; 下面才是正式的參數設定

Population_Cnt = 100 ; 群體大小設 100
Select_Method = Wheel ; 設定為輪盤式選擇法
Crossover_Method = Single ; 設定為單點交配法，還有 double / mask 可選擇設定
Mutation_Method = Polling ; 設定為逐一突變法
Max_Itera = 1000 ; 設定為最大演化代數
Gene_Len = 200   ; 設定基因長度為 200
Crossover_Rate = 0.95 ; 設定交配率
Mutation_Rate = 0.005  ; 設定突變率
Tsp_Src_File = tsp.dat  ; 設定 tsp 來源檔案之檔名
Output_File = tsp.rst  ; 最後輸出之結果檔案

-----

有時候會連 seed 的初值都寫進去，seed = (某數字) 時就當作給初值；seed = (某字串或某特定數字) 時就當隨機產生。

由於自己會想要弄得比較像是 script language，那些 keyword 順序並無關係，甚至比較常用的是，keyword 不分大小寫。

至於 tsp.data 本身紀錄著 "至少 200 筆" 之 city 座標 (可想想為何只說是 "至少")。而最後還會為該程式處理 argv 之引數，弄出來的東西最後盡可能給日後可以用 batch file 就可以執行，不再重新 compiler。

將 ga.set 之變數值讀入，這對初學者而言是份很好的 homewok，但我想不透為什麼學校老師從沒針對這議題給出類似的 homework。

會使用多一 .set 這方式，主因乃是這份程式會有許多可變的參數、原始資料，要全寫死在程式裡面較不適合，可以拿出來額外當讀檔之參數設定；但若參數和原始資料全都放在一起，實在認為有點不洽當。另外一好處是，若此程式有寫入 argc / argv ，其實要做結果之統計，會方便很多，即使要做計時之統計[註一] 也會方便許多。

-----

[註一] 這問題已跳 tone。筆者目前看到大多數在講演化式演算法做 wall time 統計之文獻，其實給的數據在 cs 領域裡面是沒有太大意義的，所以也別太在意到底是怎麼計時的，因目前也沒有一份標準的規格告訴大家，演化式演算法他們在做統計時是怎麼統計的，也沒說明 compiler 參數標準要用哪套、要下怎樣的參數，導致實作面幾乎沒人提起。有些人從程式一開始就計時，一直到程式結束；有些人從「演算法初始化」到「演算法結束」作為計時，所以「寫入檔案、結果輸出」這花時間的動作，也是有些人納入計時、有些人納入不計時。即使如此，目前筆者頂多看過「使用的IDE 軟體」，也從沒給過「編譯參數」。總之大多的計時統計在 cs 領域裡面，是份不可靠、不會讓人信服的。甚至在原著不給原始碼的情況下，使用之硬體配備較原著稍差，最後程式碼寫完跑出來之效果比原著好了「不少倍」(5~10倍)，也不足為奇。只能說這數據留著和原著的結果做比對便可，畢竟真要做細部的效率分析的話，真的沒那麼容易，這也可能是最常拿自己所撰的 code 和 lingo 的結果 / 速度做比較之原因。