โร้ป

ตัวอย่างการเก็บคำว่า‘The quick brown fox’ในโร้ป

ตัวอย่างการทำ‘abcdef’ให้สมดุล

ในการเขียนโปรแกรมคอมพิวเตอร์นั้น โร้ป (อังกฤษ: 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)

กราฟแสดงประสิทธิภาพของโร้ป

กราฟแสดงเวลาที่ใช้ในการต่อสายอักขระ

กราฟแสดงเวลาที่ใช้ในการสร้างสายอักขระ

กราฟแสดงเวลาที่ใช้ในการท่องสายอักขระ

อ้างอิง

1. 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2007-02-25. สืบค้นเมื่อ 2011-02-21. {{cite journal}}: ไม่รู้จักพารามิเตอร์ |coauthors= ถูกละเว้น แนะนำ (|author=) (help)

แหล่งข้อมูลอื่น

• SGI's implementation of ropes for C++
• libstdc++ support for ropes
• Ropes for Java
• Ropes เก็บถาวร 2011-07-27 ที่ เวย์แบ็กแมชชีน for Ocaml