Go：创建高性能的字符串

【译文】 原文地址

我最近一直在用空闲时间来解决LeetCode中的问题，我认为这是一个锻炼Golang的机会，并使用Go作为练习LeetCode的主要语言。Go是一种令人惊叹的编程语言，我从根本上赞同go语言的设计，即一种和C语言一样高性能。而且和JavaScript和Python这些脚本语言一样高效和易于编程。我建议你有机会也学习和尝试下。是的，我非常喜欢Go。

下面回到我LeetCode问题： leetcode 1249 ，该问题要求删除最少数量的圆括号，直到字符串达到平衡，即字母加上有效圆括号。首先，该问题解决方法需要构建一组需要删除圆括号的索引，然后循环遍历字符串的每个字符，并构建一个新的包含所需的有效字符的字符串（减去无效的圆括号）。

因此我解决了这个问题，但是总觉得有些不对劲。我的运行时间是824ms，击败了大约25.29%的Go提交者。我在想Go不是应该很快的吗？这也是我学习这门语言的原因。我知道我的方案已经优化了的，因为我验证了作者的解决方法，因此应该不是算法的原因，尽管有一点也不是最根本原因。

后来我用JavaScript重写了这个问题，看看运行效果如何。令我惊讶的是，在这个问题上JavaScript比Golang运行速度快了9倍。等等，什么？感觉不对。这时我开始进一步调查原因。我再次运行了这个问题的程序看是否是编译错误或其他原因，但不是Golang还是比JavaScript慢9倍。

Golang代码：

package main

import (
   "fmt"
)

func minRemoveToMakeValid(s string) string {

   stack := make([]int, 0)
   toRemove := make([]int, 0)

   for i := 0; i < len(s); i++ {

      if string(s[i]) == "(" {
         stack = append(stack, i)
      }else if string(s[i]) == ")" && len(stack) == 0 {
         toRemove = append(toRemove, i)
      } else if string(s[i]) == ")" && len(stack) > 0 {
         stack = stack[:len(stack) - 1]
      }
   }

   newString := ""
   toRemove = append(toRemove, stack...)

   removeMap := make(map[int]bool)

   for i:=0; i<len(toRemove); i++ {
      removeMap[toRemove[i]] = true
   }

   for i := 0; i < len(s); i++ {
      if !removeMap[i] {
         newString += string(s[i])
      }
   }

   return newString
}

func main() {
   s:= minRemoveToMakeValid("lee(t(c)o)de)")
   fmt.Println(s)
}

JavaScript代码：

/**
 * @param {string} s
 * @return {string}
 */
const minRemoveToMakeValid = (s) => {
    let stack = [];
    let toRemove = [];
    let stringOut = ""

    for(let i=0; i< s.length;i++){
        if(s[i] === "("){
            stack.push(i)
        }else if(s[i] === ")" && stack.length === 0){
            toRemove.push(i)

        }else if(s[i] === ")" && stack.length > 0){
            stack.pop();
        }
    }

    toRemove = toRemove.concat(stack)
    let removeMap = {}

    for(let i = 0; i<toRemove.length; i++){
        removeMap[toRemove[i]] = true
    }

    for(let i=0; i< s.length;i++){
        if(!removeMap[i]){
            stringOut+=s[i]
        }
    }

    return stringOut
};

console.log(minRemoveToMakeValid("lee(t(c)o)de)"));

正如你所看到的，以上两种代码几乎是相同的，所以这并不是js代码有特殊的优化。JS只是重写了go代码，两种方法应该是可比较的，而不是快这么多。

我在网上对这个问题进一步研究，我发现Golang字符串string对象是不可变的，运行时对字符串截取部分或者增加新的字符到字符串常量，Go都会创建新的string对象并拷贝。

让我们看看那些非常低效的字符串代码：

newString := ""
newString += string(s[i])
for(let i=0; i< s.length;i++){
    if(!removeMap[i]){
        stringOut+=s[i]
    }
}

在JavaScript中，字符串常量的创建是非常常用的，因此初始化空字符串并添加字符到字符串是有优化过的。但是Golang字符串是不可变的，所以每次添加字符到字符串变量，Go都会创建一个字符串的拷贝，这从内存和运行的角度来看都是很低效的。

在Golang中，如果你想创建一个字符串，需要使用strings包。Builder类型是bytes.Buffer的一个子集。Golang将字符串视为字节切片，其中每个字节都是字符串中字符的ASCII码。如果您想在内存和运行时上高效地对字符串进行操作，就需要使用byte buffer或者更高级的字符串结构体。

因此，我继续优化之前的Go代码：

// --- Initialize the string builder
var b strings.Builder
b.Grow(len(s) - len(toRemove))
// --- Write bytes in the bytes buffer
for i := 0; i < len(s); i++ {
   if !removeMap[i] {
      b.Write([]byte{s[i]})
   }
}

在我解决了这个优化的问题后，我再次提交我的解决方案，令我惊讶的是：

通过这个小小的优化，我可以使我的Golang程序运行速度提高80倍。同样，我的程序比最初的版本快80被，比JavaScript版本的快9倍。这下验证了我当初的信念Go确实是一门快速的编程语言。

因此，对刚刚接触Golang的程序员来说，清楚这类细节，因为如果不正确使用Go，您的生产应用程序可能运行的很慢，会失去许多优化和语言优势。

有疑问加站长微信联系（非本文作者）