โร้ป

ในการเขียนโปรแกรมคอมพิวเตอร์นั้น โร้ป (; แปลเป็นภาษาไทยว่า เชือก) จัดเป็นโครงสร้างข้อมูลชนิดหนึ่งที่ใช้ในการจัดเก็บข้อมูลประเภท สตริง (string) และมีประสิทธิภาพสูงในการใช้งานแทนที่สตริง แต่เป็นสตริงที่มีขนาดที่ใหญ่กว่าสตริงทั่วไปในบางครั้งจึงเรียกว่า Heavyweight String โดยจะใช้ต้นไม้แบบทวิภาคในการเก็บข้อมูลที่เป็นแถวลำดับของสายข้อความ โดยหลักการของโร้ปนั้นได้ถูกนำเสนอไว้ในบทความทางวิชาการที่ชื่อว่า "Ropes: an Alternative to Strings".

โดยโร้ปนั้นได้ให้ประสิทธิภาพการทำงานที่ดีกว่าทั้ง สตริง และ สตริงบัฟเฟอร์ สำหรับการใช้งานในการแก้ไขสตริงทั่วไป เช่น การเชิ่อมสตริง, ลบสตริง, แทรกสตริง เป็นต้น อีกทั้งโร้ปจะไม่เปลี่ยนรูป ดังนั้นจึงเหมาะสำหรับใช้ในการเขียนโปรแกรมที่มีการทำงานแบบมัลติเทร็ด

การเปรียบเทียบโร้ปกับสตริงแบบอาเรย์ปกติ

ในตารางต่อไปนี้จะเป็นการแสดงให้เห็นและเปรียบเทียบถึงลักษณะการทำงานของอัลกอลิธึมของสตริงและโร้ป แต่การที่สตริงแบบปกติมีขนาดโอเวอร์เฮดที่เล็กกว่าโร้ป ดังนั้นการทำงานบางคำสั่งโดยที่สตริงและโร้ปมีขนาดเล็กๆ นั้นสตริงอาจทำได้เร็วการโร้ป แต่โดยทั่วไปแล้วถ้าสายข้อความมีขนาดใหญ่โร้ปมักจะมีการทำงานที่เร็วกว่าสตริง
  คำสั่ง      ประสิทธิภาพของโร้ป     ประสิทธิภาพของสตริง
   concatenation       O(n)
   substring        O(n) 
   indexing       O(log n)          
   iteration      O(n)               O(n)


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

ไฟล์:Rope4.PNG

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

Rope5.PNG

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

Rope6.PNG

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

อ้างอิง

แหล่งข้อมูลอื่น
 SGI's implementation of ropes for C++
 libstdc++ support for ropes
 Ropes for Java
 Ropes  for Ocaml

หมวดหมู่:ต้นไม้แบบทวิภาค
หมวดหมู่:โครงสร้างข้อมูลสายอักขระ