Algorithm
lc636_函数的独占时间_栈模拟
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
/*
题解思路:
感觉就是模拟一个stack的调用，然后end用数字加一去操作.
__好久没写了，看题到AC1小时，离大谱，还是要多练.
*/
func exclusiveTime(n int, logs []string) []int {
stack := make([]int, 0, n)
ans := make([]int, n)
splitLog := func(in string) (funcID int, opStr string, index int) {
res := strings.Split(in, ":")
if len(res) != 3 {
panic(res)
}
funcID, err := strconv.Atoi(res[0])
if err != nil {
panic(err)
}
opStr = res[1]
index, err = strconv.Atoi(res[2])
if err != nil {
panic(err)
}
return
}
preFuncID, preOpStr, preIndex := splitLog(logs[0])
stack = append(stack, preFuncID)
if preOpStr != "start" {
panic("first opStr != start")
}
for _, log := range logs[1:] {
funcID, opStr, index := splitLog(log)
// fmt.Println(funcID, opStr, index)
if opStr != "start" {
if funcID != preFuncID {
errMsg := fmt.Sprintf("stack funcID %v not match preFuncID %v\n",
funcID, preFuncID)
panic(errMsg)
}
index++
ans[funcID] += index - preIndex
// fmt.Println(funcID, ans[funcID])
stack = stack[:len(stack)-1]
} else {
if preFuncID > -1 {
ans[preFuncID] += index - preIndex
}
// fmt.Println(preFuncID, ans[preFuncID])
stack = append(stack, funcID)
}
if len(stack) > 0 {
preFuncID, preOpStr, preIndex = stack[len(stack)-1], opStr, index
} else {
// WA了一发，因为没处理这里
preFuncID, preOpStr, preIndex = -1, opStr, index
}
}
return ans
}
/*
题解比我简洁一点，学习
*/
func exclusiveTime_ans(n int, logs []string) []int {
ans := make([]int, n)
type pair struct{ idx, timestamp int }
st := []pair{}
for _, log := range logs {
sp := strings.Split(log, ":")
idx, _ := strconv.Atoi(sp[0])
timestamp, _ := strconv.Atoi(sp[2])
if sp[1][0] == 's' {
if len(st) > 0 {
ans[st[len(st)-1].idx] += timestamp - st[len(st)-1].timestamp
st[len(st)-1].timestamp = timestamp
}
st = append(st, pair{idx, timestamp})
} else {
p := st[len(st)-1]
st = st[:len(st)-1]
ans[p.idx] += timestamp - p.timestamp + 1
if len(st) > 0 {
st[len(st)-1].timestamp = timestamp + 1
}
}
}
return ans
}
|
Review
concurrence in go的英文原文的最后一节 work stealing
All things considered, stealing continuations are considered to be theoretically supe‐ rior to stealing tasks, and therefore it is best to queue the continuation and not the goroutine
综合考虑所有因素，偷接被认为在理论上优于偷接任务，因此最好是排队继续而不是goroutine
So why don’t all work-stealing algorithms implement continuation stealing? Well, continuation stealing usually requires support from the compiler. Luckily, Go has its own compiler, and continuation stealing is how Go’s work-stealing algorithm is implemented. Languages that don’t have this luxury usually implement task, or socalled “child, ” stealing as a library.
那么，为什么不是所有的工作窃取算法都实现了延续窃取呢?嗯，延续窃取通常需要编译器的支持。幸运的是，Go有自己的编译器，延续窃取是Go工作窃取算法的实现方式。没有这种奢侈的语言通常实现任务，或所谓的“孩子”，窃取作为一个库。
感觉go自己实现运行时的好处还是挺多的:
- 可以work stealing, 让协程切换使得并发效率更好
- 可以动态调整堆栈大小
综合来看都是为goroutine服务，良好的并发
Tips
golang yaml解析添加默认值与校验
通过转成json来做校验和默认值的绕过方式还是挺机智的
Share
concurrence in go简单读书笔记分享
速率限制
如果你曾经使用过API来获取服务，那么你可能经受过与速率限制相抗衡。速率限制使得某种资源每次访问的次数受限。资源可以是任何东西：API连接，磁盘I/O，网络包，错误。
你有没有想过为什么会需要制定速率限制？为什么不允许无限制地访问系统？最明显的答案是，通过对系统进行速率限制，可以防止整个系统遭受攻击。如果恶意用户可以在他们的资源允许的情况下极快地访问你的系统，那么他们可以做各种事情。
例如，他们可以用日志消息或有效的请求填满服务器的磁盘。如果你的日志配置错误，他们甚至可能会执行恶意的操作，然后提交足够的请求，将任何活动记录从日志中移出并放入/dev/null中导致日志系统完全崩溃。他们可能试图暴力访问资源，或者执行分布式拒绝服务攻击。如果你没有对系统进行请求限制，你的系统就成了一个走在街上不穿衣服的大美女。（这个例子过于形象了，离谱）
后面的文章要结合代码和运行结果仔细看，所以推荐看原文，实现之后，还是很优美的
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
func Open() *APIConnection {
return &APIConnection{
apiLimit: MultiLimiter( //1
rate.NewLimiter(Per(2, time.Second), 2),
rate.NewLimiter(Per(10, time.Minute), 10)),
diskLimit: MultiLimiter(rate.NewLimiter(rate.Limit(1), 1)), //2
networkLimit: MultiLimiter(rate.NewLimiter(Per(3, time.Second), 3)) //3
}
}
type APIConnection struct {
networkLimit,
diskLimit,
apiLimit RateLimiter
}
func (a *APIConnection) ReadFile(ctx context.Context) error {
err := MultiLimiter(a.apiLimit, a.diskLimit).Wait(ctx) //4
if err != nil {
return err
}
// Pretend we do work here
return nil
}
func (a *APIConnection) ResolveAddress(ctx context.Context) error {
err := MultiLimiter(a.apiLimit, a.networkLimit).Wait(ctx) //5
if err != nil {
return err
}
// Pretend we do work here
return nil
}
/*
01:40:15 ResolveAddress
01:40:15 ReadFile
01:40:16 ReadFile
01:40:17 ResolveAddress
01:40:17 ResolveAddress
01:40:17 ReadFile
01:40:18 ResolveAddress
01:40:18 ResolveAddress
01:40:19 ResolveAddress
01:40:19 ResolveAddress
01:40:21 ResolveAddress
01:40:27 ResolveAddress
01:40:33 ResolveAddress
01:40:39 ReadFile
01:40:45 ReadFile
01:40:51 ReadFile
01:40:57 ReadFile
01:41:03 ReadFile
01:41:09 ReadFile
01:41:15 ReadFile
01:41:15 Done.
*/
|