go - 交换可与任意 slice 配合使用的实现

我正在尝试实现container/heap的包装，以使堆初始化更简单。
heap.Interface的一个重要的必需功能是Swap (i, j int)，我使用reflect.Swapper实现了该功能。但是事实证明这是行不通的，因为用于堆的片可能会增长，并且初始化之前存储的swapper将过时。

我通过每次将新项目推入堆时都覆盖swapper来解决此问题。我的完整实现粘贴在下面:

package heaptools

import (
    "container/heap"
    "reflect"
)

var _ heap.Interface = &sliceHeap{}

type sliceHeap struct {
    slice   reflect.Value
    less    func(i, j int) bool
    swapper func(i, j int)
}

func (h *sliceHeap) Len() int {
    return h.slice.Elem().Len()
}

func (h *sliceHeap) Less(i, j int) bool {
    return h.less(i, j)
}

func (h *sliceHeap) Swap(i, j int) {
    if i == j {
        return
    }
    h.swapper(i, j)
}

func (h *sliceHeap) Push(x interface{}) {
    e := h.slice.Elem()
    e.Set(reflect.Append(e, reflect.ValueOf(x)))
    h.swapper = reflect.Swapper(e.Interface())
}

func (h *sliceHeap) Pop() interface{} {
    e := h.slice.Elem()
    last := e.Index(e.Len() - 1)
    e.SetLen(e.Len() - 1)
    return last.Interface()
}

func NewSliceHeap(slice interface{}, less func(i, j int) bool) heap.Interface {
    v := reflect.ValueOf(slice)
    sh := &sliceHeap{
        slice:   v,
        less:    less,
        swapper: reflect.Swapper(v.Elem().Interface()),
    }
    heap.Init(sh)
    return sh
}

但是此解决方案使推送速度大大降低。我已经在Google上进行了搜索，发现了以下用于常规 slice 交换的方法:

A := []int{1,2}
V := reflect.ValueOf(A)
x, y := V.Index(0).Interface(), V.Index(1).Interface()
V.Index(0).Set(reflect.ValueOf(y))
V.Index(1).Set(reflect.ValueOf(x))

但是事实证明它甚至更慢。

我如何在这里工作更快的swapper？

最佳答案

正如@Adrian指出的那样，很难提出总是指向正确 slice 且与reflect.Swapper返回的 slice 一样快的交换实现。因为reflect.Swapper根据仅在包中某些 private 字段中可用的某些信息来选择最快的实现。

优化的一个明显机会是避免不必要地创建新的Swapper。

正如@Adrian所建议的那样，我只能将h.swapper设置为nil，并且仅当确实调用Swap时才创建一个新的。

通过检查基础数组的地址是否更改，我们可以使其更快。请记住，仅当 slice 中没有足够的空间时才分配新数组，大多数情况下，基础数组的地址应该相同，并且我们不需要创建新的交换函数。

通过以上两个优化，代码将变为:

func (h *sliceHeap) Swap(i, j int) {
    if i == j {
        return
    }
    if h.swapper == nil {
        h.swapper = reflect.Swapper(h.slice.Elem().Interface())
    }
    h.swapper(i, j)
}

func (h *sliceHeap) Push(x interface{}) {
    e := h.slice.Elem()
    slicePtr := e.Pointer()
    e.Set(reflect.Append(e, reflect.ValueOf(x)))
    // If the pointer to the first element of the slice changes, we need a new Swapper
    if e.Pointer() != slicePtr {
        h.swapper = nil
    }
}