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

Я придерживаюсь следующей ментальной модели:

  • Если я знаю, что операция на моем срезе не потребует изменения длины, емкости или базового массива среза, я должен использовать операции среза на месте, чтобы уменьшить выделение памяти. Общие операции: фильтрация и сортировка.
  • Если я знаю, что операция на моем срезе может потребовать изменения длины, емкости или базового массива среза, я не могу гарантировать, что операции могут быть выполнены на месте. Общие операции: вставка, сращивание и добавление.

Эти различия важны при разработке сигнатуры функции. Давайте посмотрим на несколько примеров.

Разворот на месте

func Reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

Обратите внимание на некоторые детали этой функции:

  • Функция ничего не возвращает
  • Нет ни вызовов добавления, ни создания новых экземпляров среза
  • Срез принимается как значение, а не как указатель.

Основываясь на этих деталях, как пользователь функции я могу определить, что функция будет выполнять операции среза на месте, как показано:

mySlice := []int{10, 20, 30, 40, 50}
// view values and pointer address before reversing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
Reverse(mySlice)
// view values and pointer address after reversing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])

Вывод:

Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [50 40 30 20 10]; Pointer: 0xc00000c360

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

Как насчет того, что посложнее. Давайте посмотрим на стандартную реализацию remove.

Удаление на месте

func Remove(s []int, i int) []int {
    copy(s[i:], s[i+1:])
    return s[:len(s)-1]
}

Обратите внимание на некоторые детали этой функции:

  • Функция возвращает фрагмент [] int.
  • Функция использует команду копировать.
  • Срез принимается как значение, а не как указатель.

Эта функция немного сложнее, но мы можем видеть, как команда copy используется для перезаписи элементов текущего фрагмента. Фактически, команда copy предназначена для копирования только меньшего из двух отрезков, что означает, что нет опасности перезаписать что-то вне диапазона и нет необходимости изменять емкость базового массива:

mySlice := []int{10, 20, 30, 40, 50}
// view values and pointer address before removal
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
mySlice = Remove(mySlice, 3)
// view values and pointer address after removal
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])

Вывод:

Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [10 20 30 50]; Pointer: 0xc00000c360

И снова мы видим, что операции выполнялись in-plac e, поскольку срез поддерживает тот же указатель на элемент базового массива.

Наконец, давайте рассмотрим более сложный пример, сварку.

Соединение «на месте»

func Splice(a *[]int, i int, deleteCount int, items ...int) []int {
    arr := *a // for convenience
    if len(arr) == 0 {
        *a = append(arr, items...)
        return []int{}
    }
    if deleteCount <= 0 {
        *a = append(arr[:i], append(items, arr[i:]...)...)
        return []int{}
    }
    d := append(make([]int, 0, len(arr[i:i+deleteCount])),
    arr[i:i+deleteCount]...)
    *a = append(arr[:i], append(items, arr[i+deleteCount:]...)...)
    return d
}

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

  • Пользователь может передать срез вместе с индексом, количеством элементов для удаления и количеством элементов для вставки.
  • Пользователь получит обратно slice [] int для всех элементов, которые были удалены.
  • Пользователю не нужно повторно назначать изменения своему срезу, это обрабатывается функцией
  • Функция использует добавление, что является убедительным свидетельством того, что манипулирование фрагментами на месте невозможно.

Вы заметите, что я поставил «на месте» в кавычки в заголовке этой функции. Это связано с тем, что функция обеспечивает манипулирование срезами «на месте» с точки зрения пользователя, а не с точки зрения реализации функции. Я имею в виду, что пользователю не нужно переназначать исходный фрагмент на основе вывода функции, он обрабатывается функцией от имени пользователя:

mySlice := []int{10, 20, 30, 40, 50}
// view values and pointer address before splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
_ = Splice(&mySlice, 2, 2, 100, 200, 300)
// view values and pointer address after splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])

Здесь мы передаем наш фрагмент, говорим функции начать с индекса 2, удаляем 2 элемента и вставляем 3 элемента (100, 200, 300). Функция вернет удаленные элементы в виде фрагмента [] int {30, 40}; однако мы просто игнорируем этот возвращенный фрагмент. Обратите внимание, как пользователю нужно передать адрес своего фрагмента. Это явный признак того, что функция будет управлять переменной от имени пользователя.

Вывод:

Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [10 20 100 200 300 50]; Pointer: 0xc00000e1e0

Как показано, фрагмент пользователя был изменен «на месте». Указатель больше не указывает на тот же базовый элемент массива; однако пользователю не нужно было целенаправленно переназначать новую переменную (или возвращать исходную переменную).

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

func Splice(a []int, i int, deleteCount int, items ...int) ([]int, []int) {
    if len(a) == 0 {
        a = append(a, items...)
        return a, []int{}
    }
    if deleteCount <= 0 {
        a = append(a[:i], append(items, a[i:]...)...)
        return a, []int{}
    }
    d := append(make([]int, 0, len(a[i:i+deleteCount])),
    a[i:i+deleteCount]...)
    a = append(a[:i], append(items, a[i+deleteCount:]...)...)
    return a, d
}

Теперь мы вызываем функцию без адреса среза:

mySlice := []int{10, 20, 30, 40, 50}
// view values and pointer address before splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])
mySlice, _ = Splice(mySlice, 2, 2, 100, 200, 300)
// view values and pointer address after splicing
fmt.Printf("Values: %v; Pointer: %p\n", mySlice, &mySlice[0])

Вывод:

Values: [10 20 30 40 50]; Pointer: 0xc00000c360
Values: [10 20 100 200 300 50]; Pointer: 0xc00000e1e0

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

Бонус: выделение памяти для фрагментов на месте

Существует два идиоматических подхода к выполнению операций срезами на месте во избежание выделения памяти. Оба подхода перезаписывают значения в исходном срезе.

Перезаписать и нарезать

Мы уже видели один подход для решения этой проблемы, который обычно используется, когда вы хотите удалить элемент:

func Remove(s []int, i int) []int {
    copy(s[i:], s[i+1:]) // overwrite the original slice
    return s[:len(s)-1] // return slice of remaining elements
}

Другой подход используется для фильтрации и следует той же концепции перезаписи элементов фрагмента и возврата фрагмента с len (), меньшим или равным исходному фрагменту:

func RemoveZeros(s []int) []int {
    i := 0
    for _, v := range s {
        if v != 0 {
            s[i] = v // overwrite the original slice
            i++
        }
    }
    return s[:i] // return slice of remaining elements
}

Нулевой длины и добавления

func RemoveZeros(s []int) []int {
    out := s[:0] // zero-length slice from original
    for _, v := range s {
        if v != 0 {
            out = append(out, v) // overwrite the original slice
        }
    }
    return out // return elements
}