英文:
Does this Go method "allocate new memory"?
问题
我正在使用Donovan和Kernighan的《Go语言程序设计》(The Go Programming Language)学习Go。对于其他人来说,这个问题的答案可能显而易见,但我被困住了,不知道从哪里开始。
作为《GOPL》的练习,作者要求读者修改他们的reverse
程序(用于原地反转一个int
切片),以便“原地反转表示UTF-8编码字符串的[]byte
切片的字符”(93页)。他们补充说:“你能在不分配新内存的情况下完成吗?”
简而言之,我想问一下下面的代码是否会分配新的内存。根据打印语句的结果,我认为不会,但我不确定。另一种表达我的困惑的方式是:如果reverse
方法是原地反转的,我希望它不会分配新的内存。所以,我假设我一定漏掉了什么,因为他们要求该方法在原地工作,然后增加了不分配新内存的挑战。他们是在暗示我避免了我已经做过的某些事情吗?在内存分配方面是否有一些额外的技巧(无论是在Go中还是在一般情况下)?
以下是要翻译的代码:
package main
import (
"fmt"
"unicode/utf8"
)
func main() {
phrase := "Hello, 世界!"
fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
phrase = string(reverseByRune([]byte(phrase)))
fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
}
func reverseByRune(b []byte) []byte {
for i := 0; i < len(b); {
_, size := utf8.DecodeRune(b[i:])
reverse(b[i : i+size])
i += size
}
reverse(b)
return b
}
func reverse(b []byte) []byte {
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return b
}
你可以在Go Playground上查看它:https://play.golang.org/p/Qn7nYXLGoQn。
PS:我只能点赞和接受一次,但如果有人想要额外的感谢,我很乐意获得有关内存分配的任何链接(尤其是关于Go语言的)。
英文:
(I'm learning Go using Donovan and Kernighan's The Go Programming Language. The answer to this will probably be painfully obvious to others, but I'm stumped and not sure where to begin.)
As an exercise in GOPL, the authors ask the reader to modify their reverse
program (which reverses a slice of int
s in place) "to reverse the characters of a []byte
slice that represents a UTF-8 encoded string, in place" (93). They add: "Can you do it without allocating new memory?"
In a nutshell, I want to ask whether the following allocates new memory. I think that it doesn't, based on the outcome of the print statements, but I'm not sure. Another way to put my confusion is this: if the reverse
method reverses in place, I would expect it not to allocate new memory. So, I'm assuming that I must be missing something because they ask for the method to work in place and then add the challenge of not allocating new memory. Are they nudging me to avoid something I've done? Is there some extra trick here worth knowing about memory allocation (in Go or in general)?
package main
import (
"fmt"
"unicode/utf8"
)
func main() {
phrase := "Hello, 世界!"
fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
phrase = string(reverseByRune([]byte(phrase)))
fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
}
func reverseByRune(b []byte) []byte {
for i := 0; i < len(b); {
_, size := utf8.DecodeRune(b[i:])
reverse(b[i : i+size])
i += size
}
reverse(b)
return b
}
func reverse(b []byte) []byte {
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return b
}
Here it is on the Go Playground: https://play.golang.org/p/Qn7nYXLGoQn.
PS I can only upvote and accept once, but if anyone wants extra thanks, I'd love any links about memory allocation (especially in Go).
答案1
得分: 1
编辑: 可能问题中的实现也没有在堆上分配内存,但建议的修改仍然应该更高效一点。我最初以为问题中的代码来自书籍,并且有我无法检查的内存分配,因为没有本地编译器。
这是我认为应该没有内存分配的实现。
package main
import (
"fmt"
"unicode/utf8"
)
func main() {
phrase := "Hello, 世界!"
fmt.Printf("反转前:内存地址 %p => phrase: %s\n", &phrase, phrase)
phrase = string(reverseByRune([]byte(phrase)))
fmt.Printf("反转后:内存地址 %p => phrase: %s\n", &phrase, phrase)
}
func reverseByRune(b []byte) []byte {
reverse := func(i, j int) {
for ; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
}
for i := 0; i < len(b); {
_, size := utf8.DecodeRune(b[i:])
reverse(i, i+size-1)
i += size
}
reverse(0, len(b)-1)
return b
}
reverse()
的原始实现需要内存来创建 b []byte
切片,并且不必要地返回一个值。尽管理论上可以通过从 reverse
中删除 return
来进行优化。然后编译器可以“猜测”没有人可以保留对切片的指针,并确保切片在堆栈上创建而不是堆上。但这只是理论推测-我不确定 Go 的编译器是否那么聪明。
建议的实现与原始实现相同,但在原始切片内部进行操作。
当我们谈论“无内存分配”时,通常是指在函数内部发生的情况,即 reverseByRune()
。在堆栈上分配的局部变量,如 i
和 j
,不计算在内,因为它们是廉价的。
以下是给定方法可能是最高效的实现:
package main
import (
"fmt"
"unicode/utf8"
)
func main() {
phrase := []byte("Hello, 世界!")
fmt.Printf("反转前:内存地址 %p => phrase: %s\n", &phrase, string(phrase))
reverseByRune(phrase)
fmt.Printf("反转后:内存地址 %p => phrase: %s\n", &phrase, string(phrase))
}
func reverseByRune(b []byte) {
for i := 0; i < len(b); {
_, size := utf8.DecodeRune(b[i:])
for k, p := i, i+size-1; k < p; k, p = k+1, p-1 {
b[k], b[p] = b[p], b[k]
}
i += size
}
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
}
但这有点过度设计!
英文:
EDIT: Probably the implementation in the question also does not allocate memory on the heap, but the suggested modification still should be a tiny little bit more efficient. I originally thought the code in the question is from the book and has memory allocations that I can't check due to lack of local compiler.
Here is an implementation that I believe should be without memory allocation.
https://play.golang.org/p/N4mkYoiIHvn
package main
import (
"fmt"
"unicode/utf8"
)
func main() {
phrase := "Hello, 世界!"
fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
phrase = string(reverseByRune([]byte(phrase)))
fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, phrase)
}
func reverseByRune(b []byte) []byte {
reverse := func (i, j int) {
for ; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
}
for i := 0; i < len(b); {
_, size := utf8.DecodeRune(b[i:])
reverse(i, i+size-1)
i += size
}
reverse(0, len(b)-1)
return b
}
The original implementation of reverse()
needs memory to create the b []byte
slice and also unnecessarily returns a value. Though theoretically that could be optimized by removing return
from reverse
. Then a compiler can "guess" nobody can keep a pointer to the slice and can make sure the slice is created on stack instead of the heap. But this is just theoretical speculation-I'm not sure if Go's compiler is that smart.
The suggested implementation does same as the original but within the original slice.
When we talk about "no memory allocation," we usually mean what happens within a function, in this case the reverseByRune()
. Local variables allocated on stack like i
& j
does not count as they are cheap.
And here is what probably would be the most efficient implementation for given approach:
https://play.golang.org/p/YOOSZjIWKZ_r
package main
import (
"fmt"
"unicode/utf8"
)
func main() {
phrase := []byte("Hello, 世界!")
fmt.Printf("Before reverse:\tmemory address %p => phrase: %s\n", &phrase, string(phrase))
reverseByRune(phrase)
fmt.Printf("After reverse:\tmemory address %p => phrase: %s\n", &phrase, string(phrase))
}
func reverseByRune(b []byte) {
for i := 0; i < len(b); {
_, size := utf8.DecodeRune(b[i:])
for k, p := i, i+size-1; k < p; k, p = k+1, p-1 {
b[k], b[p] = b[p], b[k]
}
i += size
}
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
}
But that is overkill!
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论