31

高效截取字符串的一些思考

 4 years ago
source link: https://www.tuicool.com/articles/rArQBvN
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

原文链接： https://blog.thinkeridea.com/...

最近我在 Go Forum 中发现了 String size of 20 character 的问题，“ hollowaykeanho ” 给出了相关的答案，而我从中发现了截取字符串的方案并非最理想的方法，因此做了一系列实验并获得高效截取字符串的方法，这篇文章将逐步讲解我实践的过程。

字节切片截取

这正是 “ hollowaykeanho ” 给出的第一个方案，我想也是很多人想到的第一个方案，利用 go 的内置切片语法截取字符串： 

s := "abcdef"
fmt.Println(s[1:4])

我们很快就了解到这是按字节截取，在处理 ASCII 单字节字符串截取，没有什么比这更完美的方案了，中文往往占多个字节，在 utf8 编码中是3个字节，如下程序我们将获得乱码数据： 

s := "Go 语言"
fmt.Println(s[1:4])

杀手锏 - 类型转换 []rune

“ hollowaykeanho ” 给出的第二个方案就是将字符串转换为 []rune ，然后按切片语法截取，再把结果转成字符串。 

s := "Go 语言"
rs := []rune(s)
fmt.Println(strings(rs[1:4]))

首先我们得到了正确的结果，这是最大的进步。不过我对类型转换一直比较谨慎，我担心它的性能问题，因此我尝试在搜索引擎和各大论坛查找答案，但是我得到最多的还是这个方案，似乎这已经是唯一的解。

我尝试写个性能测试评测它的性能：

package benchmark

import (
    "testing"
)

var benchmarkSubString = "Go语言是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的编程语言。为了方便搜索和识别，有时会将其称为Golang。"
var benchmarkSubStringLength = 20

func SubStrRunes(s string, length int) string {
    if utf8.RuneCountInString(s) > length {
        rs := []rune(s)
        return string(rs[:length])
    }

    return s
}

func BenchmarkSubStrRunes(b *testing.B) {
    for i := 0; i < b.N; i++ {
        SubStrRunes(benchmarkSubString, benchmarkSubStringLength)
    }
}

我得到了让我有些吃惊的结果：

goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark
BenchmarkSubStrRunes-8            872253              1363 ns/op             336 B/op          2 allocs/op
PASS
ok      github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark     2.120s

对 69 个的字符串截取前 20 个字符需要大概 1.3 微秒，这极大的超出了我的心里预期，我发现因为类型转换带来了内存分配，这产生了一个新的字符串，并且类型转换需要大量的计算。

救命稻草 - utf8.DecodeRuneInString

我想改善类型转换带来的额外运算和内存分配，我仔细的梳理了一遍 strings 包，发现并没有相关的工具，这时我想到了 utf8 包，它提供了多字节计算相关的工具，实话说我对它并不熟悉，或者说没有主动（直接）使用过它，我查看了它所有的文档发现 utf8.DecodeRuneInString 函数可以转换单个字符，并给出字符占用字节的数量，我尝试了如此下的实验： 

package benchmark

import (
    "testing"
    "unicode/utf8"
)

var benchmarkSubString = "Go语言是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的编程语言。为了方便搜索和识别，有时会将其称为Golang。"
var benchmarkSubStringLength = 20

func SubStrDecodeRuneInString(s string, length int) string {
    var size, n int
    for i := 0; i < length && n < len(s); i++ {
        _, size = utf8.DecodeRuneInString(s[n:])
        n += size
    }

    return s[:n]
}

func BenchmarkSubStrDecodeRuneInString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        SubStrDecodeRuneInString(benchmarkSubString, benchmarkSubStringLength)
    }
}

运行它之后我得到了令我惊喜的结果：

goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark
BenchmarkSubStrDecodeRuneInString-8     10774401               105 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark     1.250s

较 []rune 类型转换效率提升了 13倍 ，消除了内存分配，它的确令人激动和兴奋，我迫不及待的回复了 “ hollowaykeanho ” 告诉他我发现了一个更好的方法，并提供了相关的性能测试。

我有些小激动，兴奋的浏览着论坛里各种有趣的问题，在查看一个问题的帮助时 (忘记是哪个问题了-_-||) ，我惊奇的发现了另一个思路。

良药不一定苦 - range 字符串迭代

许多人似乎遗忘了 range 是按字符迭代的，并非字节。使用 range 迭代字符串时返回字符起始索引和对应的字符，我立刻尝试利用这个特性编写了如下用例： 

package benchmark

import (
    "testing"
)

var benchmarkSubString = "Go语言是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的编程语言。为了方便搜索和识别，有时会将其称为Golang。"
var benchmarkSubStringLength = 20

func SubStrRange(s string, length int) string {
    var n, i int
    for i = range s {
        if n == length {
            break
        }

        n++
    }

    return s[:i]
}

func BenchmarkSubStrRange(b *testing.B) {
    for i := 0; i < b.N; i++ {
        SubStrRange(benchmarkSubString, benchmarkSubStringLength)
    }
}

我尝试运行它，这似乎有着无穷的魔力，结果并没有令我失望。

goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark
BenchmarkSubStrRange-8          12354991                91.3 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark     1.233s

它仅仅提升了13%，但它足够的简单和易于理解，这似乎就是我苦苦寻找的那味良药。

如果你以为这就结束了，不、这对我来只是探索的开始。

终极时刻 - 自己造轮子

喝了 range 那碗甜的腻人的良药，我似乎冷静下来了，我需要造一个轮子，它需要更易用，更高效。

于是乎我仔细观察了两个优化方案，它们似乎都是为了查找截取指定长度字符的索引位置，如果我可以提供一个这样的方法，是否就可以提供用户一个简单的截取实现 s[:strIndex(20)] ，这个想法萌芽之后我就无法再度摆脱，我苦苦思索两天来如何来提供易于使用的接口。

之后我创造了 exutf8.RuneIndexInString 和 exutf8.RuneIndex 方法，分别用来计算字符串和字节切片中指定字符数量结束的索引位置。

我用 exutf8.RuneIndexInString 实现了一个字符串截取测试： 

package benchmark

import (
    "testing"
    "unicode/utf8"

    "github.com/thinkeridea/go-extend/exunicode/exutf8"
)

var benchmarkSubString = "Go语言是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的编程语言。为了方便搜索和识别，有时会将其称为Golang。"
var benchmarkSubStringLength = 20

func SubStrRuneIndexInString(s string, length int) string {
    n, _ := exutf8.RuneIndexInString(s, length)
    return s[:n]
}

func BenchmarkSubStrRuneIndexInString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        SubStrRuneIndexInString(benchmarkSubString, benchmarkSubStringLength)
    }
}

尝试运行它，我对结果感到十分欣慰：

goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark
BenchmarkSubStrRuneIndexInString-8      13546849                82.4 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark     1.213s

性能较 range 提升了 10%，让我很欣慰可以再次获得新的提升，这证明它是有效的。

它足够的高效，但是却不够易用，我截取字符串需要两行代码，如果我想截取 10~20之间的字符就需要4行代码，这并不是用户易于使用的接口，我参考了其它语言的 sub_string 方法，我想我应该也设计一个这个样的接口给用户。

exutf8.RuneSubString 和 exutf8.RuneSub 是我认真思索后编写的方法：

func RuneSubString(s string, start, length int) string

它有三个参数：

s
start
length

我为他们提供了别名，根据使用习惯大家更倾向去 strings 包寻找这类问题的解决方法，我创建了 exstrings.SubString 和 exbytes.Sub 作为更易检索到的别名方法。

最后我需要再做一个性能测试，确保它的性能：

package benchmark

import (
    "testing"

    "github.com/thinkeridea/go-extend/exunicode/exutf8"
)

var benchmarkSubString = "Go语言是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的编程语言。为了方便搜索和识别，有时会将其称为Golang。"
var benchmarkSubStringLength = 20

func SubStrRuneSubString(s string, length int) string {
    return exutf8.RuneSubString(s, 0, length)
}

func BenchmarkSubStrRuneSubString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        SubStrRuneSubString(benchmarkSubString, benchmarkSubStringLength)
    }
}

运行它，不会让我失望：

goos: darwin
goarch: amd64
pkg: github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark
BenchmarkSubStrRuneSubString-8          13309082                83.9 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/thinkeridea/go-extend/exunicode/exutf8/benchmark     1.215s

虽然相较 exutf8.RuneIndexInString 有所下降，但它提供了易于交互和使用的接口，我认为这应该是最实用的方案，如果你追求极致仍然可以使用 exutf8.RuneIndexInString ，它依然是最快的方案。

总结

当看到有疑问的代码，即使它十分的简单，依然值得深究，并不停的探索它，这并不枯燥和乏味，反而会有极多收获。

从起初 []rune 类型转换到最后自己造轮子，不仅得到了 16倍 的性能提升，我还学习了 utf8 包、加深了 range 遍历字符串的特性 以及为 go-extend 仓库收录了多个实用高效的解决方案，让更多 go-extend 的用户得到成果。

go-extend 是一个收录实用、高效方法的仓库，读者们如果好的函数和通用高效的解决方案，期待你们不吝啬给我发送 Pull request ，你也可以使用这个仓库加快功能实现及提升性能。

转载：

本文作者： 戚银（ thinkeridea ）

本文链接： https://blog.thinkeridea.com/201910/go/efficient_string_truncation.html

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK