# 什么是内存逃逸
在Go语言中，内存分配有两种方式：栈分配和堆分配。栈分配是在函数调用时为局部变量分配内存，当函数返回时，这些内存会自动释放。而堆分配则是通过 new 或者 make 函数动态分配内存，需要手动进行释放。

内存逃逸是指原本应该在栈上分配的内存被分配到了堆上。这意味着即使函数返回后，这部分内存也不会被自动释放，需要等待垃圾回收器来回收。

# 内存逃逸的影响
如果频繁发生内存逃逸，会导致程序占用过多的内存资源，影响程序的性能和稳定性。主要体现在以下几个方面：

内存占用增加：由于堆分配的内存不会自动释放，所以会导致程序占用的内存资源不断增加，特别是在长时间运行的程序中，可能会导致系统资源耗尽。
性能下降：相比于栈分配，堆分配需要更多的 CPU 和内存资源，因此会导致程序的运行速度变慢。
程序不稳定：如果程序中存在大量的内存逃逸，可能会导致垃圾回收器频繁工作，从而影响程序的稳定性。
# 内存逃逸的原因
内存逃逸的主要原因是在函数返回后，局部变量仍然被外部引用。以下是一些可能导致内存逃逸的情况：

变量的生命周期超出了其作用域，当一个变量在函数外部被引用，比如被赋值给一个包级别的变量或者作为返回值，这个变量就会发生逃逸。
大对象的分配，对于大型的数据结构，Go 有时会选择在堆上分配内存，即使它们没有在函数外部被引用。
闭包引用，如果一个函数返回一个闭包，并且该闭包引用了函数的局部变量，那么这些变量也会逃逸到堆上。
接口动态分配，当一个具体类型的变量被赋值给接口类型时，由于接口的动态特性，具体的值可能会发生逃逸。
切片和 map 操作，如果对切片进行操作可能导致其重新分配内存，或者向 map 中插入数据，这些操作可能导致逃逸。
# 内存逃逸的检测
Go 提供了一个内置的工具来检测内存逃逸，即 go build 命令的 “-gcflags '-m'” 选项。使用这个选项编译程序，编译器会输出内存逃逸的分析信息。

例如，可以使用以下命令来分析你的程序：

go build -gcflags '-m' main.go
编译器会输出关于哪些变量发生了逃逸的详细信息。

另外可以通过 go tool pprof 来分析程序的内存使用情况，通过结合使用r untime.MemProfile 和 pprof，可以检测和分析内存逃逸现象。

# 解决方法
以下是在 Go 语言中避免内存逃逸的一些常见方法：

### 1. 局部变量尽量在栈上分配
    - 保持短小的函数，避免在函数内部创建过大的对象。
    - 对于较小且不会被外部引用的变量，尽量在函数内部使用值类型，而非指针类型。

### 2. 避免在函数中返回指针指向函数内的局部变量
    - 如果需要返回数据，优先返回值类型，而非指针。

### 3. 减少使用闭包
    - 闭包可能会捕获外部变量，导致这些变量逃逸到堆上。

### 4. 合理使用字符串拼接
    - 避免频繁的小字符串拼接操作，以免产生大量临时字符串对象。可以使用 `strings.Builder` 进行高效的字符串拼接。

### 5. 谨慎使用接口
    - 当实现接口时，如果对象较大且不需要在不同的函数间共享，尽量避免使用接口类型。

### 6. 数据结构优化
    - 例如，使用切片时，如果预先知道其长度，应指定容量，避免不必要的内存重新分配。

### 7. 避免在循环中分配内存
    - 不要在循环体内部频繁地创建新的对象。

通过遵循上述原则，并结合对代码的性能分析和优化，可以有效地减少内存逃逸，提高程序的性能和内存使用效率。

golang中怎么避免内存逃逸？

# 冒泡排序

```go
func bubble_sort(array []int, sz int) {
	for i := 0; i < sz-1 ; i++ {
		for j := 0; j < sz-1-i; j++ {
			if array[j] > array[j+1] {
				array[j], array[j+1] = array[j+1], array[j]
			}
		}
	}
}
```

# 选择排序

```go
func select_sort(arr []int, sz int) {
	var i int = 0
	var j int = 0
	for i = 0; i < sz; i++ {
		var min int = i
		for j=i+1; j < sz; j++ {
			if arr[j] < arr[min] {
				min = j
			}
		}
		arr[i], arr[min] = arr[min], arr[i]
	}
}
```
# 插入排序

```go
func insert_sort(arr []int, sz int) {
	sortNum := 0
	i := 0
	j := 0
	for i=0; i<sz; i++ {
		sortNum = arr[i]
		// 找插入的地方
		for j=i-1; j>=0; j-- {
			if arr[j] < sortNum {
				break
			}
			arr[j+1] = arr[j]
		}
		arr[j+1] = sortNum
	}
}
```

# 希尔排序

```go
func shell_sort_in_group(arr []int, sz int, pos int, step int) {
	sortNum := 0
	i := 0
	j := 0
	for i=pos+step; i<sz; i+=step {
		// pos + step 就是该组的第一个元素的位置
		// 例如：当pos==0的时候，该组的第一个元素就是整个序列的第一个元素
		// 当pos==1的时候，该组第一个元素就是这个那个序列的第二个元素
		sortNum = arr[i]
		for j=i-step; j>=0; j-=step {
			if arr[j] < sortNum {
				break
			}
			arr[j+step] = arr[j]
		}
		arr[j+step] = sortNum
	}
}
func shell_sort(arr []int, sz int) {
	i := 0
	step := 0 // 希尔间隔
	for step = sz/2; step>0; step/=2 {
		// 步长为step，即共有istep个组，对每一组都执行插入排序
		for i=0; i<step; i++ {
			// 每一组的组排序就是插入排序的稍微修改的版本
			shell_sort_in_group(arr, sz, i, step)
		}
	}
}

```

# 快速排序

```go
func quick_sort_part_sort1(arr []int, begin int, end int) int {
	// Hoare思想
	left := begin
	right := end
	keyi := left
	for left < right {
		// 右边走，找小
		for left < right && arr[right] >= arr[keyi] {
			right--
		}
		// 左边走，找大
		for left < right && arr[left] <= arr[keyi] {
			left++
		}
		arr[left], arr[right] = arr[right], arr[left]
	}
	arr[keyi], arr[right] = arr[right], arr[keyi]
	keyi = left
	return keyi
}
func quick_sort_part_sort2(arr []int, begin int, end int) int {
	// 挖坑法
	key := arr[begin]
	piti := begin
	for begin < end {
		// 右边找小的，填到左边的坑里面去，这个位置形成新的坑
		for begin < end && arr[end] >= key {
			end--
		}
		arr[piti] = arr[end]
		piti = end
 
		// 左边找大的，填到右边的坑里面去，这个位置形成新的坑
		for begin < end && arr[begin] <= key {
			begin++
		}
		arr[piti] = arr[begin]
		piti = begin;
	}
	arr[piti] = key
	return piti
}
func quick_sort_by_interval(arr []int, begin int, end int) {
	if begin >= end {
		return // 区间不存在
	}
	keyi := quick_sort_part_sort1(arr, begin, end)
	quick_sort_by_interval(arr, begin ,keyi-1)
	quick_sort_by_interval(arr, keyi+1, end)
}
func quick_sort(arr []int, sz int) {
	begin := 0
	end := sz - 1
	quick_sort_by_interval(arr, begin ,end)
}
```


# 堆排序

```go
func heap_sort_adjust_down(arr []int, size int, parent int) {
	child := parent*2+1
	for child < size {
		// 选出左右孩子中小/大的那个
		if child + 1 < size && arr[child+1] > arr[child] {
			child++
		}
		// 孩子和父亲比较
		if arr[child] > arr[parent] {
			arr[child], arr[parent] = arr[parent], arr[child]
			parent = child
			child = parent*2 + 1
		} else {
			break
		}
	}
}
func heap_sort(arr []int, sz int) {
	for i:=(sz-1-1)/2; i>=0; i-- {
		heap_sort_adjust_down(arr, sz, i)
	}
	// 
	end := sz-1
	for end > 0 {
		arr[0],arr[end] = arr[end],arr[0]
		heap_sort_adjust_down(arr, end, 0)
		end--
	}
}
```

# 归并排序

```go
func merge_sort_by_group(arr []int, begin int, end int, tmp_array []int){
	if begin >= end {
		return
	}
	mid := (begin + end) / 2
	// [begin,mid][mid+1,end]分治递归，让子区间有序
	merge_sort_by_group(arr, begin, mid, tmp_array)
	merge_sort_by_group(arr, mid+1, end, tmp_array)
	// 归并[begin,mid][mid+1,end]
	begin1 := begin; end1 := mid;
	begin2 := mid+1; end2 := end;
	i := begin1
	for begin1 <= end1 && begin2 <= end2 {
		if arr[begin1] < arr[begin2] {
			tmp_array[i] = arr[begin1]
			i++
			begin1++
		} else {
			tmp_array[i] = arr[begin2]
			i++
			begin2++
		}
	}
	for begin1 <= end1 {
		tmp_array[i] = arr[begin1]
		i++
		begin1++
	}
	for begin2 <= end2 {
		tmp_array[i] = arr[begin2]
		i++
		begin2++
	}
	//把归并后的数据拷贝回原来的数组
	copy(arr[begin:end+1], tmp_array[begin:end+1])
}
func merge_sort(arr []int, sz int) {
	tmp_array := make([]int, sz) // 创建一个大小为sz的整数数组并初始化为0
	merge_sort_by_group(arr, 0, sz-1, tmp_array)
}
```

# 基数排序

```go
var (
	K int = 3 // 基数排序需要的全局变量
	RADIX int = 10
	queue [][]int
)
func radix_sort_queue_pop(qu []int) []int {
    if len(qu) == 0 {
        return qu // 如果数组为空，不做任何操作
    }
    // 删除第一个元素
    qu = qu[1:]
    return qu
}
func radix_sort_queue_push(qu []int, data int) []int {
	qu = append(qu, data)
	return qu
}
func radix_sort_get_key(value int, k int) int {
	key := 0
	for k >= 0 {
		key = value % 10
		value /= 10
		k--
	}
	return key
}
func radix_sort_distribute(arr []int, left int, right int, k int){
	// k表示是第几次分发数据
	for i:=left; i<right; i++ {
		key := radix_sort_get_key(arr[i], k)
		queue[key] = radix_sort_queue_push(queue[key], arr[i])
	}
}
func radix_sort_collect(arr []int) {
	k := 0
	for i:=0; i < RADIX; i++ {
		for len(queue[i]) != 0 {
			arr[k] = queue[i][0] // 先进先出
			k++
			queue[i] = radix_sort_queue_pop(queue[i])
		}
	}
}
func radix_sort_by_group(arr []int, left int, right int) {
	for i:=0; i<K; i++ {
		// 分发数据
		radix_sort_distribute(arr, left, right, i)
		// 回收数据
		radix_sort_collect(arr)
	}
}
func radix_sort(arr []int, sz int) {
	// 初始化队列
	queue = make([][]int, RADIX)
	left := 0
	right := sz;
	radix_sort_by_group(arr, left, right)
}

```


Go语言实现八大排序

在网上看到的比较考验思路的题，学习学习罢-
## 题目
假设有一个超长的切片，切片的元素类型为int，切片中的元素为乱序排序。限时5秒，使用多个goroutine查找切片中是否存在给定的值，在查找到目标值或者超时后立刻结束所有goroutine的执行。

比如，切片 [23,32,78,43,76,65,345,762,......915,86]，查找目标值为 345 ，如果切片中存在，则目标值输出"Found it!"并立即取消仍在执行查询任务的goroutine。

如果在超时时间未查到目标值程序，则输出"Timeout！Not Found"，同时立即取消仍在执行的查找任务的goroutine。



## 题解
思路：

首先创建一个通道来通知所有的 Goroutine 停止执行。

启动多个 Goroutine 来并行地在切片中查找目标值。

使用 time.After 创建一个超时通道，当超时发生时，通过停止通道通知所有 Goroutine 停止。

每个 Goroutine 在找到目标值时，通过停止通道通知其他 Goroutine 停止，并输出结果。


```go
package main

import (
    "context"
    "fmt"
    "os"
    "time"
)

func main() {
    timer := time.NewTimer(time.Second * 5)
    data := []int{1, 2, 3, 10, 999, 8, 345, 7, 98, 33, 66, 77, 88, 68, 96}
    dataLen := len(data)
    size := 3
    target := 345
    ctx, cancel := context.WithCancel(context.Background())
    resultChan := make(chan bool)
    for i := 0; i < dataLen; i += size {
        end := i + size
        if end >= dataLen {
            end = dataLen - 1
        }
        go SearchTarget(ctx, data[i:end], target, resultChan)
    }
    select {
    case <-timer.C:
        fmt.Fprintln(os.Stderr, "Timeout! Not Found")
        cancel()
    case <- resultChan:
        fmt.Fprintf(os.Stdout, "Found it!\n")
        cancel()
    }

    time.Sleep(time.Second * 2)
}

func SearchTarget(ctx context.Context, data []int, target int, resultChan chan bool) {
    for _, v := range data {
        select {
        case <- ctx.Done():
            fmt.Fprintf(os.Stdout, "Task cancelded! \n")
            return
        default:
        }
        // 模拟一个耗时查找，这里只是比对值，真实开发中可以是其他操作
        fmt.Fprintf(os.Stdout, "v: %d \n", v)
        time.Sleep(time.Millisecond * 1500)
        if target == v {
            resultChan <- true
            return
        }
    }

}
```

多协程查询切片问题

# **指针**
### 可变和不可变数据

Python 里面是没有指针的概念的，所以学习到 Go 的指针这个章节的时候我一直都是一知半解的，虽然看了不少资料也问了 ChatGPT 很多次，但是到现在也还没完全弄清楚到底什么时候应该用指针什么时候不能使用指针。

Go 语言拥有四类主要的数据类型：

**基本类型：**
涵盖了各种数字类型（如整数类型的 int、uint 等，浮点数类型的 float32、float64 等）、字符串类型（用于表示文本数据）以及布尔类型（true 和 false 两种取值，用于表示逻辑条件）。



**聚合类型：**
其中包括数组（具有固定长度且元素类型相同的有序集合）和结构体（将不同类型的数据组合在一起形成的自定义复合数据类型）。

**引用类型：**
包含了指针（用于指向其他变量的内存地址）、切片（动态大小的数组视图）、映射（键值对的数据结构）、函数（可作为参数传递和返回）以及通道（用于 goroutine 之间的通信）。

**接口类型：**
接口定义了一组方法的签名，任何类型只要实现了这些方法就满足该接口。

在 Python 中，对于数据类型存在可变类型和不可变类型的划分。这种可变和不可变的特性实际上与 Go 语言中的指针存在一定的关联。具体来说，当将一个变量作为参数传递给一个函数时，如果在函数内部能够直接修改这个变量本身，那么它就是可变类型；反之，如果在函数内部无法修改该变量本身，那它就是不可变类型。

例如，在 Python 中，以下被视为不可变类型：数字（如整数和浮点数）、字符串（一旦创建其内容无法更改）、元组（元素固定且不可修改）、布尔值等。而像列表、字典和集合等则属于可变类型。

关于在什么场景下应该使用指针，以下是两种常见的情况：
第一种情况，当传递的参数不允许直接被修改，但又希望在函数内部能够改变其值时，使用指针就能够实现对参数本身值的修改。这在需要对传入的参数进行原地修改以达到某种效果的场景中非常有用。

第二种情况，如果传递的参数是大规模的数据，直接传递值会导致大量的内存拷贝，从而带来显著的性能开销。此时，使用指针进行传递可以有效地避免这种值拷贝的操作，减少内存消耗和提高程序的运行效率。

场景1的例子很容易理解：

```go
func modifyValue(value int) {
    // 修改不会影响原始值
    value = 100
}

func modifyWithPointer(ptr *int) {
    // 修改会影响原始值
    *ptr = 100
}

func main() {
    x := 42
    modifyValue(x)
    fmt.Println(x) // 输出: 42

    y := 42
    modifyWithPointer(&y)
    fmt.Println(y) // 输出: 100
}
```

整数本身是一种不可变类型，但是通过指针，就是在函数中修改这个变量本身，这个在 Python 里面是无法做到的，这也是很典型的一个指针使用场景。

场景2的例子：

```go
package main

import "fmt"

func modifyLargeData(data *[]int) {
    // 在函数内部修改大型切片
    for i := range *data {
        (*data)[i] *= 2
    }
}

func main() {
    // 创建一个大型切片
    largeData := make([]int, 1000000)
    for i := range largeData {
        largeData[i] = i + 1
    }

    // 通过指针传递大型切片
    modifyLargeData(&largeData)

    // 打印修改后的切片部分内容
    fmt.Println(largeData[:10]) // 输出: [2 4 6 8 10 12 14 16 18 20]
}
```

在这个例子中，modifyLargeData 函数接收一个指向大型切片的指针，并在函数内部修改了切片的值。通过传递指针而不是切片本身，避免了将整个大型切片复制到函数内部的开销，提高了程序的性能。

需要注意的是，这样的优化一般在处理大型数据时才会显著体现。在处理小型数据或者基本类型时，Go 的值传递通常也足够高效。

哪些场景可以不用指针

**1、只使用参数的值**

很多时候函数只需要使用参数的值，而不需要修改参数本身，此时可以不用指针。

**2、传递可修改的类型**

切片、映射、结构体、通道： 这些引用类型本身已经具有引用传递的特性，传递它们时无需使用指针。函数内对切片、映射或通道的修改会影响原始数据。

```go
func modifySlice(slice []int) {
    // 修改会影响原始切片
    slice[0] = 100
}

func main() {
    data := []int{1, 2, 3}
    modifySlice(data)
    fmt.Println(data) // 输出: [100 2 3]
}
```

这其实跟 Python 一样，这种可变类型被当做参数传递到函数里面，在函数内部修改参数会导致参数本身被修改。

# **Map**
Map 就等于 Python 里面的字典，只是由于 Go 语言对于类型的要求，必须在定义的时候定义好 Map 的键值对的类型，这个不如 Python 灵活（当然，我后面学习到空接口就知道了 Go 也有比较灵活的类型）。

如下就是一个值可以是任意类型的 map 的例子：

```go
package main

import "fmt"

func main() {
    m1 := map[string]interface{}{}
    fmt.Println(m1)

    m2 := make(map[string]interface{})
    fmt.Println(m2)
}
```

Map 也是无序的，这个跟 Python 一样。

# **结构体**
结构体就是 Python 里面类的概念。构造函数要自己实现，构造函数可以返回类的实例的指针，也可以直接返回类的实例。

Python 里面类的函数在 Go 里面使用方法实现，方法的接受者就是类的指针，可以理解为 Python 里面的 self 的作用。

将 Go 的代码跟 Python 代码对照着看就会很清晰：

```Go
package main

import "fmt"

// Animal 类型
type Animal struct {
    Name string
}

// NewAnimal 初始化方法，返回指针
func NewAnimal(name string) *Animal {
    return &Animal{Name: name}
}

// makeSound 方法，用于发出声音
func (a *Animal) makeSound() {
    fmt.Printf("%s makes some generic animal sound\n", a.Name)
}

// Dog 类型，继承自 Animal
type Dog struct {
    *Animal
    Speed int
}

// NewDog 初始化方法，返回指针
func NewDog(name string, speed int) *Dog {
    return &Dog{Animal: NewAnimal(name), Speed: speed}
}

// makeSound 方法的重写，对于 Dog 类型
func (d *Dog) makeSound() {
    fmt.Printf("%s says Woof! Woof!\n", d.Name)
}

// run 方法，用于表示狗狗跑的行为
func (d *Dog) run() {
    fmt.Printf("%s is running at speed %d km/h\n", d.Name, d.Speed)
}

func main() {
    // 使用例子
    animal := NewAnimal("Generic Animal")
    animal.makeSound() // 输出: Generic Animal makes some generic animal sound

    dog := NewDog("Buddy", 20)
    dog.makeSound() // 输出: Buddy says Woof! Woof!
    dog.run()       // 输出: Buddy is running at speed 20 km/h
}
```


```python
class Animal:
    def __init__(self, name):
        self.name = name

    def make_sound(self):
        print(f"{self.name} makes some generic animal sound")

class Dog(Animal):
    def __init__(self, name, speed):
        super().__init__(name)
        self.speed = speed

    def make_sound(self):
        print(f"{self.name} says Woof! Woof!")

    def run(self):
        print(f"{self.name} is running at speed {self.speed} km/h")

# 使用例子
animal = Animal("Generic Animal")
animal.make_sound()  # 输出: Generic Animal makes some generic animal sound

dog = Dog("Buddy", 20)
dog.make_sound()     # 输出: Buddy says Woof! Woof!
dog.run()            # 输出: Buddy is running at speed 20 km/h
```