2017年1月29日 04:16:00go评论78阅读模式

英文:

What is the mechanism of using append to prepend in Go?

问题

假设我有一个类型为int的切片slice。在声明时，我将第三个参数设置为size，我相信这将通过设置切片的cap参数来为至少size个整数保留内存。

slice := make([]int, 0, size)

现在，假设我有一个整数变量value。要将其添加到切片的末尾，我使用以下代码：

slice = append(slice, value)

如果切片中当前的元素数量小于size，则不需要将整个底层数组复制到新位置以添加新元素。

此外，如果我想将value添加到slice的开头，可以使用以下代码：

slice = append([]int{value}, slice...)

我的问题是，在这种情况下会发生什么？如果元素数量仍然小于size，那么这些元素是如何存储在内存中的？假设在调用make()函数时进行了连续分配，是否会将所有现有元素右移以释放第一个位置给value？还是会重新分配内存并复制所有元素？

我之所以问这个问题，是因为我希望我的程序尽可能快，想知道这是否可能导致程序变慢。如果是这样，是否有任何更高效的添加到开头的替代方法？

英文:

Suppose I have a slice slice of type int. While declaring, I set the third argument to size, which I believe reserves memory for at least size ints by setting the cap parameter of the slice.

slice:=make([]int,0,size)

Now, suppose I have an integer variable value. To add it to the slice at the end, I use

slice=append(slice,value)

If the number of elements currently in the slice is less than size, then there will be no need to copy the entire underlying array to a new location in order to add the new element.

Further, if I want to prepend value to slice, as suggested here and here, I use

slice=append([]int{value},slice...)

My question is, what happens in this case? If the number of elements is still less than size, how are the elements stored in the memory? Assuming a contiguous allocation when the make() function was invoked, are all existing elements right shifted to free the first space for value? Or is memory reallocated and all elements copied?

The reason for asking is that I would like my program to be as fast as possible, and would like to know if this is a possible cause for slowing it down. If it is so, is there any alternative way of prepending that would be more time efficient?

答案1

得分: 6

使用重新切片和复制

内置的append()函数总是将元素追加到切片的末尾。你不能仅仅使用append()函数来在切片的开头插入元素。

话虽如此，如果你有一个切片的容量大于长度（即在元素之后有"空闲"空间），并且你想在开头插入一个元素，你可以重新切片原始切片，将所有元素复制到索引加一的位置以为新元素腾出空间，然后将新元素设置为索引为0的位置。这样就不需要进行新的分配。下面是一个示例：

func prepend(dest []int, value int) []int {
    if cap(dest) > len(dest) {
        dest = dest[:len(dest)+1]
        copy(dest[1:], dest)
        dest[0] = value
        return dest
    }

    // 没有空间，需要分配新的切片：
    // 为未来使用一些额外的空间：
    res := make([]int, len(dest)+1, len(dest)+5)
    res[0] = value
    copy(res[1:], dest)
    return res
}

测试代码：

s := make([]int, 0, 5)
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

输出结果（在Go Playground上尝试）：

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]

注意：如果没有足够的空间来插入新元素，由于性能很重要，我们没有简单地使用以下代码：

res := append([]int{value}, dest...)

因为它进行了比必要的更多的分配和复制：首先为字面量([]int{value})分配一个切片，然后append()在追加dest时又分配了一个新的切片。

相反，我们的解决方案只分配了一个新的数组（通过make()函数），然后将value设置为第一个元素，并复制dest（之前的元素）。

使用链表

如果你需要多次在开头插入元素，普通的切片可能不是一个合适的选择。一个更快的替代方案是使用链表，这样在插入元素时不需要分配切片/数组或复制，只需创建一个新的节点元素，并将其指定为根节点（第一个元素）。

标准库在container/list包中提供了一个通用的链表实现。

手动管理较大的后备数组

如果你愿意自己管理一个较大的后备数组（或切片），还有另一种解决方案。

如果你愿意自己管理一个较大的后备数组（或切片

英文:

With reslicing and copying

The builtin append() always appends elements to a slice. You cannot use it (alone) to prepend elements.

Having said that, if you have a slice capacity bigger than length (has "free" space after its elements) to which you want to prepend an element, you may reslice the original slice, copy all elements to an index one higher to make room for the new element, then set the element to the 0<sup>th</sup> index. This will require no new allocation. This is how it could look like:

func prepend(dest []int, value int) []int {
	if cap(dest) &gt; len(dest) {
		dest = dest[:len(dest)+1]
		copy(dest[1:], dest)
		dest[0] = value
		return dest
	}

	// No room, new slice need to be allocated:
	// Use some extra space for future:
	res := make([]int, len(dest)+1, len(dest)+5)
	res[0] = value
	copy(res[1:], dest)
	return res
}

Testing it:

s := make([]int, 0, 5)
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

Output (try it on the Go Playground):

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]

Note: if no room for the new element, since performance does matter now, we didn't just do:

res := append([]int{value}, dest...)

Because it does more allocations and copying than needed: allocates a slice for the literal ([]int{value}), then append() allocates a new when appending dest to it.

Instead our solution allocates just one new array (by make(), even reserving some space for future growth), then just set value as the first element and copy dest (the previous elements).

With linked list

If you need to prepend many times, a normal slice may not be the right choice. A faster alternative would be to use a linked list, to which prepending an element requires no allocations of slices / arrays and copying, you just create a new node element, and you designate it to be the root by pointing it to the old root (first element).

The standard library provides a general implementation in the container/list package.

With manually managing a larger backing array

Sticking to normal slices and arrays, there is another solution.

If you're willing to manage a larger backing array (or slice) yourself, you can do so by leaving free space before the slice you use. When prepending, you can create a new slice value from the backing larger array or slice which starts at an index that leaves room for 1 element to be prepended.

Without completeness, just for demonstration:

var backing = make([]int, 15) // 15 elements
var start int

func prepend(dest []int, value int) []int {
	if start == 0 {
		// No more room for new value, must allocate bigger backing array:
		newbacking := make([]int, len(backing)+5)
		start = 5
		copy(newbacking[5:], backing)
		backing = newbacking
	}

	start--
	dest = backing[start : start+len(dest)+1]
	dest[0] = value
	return dest
}

Testing / using it:

start = 5
s := backing[start:start] // empty slice, starting at idx=5
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

// Prepend more to test reallocation:
for i := 10; i &lt; 15; i++ {
	s = prepend(s, i)
}
fmt.Println(s)

Output (try it on the Go Playground):

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]
[14 13 12 11 10 8 9 1 2 3 4]

Analysis: this solution makes no allocations and no copying when there is room in the backing slice to prepend the value! All that happens is it creates a new slice from the backing slice that covers the destination +1 space for the value to be prepended, sets it and returns this slice value. You can't really get better than this.

If there is no room, then it allocates a larger backing slice, copies over the content of the old, and then does the "normal" prepending.

With tricky slice usage

Idea: imagine that you always store elements in a slice in backward order.

Storing your elements in backward order in a slice means a prepand becomes append!

So to "prepand" an element, you can simply use append(s, value). And that's all.

Yes, this has its limited uses (e.g. append to a slice stored in reverse order has the same issues and complexity as a "normal" slice and prepand operation), and you lose many conveniences (ability to list elements using for range just to name one), but performance wise nothing beats prepanding a value just by using append().

Note: iterating over the elements that stores elements in backward order has to use a downward loop, e.g.:

for i := len(s) - 1; i &gt;= 0; i-- {
    // do something with s[i]
}

Final note: all these solutions can easily be extended to prepend a slice instead of just a value. Generally the additional space when reslicing is not +1 but +len(values), and not simply setting dst[0] = value but instead a call to copy(dst, values).

答案2

得分: 4

"prepend"调用将需要分配一个数组并复制所有元素，因为在Go中，切片被定义为起始点、大小和分配（分配从起始点计数）。

切片无法知道第一个元素之前的元素是否可以用来扩展切片。

对于以下代码：

slice = append([]int{value}, slice...)

将会发生以下情况：

分配一个新的数组，其中只有一个元素value（可能在堆栈上）。
创建一个切片来映射这个元素（起始点=0，大小=1，分配=1）。
执行append调用。
append发现没有足够的空间来扩展单个元素的切片，因此分配一个新的数组并复制所有元素。
创建一个新的切片对象来引用这个数组。

如果在大容器的两端进行添加/删除是你的应用程序的常见用例，那么你需要一个deque（双端队列）容器。不幸的是，Go中没有提供这个容器，并且在保持可用性的同时高效地为通用的包含类型编写它是不可能的（因为Go仍然缺乏泛型）。

然而，你可以为你的特定情况实现一个deque，这很容易（例如，如果你有一个具有已知上限的大容器，可能只需要一个circular buffer（循环缓冲区），这只需要几行代码）。

我对Go非常陌生，所以以下可能是非常糟糕的Go代码...但这是一个使用增长的循环缓冲区来实现deque的尝试（根据用例，这可能是一个好的解决方案，也可能不是）

type Deque struct {
	buffer  []interface{}
	f, b, n int
}

func (d *Deque) resize() {
	new_buffer := make([]interface{}, 2*(1+d.n))
	j := d.f
	for i := 0; i < d.n; i++ {
		new_buffer[i] = d.buffer[j]
		d.buffer[j] = nil
		j++
		if j == len(d.buffer) {
			j = 0
		}
	}
	d.f = 0
	d.b = d.n
	d.buffer = new_buffer
}

func (d *Deque) push_back(x interface{}) {
	if d.n == len(d.buffer) {
		d.resize()
	}
	d.buffer[d.b] = x
	d.b++
	if d.b == len(d.buffer) {
		d.b = 0
	}
	d.n++
}

func (d *Deque) push_front(x interface{}) {
	if d.n == len(d.buffer) {
		d.resize()
	}
	if d.f == 0 {
		d.f = len(d.buffer)
	}
	d.f--
	d.buffer[d.f] = x
	d.n++
}

func (d *Deque) pop_back() interface{} {
	if d.n == 0 {
		panic("Cannot pop from an empty deque")
	}
	if d.b == 0 {
		d.b = len(d.buffer)
	}
	d.b--
	x := d.buffer[d.b]
	d.buffer[d.b] = nil
	d.n--
	return x
}

func (d *Deque) pop_front() interface{} {
	if d.n == 0 {
		panic("Cannot pop from an empty deque")
	}
	x := d.buffer[d.f]
	d.buffer[d.f] = nil
	d.f++
	if d.f == len(d.buffer) {
		d.f = 0
	}
	d.n--
	return x
}

英文:

The "prepend" call will need to allocate an array and copy all elements because a slice in Go is defined as a starting point, a size and an allocation (with the allocation being counted from the starting point).

There is no way a slice can know that the element before the first one can be used to extend the slice.

What will happen with

slice = append([]int{value}, slice...)

a new array of a single element value is allocated (probably on stack)
a slice is created to map this element (start=0, size=1, alloc=1)
the append call is done
append sees that there is not enough room to extend the single-element slice so allocates a new array and copies all the elements
a new slice object is created to refer to this array

If appending/removing at both ends of a large container is the common use case for your application then you need a deque container. It is unfortunately unavailable in Go and impossible to write efficiently for generic contained types while maintaining usability (because Go still lacks generics).

You can however implement a deque for your specific case and this is easy (for example if you have a large container with a known upper bound may be a circular buffer is all you need and that is just a couple of lines of code away).

I'm very new to Go, so may be the following is very bad Go code... but it's an attempt to implement a deque using a growing circular buffer (depending on the use case this may be or may be not a good solution)

type Deque struct {
	buffer  []interface{}
	f, b, n int
}

func (d *Deque) resize() {
	new_buffer := make([]interface{}, 2*(1+d.n))
	j := d.f
	for i := 0; i &lt; d.n; i++ {
		new_buffer[i] = d.buffer[j]
		d.buffer[j] = nil
		j++
		if j == len(d.buffer) {
			j = 0
		}
	}
	d.f = 0
	d.b = d.n
	d.buffer = new_buffer
}

func (d *Deque) push_back(x interface{}) {
	if d.n == len(d.buffer) {
		d.resize()
	}
	d.buffer[d.b] = x
	d.b++
	if d.b == len(d.buffer) {
		d.b = 0
	}
	d.n++
}

func (d *Deque) push_front(x interface{}) {
	if d.n == len(d.buffer) {
		d.resize()
	}
	if d.f == 0 {
		d.f = len(d.buffer)
	}
	d.f--
	d.buffer[d.f] = x
	d.n++
}

func (d *Deque) pop_back() interface{} {
	if d.n == 0 {
		panic(&quot;Cannot pop from an empty deque&quot;)
	}
	if d.b == 0 {
		d.b = len(d.buffer)
	}
	d.b--
	x := d.buffer[d.b]
	d.buffer[d.b] = nil
	d.n--
	return x
}

func (d *Deque) pop_front() interface{} {
	if d.n == 0 {
		panic(&quot;Cannot pop from an empty deque&quot;)
	}
	x := d.buffer[d.f]
	d.buffer[d.f] = nil
	d.f++
	if d.f == len(d.buffer) {
		d.f = 0
	}
	d.n--
	return x
}

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。

What is the mechanism of using append to prepend in Go?

问题

答案1

使用重新切片和复制

使用链表

手动管理较大的后备数组

With reslicing and copying

With linked list

With manually managing a larger backing array

With tricky slice usage

答案2

在Go语言中测试不返回结果的方法。

WebSocket连接失败：连接建立错误：net::ERR_SSL_PROTOCOL_ERROR

如何使用反射(reflect)在Go语言中获取结构体子字段的项目数量

Golang gorm预加载

What's the correct way to type hint an empty list as a literal in python?

如何在Highcharts Gantt中更改本地化的星期名称

如何在同一个流中使用多个过滤器和映射函数？

如何使用Map/Set来将代码优化到O(n)？

.NET MAUI Android在GitHub Actions上构建失败，错误代码为1。

如何在Playwright视觉比较中屏蔽多个定位器？

在C++中，可以使用可变模板参数来检索类型的内部类型。

selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: stale element not found

Creating and opening a URL to log in to Website via Basic Auth with Robot Framework/Selenium (Python)

AG Grid 在上下文菜单中以大文本形式打开

发表评论