零、内容

https://github.com/EndlessCheng/codeforces-go/blob/master/leetcode/README.md

一、相向双指针

https://www.bilibili.com/video/BV1bP411c7oJ?spm_id_from=333.788.videopod.sections&vd_source=61d0ab7742b04564fc1fbeb00533f72e 题单：

1. 167. 两数之和 II - 输入有序数组 https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solution/san-shu-zhi-he-bu-hui-xie-xiang-xiang-sh-6wbq/
2. 15. 三数之和 https://leetcode.cn/problems/3sum/solution/shuang-zhi-zhen-xiang-bu-ming-bai-yi-ge-pno55/

两数之和2-输入为有序数组

• 题目背景：在一个有序数组中，找到两个数，使它们的和等于目标值。
• 核心算法：使用“相向双指针”技巧。左指针从头，右指针从尾，根据当前和与目标值的关系移动指针，时间复杂度为 O(n)。

1. 随便找两个数组 eg 3 & 8，
2. 3+8 = 11 > 9
3. 那么3和 3 - 8 中间的数加起来也大于 11 （同样大于9）
4. 那么把 8 去掉（右指针向前移动 ）
5. 或者
6. 2+6 = 8 < 9
7. 那么2 和 2-6 中间的数加起来也都小于 8 （同样小于9）
8. 那么把2 去掉（左指针向后移动）

TODO

func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1
    for {
        s := numbers[left] + numbers[right]
        if s == target {
            return []int{left + 1, right + 1} // 题目要求下标从 1 开始
        }
        if s > target {
            right--
        } else {
            left++
        }
    }
}

三数之和

• 题目背景：在一个数组中，找到所有和为 0 的三元组。
• 核心算法：先对数组排序，然后固定一个数，剩下的用双指针法寻找另外两个数。注意去重处理，避免重复三元组，时间复杂度为 O(n²)。

G M P 模型

一句话：调度器调度任务队列、P在M上运行去执行G

两个任务队列 - 全局任务队列 - P本地队列 调度器

总览

​ 1、我们通过 go func () 来创建一个 goroutine；

​ 2、有两个存储 G 的队列，一个是局部调度器 P 的本地队列、一个是全局 G 队列。新创建的 G 会先保存在 P 的本地队列中，如果 P 的本地队列已经满了就会保存在全局的队列中；

​ 3、G 只能运行在 M 中，一个 M 必须持有一个 P，M 与 P 是 1：1 的关系。M 会从 P 的本地队列弹出一个可执行状态的 G 来执行，如果 P 的本地队列为空，就会向其他的 MP 组合偷取一个可执行的 G 来执行；

​ 4、一个 M 调度 G 执行的过程是一个循环机制；

​ 5、当 M 执行某一个 G 时候如果发生了 syscall 或则其余阻塞操作，M 会阻塞，如果当前有一些 G 在执行，runtime 会把这个线程 M 从 P 中摘除 (detach)，然后再创建一个新的操作系统的线程 (如果有空闲的线程可用就复用空闲线程) 来服务于这个 P；

// The Interface type describes the requirements
// for a type using the routines in this package.
// Any type that implements it may be used as a
// min-heap with the following invariants (established after
// [Init] has been called or if the data is empty or sorted):
//
//	!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
//
// Note that [Push] and [Pop] in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use [heap.Push] and [heap.Pop].
type Interface interface {
	sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

初始化一个堆

MVCC（多版本并发控制） 是一种数据库并发控制机制，用于管理多个事务并发操作时，确保事务的 隔离性 和 一致性。在 MySQL InnoDB 存储引擎中，MVCC 是实现 事务隔离 和 高并发 数据访问的关键技术之一。MVCC 允许多个事务在 不冲突 的情况下并发执行，同时保证每个事务的 数据一致性。

1. MVCC 的工作原理

MVCC 通过 维护数据的多个版本 来实现高并发控制，而不是像传统的锁机制那样阻塞事务，MVCC 通过给每个事务分配 快照 来实现并发读写。

1.1. 事务的隔离性

在 MVCC 中，每个事务都有一个 独立的视图（Read View），它表示当前事务看到的数据版本。这确保了不同的事务可以并发执行，但又不互相影响，避免了 脏读、不可重复读 和 幻读 问题。

1.2. 如何维护多个版本的记录

• InnoDB 会为每个数据行维护多个版本，这些版本用于支持多个事务并发执行。每个修改操作会创建数据的一个新的版本。

• 每个版本的数据行都会包含 事务 ID 和 回滚标识（Undo Log），这些信息有助于数据库确定该数据是否对当前事务可见。

例如，在更新操作时，更新前的版本 保留在 Undo Log 中，而新的版本会出现在 数据表中。

2. Read View 在 MVCC 中如何工作

Read View 是 MySQL 在 MVCC 中实现隔离性的关键概念。当一个事务需要读取数据时，数据库会为该事务创建一个 Read View，并根据该视图决定事务能够看到哪些数据。

地址：

• https://github.com/github/gh-ost/tree/master/go
• https://deepwiki.com/github/gh-ost

目录结构

├── base
│   ├── context_test.go
│   ├── context.go
│   ├── default_logger.go
│   ├── load_map_test.go
│   ├── load_map.go
│   ├── utils_test.go
│   └── utils.go
├── binlog
│   ├── binlog_dml_event.go
│   ├── binlog_entry.go
│   ├── binlog_reader.go
│   ├── gomysql_reader.go
│   └── testdata
│       ├── mysql-bin.000066
│       ├── mysql-bin.000070
│       ├── rbr-sample-0.txt
│       ├── rbr-sample-1.txt
│       └── rbr-sample-2.txt
├── cmd
│   └── gh-ost
│       └── main.go
├── logic
│   ├── applier_test.go
│   ├── applier.go
│   ├── hooks_test.go
│   ├── hooks.go
│   ├── inspect_test.go
│   ├── inspect.go
│   ├── migrator_test.go
│   ├── migrator.go
│   ├── server_test.go
│   ├── server.go
│   ├── streamer_test.go
│   ├── streamer.go
│   ├── test_utils.go
│   └── throttler.go
├── mysql
│   ├── binlog_test.go
│   ├── binlog.go
│   ├── connection_test.go
│   ├── connection.go
│   ├── instance_key_map.go
│   ├── instance_key_test.go
│   ├── instance_key.go
│   ├── replica_terminology_map.go
│   └── utils.go
└── sql
    ├── builder_test.go
    ├── builder.go
    ├── encoding.go
    ├── parser_test.go
    ├── parser.go
    ├── types_test.go
    └── types.go

9 directories, 47 files

入口 cmd/gh-ost/main.go

1. 什么是GC

GC，全称 Garbage Collection，即垃圾回收，是一种自动内存管理的机制。

2. 为什么GC

程序向操作系统申请的内存不再需要时

3. 怎么GC

• 赋值器（Mutator）：用户代码，负责修改对象引用关系。
• 回收器（Collector）：负责标记和回收无用内存。

4. GC 可观测

GODEBUG=gctrace=1 debug.ReadGCStats runtime.ReadMemStats

5. 为什么会出现内存泄漏

-  预期能被快速释放的内存因被根对象引用而没有得到迅速释放
		 - 指针
		 - 全局变量
 - Goroutine 泄漏
 Goroutine 作为一种逻辑上理解的轻量级线程，需要维护执行用户代码的上下文信息。在运行过程中也需要消耗一定的内存来保存这类信息，而这些内存在目前版本的 Go 中是不会被释放的。因此，如果一个程序持续不断地产生新的 goroutine、且不结束已经创建的 goroutine 并复用这部分内存，就会造成内存泄漏的现象.
 eg: 曾经项目中遇到的，mock了一个链接，忘记关闭

// FillArgsInSQL 使用 mock db 将参数填回 SQL
func FillArgsInSQL(sql string, args ...any) string {
	db, _, _ := sqlmock.New()
	defer db.Close() // <——  如果没关闭
	gormDB, _ := gorm.Open(
		mysql.New(mysql.Config{
			Conn: db,   // Existing mock database connection
			SkipInitializeWithVersion: true, // 跳过 SELECT VERSION() 检查
		}),
		&gorm.Config{DryRun: true})
	sqlStmt := gormDB.ToSQL(func(tx *gorm.DB) *gorm.DB {
		return tx.Raw(sql, JsonToBasicType(args)...)
	})
	return sqlStmt
}

6. 常见的垃圾回收方法

所有的 GC 算法其存在形式可以归结为追踪（Tracing）和引用计数（Reference Counting）这两种形式的混合运用。 目前比较常见的 GC 实现方式包括：

https://www.notion.so/sort-23f21f3fbf218042a172fcee79ac3d8b?source=copy_link

exec.Command 与 os.StartProcess 有什么不一样

这是一个非常经典的问题：exec.Command 和 os.StartProcess 都可以启动新进程，但功能和易用性完全不同。我给你详细拆解一下：

1.

os.StartProcess

特点

• Go 最底层的 进程创建 API，是对系统调用 fork + exec（类 Unix）或 CreateProcess（Windows）的直接封装。
• 调用麻烦，需要手动准备命令参数、环境变量、标准输入输出、文件描述符等。
• 返回 *os.Process，只能用它做简单的进程管理（等待、杀死）。

用法示例

package main

import (
	"os"
	"syscall"
)

func main() {
	// argv 必须是完整路径 + 参数数组
	procAttr := &os.ProcAttr{
		Dir:   "",
		Env:   os.Environ(),
		Files: []*os.File{os.Stdin, os.Stdout, os.Stderr}, // 指定标准IO
		Sys:   &syscall.SysProcAttr{},
	}

	process, err := os.StartProcess("/bin/ls", []string{"ls", "-l"}, procAttr)
	if err != nil {
		panic(err)
	}
	process.Wait()
}

👉 缺点：调用复杂，几乎不做封装。

(https://mp.weixin.qq.com/s?biz=MzA4ODg0NDkzOA==&mid=2247510020&idx=1&sn=c4daaaf3e895bf17a76e2481a74bf243&chksm=91a791e540e5ee433099f24654eaf06126750dd2392d660bf9144cbf33582e4e0022a6f060f9#rd)

也就是说只有符合上述函数签名的函数类型才是可以被for range支持的iterator。即所谓自定义iterator，本质上就是一个接受一个函数类型参数的函数(如上图中红框①)，按惯例，这个函数类型的参数被命名为yield(见红框②)。从Backward函数的返回值(一个iterator)的实现来看，当yield函数返回false时，迭代结束；否则迭代继续进行，直到集合类型(如slice)中所有元素都被遍历完。

其实，for range+自定义iterator可以看成是Go提供的又一个“语法糖”，它是通过Go编译器在编译阶段的代码转换来实现的。下面我们还基于Backward那个例子来看看这个转换过程：

https://www.liwenzhou.com/posts/Go/pprof/

四个方面

1. CPU profile：报告程序的 CPU 使用情况，按照一定频率去采集应用程序在 CPU 和寄存器上面的数据
2. Memory profile（Heap Profile：内存使用情况
3. Block profiling：goroutine 不在运行的状态，可以用来分析和查找死锁等性能瓶颈
4. Goroutine profiling：goroutines的使用情况，以及调用关系

Go语言内置了获取程序的运行数据的工具，包括以下两个标准库：

• runtime/pprof：采集工具型应用运行数据进行分析
• net/http/pprof：采集服务型应用运行时数据进行分析

CPU的采集

pprof.StartCPUProfile(w io.Writer)
pprof.StopCPUProfile()

得到采样数据之后，使用go tool pprof工具进行内存性能分析。

内存

pprof.WriteHeapProfile(w io.Writer)

go tool pprof默认是使用-inuse_space进行统计，还可以使用-inuse-objects查看分配对象的数量。

import _ “net/http/pprof”

你的 HTTP 服务都会多出/debug/pprof endpoint

(pprof) top3
Showing nodes accounting for 100.37s, 87.68% of 114.47s total
Dropped 17 nodes (cum <= 0.57s)
Showing top 3 nodes out of 4
      flat  flat%   sum%        cum   cum%
    42.52s 37.15% 37.15%     91.73s 80.13%  runtime.selectnbrecv
    35.21s 30.76% 67.90%     39.49s 34.50%  runtime.chanrecv
    22.64s 19.78% 87.68%    114.37s 99.91%  main.logicCode

其中：