Вступление
Одна из самой общей возможности процедурных языков программирования, это концепция массива. Массивы могут показаться чем-то простым, но с другой стороны, перед их добавлением в язык требуется решить несколько вопросов, таких как:
- Фиксированный или переменный размер?
- Размер это часть типа?
- Что из себя будут представлять многомерные массивы?
- Что из себя представляем понятие пустого массива?
Ответы на эти вопросы определят массивы как простую возможность языка, или как основную часть его дизайна.
Во времена ранней разработки Go, поиск ответов на эти вопросы потребовали годы обсуждений, прежде чем их концепция стала выглядеть так, как мы посчитали нужным. Ключевым шагом стало создание концепции слоев (slices), которые основаны на массивах фиксированного размера, дабы создать гибкую и расширяемую структуру данных. Однако, многие новички в Go спотыкаются о принципы работы слоев, возможно это происходит из-за того, что их опыт работы с другими языками оставил свой след.
В этой публикации мы постараемся развеять все эти недоразумения. Добьемся мы этого по кусочкам объясняя как работает функция append, и почему она работает именно так и никак иначе.
Массивы
Массивы это важный кусочек языка Go, но, как и фундамент здания, он спрятан под более видимыми частями. Мы должны ввести вас в курс дела, прежде чем перейти к более интересным, мощным и заметным особенностям слоев.
Массивы не часто встретишь в программах на Go, потому-что в тип массива входит его размер, что ограничивает возможности использование.
Например объявление:
var buffer [256]byte создает переменную buffer, которая содержит 256 байт. Тип переменной buffer включает в себя размер и выглядит так: [256]byte. Массив из 512 байт будет иметь тип [512]byte.
Данные связанные с массивом это просто массив элементов. Схематически, наш буфер в памяти будет иметь примерно следующий вид:
buffer: byte byte byte ... 256 times ... byte byte byte То есть, переменная содержит 256 байт данных и ничего более. Мы можем получить доступ к элементам с помощью привычного синтаксиса индексации buffer[0], buffer[1], и так до buffer[255] (индекс от 0 до 255 охватывает 256 элементов). Попытка выйти за пределы этого диапазона приведет к аварийной остановке программы.
Существует встроенная функция len, которая возвращает количество элементов массива, слоя и некоторых других типов. Очевидно, что именно вернет len для массива В нашем случае len(buffer) вернет значение 256.
Для массивов можно найти свое место применения. Например они хороши, для преобразования матриц, но наиболее частое их применение в Go это хранение слоев.
Слои: Верхушка слоя
Слои там, где происходит что-то интересное, но перед тем как приступить к их использованию, потребуется понять их надобность и то, что-же они делают.
Слой это структура данных описывающая множественное разделение массива и хранящееся отдельно от переменной. Слой это не массив. Слой описывает часть массива.
Если мы возьмем массив buffer из предыдущего раздела, то мы можем создать слой, который будет описывать элементы от 100 до 150 (если быть точным, то от 100 до 149 включительно) путем нарезания массива:
var slice []byte = buffer[100:150] В этом куске кода, чтобы быть точными, мы использовали полное объявление переменной. Переменная slice имеет тип []byte, читается как «срез байтов» (slice of bytes) и создана из массива buffer, путем нарезания начиная с элемента 100 (включительно) до 150 (исключительно). В более «идиоматическом» (от пер. читай «намекающем», «сокращенном») синтаксисе, то мы бы опустили тип, который будет определен в процессе инициализации:
var slice = buffer[100:150] А внутри функции мы бы использовали короткую форму объявления:
slice := buffer[100:150] Что же из себя представляет слой? Это не полное описание, но с этого момента думайте о слове как о небольшой структуре, состоящей из двух элементов: длинны и указателя на элемент массива. Считайте что «за кулисами» это выглядит примерно так:
type sliceHeader struct { Length int ZerothElement *byte } slice := sliceHeader{ Length: 50, ZerothElement: &buffer[100], } Конечно, это лишь иллюстрация. Несмотря на это, из этого примера можно понять то, что структура sliceHeader недоступна программисту, а тип указателя зависит от типа элементов, однако он дает возможность понять основную идею механики работы слоев.
До сих пор мы использовали операцию нарезания массива, однако мы можем нарезать и слой:
slice2 := slice[5:10] Точно так-же как и прежде, эта операция создает новый слой, но в этом случае из элементов с 5 до 9 (включительно) относительно оригинального слоя, что означает элементы с 105 по 109 оригинального массива. Базовая структура sliceHeader для переменной slice2 будет выглядеть так:
slice2 := sliceHeader{ Length: 5, ZerothElement: &buffer[105], } Обратите внимание, что верхушка до сих пор указывает на базовый массив, находящийся в переменной buffer.
Мы так-же можем перенарезать, что означает нарезать слой и сохранить результат в структуре нарезаемого слоя. Т.е. после:
slice = slice[5:10] структура sliceHeader для переменной slice будет выглядеть так-же как и для переменной slice2. Вы будете часто видеть перенарезку, например для сокращения слоя. В этом примере будет опущен первый и последний элемент нашего слоя:
slice = slice[1:len(slice)-1] Вы можете часто слышать от опытных Go программистов о «верхушке слоя», т.к. это и есть то, что хранится в переменной слоя. Например, когда вы вызываете функцию которая берет слой как аргумент, такая как bytes.IndexRune, то в функцию будет передана верхушка. В этом примере:
slashPos := bytes.IndexRune(slice, '/') аргумент slice будет передан в функцию IndexRune и, по факту, это лишь «верхушка слоя».
Есть еще один элемент данных в «верхушке слоя» о котором мы поговорим ниже, но сначала давайте взглянем на то, что значит «верхушка слоя», когда вы пишете программу использующую слои.
Передача слоев в функции
Очень важно понять то, что даже если слой содержит указатель, сам по себе он является значением. Под капотом, это структура содержащая указатель и длину. Это не указатель на структуру.
Это важно.
Когда мы вызываем IndexRune в предыдущем примере, она принимает копию «верхушки заголовка». Такое поведение имеет важное последствие.
Рассмотрим простую функцию:
func AddOneToEachElement(slice []byte) { for i := range slice { slice[i]++ } } Она делает именно то, что написано в названии, т.е. обходит все элементы слоя (используя цикл for range), увеличивая его элементы.
Попробуйте:
func main() { slice := buffer[10:20] for i := 0; i < len(slice); i++ { slice[i] = byte(i) } fmt.Println("before", slice) AddOneToEachElement(slice) fmt.Println("after", slice) } Несмотря на то что «верхушка слоя» передается в функцию, она включает указатель на элементы массива, поэтому оригинальная верхушка слоя и его копия описывают один и тот-же массив. Как следствие, когда функция завершается, измененные элементы можно увидеть через исходный слой.
Аргумент функции на самом деле копия, и данный пример это показывает:
func SubtractOneFromLength(slice []byte) []byte { slice = slice[0 : len(slice)-1] return slice } func main() { fmt.Println("Before: len(slice) =", len(slice)) newSlice := SubtractOneFromLength(slice) fmt.Println("After: len(slice) =", len(slice)) fmt.Println("After: len(newSlice) =", len(newSlice)) } Здесь мы видим что содержимое слоя аргумента может быть изменено через функцию, но не его заголовок. Длинна сохранена в переменной slice и не изменяется в результате вызова функции, т. к. в функцию передается копия заголовка слоя, а не исходный. Таким образом, если мы хотим написать функцию которая изменяет заголовок, мы должны вернуть его, как мы это сделали в примере. Переменная slice не изменяется, но возвращаемое значение имеет новую длину, которая сохранена в newSlice.
Указатели на слои: Методы получения
Существует и другой путь написания функции которая изменяет верхушку слоя, и это передача в функцию указатель на слой. Вот вариация нашего примера, для демонстрации данной возможности:
func PtrSubtractOneFromLength(slicePtr *[]byte) { slice := *slicePtr *slicePtr = slice[0 : len(slice)-1] } func main() { fmt.Println("Before: len(slice) =", len(slice)) PtrSubtractOneFromLength(&slice) fmt.Println("After: len(slice) =", len(slice)) } Пример может показаться немного неуклюжим, учитывая дополнительный уровень абстракции (временная переменная), но есть один случай, где вы будете применять указатели на слои. Принято использование указателя в качестве приемника при написании метода, который изменяет слой.
Скажем, мы захотели метод который ликвидирует последний слэш. Мы можем написать его примерно так:
type path []byte func (p *path) TruncateAtFinalSlash() { i := bytes.LastIndex(*p, []byte("/")) if i >= 0 { *p = (*p)[0:i] } } func main() { pathName := path("/usr/bin/tso") // Преобразование из строки в path pathName.TruncateAtFinalSlash() fmt.Printf("%s\n", pathName) } Если вы запустите пример, то вы увидите, что произойдет то, что требовалось, т. е. метод изменит слой.
С другой стороны, если мы захотим написать метод для path, который устанавливает верхний регистр ASCII символов (с не Английские буквами поведение не определено), то метод может оперировать значением, а не указателем, потому-что значение приемника все еще указывает на нужный нам массив.
type path []byte func (p path) ToUpper() { for i, b := range p { if 'a' <= b && b <= 'z' { p[i] = b + 'A' - 'a' } } } func main() { pathName := path("/usr/bin/tso") pathName.ToUpper() fmt.Printf("%s\n", pathName) } Здесь метод ToUpper использует две переменных в for range для того, чтобы использовать индекс элемента и, непосредственно, сам элемент слоя. Это позволит избежать повторной записи в p[i].
Мощность
Рассмотрим следующую функцию, которая увеличивает слой ints на один элемент:
func Extend(slice []int, element int) []int { n := len(slice) slice = slice[0 : n+1] slice[n] = element return slice } Теперь запустим:
func main() { var iBuffer [10]int slice := iBuffer[0:0] for i := 0; i < 20; i++ { slice = Extend(slice, i) fmt.Println(slice) } } Посмотрим как слой растет до тех пор пока… он не растет.
Пришло время поговорить о третьем компоненте верхушки слоя: его мощности. Помимо указателя на массив и его длинны, верхушка слоя содержит его мощность:
type sliceHeader struct { Length int Capacity int ZerothElement *byte } Поле Capacity содержит запись о том, сколько места занимает массив на самом деле – это максимальное значение, которое может достигнуть Length. Попытка увеличения слоя выше его мощности приведет к выходу за пределы массива и вызовет экстренное завершение программы.
В этом примере создается слой
slice := iBuffer[0:0] и его верхушка выглядит как:
slice := sliceHeader{ Length: 0, Capacity: 10, ZerothElement: &iBuffer[0], } Поле Capacity эквивалентно длине оригинального массива минус индекс элемента массива, который является первым элементом слоя (в данном случае ноль). Если вы хотите узнать мощность слоя, то используйте функцию cap:
if cap(slice) == len(slice) { fmt.Println("slice is full!") } Make
Что если мы захотим увеличить слой больше чем его мощность? Мы не можем! По определению мощность это предел роста. Но вы можете получить тот-же результат путем создания нового массива, копирования данных и изменения слоя описывающего новый массив.
Давайте начнем с выделения. Мы можем использовать функцию new для выделения большего массива и в результате большего слоя, но будет проще использовать функцию make. Она выделяет новый массив и создает верхушку слоя. Функция make имеет три аргумента: тип слоя, начальная длинна и его мощность, где длина массива это то, что make выделяет для данных слоя. В результате этот вызов функции создает слой длинной 10 и возможностью расширения на 5 (15-10), что вы можете увидеть запустив это:
slice := make([]int, 10, 15) fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice)) Этот фрагмент удваивает мощность нашего int слоя, но оставляет такую-же длину:
slice := make([]int, 10, 15) fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice)) newSlice := make([]int, len(slice), 2*cap(slice)) for i := range slice { newSlice[i] = slice[i] } slice = newSlice fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice)) После этого слой имеет гораздо больше места для роста перед тем, как ему потребуется еще одно перераспределение.
При создании слоев часто бывает что длинна и мощность это одно и тоже. Функция make имеет сокращенный вариант. Длинна по умолчанию становится мощностью, поэтому вы можете указать их в одном значении. После
gophers := make([]Gopher, 10) у слоя gophers длинна и мощность будет равна 10.
Копирование
После того как мы удвоили мощность нашего слоя в предыдущем разделе, мы переписали цикл для копирования старых данных в новый слой. В Go есть встроенная функция copy, которая упрощает эту задачу. Её аргументы это два слоя и она копирует данные из правого в левый слой. Вот наш пример переписанный на использование copy:
newSlice := make([]int, len(slice), 2*cap(slice)) copy(newSlice, slice) Функция copy умная. Она копирует только то, что может, обращая внимание на длину обоих аргументов. Другими словами, количество элементов, которые будут скопированы, равно минимальной из длин обоих слоев. Это может сэкономить немного «бюрократии». Кроме того, copy возвращает целочисленное значение – количество элементов, которые были скопированы, хотя это не всегда стоит проверки.
Функция copy так-же учитывает случаи, когда источник и приемник пересекаются (прим. пер. это как memmove() в C), это означает что функция может быть использована для перемещения элементов внутри одного слоя. Ниже пример того, как с помощью функции copy вставить значение в середину слоя.
// Вставляет вставляемое значение в слой по указанному индексу, // который должен быть из определенного диапазона. // Слой должен иметь свободное место для нового элемента. func Insert(slice []int, index, value int) []int { // Увеличиваем слой на один элемент slice = slice[0 : len(slice)+1] // Используем copy для перемещения верхней части слоя наружу и создания пустого места copy(slice[index+1:], slice[index:]) // Записываем новое значение. slice[index] = value // Возвращаем результат. return slice } Есть несколько моментов, которые вы можете заметить в этой функции. Во первых, что очевидно, она должна вернуть слой, потому-что его длинна изменилась. Во вторых, используется удобное сокращение. Выражение
slice[i:] означает тоже самое, что и
slice[i:len(slice)] Кроме того, мы не использовали еще один трюк, мы так-же можем оставить первый элемент выражения пустым; по умолчанию это будет ноль. Таким образом
slice[:] Означает просто слой самого себя, что полезно при нарезании массива. Это выражение самый короткий пусть сказать: «слой, описывающий все элементы массива»:
array[:] Но это было между делом, давайте испытаем нашу функцию Insert.
slice := make([]int, 10, 20) // Заметим, что capacity > length: есть место для вставки элемента. for i := range slice { slice[i] = i } fmt.Println(slice) slice = Insert(slice, 5, 99) fmt.Println(slice) Вставка: Пример
Несколько разделов назад, мы написали функцию Extend, которая расширяла слой на один элемент. Она была неправильной, хотя бы по той причине, что в случае, когда мощность слоя была слишком маленькой, функция могла завершиться с ошибкой (в нашем примере функция Insert подвержена такой-же проблеме). Теперь мы знаем как это исправить, поэтому давайте напишем надежную реализацию функции Extend для целочисленных слоев.
func Extend(slice []int, element int) []int { n := len(slice) if n == cap(slice) { // Слой полон; должны расти. // Мы удвоили его размер и добавили 1, поэтому если размер равен нулю, мы по прежнему можем вырасти newSlice := make([]int, len(slice), 2*len(slice)+1) copy(newSlice, slice) slice = newSlice } slice = slice[0 : n+1] slice[n] = element return slice } В данном случае особенно важно вернуть слой, т. к. когда мы перераспределили его, слой который у нас получился описывает совершенно другой массив. Вот небольшой кусочек для демонстрации что произойдет, если слой заполнится:
slice := make([]int, 0, 5) for i := 0; i < 10; i++ { slice = Extend(slice, i) fmt.Printf("len=%d cap=%d slice=%v\n", len(slice), cap(slice), slice) fmt.Println("address of 0th element:", &slice[0]) } Обратите внимание на перераспределение, когда первоначальный массив размера 5 заполняется. Мощность и адрес нулевого элемента изменяются, когда выделяется новый массив.
Используя надежную функцию Extend в качестве основы, мы можем написать еще более лучшую функцию, которая позволит нам расширить слой несколькими элементами. Для этого воспользуемся возможностью Go по обращению списка аргументов в массив. То есть, мы используем возможность Go использовать переменное количество аргументов функции.
Давайте назовем функцию Append. Для первой версии, мы можем просто вызывать Extend до тех пор, пока не закончатся аргументы функции. Прототип функции Append выглядит так:
func Append(slice []int, items ...int) []int Это говорит нам о том, что Append берет один аргумент – слой, а за ним следует от нуля до бесконечности аргументов типа int. Эти элементы будущие кусочки слоя, как вы можете увидеть:
// Append добавляет элементы в слой. // Первая версия: просто циклически вызываем Extend. func Append(slice []int, items ...int) []int { for _, item := range items { slice = Extend(slice, item) } return slice } Заметьте что цикл for range выполняется для каждого элемента аргумента items, который имеет тип []int. Так-же заметьте использование пустого идентификатора _, который отбрасывает индекс, т. к. в цикле он нам не нужен.
Попробуйте это:
slice := []int{0, 1, 2, 3, 4} fmt.Println(slice) slice = Append(slice, 5, 6, 7, 8) fmt.Println(slice) Другой новый прием в этом примере это то, что инициализация слоя производится составным литералом, который состоит из типа и элементов слоя, заключенных в фигурные скобки:
slice := []int{0, 1, 2, 3, 4} Функция Append так-же интересна по другой причине. Мы можем не просто добавлять элементы, мы можем передавить в качестве аргументов функции целые слои используя …:
slice1 := []int{0, 1, 2, 3, 4} slice2 := []int{55, 66, 77} fmt.Println(slice1) slice1 = Append(slice1, slice2...) // '...' обязательно! fmt.Println(slice1) Конечно, мы можем сделать Append более эффективной, путем единичного выделения, опираясь на Extend:
// Append добавляет элементы в слой. // Эффективная версия. func Append(slice []int, elements ...int) []int { n := len(slice) total := len(slice) + len(elements) if total > cap(slice) { // Перераспределение. Увеличим размер в 1.5 раза, что позволит нам расти дальше. newSize := total*3/2 + 1 newSlice := make([]int, total, newSize) copy(newSlice, slice) slice = newSlice } slice = slice[:total] copy(slice[n:], elements) return slice } Обратите внимание, что здесь мы дважды используем copy, чтобы переместить слой данных в новый участок памяти и затем скопировать добавленные элементы в конец старых данных.
Попробуйте, поведение такое-же, как и прежде:
slice1 := []int{0, 1, 2, 3, 4} slice2 := []int{55, 66, 77} fmt.Println(slice1) slice1 = Append(slice1, slice2...) // '...' обязательно! fmt.Println(slice1) Append: Встроенная функция
Итак, мы пришли к выводу, что в Go нужно добавить встроенную функцию append. Она делает то-же самое, что и наша функция Append из примера, с одинаковой эффективностью, но работает для любого типа слоев.
Слабость Go заключается в том, что любая операция определенная на «общем-типе» должна быть предоставлена во время выполнения. Когда-нибудь это может измениться, но сейчас, дабы упростить работу со слоями, Go предоставляет встроенную общую функцию append. Она работает так-же как и наша целочисленная версия, но для любого типа слоя.
Помните что поскольку верхушка слоя обновляется каждый раз при вызове append, вам необходимо сохранить полученный слой после вызова. На самом деле, компилятор не позволит вам вызвать append без сохранения результата.
Вот некоторые однострочечники с выводом. Попробуйте их, изменяйте и исследуйте:
// Создаем пару начальных слоев. slice := []int{1, 2, 3} slice2 := []int{55, 66, 77} fmt.Println("Start slice: ", slice) fmt.Println("Start slice2:", slice2) // Добавляем элемент в слой. slice = append(slice, 4) fmt.Println("Add one item:", slice) // Добавляем один слой в другой. slice = append(slice, slice2...) fmt.Println("Add one slice:", slice) // Делаем копию слоя (int). slice3 := append([]int(nil), slice...) fmt.Println("Copy a slice:", slice3) // Копируем слой в конец самого себя. fmt.Println("Before append to self:", slice) slice = append(slice, slice...) fmt.Println("After append to self:", slice) Стоит остановится и подумать о последних строчках примера и понять как дизайн слоев позволяет делать такие простые вызовы правильными.
Существует множество примеров в вики (созданной сообществом) "Slice Tricks", использующих append, copy и других путей использования слоев.
Nil
Кроме того, используя новоприобретенные знания мы можем понять что из себя представляет «нулевой» (nil) слой. Естественно, это нулевое значение верхушки слоя:
sliceHeader{ Length: 0, Capacity: 0, ZerothElement: nil, } или просто
sliceHeader{} Ключевым является то, что указатель тоже равен nil. Данный слой
array[0:0] имеет нулевую длину (и может даже нулевую мощность), но его указатель не nil, поэтому это все еще не нулевой слой.
Очевидно, что пустой слой может расти (предполагая что он не нулевой мощности), но «нулевой» (nil) слой не содержит массива, куда можно положить значения и не может вырасти, даже для того, чтобы содержать хоть один элемент.
Стоит отметить, что «нулевой» (nil) слой, по сути дела, эквивалентен слою нулевой длины, даже если он ни на что не указывает. Он имеет нулевую длину и в него можно что-нибудь добавить с выделением. В качестве примера, посмотрите на несколько строчек выше, где копируется слой, добавляя «нулевой» (nil) слой.
Строки
Теперь кратко о строках в Go в контексте слоев.
На самом деле, строки очень просты: это слои байт только для чтения, с небольшой дополнительной синтаксической поддержкой со стороны языка.
Так как они только для чтения, у них нет мощности (вы не можете увеличить их), однако в большинстве случаев вы можете обращаться с ними как слоями байт.
Для начала, мы можем использовать индексацию, для доступа к отдельным байтам:
slash := "/usr/ken"[0] // записывает байт '/' Мы можем нарезать строку для создания подстроки:
usr := "/usr/ken"[0:4] // записывает строку "/usr" Должно быть очевидным то, что происходит за занавесом, когда мы нарезаем строку.
Так-же мы можем взять обычный слой байт и создать из него строку, путем простого преобразования:
str := string(slice) а так-же из строки сделать слой байт:
slice := []byte(usr) Массив лежащий в основе строк скрыт от глаз, нет никакого способа получить к нему доступ, кроме как через строку. Это значит, что когда мы делаем эти преобразования должна быть создана копия массива. Go берет на себя эту работу, так-что не волнуйтесь об этом. После любого подобного преобразования, изменение массива лежащего в основе слоя байт не влияет на соответствующую строку.
Важным следствием похожего поведения строк как слоев заключается в том, что создание подстроки происходит очень эффективно. Все что требуется, это создание двух верхушек строк. Так как строка только для чтения, то исходная строка и строка полученная в результате нарезки могут безопасно разделять один и тот-же массив.
Историческая справка: Ранние реализации строк всегда отдельно выделялись, но с тех пор в языке появились слои, которые предоставили возможность создания более эффективной работы со строками. Некоторые бенчмарки стали показывать огромный прирост скорости.
Конечно, есть много еще того что стоит рассказать о строках, но эта тема для другой публикации.
Заключение
Понимание принципов работы слоев, помогает понять как они сделаны. Есть небольшая структура данных, верхушка слоя, связанная с переменной типа слой и эта верхушка описывает часть отдельно выделенного массива. Когда мы создаем слой, то заголовок копируется, но массив всегда разделяется.
После того, как вы оцените их работу, слои станут не только простыми в использовании, но мощными и выразительными, особенно с помощью встроенных функций copy и append.
ссылка на оригинал статьи http://habrahabr.ru/post/202948/
Добавить комментарий