漫談 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

新好男人

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

---
這到底是誰說的 XD

講

覺得今天講 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

合照

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

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

錯誤

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

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