Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การเรียงลำดับภายในของกระแสตัวเลขภายใต้เงื่อนไขที่จำกัดขนาดหน่วยความจำ
Year (A.D.)
2020
Document Type
Thesis
First Advisor
Suphakant Phimoltares
Second Advisor
Chidchanok Lursinsap
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Computer Science and Information Technology
DOI
10.58837/CHULA.THE.2020.1479
Abstract
Due to technological advancements, data consumption is exponentially increasing. However, the size of memory storage increases linearly. Therefore, memory storage is insufficient to store big data. Besides, all existing sorting algorithms cannot sort big data in the memory storage with limited capacity, which is much smaller than the data size. Although external sorting algorithms can sort big data, they cannot keep a sorting result on limited memory storage. This dissertation proposed two new sorting algorithms to handle the sorting issue of streaming data in limited memory storage, namely, streaming data sort, and fast streaming data sort. Both sorting algorithms are focused on streaming data of integer numbers and proceeded on limited memory storage whose size is less than the data size. An upper bound of the memory storage size of the streaming data size n is revealed in this research. Both algorithms obtain the time complexity O(n) and the space complexity O(M), where M is the size of memory space and M is n/3. The experimental results of two proposed algorithms show they can solve sorting issue of streaming data in limited memory storage 35% smaller than data size. Moreover, the speed of fast streaming data sort is about 28 times faster than streaming data sort.
Other Abstract (Other language abstract of ETD)
เนื่องด้วยความก้าวหน้าทางเทคโนโลยีส่งผลให้การบริโภคข้อมูลมีการเพิ่มขึ้นแบบเอกซ์โพเนนเชียล อย่างไรก็ตามขนาดของหน่วยเก็บหน่วยความจำเพิ่มขึ้นแบบเชิงเส้น ดังนั้นขนาดของหน่วยเก็บหน่วยความจำไม่เพียงพอที่จะจัดเก็บข้อมูลขนาดใหญ่ นอกจากนี้ขั้นตอนวิธีการเรียงลำดับใดๆ ที่ปรากฎอยู่ไม่สามารถเรียงข้อมูลขนาดใหญ่บนหน่วยเก็บหน่วยความจำที่มีความจุจำกัดซึ่งน้อยกว่าขนาดของข้อมูลดังกล่าวอยู่มาก แม้ว่าขั้นตอนวิธีการเรียงลำดับภายนอกจะสามารถเรียงลำดับข้อมูลขนาดใหญ่แต่ไม่สามารถจัดเก็บผลการเรียงลำดับด้วยหน่วยเก็บหน่วยความจำที่จำกัดได้ วิทยานิพนธ์นี้เสนอขั้นตอนวิธีการเรียงลำดับแบบใหม่สองวิธีเพื่อจัดการปัญหาการเรียงลำดับของข้อมูลแบบกระแสบนหน่วยเก็บหน่วยความจำที่จำกัดซึ่งเรียกว่าการเรียงข้อมูลแบบกระแส และการเรียงกระแสข้อมูลอย่างไว ขั้นตอนวิธีการเรียงลำดับทั้งสองถูกพิจารณาบนข้อมูลแบบกระแสของตัวเลขจำนวนเต็มและดำเนินการบนหน่วยเก็บหน่วยความจำที่จำกัดซึ่งมีขนาดน้อยกว่าขนาดของข้อมูล ขอบเขตบนของขนาดของหน่วยเก็บหน่วยความจำสำหรับขนาดข้อมูลแบบกระแส n ถูกแสดงแล้วในงานวิจัยนี้ ขั้นตอนวิธีทั้งสองให้ความซับซ้อนเชิงเวลา O(n) และความซับซ้อนเชิงพื้นที่เท่ากับ O(M) โดยที่ M คือ ขนาดของหน่วยความจำและ M เท่ากับ n/3 ผลการทดลองชี้ว่าสองขั้นตอนวิธีที่เสนอสามารถแก้ปัญหาของข้อมูลแบบกระแสบนหน่วยเก็บหน่วยความจำที่จำกัดที่มีขนาดค่าน้อยกว่า 35% ของขนาดข้อมูลเล็กน้อย ยิ่งไปกว่านั้นความเร็วของการเรียงข้อมูลแบบกระแสอย่างไวเร็วกว่าการเรียงข้อมูลแบบกระแสประมาณ 28 เท่า
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Chaikhan, Suluk, "Internal sorting of streaming numbers constrained by limited memory size" (2020). Chulalongkorn University Theses and Dissertations (Chula ETD). 75245.
https://digital.car.chula.ac.th/chulaetd/75245