Rope data structure
algorithm
33
hardcore
17
White

huydx viết ngày 05/10/2016

Bài viết thuộc chủ đề nghiên cứu của nhóm ruby hardcore

Introduction

Vừa rồi khi lướt qua editor mới của google viết bằng Rust, gọi là xi-editor thì mình có thấy một đoạn giới thiệu

A persistent rope data structure. Persistent ropes are efficient even for very large files. In addition, they present a simple interface to their clients - conceptually, they're a sequence of characters just like a string, and the client need not be aware of any internal structure.

Khá tò mò về việc tại sao một data-structure lại giúp được một editor tăng tốc độ nên mình có tìm hiểu qua một chút về data-structure khá thú vị này.

Một cách ngắn gọn, thì Rope là một data-structure giúp bạn có thể edit (concat, insert, delete) với tốc độ nhanh và không phụ thuộc vào độ dài của string. Điều đó tương đương với việc thao tác edit trên string được cung cấp bởi các thư viện std của các ngôn ngữ sẽ là chậm, và khi string càng dài thì thao tác trên sẽ càng costly, tại sao vậy?

Lý do thao tác edit trên raw string chậm xuất phát chính từ các đặc điểm mà chúng ta "muốn" một string có như là immutable và contiguos array bytes. Do đó giả sử bạn muốn concat 2 arrays thì bạn phải copy cả 2 (cost để copy cũng không hề nhỏ, bạn thử tự viết hàm memcpy là biết :P ). Ngoài ra do string được store dưới dạng contigous array bytes thì khi bạn allocate một string lớn thì dẫn đến bạn sẽ tốn một chunk memory lớn, do đó sẽ dễ dẫn đến memory fragmentation.

Về rope

Rope có thể hiểu là một cây tìm kiếm (search tree) mà lá (leaf) sẽ là những substring của một string lớn. Những thao tác mà rope support gồm có:

  1. Fetch ith character: đưa vào một index (vị trí) i, lấy về character ở vị trí đó, thao tác này rất cần thiết để "khôi phục" nguyên gốc một string từ một rope.
  2. Concatenate two ropes: tương đương với thao tác concat string, chúng ta có thể nối 2 rope lại với nhau.
  3. Substring: tương đương với thao tác split của string thông thường
  4. Iterate over each character: thao tác này kết hợp với thao tác 1 để giúp "build" một string từ một rope

alt text

Lưu ý là cây sử dụng trong rope có thể chỉ là binary search tree, có thể là B-Tree hay là AVL tree. Với binary search tree thông thường thì bạn sẽ không có thao tác rebalance, tức là thao tác để đảm bảo là depth của tree sẽ luôn ở mức thấp nhất có thể, qua đó thao tác retrieve một character (để reach đến leaf) sẽ luôn đảm bảo ở tình huống tồi nhất cũng là O(logn)

Rope Std String
Concatenation O(1) O(n)
Substring O(1) O(1)
Retrieve character O(log n) O(1)
Retrieve all characters sequentially (cost per character) O(1) O(1)

Dưới đây là đoạn code go sử dụng binary search tree cho rope mà mình có tham khảo trên internet và thêm thắt một chút. Nhìn code bạn có thể hiểu được

  • concat chỉ đơn thuần là pointer assignment, cost là cố định
  • để retrieve được string từ rope thì sẽ rất tốn cost, string càng dài thì retrieve càng mất thời gian
package rope

import (
    "bytes"
    "encoding/json"
    "fmt"
    "unicode/utf8"
)

//Rope represents a persistent rope data structure.
type Rope struct {
    value  []rune
    weight int
    length int
    left   *Rope
    right  *Rope
}

//isLeaf returns true if the rope is a leaf.
func (rope *Rope) isLeaf() bool {
    return rope.left == nil
}

//panics if rope is nil
func (rope *Rope) panicIfNil() {
    if rope == nil {
        panic(fmt.Sprintf("Operation not permitted on empty rope"))
    }
}

//New returns a new rope initialized with given string.
func New(bootstrap string) *Rope {
    len := utf8.RuneCountInString(bootstrap)
    return &Rope{
        value:  []rune(bootstrap),
        weight: len,
        length: len}
}

//Len returns the length of the rope.
func (rope *Rope) Len() int {
    if rope == nil {
        return 0
    }
    return rope.length
}

//String returns the complete string stored in the rope.
func (rope *Rope) String() string {
    return rope.Report(1, rope.length)
}

//Internal struct for generating JSON
type ropeForJSON struct {
    Value  string
    Weight int
    Length int
    Left   *ropeForJSON
    Right  *ropeForJSON
}

//Utility function that transforms a *Rope in a *ropeForJSON.
func (rope *Rope) toRopeForJSON() *ropeForJSON {
    if rope == nil {
        return nil
    }
    return &ropeForJSON{
        Weight: rope.weight,
        Value:  string(rope.value),
        Length: rope.length,
        Left:   rope.left.toRopeForJSON(),
        Right:  rope.right.toRopeForJSON(),
    }
}

//ToJSON converts a rope to indented JSON.
func (rope *Rope) ToJSON() string {
    rope2 := rope.toRopeForJSON()
    var out bytes.Buffer
    b, _ := json.Marshal(rope2)
    json.Indent(&out, b, "", "  ")
    return string(out.Bytes())
}

//Index retrieves the rune at index.
func (rope *Rope) Index(idx int) rune {
    if idx < 1 || idx > rope.length {
        panic(fmt.Sprintf("Rope - Index out of bounds %d/%d", idx, rope.length))
    }

    if rope.isLeaf() {
        return rope.value[idx-1]
    } else if idx > rope.weight {
        return rope.right.Index(idx - rope.weight)
    } else {
        return rope.left.Index(idx)
    }
}

//Concat merges two ropes.
func (rope *Rope) Concat(other *Rope) *Rope {
    //Special case: if the first rope is nil, just return the second rope
    if rope == nil {
        return other
    }
    //Special case: if the other rope is nil, just return the first rope
    if other == nil {
        return rope
    }
    //Return a new rope with 'rope' and 'other' assigned respectively
    //to left and right subropes.
    return &Rope{
        weight: rope.Len(),
        length: rope.Len() + other.Len(),
        left:   rope,
        right:  other,
    }
}

//Internal function used by Split function.
func (rope *Rope) split(idx int, secondRope *Rope) (*Rope, *Rope) {
    //If idx is equal to rope weight, we're arrived:
    //- If is leaf, return it;
    //- Otherwise, return its left rope.
    //Right rope initialises secondRope.
    if idx == rope.weight {
        var r *Rope
        if rope.isLeaf() {
            r = rope
        } else {
            r = rope.left
        }
        return r, rope.right
    } else if idx > rope.weight {
        //We have to recurse on right side.
        newRight, secondRope := rope.right.split(idx-rope.weight, secondRope)
        return rope.left.Concat(newRight), secondRope
    } else {
        //idx < rope.weight, we recurse on the left side
        if rope.isLeaf() {
            //It's a leaf: we have to create a new rope by splitting leaf at index
            var lr *Rope
            if idx > 0 {
                lr = &Rope{
                    weight: idx,
                    value:  rope.value[0:idx],
                    length: idx,
                }
            }
            secondRope = &Rope{
                weight: len(rope.value) - idx,
                value:  rope.value[idx:len(rope.value)],
                length: len(rope.value) - idx,
            }
            return lr, secondRope
        } else {
            newLeft, secondRope := rope.left.split(idx, secondRope)
            return newLeft, secondRope.Concat(rope.right)
        }
    }
}

//Split generates two strings starting from one, splitting it at  index.
func (rope *Rope) Split(idx int) (firstRope *Rope, secondRope *Rope) {
    rope.panicIfNil()
    if idx < 0 || idx > rope.length {
        panic(fmt.Sprintf("Rope - Split out of bounds %d/%d", idx, rope.length))
    }
    //Create the slices for split
    return rope.split(idx, secondRope)
}

//Insert generates a new rope inserting a string into the original rope.
func (rope *Rope) Insert(idx int, str string) *Rope {
    if rope == nil {
        return New(str)
    }
    //Split rope at insert point
    r1, r2 := rope.Split(idx)
    //Rejoin the two split parts with string to insert as middle rope
    return r1.Concat(New(str)).Concat(r2)
}

//Delete generates a new rope by deleting from
//the original one starting at  idx.
func (rope *Rope) Delete(idx int, length int) *Rope {
    rope.panicIfNil()

    r1, r2 := rope.Split(idx - 1)
    _, r4 := r2.Split(length)
    return r1.Concat(r4)
}

//Report return a substring of the rope starting from index included.
func (rope *Rope) Report(idx int, length int) string {
    if rope == nil {
        return ""
    }
    res := make([]rune, length)
    rope.internalReport(idx, length, res)
    return string(res)
}

func (rope *Rope) internalReport(idx int, length int, res []rune) {
    //if idx > rope.weight we go right with modified idx
    if idx > rope.weight {
        rope.right.internalReport(idx-rope.weight, length, res)
    } else
    //if idx <= rope.weight we check if the left branch
    //has enough values to fetch report, else we split
    if rope.weight >= idx+length-1 {
        //we have enough space, just go left or take the string
        if rope.isLeaf() {
            //we're in a leaf, fetch from here
            copy(res, rope.value[idx-1:idx+length-1])
        } else {
            rope.left.internalReport(idx, length, res)
        }
    } else {
        //Split the work
        rope.left.internalReport(idx, rope.weight-idx+1, res[:rope.weight])
        rope.right.internalReport(1, length-rope.weight+idx-1, res[rope.weight:])
    }
}

//Substr returns part of the rope, starting at index.
func (rope *Rope) Substr(idx int, length int) *Rope {
    if idx < 1 {
        rope.Report(1, length)
    }
    if idx+length-1 > rope.length {
        rope.Report(idx, rope.length-idx+1)
    }

    _, r1 := rope.Split(idx - 1)
    r2, _ := r1.Split(length)
    return r2
}

Và đây là code để test

package rope

import "testing"

//Test rope creation
func TestRopeCreation(t *testing.T) {
    r := New("test")
    if r.String() != "test" {
        t.Error("Error creating rope - equality fail: ", r, " != test")
    }
    if r.Len() != 4 {
        t.Error("Error creating rope - length fail: ", r.Len(), "!= 4")
    }
}

//Test rope concatenation
func TestRopeConcat(t *testing.T) {
    r := New("abcdef")
    r2 := New("ghilmno")
    r3 := r.Concat(r2)
    if r.String() != "abcdef" || r.Len() != 6 {
        t.Error("Error concatenating ropes, r modified:", r)
    }
    if r2.String() != "ghilmno" || r2.Len() != 7 {
        t.Error("Error concatenating ropes, r2 modified:", r2)
    }
    if r3.String() != "abcdefghilmno" || r3.Len() != 13 {
        t.Error("Error concatenating ropes, r3 not correct:", r3, "!= abcdefghilmno")
    }
}

//Test rope split
func TestRopeSplit(t *testing.T) {
    r := New("abcdef")
    r1, r2 := r.Split(4)
    if r.String() != "abcdef" || r1.String() != "abcd" || r2.String() != "ef" {
        t.Error("Error splitting string: abcd/ef => ", r1, r2)
    }
}

//benchmark test
func BenchmarkRope_Concat(b *testing.B) {
    r1 := New("fffffffffffffffffffffffffffffff")
    r2 := New("gggggggggggggggggggggggggggggggggggggggggg")
    for i := 0; i < b.N; i++ {
        r3 := r1.Concat(r2)
        r3.String()
    }
}

func BenchmarkString_Concat(b *testing.B) {
    r1 := "fffffffffffffffffffffffffffffff"
    r2 := "gggggggggggggggggggggggggggggggggggggggggg"
    for i := 0; i < b.N; i++ {
        _ = r1 + r2
    }
}

Như vậy bạn có thể thấy để trade-off cho thao tác build toàn bộ string rất chậm thì chúng ta bị được một lợi thế là mỗi lần cần edit (concat, insert hay split) thì chúng ta có thể thực hiện với O(1) trên rope. Điều đó rất có ích khi build một editor, tại vì:

  • editor chỉ cần render "một phần" của một string lớn (cụ thể là line by line)
  • editor thường nhận vào một string rất lớn
  • editor cần thao tác concat/split/insert rất nhanh để đảm bảo sự "smooth" khi thao tác edit text từ phía user

Tham khảo:

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

116 bài viết.
942 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
148 14
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết gần 2 năm trước
148 14
White
118 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
118 15
White
95 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết 3 năm trước
95 10
Bài viết liên quan
White
10 0
Hadoop là cái gì vậy? “Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các ứng dụng phân tán có cường độ dữ liệu lớn một cách ...
nguyenduyhao1111 viết gần 2 năm trước
10 0
White
20 2
Tiếp nối phần 1 http://kipalog.com/posts/7concurrencymodelsinsevenweekphan1. Trong phần này chúng ta sẽ tiếp tục tìm hiểu về mô hình ThreadLock th...
huydx viết gần 2 năm trước
20 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
116 bài viết.
942 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!