【译文】原文地址
我最近一直在用空闲时间来解决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，您的生产应用程序可能运行的很慢，会失去许多优化和语言优势。
有疑问加站长微信联系（非本文作者）
