与任意切片一起使用的交换实现

Question

我正在尝试实现一个包装器container/heap以使堆初始化更简单。

heap.Interfaceis的一个重要必需功能Swap (i, j int)，我用reflect.Swapper. 但事实证明这是行不通的，因为用于堆的切片可能会增长，并且swapper在初始化之前存储的 I 将过时。

我通过覆盖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

}

但是这种解决方案会使推送速度变慢。我用谷歌搜索并找到了以下一般切片交换的方法：

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地在这里工作？

Answer 1

正如@Adrian 指出的那样，很难想出一个始终指向正确切片并且与reflect.Swapper. 因为reflect.Swapper根据仅在包中的某些私有字段中可用的某些信息来选择可能的最快实现。一个明显的优化机会是避免不必要地创建 new Swappers。正如@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    }}