Go语言中如何在零内存分配情况下反转字符串?

文章目录

一日午饭后散步中,同事问了一道Go相关的测试题目,是他之前面试中面试官问的一个题目,他到现在还没有找到答案。这道测试题就是本篇博文的标题:Go语言中如何在零内存分配情况下反转字符串?

Go语言中反转字符串很好处理。我们只需要将使用[]byte(string)强制将字符串转换成字节切片,然后将该字节切片中第一个字节和最后一个字节对调,第二个字节和倒数第二个字节对调,依次类推,完成整个字节切片反转后,再将字节切片转换成字符串就行了。整个反转操作的时间复杂度是O(n)。需要注意的是对于包含中文等多字节文本的字符串需要转换成[]rune类型。为了减少处理起来的复杂性,本博文就只考虑英文字符串的反转了。相关代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
func main() {
str := "hello,world"
bytes := reverse([]byte(str))
println(string(bytes))
}

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

上面处理是完成了反转字符串的目标,但是string和[]byte或[]rune类型互转时候,会进行内存分配的。至于为啥进行了内存分配可以参见本人写的电子书《深入Go语言之旅》中[]byte(string) 和 string([]byte)为什么需要进行内存拷贝?这一小节。本篇博文不再详述。

既然上面处理使用的[]byte(string)和 string([]byte)方法进行字符串和字节切片互转时候需要进行内存分配,那么有没有不进行内存分配的转换方法呢?

答案是有的。因为string和[]byte底层类型大致一样,我们可以通过非类型安全指针unsafe.Pointer进行指针类型转换,该方法是优化字符串和字节切片互转的常见手段。具体实现可以参考下面:

1
2
3
4
5
6
7
8
9
10
11
12
func bytes2string(b []byte) string{
return *(*string)(unsafe.Pointer(&b))
}

func string2bytes(s string) []byte {
return *(*[]byte)(unsafe.Pointer(
&struct {
string
Cap int
}{s, len(s)},
))
}

再接着上面的反转字符串处理,我们使用无内存分配的方式试一下,点击在线运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func main() {
str := "hello,world"
fmt.Println("原始字符串:", str)
bytes := reverse(string2bytes(str))
fmt.Println("反转字符串:", bytes2string(reverse(bytes)))
}

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

func bytes2string(b []byte) string {
return *(*string)(unsafe.Pointer(&b))
}

func string2bytes(s string) []byte {
return *(*[]byte)(unsafe.Pointer(
&struct {
string
Cap int
}{s, len(s)},
))
}

运行上面代码我们可以看到类似下面的SEGV内存错误:

1
2
3
unexpected fault address 0x461f48
fatal error: fault
[signal SIGSEGV: segmentation violation code=0x2 addr=0x461f48 pc=0x454f97]

这是因为我们直接操作的是字符底层内容,而字符串底层内容存储在的进程内存布局的.rodata段(准确说应该是data段中.rodata节)中,该段是只读的。我们反转字符时候,会进行写入操作,故运行时会报出上面的段错误提示,这也是Go中字符串只读的原因。字符串的底层结构如下:

一路下来貌似无法做到在零内存分配情况下反转字符串。其实只需要改变上面字符底层内容所在内存的权限,让它可写就行了。Linux中提供了mprotect系统调用,可以用来更改进程内存页的读写权限。需要注意的mprotect操作的最小单位是内存页,传入的地址参数需要以页边界对齐。最后代码如下,点击在线运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func main() {
str := "hello,world"

sh := *(*reflect.StringHeader)(unsafe.Pointer(&str))
page := getPage(uintptr(unsafe.Pointer(sh.Data)))
syscall.Mprotect(page, syscall.PROT_READ|syscall.PROT_WRITE) // 改变内存页的只读权限

fmt.Println("原始字符串:", str)
bytes := (*(*[0xFF]byte)(unsafe.Pointer(sh.Data)))[:len(str)]
fmt.Println("反转字符串:", bytes2string(reverse(bytes)))
}

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

func getPage(p uintptr) []byte {
return (*(*[0xFFFFFF]byte)(unsafe.Pointer(p & ^uintptr(syscall.Getpagesize()-1))))[:syscall.Getpagesize()]
}

func bytes2string(b []byte) string {
return *(*string)(unsafe.Pointer(&b))
}

func string2bytes(s string) []byte {
return *(*[]byte)(unsafe.Pointer(
&struct {
string
Cap int
}{s, len(s)},
))
}

至此任务完成。需要注意的是上面代码中使用到固定大小的数组,不是非常完美的解决方案。