这个 Go 方法是否会“分配新的内存”?

huangapple go评论91阅读模式
英文:

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 ints 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 (
	&quot;fmt&quot;
	&quot;unicode/utf8&quot;
)

func main() {
	phrase := &quot;Hello, 世界!&quot;
	fmt.Printf(&quot;Before reverse:\tmemory address %p =&gt; phrase: %s\n&quot;, &amp;phrase, phrase)
	phrase = string(reverseByRune([]byte(phrase)))
	fmt.Printf(&quot;After reverse:\tmemory address %p =&gt; phrase: %s\n&quot;, &amp;phrase, phrase)
}

func reverseByRune(b []byte) []byte {
	for i := 0; i &lt; 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 &lt; 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()。在堆栈上分配的局部变量,如 ij,不计算在内,因为它们是廉价的。

以下是给定方法可能是最高效的实现:

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 (
	&quot;fmt&quot;
	&quot;unicode/utf8&quot;
)

func main() {
	phrase := &quot;Hello, 世界!&quot;
	fmt.Printf(&quot;Before reverse:\tmemory address %p =&gt; phrase: %s\n&quot;, &amp;phrase, phrase)
	phrase = string(reverseByRune([]byte(phrase)))
	fmt.Printf(&quot;After reverse:\tmemory address %p =&gt; phrase: %s\n&quot;, &amp;phrase, phrase)
}

func reverseByRune(b []byte) []byte {
	reverse := func (i, j int) {
		for ; i &lt; j; i, j = i+1, j-1 {
			b[i], b[j] = b[j], b[i]
		}
	}
	for i := 0; i &lt; 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 (
	&quot;fmt&quot;
	&quot;unicode/utf8&quot;
)

func main() {
	phrase := []byte(&quot;Hello, 世界!&quot;)
	fmt.Printf(&quot;Before reverse:\tmemory address %p =&gt; phrase: %s\n&quot;, &amp;phrase, string(phrase))
	reverseByRune(phrase)
	fmt.Printf(&quot;After reverse:\tmemory address %p =&gt; phrase: %s\n&quot;, &amp;phrase, string(phrase))
}

func reverseByRune(b []byte) {
	for i := 0; i &lt; len(b); {
		_, size := utf8.DecodeRune(b[i:])
		for k, p := i, i+size-1; k &lt; 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 &lt; j; i, j = i+1, j-1 {
		b[i], b[j] = b[j], b[i]
	}
}

But that is overkill!

huangapple
  • 本文由 发表于 2021年7月10日 03:47:28
  • 转载请务必保留本文链接:https://go.coder-hub.com/68322049.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定