Алиасинг ломтиков - PullRequest
Новая
       17

Алиасинг ломтиков

0 голосов
/ 13 ноября 2018

Как проверить, резервируются ли два среза одним и тем же массивом?

Например: 

a := []int{1, 2, 3}
b := a[0:1]
c := a[2:3]

alias(b, c) == true

Как должен выглядеть alias?

Ответы [ 2 ]

0 голосов
/ 13 ноября 2018

Найден один из способов здесь .Идея состоит в том, что, хотя я не думаю, что есть способ найти начало резервного массива, ptr + cap среза должен [*] указывать на его конец.Затем сравнивается последний указатель на равенство, например: 

func alias(x, y nat) bool {
    return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]
}

[*] Код включает следующее примечание:

Примечание: псевдоним предполагает, что емкость базовых массивовникогда не изменяется для значений nat;то есть, что в этом коде нет выражений с 3 операндами (или, что еще хуже, операций на основе отражения с тем же эффектом).

0 голосов
/ 13 ноября 2018

Как правило, вы не можете определить, используется ли массив резервных копий для двух срезов, потому что, используя выражение полного среза , можно контролировать емкость результирующего среза, и тогда не будет перекрытия.даже при проверке емкости.

Например, если у вас есть резервный массив с 10 элементами, может быть создан фрагмент, который содержит только первые 2 элемента, и его емкость может быть равна 2. И другой фрагмент можетbe create, который содержит только последние 2 элемента, его емкость снова равна 2.

См. этот пример: 

a := [10]int{}

x := a[0:2:2]
y := a[8:10:10]

fmt.Println("len(x) = ", len(x), ", cap(x) = ", cap(x))
fmt.Println("len(y) = ", len(y), ", cap(y) = ", cap(y))

Выше будет напечатано, что длина и емкость x и y равны 2. У них, очевидно, одинаковый резервный массив, но у вас не будет никаких средств сказать это.

Редактировать: Я неправильно понял вопрос, иниже описано, как определить, перекрываются ли (элементы) 2 срезов.

Для этого не существует языковой поддержки, но поскольку срезы имеют непрерывный участок некоторого резервного массива, мыпроверка того, перекрывается ли диапазон адресов их элементов.

К сожалению, указатели не упорядочены в том смысле, что мы не можем применять к ним операторы < и > (в Go есть указатели, нонет арифметики указателей).И проверить, совпадают ли все адреса элементов первого слайса с любым из второго, это неосуществимо.

Но мы можем получить значение указателя (адрес) как тип uintptr, используя отражениепакет, более конкретно метод Value.Pointer() (или мы могли бы также сделать это, используя пакет unsafe, но reflect "безопаснее"), а значения uintptr являются целыми числами, они упорядочены,поэтому мы можем сравнить их.

Итак, что мы можем сделать, это получить адреса первого и последнего элементов срезов, и, сравнивая их, мы можем определить, перекрываются ли они.

Вотпростая реализация: 

func overlap(a, b []int) bool {
    if len(a) == 0 || len(b) == 0 {
        return false
    }

    amin := reflect.ValueOf(&a[0]).Pointer()
    amax := reflect.ValueOf(&a[len(a)-1]).Pointer()
    bmin := reflect.ValueOf(&b[0]).Pointer()
    bmax := reflect.ValueOf(&b[len(b)-1]).Pointer()

    return !(amax < bmin || amin > bmax)
}

Тестирование: 

a := []int{0, 1, 2, 3}
b := a[0:2]
c := a[2:4]
d := a[0:3]

fmt.Println(overlap(a, b)) // true
fmt.Println(overlap(b, c)) // false
fmt.Println(overlap(c, d)) // true

Попробуйте на Go Playground .

...