Slice ב-Golang: append, make, len מול cap ובאג השיתוף

slice בדוגמה אחת

slice הוא תצוגה על מערך שיכולה לגדול. יוצרים אותו עם ליטרל או עם make, מגדילים אותו עם append, וקוראים את הגודל שלו עם len.

package main

import "fmt"

func main() {
	langs := []string{"Go", "Rust"}
	langs = append(langs, "Zig", "C")
	fmt.Println(langs, len(langs))

	for i, l := range langs {
		fmt.Println(i, l)
	}

	fmt.Println(langs[1:3]) // elements 1 and 2
}

ל-[]string אין אורך בתוך הסוגריים המרובעים. זה ההבדל מטיפוס מערך כמו [4]string, שהגודל שלו קבוע.

מה זה slice

ערך של slice הוא header קטן עם שלושה שדות:

• מצביע לאיבר במערך שמתחת
• אורך: כמה איברים ה-slice רואה
• קיבולת: כמה איברים קיימים מהמצביע הזה ועד סוף המערך שמתחת

העתקה של slice (הצבה שלו, העברה שלו לפונקציה) מעתיקה רק את ה-header הזה. שני העותקים מצביעים על אותם איברים. כמעט כל הפתעה עם slices נובעת משכחה של זה.

make: אורך וקיבולת

make([]T, len, cap) מקצה מערך שמתחת ומחזירה slice עליו. הקיבולת היא אופציונלית וברירת המחדל שלה היא האורך.

package main

import "fmt"

func main() {
	a := make([]int, 3) // len 3, cap 3, all zeros
	fmt.Println(a, len(a), cap(a))

	b := make([]int, 0, 10) // len 0, room for 10
	fmt.Println(b, len(b), cap(b))

	for i := range 5 {
		b = append(b, i*i)
	}
	fmt.Println(b, len(b), cap(b)) // no reallocation happened
}

בלבול נפוץ: make([]int, 5) ואחריו חמש קריאות append נותנים עשרה איברים, שחמשת הראשונים מהם הם אפס. השתמשו ב-make([]int, 0, 5) כשמתכננים להוסיף עם append, או ב-make([]int, 5) כשמתכננים להציב לפי אינדקס.

הקצאה מראש של קיבולת כשהגודל הסופי ידוע חוסכת גדילות חוזרות. זו אופטימיזציה, לא דרישה.

append וגדילה

append מוסיפה איברים אחרי האורך הנוכחי. אם הקיבולת גדולה מספיק, היא כותבת במקום. אם לא, היא מקצה מערך גדול יותר, מעתיקה אליו את האיברים הישנים ומחזירה slice שמצביע על המערך החדש.

package main

import "fmt"

func main() {
	var s []int
	prevCap := cap(s)
	for i := range 2000 {
		s = append(s, i)
		if cap(s) != prevCap {
			fmt.Printf("len %4d  cap %4d\n", len(s), cap(s))
			prevCap = cap(s)
		}
	}
}

הקיבולת בערך מוכפלת כל עוד ה-slice קטן, וגדלה בפקטור קטן יותר (שמתקרב ל-1.25x) אחרי שהוא עובר 256 איברים. המספרים המדויקים הם פרט של סביבת הריצה שהשתנה בין גרסאות של Go, אז לעולם אל תכתבו קוד שתלוי בהם.

מכיוון ש-append עשויה להחזיר מערך אחר, חייבים להשתמש בתוצאה שלה:

append(s, 4)     // compile error: append(s, 4) (value of type []int) is not used
s = append(s, 4) // correct

הוספה של slice שלם משתמשת בתחביר הפריסה: s = append(s, other...).

חיתוך משתף את המערך שמתחת

s[low:high] יוצר header חדש של slice על אותו מערך, שמכסה את האינדקסים מ-low ועד high לא כולל. אפשר להשמיט כל אחד מהגבולות. שום איבר לא מועתק.

package main

import "fmt"

func main() {
	nums := []int{10, 20, 30, 40, 50}
	mid := nums[1:4] // 20 30 40
	mid[0] = 99
	fmt.Println(nums) // the write shows up in nums

	fmt.Println(len(mid), cap(mid)) // cap runs to the end of nums
}

פלט:

[10 99 30 40 50]
3 4

השיתוף הזה הוא מה שהופך חיתוך לזול. הוא גם המקור לבאג המפורסם ביותר של slices.

באג ה-aliasing של append

כשלתת slice יש קיבולת פנויה, append אליו כותב לתוך המערך של ההורה, מעל איברים שההורה עדיין משתמש בהם.

package main

import "fmt"

func main() {
	base := []int{1, 2, 3, 4, 5}
	first := base[:2] // [1 2], cap 5

	first = append(first, 100) // fits in capacity: overwrites base[2]
	fmt.Println(base)
	fmt.Println(first)

	// Two slices built from the same prefix clobber each other.
	prefix := make([]string, 0, 4)
	prefix = append(prefix, "cmd")
	a := append(prefix, "build")
	b := append(prefix, "test")
	fmt.Println(a, b) // both print test
}

פלט:

[1 2 100 4 5]
[1 2 100]
[cmd test] [cmd test]

a ו-b חולקים את המקום במערך שאחרי "cmd", ולכן ה-append השני דרס את הראשון. הקוד נראה תקין ועובד בכל פעם שהקיבולת במקרה מלאה, ולכן הבאג הזה מופיע רק לפעמים.

שני תיקונים:

1. ביטוי החיתוך המלא s[low:high:max] מגביל את הקיבולת ל-max-low. בלי קיבולת פנויה, ה-append הבא חייב להקצות. first := base[:2:2] הופך את הדוגמה הראשונה לבטוחה.
2. העתיקו במפורש כש-slice יחיה יותר מהקריאה או שיוסיפו אליו באופן עצמאי: slices.Clone(prefix) או append([]string(nil), prefix...).

מלכודת קרובה: slice קטן של מערך ענק שומר את כל המערך בחיים מבחינת ה-garbage collector. אם קוראים קובץ של 100 MB ושומרים את data[:10], ה-100 MB נשארים בזיכרון. שכפלו את החלק שאתם שומרים.

copy

הפונקציה המובנית copy(dst, src) מעתיקה min(len(dst), len(src)) איברים ומחזירה את המספר הזה. היא אף פעם לא מגדילה את dst.

package main

import (
	"fmt"
	"slices"
)

func main() {
	src := []int{1, 2, 3}

	dst := make([]int, len(src))
	n := copy(dst, src)
	dst[0] = 100
	fmt.Println(n, src, dst) // independent

	var empty []int
	fmt.Println(copy(empty, src)) // 0: dst has no length

	c := slices.Clone(src) // the one-line version (Go 1.21)
	fmt.Println(c)
}

copy מטפלת נכון במקור וביעד שחופפים, כך ש-copy(s[1:], s) מזיזה איברים קדימה בלי להשחית אותם.

החבילה slices

מאז Go 1.21 לחבילה הסטנדרטית slices יש פונקציות עזר גנריות לפעולות שפעם כתבו ביד.

package main

import (
	"fmt"
	"slices"
)

func main() {
	s := []int{5, 2, 8, 2, 9}

	fmt.Println(slices.Contains(s, 8)) // true
	fmt.Println(slices.Index(s, 2))    // 1
	fmt.Println(slices.Max(s), slices.Min(s))

	slices.Sort(s)
	fmt.Println(s)
	i, found := slices.BinarySearch(s, 8)
	fmt.Println(i, found)

	s = slices.Compact(s) // drop adjacent duplicates
	fmt.Println(s)

	s = slices.Delete(s, 1, 2) // remove index 1
	fmt.Println(s)

	s = slices.Insert(s, 1, 3, 4)
	fmt.Println(s)

	slices.Reverse(s)
	fmt.Println(s, slices.Equal(s, []int{9, 8, 4, 3, 2}))
}

Delete ו-Insert מחזירות slice שחייבים להציב, כמו append. למיון יש דף משלו: מיון.

הסרת איברים תוך כדי לולאה לפי אינדקס מדלגת על איברים. השתמשו במקום זה ב-slices.DeleteFunc:

s = slices.DeleteFunc(s, func(n int) bool { return n%2 == 0 }) // drop evens

slices דו ממדיים

slice של slices נותן רשת שהשורות שלה יכולות להיות באורכים שונים. צריך להקצות כל שורה בנפרד.

package main

import "fmt"

func main() {
	rows, cols := 3, 4
	grid := make([][]int, rows)
	for r := range grid {
		grid[r] = make([]int, cols)
	}
	grid[1][2] = 7

	for _, row := range grid {
		fmt.Println(row)
	}

	// Rows of different lengths are fine.
	triangle := [][]int{{1}, {1, 1}, {1, 2, 1}}
	fmt.Println(triangle)
}

שכחה של ה-make הפנימי משאירה כל שורה nil, ו-grid[1][2] = 7 גורם ל-panic עם index out of range [2] with length 0.

slices שהם nil ו-slices ריקים

package main

import (
	"encoding/json"
	"fmt"
)

func main() {
	var a []int  // nil
	b := []int{} // empty, not nil

	fmt.Println(len(a), len(b), a == nil, b == nil)

	a = append(a, 1) // append works on nil
	fmt.Println(a)

	ja, _ := json.Marshal(struct{ Items []int }{})
	jb, _ := json.Marshal(struct{ Items []int }{Items: []int{}})
	fmt.Println(string(ja), string(jb))
}

slice שהוא nil מתנהג כמו slice ריק עבור len, cap, range ו-append, אז העדיפו var s []T כמצב ההתחלתי. אתחלו ל-[]T{} רק כשההבדל משנה, בעיקר בפלט JSON (null מול []). בדקו ריקנות עם len(s) == 0, לא עם s == nil.

slices ופונקציות

פונקציה שמקבלת slice יכולה לשנות את האיברים שלו, והקורא רואה את השינויים. היא לא יכולה לשנות את האורך אצל הקורא, כי היא קיבלה עותק של ה-header. פונקציה שמוסיפה איברים חייבת להחזיר את ה-slice החדש:

func addAll(s []int, vals ...int) []int {
	return append(s, vals...)
}

זו הסיבה ש-append, slices.Delete ו-slices.Insert כולן מחזירות slice.

טעויות נפוצות

• התעלמות מהתוצאה של append. זה לא מתקמפל כשזורקים אותה לגמרי, אבל append(s, x) שמוצב למשתנה אחר מזה שממשיכים להשתמש בו הוא באג לוגי.
• שני appends מאותו בסיס. הם עשויים לחלוק אחסון. שכפלו את הבסיס או השתמשו בביטוי חיתוך מלא.
• make([]T, n) ואחריו append. משאיר n אפסים בהתחלה.
• אינדקס מחוץ לטווח. s[len(s)] גורם ל-panic. האיבר האחרון הוא s[len(s)-1].
• השוואת slices עם ==. רק s == nil מתקמפל. השתמשו ב-slices.Equal.