算法

算法基础

目录

  • 数据结构
    • 数组
    • 链表
    • 二叉树
  • 算法
    • 快排
    • 二分查找
    • 递归

数据结构

数组

  • 排序
  • 查找
    • 二分查找
    • 包含重复元素的首元素索引
  • 技巧
    • 最大连续和
    • 查找次数超过 n/2 的元素

链表

  • 节点定义
  • 单链表 & 双链表
  • 倒序
  • 合并
    • 两个有序链表合并
    • 多个有序链表合并

二叉树

  • 节点定义

  • 构造

    • 由数组构造二叉树
    • 由遍历结果构造二叉树

  • 遍历

    • 深度优先遍历
    • 广度优先遍历
    • 先、中、后序遍历

  • 应用

    • 两个节点的首个公共父节点
    • 最大连通度
    • 最大连通和

常见解题思路 递归，根据当前节点信息、递归左子树返回数据、递归右子树返回数据，判断是否解决；有时需要额外的变量存储结果。

coding►算法

排序

快排

说明

图解 思路 参考 leetcode，忽略 random 优化的思路步骤如下。

  • 每次排序选第一个元素作为基准元素，将基准元素保存在变量 pivot 中，此时空出一个位置（即基准元素，不必重置元素值）
  • 定义两个游标 left、right 分别从数组两端遍历，其中分别初始化为待排序子数组的左边界索引和右边界索引
  • 然后从右边找一个小于基准值的元素，放到左侧空出的位置，此时该位置空置
  • 然后从左侧找一个大于基准值的元素，放到右侧空出的位置，此时该位置空置
  • 重复前两步，直到左右游标相遇（left == right），此时游标所指位置空置
  • 将基准元素放入游标位置，此时游标左侧的值都小于基准值，游标右侧的值都大于基准值
  • 递归的对游标左侧数组和右侧数组排序
  • 得到一个排序完成的数组

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 快速排序
 * @param nums  数组
 * @param left  排序的左边界索引
 * @param right 排序的右边界索引
 */
function qsort(nums, left, right) {
    if (left >= right) return;

    var pivot = nums[left], i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] > pivot) --j;
        nums[i] = nums[j];

        while (i < j && nums[i] <= pivot) ++i;
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    qsort(nums, left, i-1);
    qsort(nums, i+1, right);
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13

var v;
v = [3, 2, 1, 3, 4, 0, -1, 8, 9, 1, 0];
qsort(v, 0, v.length - 1);
console.log(v);

v = [];
qsort(v, 0, v.length - 1);
console.log(v);

v = [5, 4, 3, 2, 1];
qsort(v, 0, v.length - 1);
console.log(v);

输出

1
2
3
[ -1, 0, 0, 1, 1, 2, 3, 3, 4, 8, 9 ]
[]
[ 1, 2, 3, 4, 5 ]
架构►Java►框架►spring

spring aspect

new Bean 问题

在一些场景下，我们需要通过 new 来创建 spring bean，而不是借助 spring 框架，这时会遇到 @Autowired 注解的字段没有初始化的问题（null）。 此时，可以借助 aspect 来解决，具体步骤可以分为三步。

  • 引入依赖
  • 配置 context:spring-configed
  • 命令行添加参数 -javaagent:/path/to/aspectjweaver-{version}.jar

对于 spring boot，启用 context:spring-configed 可以在 Application 类上使用注解 @EnableSpringConfigured 来实现，可能还需要 @EnableAspectJAutoProxy 注解。对于xml配置，可以添加如下代码。

1
2
<aop:aspectj-autoproxy/>
<context:spring-configured/

参考

架构►概念

流批一体数据平台及一站式机器学习平台

参考

coding►go

go usage

[TOC]

说明

  • 如果一个对象的字段使用指针的方式引用了另外一个对象的字段，那么备用的变量会增加引用次数，且从栈迁移至堆，不会出现垃圾回收导致内存非法访问问题

time.Duration

1
2
3
4
d := time.Duration(10)
d := 10 * time.Nanosecond
// d := rand.Intn(100) * time.Nanosecond ERROR
d := time.Duration(rand.Intn(100)) * time.Nanosecond

打印

打印数组

1
fmt.Printf("%v", []float64{0.1, 0.5, 0.99, 0.999})

network

发送请求

1
2
3
4
urlBaiduFanyiSug := "https://fanyi.baidu.com/sug"
data := map[string]string{"kw": "hi"}
js, _ := json.Marshal(data)
res, err := http.Post(urlBaiduFanyiSug, "application/json", bytes.NewBuffer(js))

[]byte 和 string

1
2
3
4
5
// []byte -> string; bys: []byte
s := string(bys)

// string -> []byte
bys := []byte(s)

依赖

1
2
3
4
5
6
$ go mod tidy # 整理依赖, 下载没有下载的, 移除没有的
$ go mod download # 下载依赖
$ go get # 更新依赖

# 添加依赖到 go.mod
$ go get -v -t ./...

git 仓库使用 ssh 认证

1
2
3
4
5
6
git config --global --add url."git@your-repo.com:".insteadOf "https://your-repo.com/"
# 通过 ~/.gitconfig 查看配置，如果还是有问题可检查下配置

go env -w GO111MODULE=on
go env -w GOPROXY=direct
go env -w GOSUMDB=off

查看依赖版本

1
go list -m -versions git.*.com/org/repo

添加依赖

1
2
3
go get git.*.com/org/repo

go mod edit -require git.*.com/org/repo@version

GC

阶段

阶段 STW（STOP THE WORLD）
STW sweep termination YES
concurrent mark and scan NO
STW mark termination YES

gc log

1
2
3
4
5
6
GODEBUG=gctrace=1 ./<program> <parameters>
# GODEBUG 多值
GODEBUG=gctrace=1,schedtrace=1000./<program> <parameters>

gctrace=1 : 打印 gc 日志
schedtrace=1000 : 每 1000 ms 打印一次调度器的摘要信息

格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
gctrace: setting gctrace=1 causes the garbage collector to emit a single line to standard
error at each collection, summarizing the amount of memory collected and the
length of the pause. Setting gctrace=2 emits the same summary but also
repeats each collection. The format of this line is subject to change.
Currently, it is:
	gc # @#s #%: #+#+# ms clock, #+#/#/#+# ms cpu, #->#-># MB, # MB goal, # P
where the fields are as follows:
	gc #        the GC number, incremented at each GC
	@#s         time in seconds since program start
	#%          percentage of time spent in GC since program start
	#+...+#     wall-clock/CPU times for the phases of the GC
	#->#-># MB  heap size at GC start, at GC end, and live heap
	# MB goal   goal heap size
	# P         number of processors used
The phases are stop-the-world (STW) sweep termination, concurrent
mark and scan, and STW mark termination. The CPU times
for mark/scan are broken down in to assist time (GC performed in
line with allocation), background GC time, and idle GC time.
If the line ends with "(forced)", this GC was forced by a
runtime.GC() call and all phases are STW.
1
gc # @#s #%: #+#+# ms clock, #+#/#/#+# ms cpu, #->#-># MB, # MB goal, # P
  • gc # ：编号
  • @#s ：自程序启动到打印 gc 日志的时间
  • #%：自程序启动，gc 花费的时间占比
  • #+#+# ms clock：垃圾回收时间，(sweep)+(mark & scan)+(termination)
  • #+#/#/#+# ms cpu：垃圾回收占用的 CPU 时间 (sweep)+(mark & scan (辅助时间/后台gc时间/空闲时间))+(termination)
  • #->#-># MB：gc 开始时堆大小、gc 结束时堆大小、存活堆大小
  • #MB goal ：全局堆大小
  • #P ：使用的处理器数量

ms cpu 约等于 cpu_num * ms clock

示例

1
2
3
gc 35 @1130.489s 1%: 0.71+3290+0.12 ms clock, 5.7+5932/26084/4619+1.0 ms cpu, 35956->37042->8445 MB, 37411 MB goal, 32 P

1. 第 35 次 gc，距离程序启动 1130s，自程序启动 gc 时间占比 1%

参考

Profile

1
2
3
4
5
curl http://127.0.0.1:12067/debug/pprof/profile > profile.dat
go tool pprof -http=:8081 ~/profile.dat

curl http://127.0.0.1:12067/debug/pprof/heap > heap.dat
go tool pprof -alloc_space -http=:8082 ~/heap.at

类型转换

String 转数字

1
2
3
4
5
6
7
# string -> int32
if tr, err := strconv.ParseInt("9207", 10, 32); err != nil {
	res = int32(tr)
}

# string -> int64
res, err := strconv.ParseInt("9207", 10, 64)

问题

GLIBC_2.32' not found

1
2
3
4
5
# 错误
./main: /lib64/libc.so.6: version `GLIBC_2.32' not found (required by ./main)

# 解决: 编译的时候 CGO_ENABLED 设置为 0
CGO_ENABLED=0 go build
架构►存储►redis

redis benchmark

工具

针对 redis 的 benchmark，可使用 redis 自带的 redis-benchmark 工具。

redis-benchmark

命令及参数

1
2
# 命令
$ redis-benchmark [option] [option value]

参数

参数 说明 默认值 示例
-h 主机 127.0.0.1
-p 端口 6379
-a 密码
-s 指定服务器socket
-c 客户端并发连接数 50
-n 请求数 10000
-d 以字节的形式指定 SET/GET 值的数据大小 2
-k 连接保持，1=keep alive 0=reconnect 1
-r SET/GET/INCR 使用随机 key, SADD 使用随机值
-P 通过管道传输 <numreq> 请求 1
-q 强制退出 redis，仅显示 query/sec 值
–csv 以 CSV 格式输出
-l 生成循环，永久执行测试
-t 仅运行以逗号分隔的测试命令列表 set,lpush
-l Idle 模式，仅打开 N 个 idle 连接并等待

示例

1
$ redis-benchmark -h <host> -p <port> -t set -n 100000 -d 1024 -a <password>
架构►注册发现►consul

consul trouble shooting

一次服务无法注册的故障

现象

前端

我们的 consul dashboard（基于 consul ui 源码，新增了权限控制，独立部署）突然出现 504 异常。

image-20210315222804326

打开浏览器调试器的 network，查看异常的请求。

image-20210315223014936

/v1/* 接口，向部署的node应用发送请求，node 应用再将请求通过插件（ express-http-proxy ）代理转发至 consul server。

很奇怪，其他所有机房都没有问题。而且，多刷几次，偶尔可以正常响应。

服务

这一台机器的 Java 服务报了奇怪的 \n not found: limit=0 content=�~@� 异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[ERROR 2021-03-15 20:21:39.114] com...init(ConsulBase.java:58) [[consul] init consul base failed, e=[com.orbitz.consul.ConsulException: Error connecting to Consul
        at com.orbitz.consul.AgentClient.ping(AgentClient.java:69)
        at com.orbitz.consul.Consul$Builder.build(Consul.java:708)
        ...
Caused by: java.io.IOException: unexpected end of stream on http://127.0.0.1:8500/...
        at okhttp3.internal.http1.Http1ExchangeCodec.readResponseHeaders(Http1ExchangeCodec.kt:205)
        at okhttp3.internal.connection.Exchange.readResponseHeaders(Exchange.kt:105)
        ...
        at okhttp3.RealCall.getResponseWithInterceptorChain(RealCall.kt:184)
        at okhttp3.RealCall.execute(RealCall.kt:66)
        at retrofit2.OkHttpCall.execute(OkHttpCall.java:186)
        at com.orbitz.consul.AgentClient.ping(AgentClient.java:62)
        ... 14 more
Caused by: java.io.EOFException: \n not found: limit=0 content=�~@�
        at okio.RealBufferedSource.readUtf8LineStrict(RealBufferedSource.kt:231)
        at okhttp3.internal.http1.Http1ExchangeCodec.readHeaderLine(Http1ExchangeCodec.kt:210)
        at okhttp3.internal.http1.Http1ExchangeCodec.readResponseHeaders(Http1ExchangeCodec.kt:181)
        ... 35 more

看样子，是无法连接consul，接口异常？此外，由于无法连接consol，报了一堆无法找到服务端的RPC异常，这也正常，注册中心连不上，肯定也就拿不到服务列表。

我们的 C++ 服务（ 使用库ppconsul ），直接报了无法注册的异常。

1
E0315 19:28:54.129444 11661 ...cpp:456] [consul] register local consul agent failed!

解决

首先，尝试重启 consul server。不重启还好，一重启，这台机器之前注册的服务全没了，怎么重启服务都注册不上。

image-20210315224053342

随后，查看consul日志，伴随着不太明了的异常。

image-20210315224235590

于是，想通过consul程序，看下members，确认加入了集群，但是…

image-20210315224420906

他，出错了，很奇怪的错。

1
Error retrieving members: Get "http://127.0.0.1:8500/v1/agent/members?segment=_all": EOF

到这里，可以想到的是，是consul接口出问题。开始的时候前端请求异常，应该也是因为代理请求consul接口，出错导致的。凡事都有个但是，排查端口发现，有正常的连接建立啊。

image-20210315225135881

而且呢，还很多。

image-20210315225258268

等等… 难道… 是因为… 太多了？赶紧搜下。

image-20210315225438513

好吧，找到了这里。

image-20210315225530866

单个 IP 限制的最大连接数，是 200。行吧。改大试试吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
{
    "client_addr": "0.0.0.0",
    "datacenter": "...",
    "data_dir": "...",
    "domain": "...",
    "dns_config": {
        "enable_truncate": true,
        "only_passing": true
    },
    "limits": {
        "http_max_conns_per_client": 500
    },
    "enable_syslog": true,
    "encrypt": "...",
    "leave_on_terminate": true,
    "log_level": "INFO",
    "rejoin_after_leave": true,
    "server": true,
    "bootstrap": false,
    "bootstrap_expect": 3,
    "retry_join": [
        "...",
        "...",
        "...",
        "...",
        "...",
    ],
    "ui": false
}

至此，好了。

启动失败

Failed to send gossip … invalid argument

错误信息

1
2
2023/11/10 14:48:23 [ERR] memberlist: Failed to send gossip to 172.31.153.158:9301: write udp 127.0.0.1:8301->192.168.6.8:9301: sendto: invalid argument
...

解决

修改绑定地址 -bind=192.168.6.5。

1
$ consul agent -config-dir=/etc/consul.d/ -data-dir=/var/lib/consul/ -bind=192.168.6.5