go - 与任意 slice 一起使用的交换实现

Question

我正在尝试在 container/heap 周围实现一个包装器使堆初始化更简单。
heap.Interface 的重要必需功能是 Swap (i, j int) , 我用 reflect.Swapper 实现的.但事实证明这是行不通的，因为用于堆的 slice 可能会增长，而 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
}

但是这种解决方案会使推送速度变慢。我用谷歌搜索并找到了以下一般 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在这里工作？

Answer 1

正如@Adrian 指出的那样，很难想出一个始终指向正确 slice 并且与 reflect.Swapper 返回的 slice 一样快的交换实现。 .因为reflect.Swapper根据仅在包中的某些私有(private)字段中可用的某些信息选择可能的最快实现。

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

正如@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
    }
}