ผลต่างระหว่างรุ่นของ "โร้ป"
Nullzerobot (คุย | ส่วนร่วม) ล ลบลิงก์ที่ซ้ำซ้อน wikidata |
|||
| บรรทัด 68: | บรรทัด 68: | ||
[[หมวดหมู่:โครงสร้างข้อมูลสายอักขระ]] |
[[หมวดหมู่:โครงสร้างข้อมูลสายอักขระ]] |
||
{{โครงสร้างข้อมูล}} |
{{โครงสร้างข้อมูล}} |
||
[[en:Rope (data structure)]] |
|||
[[fr:Corde (informatique)]] |
|||
รุ่นแก้ไขเมื่อ 22:59, 10 มีนาคม 2556
ในการเขียนโปรแกรมคอมพิวเตอร์นั้น โร้ป (อังกฤษ: Rope; แปลเป็นภาษาไทยว่า เชือก) จัดเป็นโครงสร้างข้อมูลชนิดหนึ่งที่ใช้ในการจัดเก็บข้อมูลประเภท สตริง (string) และมีประสิทธิภาพสูงในการใช้งานแทนที่สตริง แต่เป็นสตริงที่มีขนาดที่ใหญ่กว่าสตริงทั่วไปในบางครั้งจึงเรียกว่า Heavyweight String โดยจะใช้ต้นไม้ค้นหาแบบทวิภาคในการเก็บข้อมูลที่เป็นอาเรย์ของสายข้อความ โดยหลักการของโร้ปนั้นได้ถูกนำเสนอไว้ในบทความทางวิชาการที่ชื่อว่า "Ropes: an Alternative to Strings".[1]
โดยโร้ปนั้นได้ให้ประสิทธิภาพการทำงานที่ดีกว่าทั้ง สตริง และ สตริงบัฟเฟอร์ สำหรับการใช้งานในการแก้ไขสตริงทั่วไป เช่น การเชิ่อมสตริง, ลบสตริง, แทรกสตริง เป็นต้น อีกทั้งโร้ปจะไม่เปลี่ยนรูปและดังนั้นจึงเหมาะสำหรับใช้ในการเขียนโปรแกรมที่มีการทำงานแบบมัลติเทร็ด
การเปรียบเทียบโร้ปกับสตริงแบบอาเรย์ปกติ
ในตารางต่อไปนี้จะเป็นการแสดงให้เห็นและเปรียบเทียบถึงลักษณะการทำงานของอัลกอลิธึมของสตริงและโร้ป แต่การที่สตริงแบบปกติมีขนาดโอเวอร์เฮดที่เล็กกว่าโร้ป ดังนั้นการทำงานบางคำสั่งโดยที่สตริงและโร้ปมีขนาดเล็กๆนั้นสตริงอาจทำได้เร็วการโร้ป แต่โดยทั่วไปแล้วถ้าสายข้อความถ้ามีขนาดใหญ่โร้ปมักจะมีการทำงานที่เร็วกว่าสตริง
| คำสั่ง | ประสิทธิภาพของโร้ป | ประสิทธิภาพของสตริง |
|---|---|---|
| concatenation | O(1) | O(n) |
| substring | O(log n) | O(n) |
| indexing | O(log n) | O(1) |
| iteration | O(n) | O(n) |
กราฟแสดงประสิทธิภาพของโร้ป
กราฟแสดงเวลาที่ใช้ในการต่อสายอักขระ
กราฟแสดงเวลาที่ใช้ในการสร้างสายอักขระ
กราฟแสดงเวลาที่ใช้ในการท่องสายอักขระ
อ้างอิง
- ↑
Boehm, Hans-J (December 1995). "Ropes: an Alternative to Strings" (PDF). Software—Practice & Experience. New York, NY, USA: John Wiley & Sons, Inc. 25 (12): 1315–1330. doi:10.1002/spe.4380251203.
{{cite journal}}: ไม่รู้จักพารามิเตอร์|coauthors=ถูกละเว้น แนะนำ (|author=) (help)