【Go】高效截取字元串的一些思考

2019 年 10 月 31 日
筆記

原文鏈接：https://blog.thinkeridea.com/201910/go/efficient_string_truncation.html

最近我在 Go Forum 中發現了 [SOLVED] 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 : 開始截取的位置，如果 start 是非負數，返回的字元串將從 string 的 start 位置開始，從 0 開始計算。例如，在字元串「abcdef」中，在位置 0 的字元是「a」，位置 2 的字元串是「c」等等。如果 start 是負數，返回的字元串將從 string 結尾處向前數第 start 個字元開始。如果 string 的長度小於 start，將返回空字元串。
length：截取的長度，如果提供了正數的 length，返回的字元串將從 start 處開始最多包括 length 個字元（取決於 string 的長度）。如果提供了負數的 length，那麼 string 末尾處的 length 個字元將會被省略（若 start 是負數則從字元串尾部算起）。如果 start 不在這段文本中，那麼將返回空字元串。如果提供了值為 0 的 length，返回的子字元串將從 start 位置開始直到字元串結尾。

我為他們提供了別名，根據使用習慣大家更傾向去 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