|
เขียนเกม บนเครื่อง Nintendo DS : โปรแกรมพจนานุกรม Eng-Thai
พอดีได้ข้อมูลสนับสนุน จากคุณ real_stay เลยทดลองเขียน โปรแกรม พจนานุกรม Eng-Thai โดยหลักการค้นหาคำนั้นได้ทดลองหลายแบบ(ที่จริง แค่สองแบบ 55) คือ binary tree และ AVL tree คำศัพท์ประมาณ 3 หมื่น กว่าคำ ถ้าเป็น tree แบบ balance ก็มีความลึกประมาณ 14-15 level ทำให้ การหาค่อนข้างรวดเร็ว แต่มีปัญหาตอนที่เราจะสร้าง TREE ที่การใส่ข้อมูล จะช้ามาก binarytree ประมาณ 3 นาที ส่วน AVL tree เกือบจะชม. ได้มัง ก็ เปลี่ยนมาใช้วิธีแบบพื้นบ้าน คือ อ่านข้อมูลเข้า array แล้ว ค้นหาแบบแบ่ง ครึ่ง (จำชื่อ algorithm ไม่ได้อ่ะ) ก็แบ่งประมาณ15 ครั้งก็เจอ เลยเลือกวิธีนี้ ในการค้นหาคำใน พจนานุกรม แต่คำศัพท์ต้องเรียกลำดับด้วยนะครับ ถึงจะ ใช่วิธีนี้ได้ มาถึงตรงนี้ก็มาถึงบางอ้อ ว่า ที่ทำให้การใส่ข้อมูลช้า ก็คือข้อมูล ที่เรียงกันนี้เองทำให้ข้อมูลไปหนักทางด้านขวาตลอด เพราะเรียงคำจาก a ไปถึง z ดังนั้นถ้าเราจัดเรียงข้อมูลเข้าใหม่ให้เหมาะสม ก็คงใช้วิธีแบบ binary tree หรือ AVL tree ได้ไม่มีปัญหา ซึ่งข้อดีอย่างหนึ่งของการใช้แบบ binary tree ก็น่าจะเป็นเรื่องหน่วยความจำที่ไม่ต้องเป็นแบบ array ถ้าจำไม่ผิดจะเก็บไว้ที่ heap memory หรือเปล่า หว่า ?
สามารถ load มาดู code หรือ program สำเร็จรูปได้ ที่นี้ครับ
Create Date : 07 กันยายน 2551 |
Last Update : 7 กันยายน 2551 11:53:41 น. |
|
0 comments
|
Counter : 990 Pageviews. |
|
|
|
| |
|
|