星期六, 4月 18, 2009

漫談 heap tree

身為一個懶人如我,heap tree 對我而言是一個非常好用的 data structure,其實這篇講的不是很難,只是要講我很懶 XD

我還蠻記得我第一次學習 C++ STL 的時候,我第一次體會到,何謂需求? 如果可以分析資料的基本特性,就可以找到比較弱的方法,而不用每次都用很強的方法。舉個例子說,從一個 ordered list 中取出 max element ,早期的我可能笨笨的排序完就直接上了 (std::sort() 很方便啊 XD),但是如果每次都只是從序列中取出最大或最小元素,可能候用 std::make_heap() 搭配 std::pop_heap() 即可,而且速度比前者快很多,其實大部分我們只是想取某個特性的元素,也不用每次都拿排序來做。如果每次都僅插入元素來形成 ordered list 的話,當然也可以使用 std::list 與 std::list::sort() 來實作,這樣子我們也可以很方便的來達成我們的要求,只是每次插入一個新元素的時間為 O(n),但是只要能夠循序存取就支援這個特性。而 heap tree 雖然插入一個新元素為O(log n) ,但是考慮到記憶體使用策略,端看怎麼用了。

我記得我在很久以前與人合作寫程式的時候,有人一次讀了數mb進來存在 std::string 中,然後使用 std::string::insert ,這人就問我為什麼跑起來無敵慢,我說原因其實蠻簡單的,因為這個 member function 的時間是 O(n),後來改成分段讀取後處理,速度快了好多啊XD。

題外話: 我沒有用過 Boost::asio 和 Boost::thread ,有人用過的可以告訴我穩定否 XD?


---
寫程式時,盡量使用最弱假設,會有驚喜的。


2009/04/18 5:32 pm 大鳥 在 comments 中有提到更好的方法,不過我還沒試,所以有看的人要記得看回覆喔XD

星期五, 4月 17, 2009

新好男人

yen3姊: 有帶面紙是新好男人的表現喔
yen3: 有沒有變成新好男人我不知道,不過我變成面紙供應商倒是真的 XD


---
這到底是誰說的 XD

星期三, 4月 15, 2009

覺得今天講 Java Technicalities 說的不是很好,有點說太快了,也說太淺了,一方面是簡報只有準備這樣子,一方面是時間太短,最大的問題是自己掌握能力太差了...Orz


---
再改進

Java I/O

利用現在難得空閒(原本要講 Java Technicalities 因故延期 XD)來寫一下這篇前幾天想寫的東西好了

Java I/O 和 C++ I/O 都是採取 OO 做為設計準則,所以其實 Java I/O 並不難懂,難懂的是,為什麼會有這麼多名詞 ... Orz,其實 Java I/O 大至上可以分為

  • InputStream/ OutputStream - 一次讀取以 1 byte 為單位
  • Reader/ Writer - 一次讀取以1 char 為單位

由於 Java String 是以 UTF-8 為 default encoding ,所以如果使用 Reader/ Writer ,1 char = ?? bytes ,其實談到 I/O 與 string 躲不掉的就是編碼問題,可是這我也不懂,我們再來大概分類一下XD

  • InputStream/ OutputStream
    • StringBufferInputStream/ StringBufferOutpuStream - 如前文所提,String 並不一定是 1 char = 1 byte,所以此 class 已經不被建議使用
    • ByteArrayInputStream/ ByteArrayOutputStream - 如果你很肯定你的 String 的單位是 1 byte,可以使用這個 class + String.getBytes() 來使用
    • FileInputStream/ FileOutputStream - 檔案用的 XD
    • Socket.getInputStream()/ Socket.getOutputStream() - 很明顯,這是 Socket Programming 用的XD
    • Process.getInputStream()/ Process.getOutputstream() - 這是 Process Control 用的 XD 需用 ProcessBuilder 來建立 Process
  • Reader/ Writer
    • StringReader/ StringWriter - 官方建議用來讀取 String 的 class
    • FileReader/ FileWriter - for file
    • CharArrayReader/ CharArrayWriter - 我不想說了XD

其實還有很多沒提到的,但是我們可以把上述的的class再分別接到(做為以下 contructor argument)...

  • InputStream/ OutputStream
    • BufferedInputStream/ BufferedOutputStream - 加上 buffer
    • DataInputStream/ DataOutputStream - 支援格式化輸入輸出
  • Reader/ Writer
    • BufferedReader/ BufferedWriter - 同樣支援 readLine()/ writeLine()
    • 格式化輸入輸出我就不知道了,不過有想到Scanner 可以格式化輸入

看到這邊其實蠻亂的,不過這就是Java...Orz 其實只要記得有兩套方法就可以了,偏偏又跑出一個兩者的單向橋樑...

  • InputStreamReader/ OutputStreamWriter - 讓 InputStream/ OutputStream 可以橋接到Reader/ Writer 去,反之不行

其實原因還蠻簡單的,今天我收到的 InputStream/ OutputStream 裡面的字元不一定是以 1 byte 為單位啊(其實知道 encoding 的話,也不難辦),例如說我從 Socket 收到的訊息採用 UTF-8 的話,我們就可以寫出這種程式碼 XD

Socket connect = new Socket("balabala");
BufferedReader br = new BufferedReader(new InputStreamReader(connect.getInputStream()));

那麼其他沒有提到的有...

  • RandomAccessFile
  • ObjectInputStram/ ObjectOutputStream
  • java.nio

以後有空再說吧(以後真的會有空嗎... XD)


---
這篇倒是寫蠻快的 XD

星期二, 4月 14, 2009

合照


從 Clara 手上得到我和 Josh Ko 合照一張, Clara 說我看起來比較兇惡...XD 我只是沒有剪頭髮而己嘛 XD


---
有剪頭髮好像也差不多XD

星期一, 4月 13, 2009

錯誤

答答的鍵盤聲是美麗的錯誤 我只是個 programmer 不是 bugger producer ...Orz


---
又要 debug 一陣子了...Orz