Chulalongkorn University Theses and Dissertations (Chula ETD)
ระบบการวิเคราะห์อัลกอริทึมเชิงทดลองด้วยการวัดคำสั่งการทำงาน
Other Title (Parallel Title in Other Language of ETD)
Experimental analysis of algorithm system using instruction instrumentation
Year (A.D.)
2011
Document Type
Thesis
First Advisor
สมชาย ประสิทธิ์จูตระกูล
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิทยาศาสตร์คอมพิวเตอร์
DOI
10.58837/CHULA.THE.2011.1388
Abstract
การวิเคราะห์อัลกอริทึมมีวัตถุประสงค์เพื่อนับจำนวนครั้งการทำงานในแต่ละบรรทัดของรหัสต้นฉบับระหว่างการทดลอง เพื่อศึกษาประสิทธิภาพเชิงเวลาการทำงานของอัลกอริทึม วิทยานิพนธ์นี้นำเสนอรูปแบบบริการเพื่อการวิเคราะห์อัลกอริทึมเชิงทดลอง นำเสนอผ่านเว็บและเว็บเซอร์วิส รองรับรหัสอัลกอริทึมภาษาจาวา สามารถกำหนดรูปแบบการทดลองได้แก่ ขนาดของข้อมูลขาเข้า และลักษณะของข้อมูลขาเข้า และเก็บข้อมูลการทดลอง โดยใช้รูปแบบต้นไม้ไวยากรณ์ที่เป็นนามธรรม (AST) ในการสำรวจต้นไม้ และแทรกคำสั่งในการนับการทำงานของแต่ละบรรทัดของรหัสต้นฉบับอย่างอัตโนมัติ จากนั้นจึงแปลงรูปแบบต้นไม้กลับเป็นรหัสต้นฉบับที่พร้อมสำหรับการทดลอง โดยผลลัพธ์จะนำเสนอในรูปแบบกราฟเส้นเพื่อแสดงอัตราการเติบโตของอัลกอริทึม และฮิสโตแกรมเพื่อสะท้อนปริมาณการทำงานในแต่ละบรรทัดของรหัสต้นฉบับ วิทยานิพนธ์นี้สามารถนำไปใช้ได้กับการเรียนการสอนในเนื้อหารายวิชาที่เกี่ยวกับการวิเคราะห์อัลกอริทึม
Other Abstract (Other language abstract of ETD)
Analysis of algorithm objective is to count the number of times each source code instruction gets executed during the experiments to study the efficiency of the algorithm. This research presents a service for experimental analysis of algorithms presented by web application and web service support algorithms written as source codes in Java programming language. Experimental parameters can be configured such as range of input sizes and input characteristics. This is done by source-code instrumentation that parses the source code to obtain its associated abstract syntax tree (AST), traversing the tree, inserting extra counting instructions at instruction nodes and finally transforming the tree back into an instrumented source code ready for experiments. Experimental results are shown as a scatter plot of running time versus input size along with their correlation using curve fitting. In addition, an instruction-execution-count histogram is also shown adjacent to the source code for better visualization. This system is used effectively in teaching algorithm analysis courses.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
กระจังทอง, ธนินทร์, "ระบบการวิเคราะห์อัลกอริทึมเชิงทดลองด้วยการวัดคำสั่งการทำงาน" (2011). Chulalongkorn University Theses and Dissertations (Chula ETD). 68507.
https://digital.car.chula.ac.th/chulaetd/68507