Реализация подкачки, которая работает с произвольным слайсом

Question

Я пытаюсь реализовать оболочку вокруг 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
}

Но это решение делает продвижение намного медленнее. Я гуглил и нашел следующий способ для общего обмена слайсами:

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 выбирает самую быструю возможную реализацию, основываясь на некоторой информации, доступной только в некотором частном поле в пакете.

Очевидная возможность для оптимизации - избежать ненужного создания новых Swapper s.

В соответствии с предложением @Adrian, я могу просто установить h.swapper в nil и создать новый, только когда действительно вызывается Swap.

Мы можем сделать это еще быстрее, проверив, если адрес изменений базового массива. Помните, что новый массив выделяется только тогда, когда в срезе недостаточно места, большую часть времени адрес базового массива должен быть одинаковым, и нам не нужно создавать новую функцию подкачки.

С двумя вышеупомянутыми оптимизациями код стал бы:

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
    }
}