UTF-8符号化文字列の反転

UTF-8で符号化された文字列の文字要素を反転させるreverse関数を実現します.入力されるパラメータは、文字列に対応するバイトスライスタイプ([]byte)です.

シンプルな実装

まず,効率を考慮せずに,まず簡単な論理で実現する.スライスの反転方法は次のとおりです.

func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

データを文字スライスに変換し、スライスで反転したコードをセットすればいいです.

//  ， ， 
func reverse_rune(slice []byte) {
    r := []rune(string(slice))
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    for i := range slice {
        slice[i] = []byte(string(r))[i]
    }
}

この方法は論理がはっきりしていて,後でランダムテストをするのに適している.

その場で反転

次の関数は、その場で反転します.最初の文字を読み込むたびに、最後のフラグビットの前の文字列を先頭に移動し、前に読んだ文字をフラグビットの位置に配置し、フラグビットを前に移動します.

func reverse_byte(slice []byte) {
    for l := len(slice); l > 0; {
        r, size := utf8.DecodeRuneInString(string(slice[0:]))
        copy(slice[0:l], slice[0+size:l])
        copy(slice[l-size:l], []byte(string(r)))
        l -= size
    }
}

この実現効率はまだ少し悪いので、後でテストして比較します.

効率的なその場での反転

次の関数は、多くのフラグビットを使用して、効率的なその場反転を実現します.

func reverse(s []byte) {
    var (
        lRd, rRd           int  //  
        lWr, rWr           int  //  
        lHasRune, rHasRune bool //  
        lr, rr             rune //  
        lsize, rsize       int  //  
    )
    rRd, rWr = len(s), len(s)
    for lRd < rRd {
        if !lHasRune {
            lr, lsize = utf8.DecodeRune(s[lRd:])
            lRd += lsize
            lHasRune = true
        }
        if !rHasRune {
            rr, rsize = utf8.DecodeLastRune(s[:rRd])
            rRd -= rsize
            rHasRune = true
        }

        if lsize <= rWr-rRd {
            utf8.EncodeRune(s[rWr-lsize:], lr)
            rWr -= lsize
            lHasRune = false
        }
        if rsize <= lRd-lWr {
            utf8.EncodeRune(s[lWr:], rr)
            lWr += rsize
            rHasRune = false
        }
    }

    //  
    if lHasRune {
        utf8.EncodeRune(s[rWr-lsize:], lr)
    }
    if rHasRune {
        utf8.EncodeRune(s[lWr:], rr)
    }
}

テスト検証

次はテストコードで、上の関数の正確性と効率を検証します.

機能テスト

表ベースのテストは直感的で簡単で、より多くのテスト例を簡単に追加できます.

var tests = []struct {
    input string
    want string
}{
    {"abc", "cba"},
    {"123", "321"},
    {" ， !", "! ， "},
    {"a , . ,z", "z, . , a"},
}

func TestReverse_rune(t *testing.T) {
    for _, test := range tests {
        s := []byte(test.input)
        reverse_rune(s)
        if string(s) != test.want {
            t.Errorf("reverse(%q) = %q, want %q
", test.input, string(s), test.want)
        }
    }
}

func TestReverse_byte(t *testing.T) {
    for _, test := range tests {
        s := []byte(test.input)
        reverse_byte(s)
        if string(s) != test.want {
            t.Errorf("reverse(%q) = %q, want %q
", test.input, string(s), test.want)
        }
    }
}

func TestReverse(t *testing.T) {
    for _, test := range tests {
        s := []byte(test.input)
        reverse(s)
        if string(s) != test.want {
            t.Errorf("reverse(%q) = %q, want %q
", test.input, string(s), test.want)
        }
    }
}

テスト結果:

PS H:\Go\src\gopl\exercise4\e7> go test -run TestReverse -v
=== RUN   TestReverse_rune
--- PASS: TestReverse_rune (0.00s)
=== RUN   TestReverse_byte
--- PASS: TestReverse_byte (0.00s)
=== RUN   TestReverse
--- PASS: TestReverse (0.00s)
PASS
ok      gopl/exercise4/e7       0.263s
PS H:\Go\src\gopl\exercise4\e7>

ランダムテスト

ランダムテストも機能テストの一種であり、ランダム入力を構築することでテストのカバー範囲を拡張します.2つのポリシーがあります.

は、非効率だが明確なアルゴリズムを使用する関数を追加し、2つの実装の出力が一致しているかどうかを確認します.

は、あるパターンに合致する入力を構築し、対応する出力を知ることができる.

次は、最初のポリシーで書かれたランダムテストです.出力内容をより読みやすくするために、おなじみの文字を選択してランダム文字を生成します.

// randomSte  ， 
func randomStr(rng *rand.Rand) string {
    n := rng.Intn(25) //  24
    runes := make([]rune, n)
    for i := 0; i < n; i++ {
        var r rune
        switch rune(rng.Intn(6)) {
        case 0: // ASCII  ，1 
            r = rune(rng.Intn(0x4B) + 0x30)
        case 1: //  ，2 
            r = rune(rng.Intn(57) + 0x391)
        case 2: //  
            r = rune(rng.Intn(0xBF) + 0x3041)
        case 3: //  
            r = rune(rng.Intn(0x2BA4) + 0xAC00)
        case 4, 5, 6: //  
            r = rune(rng.Intn(0x4E00) + 0x51D6)
        }
        runes[i] = r
    }
    return string(runes)
}

func TestRandomReverse(t *testing.T) {
    seed := time.Now().UTC().UnixNano()
    t.Logf("Random seed: %d", seed)
    rng := rand.New(rand.NewSource(seed))
    for i := 0; i < 1000; i++ {
        test := randomStr(rng)
        s1 := []byte(test)
        reverse_rune(s1)
        t.Logf("%s => %s
", test, string(s1))

        s2 := []byte(test)
        reverse_byte(s2)
        if string(s1) != string(s2) {
            t.Errorf("reverse_byte(%q) = %q, want %q
", test, string(s2), string(s1))
        }

        s3 := []byte(test)
        reverse(s3)
        if string(s1) != string(s3) {
            t.Errorf("reverse_byte(%q) = %q, want %q
", test, string(s3), string(s1))
        }
    }
}

テスト結果:

PS H:\Go\src\gopl\exercise4\e7> go test -run Random
PASS
ok      gopl/exercise4/e7       0.298s
PS H:\Go\src\gopl\exercise4\e7>

-vパラメータを追加して、詳細なテストログを表示することもできます.

データムテスト

ベンチマークテストも特にありません.機能テストのテスト例を全部走ってください.

func BenchmarkReverse(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, test := range tests {
            reverse([]byte(test.input))
        }
    }
}

func BenchmarkReverse_rune(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, test := range tests {
            reverse_rune([]byte(test.input))
        }   }
}

func BenchmarkReverse_byte(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, test := range tests {
            reverse_byte([]byte(test.input))
        }   }
}

テスト結果:

PS H:\Go\src\gopl\exercise4\e7> go test -benchmem -bench .
goos: windows
goarch: amd64
pkg: gopl/exercise4/e7
BenchmarkReverse-8               5000000               286 ns/op               0 B/op          0 allocs/op
BenchmarkReverse_rune-8           500000              3610 ns/op               0 B/op          0 allocs/op
BenchmarkReverse_byte-8          3000000               583 ns/op               0 B/op          0 allocs/op
PASS
ok      gopl/exercise4/e7       6.226s
PS H:\Go\src\gopl\exercise4\e7>