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

一般 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 的結果 / 速度做比較之原因。

edisonx 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • novus
  • 開頭這樣打讓我很不好意思回覆... 但我還是要說,應該要善用「別人已經做得很好得東西」,把開發的力氣放在「別人沒想到、沒做好」的東西上。

    http://blog.ofset.org/ckhung/index.php?post/111d
    http://blog.ofset.org/ckhung/index.php?post/113c

    當成練習當然是還好,但類似的東西已經有一大堆實作了,實在是沒必要自己動手,連 Win32 API 都有 ini 讀寫函數。別說是單純的 config file parser,連 JSON 和 XML 都有一堆,最簡單像 RapidXML 只要你把幾個 *.h 加入專案中就能用了,功能完整一點的還有 boost.program_option 和 property_tree

    還有像這種東西對於學過 parsing 的人來說應該只是小菜一碟,更何況讀取小小的設定檔幾乎不可能會成為效能瓶頸,慢一點就慢一點。
  • 同意 novus 。此篇確實也只是講些基本的,或許下次被問到類似的問題,該建議他人學習使用 library 較佳。

    附一提,那兩篇 blog 真是讓我看得欲罷不能,可惜沒有推可以讓我按。

    edisonx 於 2012/02/05 02:24 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼