A pure Python Ternary Search Tree Library

จากที่ lindever แนะนำมาว่า ternary search tree (tst) เอามาใช้แทน Trie ได้ เขียนไม่ยากด้วย. เลยเคยเขียน Ternary search tree ด้วย Ruby แบบล้วนๆ และไม่ค่อยได้พยายาม optimize เท่าไหร่ ปรากฎว่ากว่าจะ build tree เสร็จใช้เวลา ~ 10 นาที [1].  สำหรับ word list ประมาณ 1 แสนคำ. วันนี้ลองเขียนดูใหม่พยายามทำ array ให้ flat กว่าเดิม และใช้ Python เขียนด้วย ปรากฎว่าเวลาที่ใช้ build tst เหลือแค่ ~ 1 นาที และเวลาที่ใช้ load tst ที่ build แล้วขึ้น memory โดยใช้ cPickle ก็ใช้เวลา ~ 10 วินาที. ทั้งหมดนี่ทดลองบนเครื่อง iBook G4 ซึ่งผมก็ค่อนข้างพอใจ ถึงจะไม่ได้เร็วมากแต่การเขียนอะไรต่ออะไรด้วย Python ล้วนๆ น่าจะดีกว่าเวลาไปเช่า web hosting ของชาวบ้าน คงหาคนยอมให้ลง Python extension ยาก. หน้า project อยู่ที่  http://code.google.com/p/kunyittst/

ป้าย:

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s