2008年9月26日 星期五

[ACM] 加速法

觀念

有修過OS應該都知道,因為執行IO動作會牽涉到interupt、system call 等等機制,花掉非常多的時間。所以對大部分的ACM題目來說,減少IO的次數是加速的好方法。

關鍵點 : 「減少IO次數」


  1. Buffered Input: 不要用scnaf() 或者cin,用fgets一次讀進來,再parse字串。
  2. Buffered Outout: 先用StringStream輸出至memory,最後再一次印出。
  3. Buffered大小約在5000Byte左右,不要太小,也不要太大,導致Memory要做Swapping或paging。

其他小方法:

1. CPU通常會對4Bytes運算做最佳化(現在的32bit系統,應該也是對4Byte資料做運算最快),所以處理資料盡量用4Bytes當一個單位。

2. 但是超過一定的資料量大小,通常長度超過十萬的陣列,那麼整個陣列的體積反而影響比較大,這時能用char, short 比較快。