ARTS-WEEK11

2019-06-04
#ARTS #LeetCode

本周ARTS

本周ARTS打卡内容：

  1. Algorithm 来源 LeetCode30
  2. Review 分享 Creating a Linux service with systemd
  3. Tip 分享 流控算法
  4. Share 分享 多人实时协作的算法和软件实现

Algorithm

Leetcode的30题 所有单词组成的子串

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

解法：

从s = "barfoothefoobarman", words = ["foo","bar"]中，找出words中所有单词组成的字符串在s中出现的位置。在看到这个问题时，首先想到的是顺着s的每个字母，看其后3个字母组成的单词是否在words中出现，若不出现，则下一个字母，若出现，则再比较其后三位组成的单词是否在words中出现，若没出现，则跳出这次比较，继续下一个字母，依次类推，遇到words中单词全部出现的情况则记录此时的字母位置，继续下一次循环。按照此思路，将words中的单词保存在map中，记录words中单词出现的次数，初始化map。轮询s中的每个字母，比较其后的单词是否出现在words中，若出现不在words中的单词，或words中的单词出现次数比words中记录的多，则不满足条件，退出，重新初始化map，否则记录该字母在s中的位置，具体代码如下：

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
func findSubstring(s string, words []string) []int {
	if s == "" || len(words) == 0 {
		return nil
	}
	var k int
	var status =true
	var result = []int{}
	wordsLen := len(words)
	wordLen := len(words[0])
	maps := initMap( words)
	mapLen := len(maps)
	for i:=0; i <= len(s)-wordLen*wordsLen;i++{
		if _,ok := maps[s[i:i+wordLen]]; !ok{
			continue
		}
		start := i
		for status  {
			if k == mapLen {
				break
			}
			if _, ok := maps[s[start:start+wordLen]];!ok{
				break
			}
			maps[s[start:start+wordLen]] -=1
			start = start+wordLen
			status, k = completed(maps)
		}
		if k == mapLen {
			result = append(result, i)
		}
		maps = initMap(words)
		k = 0
		status = true
	}
	return result
}

func completed(m map[string]int) (bool,int) {
	i := 0
	for _, v := range m{
		if v < 0{
			return false, i
		}
		if v == 0 {
			i++
		}
	}
	return true, i
}

func initMap(words []string) map[string]int{
	var maps = make(map[string]int)
	for _,v := range words {
		maps[v]+=1
	}
	return maps
}

Review

本周内容： Creating a Linux service with systemd

本文介绍了如何用systemd创建一个linux service：

创建配置

在/etc/systemd/system/rot13.service创建文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
[Unit]
Description=ROT13 demo service
After=network.target
StartLimitIntervalSec=0
[Service]
Type=simple
Restart=always
RestartSec=1
User=centos
ExecStart=/usr/bin/env php /path/to/server.php

[Install]
WantedBy=multi-user.target

其中用户需要修改的有User=，设置真实用户名，和ExecStart=，设置应用的脚本

启动服务

启动服务：

systemctl start rot13

加入到开机启动：

systemctl enable rot13

配置详解

After= 指在什么服务之后启动，例如After=mysqld.service表示Mysql运行之后启动。

Restart= 重启策略，可以配置为Restart=always，表示应用一旦退出，总是重启。Restart=on-failure，表示如果退出状态不为0，则重启。

RestartSec=重启前等待的时间，默认是100ms，通过RestartSec=1表示退出后1ms，立刻重启

需要注意Restart=always默认10s内失败5次，会放弃重启，该机制是通过两个参数控制的：

1
2
StartLimitBurst=5
StartLimitIntervalSec=10

RestartSec参数对其也有影响，例如RestartSec设置为3s，那么10s内失败5次永远不会出现。

可以设置StartLimitIntervalSec=0避免10s内失败5次而放弃的情况。当然将RestartSec设置大于1s有助于降低应用重启对系统的压力。

StartLimitAction=reboot定义达到重启失败次数限制后的行为，如此处的重启。

Tip

流控算法

https://leitty.github.io/2019/06/06/Ratelimit/

Share

Hacker News 的一个讨论帖，完整涉及了现有的多人实时协作的算法和软件实现。

https://news.ycombinator.com/item?id=19845776