0%

这是关于Optiver Trivia Night的记录(主要关于最开始的Quiz部分),最开始部分为一个大约30min的Quiz,之后为Optiver实习项目相关的介绍和答疑。其中Optiver是一家全球顶级的做市商,具体信息可以参见官网。

Quiz部分的得分与正确率和答题速度相关,在大家都答对题目的情况下,答题更快的可以获得更高的得分。

第一名可以获得Optiver的终面机会,前五名获得AirPods。

题目总量为四十道,总共用时30min,总共分为几类问题:

  • Quick Math (5s) - 基本的数学运算,难度大概在三位数加减法和两位数乘法的水平,重点可能在于时间限制较为紧迫
  • Fun Facts (20s) - 询问一些现实生活当中的数字,考察量级估计和现场搜索的能力
  • Find Pattern (30s) - 图形找规律,填写下一项是什么
  • Easy Brain Teasers (30s) - 较为简单,基本上是基本数学直觉的考察
  • Sequence (60s) - 数列找规律,填写下一项是什么
  • Medium Brain Teasers (60s) - 普通的概率问题
  • Hard Brain Teasers (120s) - 较复杂一些的概率问题

最后排名为Rank 25/150,感觉如果有一定的面试准备的话应该进前十问题不是很大。大部分题目并不会很难,提供足够的时间都能够做的出来,只是在Quiz的情况下会有很强的时间紧迫感。

以下是一部分的题目记录,其中由于Quick Math部分时间过于紧张,所以基本上没有保存到截图。

部分Fun Facts可能会随着时间改变,这里的结果以2021年9月作为参考


No. 7 (Hard Brain Teasers)

10个人围成一个圈。每个人可以拍一拍左侧或者右侧的人,请问被拍的人的个数的期望是多少?

  1. 2.5
  2. 5
  3. 7.5
  4. 8.36

Answer: C

No. 12 (Sequence)

2,3,7,16,65,?2,3,7,16,65,?

序列的下一个数字是什么?

  1. 321
  2. 81
  3. 122
  4. 179
Answer: A

No. 13 (Fun Facts)

以下最接近沪深市场一天的流通量的量级的是(以RMB计价)?

  1. 10b/day (一百亿)
  2. 100b/day (一千亿)
  3. 1t/day (一万亿)
  4. 10t/day (十万亿)

Answer: C

No. 14 (Sequence)

15,29,56,108,208,?15,29,56,108,208,?

序列的下一个数字是什么?

  1. 400
  2. 416
  3. 438
  4. 386
Answer: A

No. 15 (Fun Facts)

世界上最重的猪有多重

  1. 1157kg
  2. 1312kg
  3. 694kg
  4. 866kg
Answer: A

No.16 (Hard Brain Teasers)

有5封不同的信来自5个不同的人。如果我们随机分发信件,没有一个人收到Ta自己的信的概率是多少?

  1. 4/5
  2. 11/30
  3. 7/20
  4. 5/12

Answer: B

No. 17 (Medium Brain Teasers)

地上有一个10cm * 10cm的无限大网格,你随机扔一枚直径为1cm的硬币。问硬币碰到网格线上的概率是多少?

  1. 50%
  2. 25%
  3. 19%
  4. 11%

Answer: C

No. 18 (Find Pattern)

image-20211002152158768

Answer: A

No. 19 (Medium Brain Teasers)

红色柱体的高度是多少?

image-20211002152250669

  1. 8
  2. 10
  3. 20/3
  4. 15
Answer: A

No. 21 (Easy Brain Teasers)

下列的哪一个不是素数?

  1. 257
  2. 289
  3. 157
  4. 349
Answer: B

No. 22 (Medium Brain Teasers)

你有机会可以对数字1~6进行下注,投掷三个骰子。如果你选择的数字出现一次,你获得$1;如果两次,你获得$2;如果三次,你获得$3。你所获得金额的期望是多少?

  1. $0
  2. $0.5
  3. $1
  4. $1/3

Answer: B

No. 23 (Fun Facts)

哪一个整数区间当中包含最多的素数?

  1. [1, 100]
  2. [101, 200]
  3. [201, 300]
  4. [301, 400]

Answer: A

No. 24 (Hard Brain Teasers)

(1+2)3000(1+\sqrt{2})^{3000}小数点后第100100位的数字是多少?

提示:(1+2)3000+(12)3000(1+\sqrt{2})^{3000} + (1-\sqrt{2})^{3000} 是一个整数

  1. 0
  2. 1
  3. 4
  4. 9

Answer: D

No. 25 (Medium Brain Teasers)

你站在地球的表面上,你往南走1英里,往西走1英里,往北走1英里,最后你停留在了你开始的地方。地球上有多少点可以让你完成以上的行为?

  1. 0
  2. 1
  3. 2
  4. 无穷多个

Answer: D

No. 26 (Sequence)

91,85,94,83,97,81,?,7991,85,94,83,97,81,?,79

序列的下一个数字是什么?

  1. 80
  2. 100
  3. 102
  4. 95

Answer: B

No. 27 (Hard Brain Teasers)

考虑一个平面上的5个点,在所有的点之间两两连线,你拥有了x条直线。那么以下哪个不可能是x的值?

  1. 5
  2. 6
  3. 7
  4. 8

Answer: C

No. 28 (Easy Brain Teasers)

一个立方体的面、棱、顶点数的总和是多少?

  1. 26
  2. 28
  3. 30
  4. 24
Answer: A

No. 29 (Sequence)

99,18,36,9,1899,18,36,9,18

序列的下一个数字是什么?

  1. 36
  2. 27
  3. 9
  4. 3

Answer: C

No. 31 (Fun Facts)

一个标准的奥林匹克游泳池(25m * 50m * 2m) 有多少升水?

  1. 250
  2. 25000
  3. 2500000
  4. 250000000
Answer: C

No. 34 (Hard Brain Teasers)

一个密码只能以字母而不能以数字开头,那么po88p881有多少种排列可以是密码?

  1. 315
  2. 420
  3. 525
  4. 840
Answer: A

No. 35 (Fun Facts)

火星的平均温度是多少?

  1. -100°C
  2. -60°C
  3. -20°C
  4. 20°C
Answer: B

No. 36 (Medium Brain Teasers)

考虑一个时钟,一天当中时针和分针会重合多少次?

  1. 22
  2. 23
  3. 24
  4. 26

Answer: A

No. 37 (Easy Brain Teasers)

如果下列命题有正确的话,哪一个命题是正确的?

  1. 在列表中至少有1个命题是错误的
  2. 在列表中至少有2个命题是错误的
  3. 在列表中至少有3个命题是错误的
  4. 在列表中至少有4个命题是错误的
Answer: A

No. 38 (Sequence)

3,3,27,69,129,?-3,3,27,69,129,?

序列的下一个数字是什么?

  1. 178
  2. 207
  3. 312
  4. 268
Answer: B

No. 39 (Find Pattern)

image-20211002153239630

Answer: B

No. 40 (Hard Brain Teasers)

一个国际象棋棋盘的每个小正方形边长都为2。请问在棋盘上作一个圆,能够使得整个圆的圆周都在黑色方形内部的最大的圆半径为多少?

  1. Sqrt(2)
  2. 2
  3. Sqrt(10)
  4. Sqrt(34)

Answer: C

所谓的72规则是一个用来在已知年化收益的情况下,估计投入资金实现翻倍需要年数的估算公式,公式表示如下:

Years to Double=72Interest Rate\text{Years to Double} = \frac{72}{\text{Interest Rate}}

首先通过homebrew安装rustup管理工具:

1
$ brew install rustup

安装完后发现并不能够找到rustup指令,通过brew list进行查询,发现实际上安装的为rustup-init,于是再在命令行执行:

1
$ rustup-init

顺着流程安装完成之后,重启终端便可以安装好rust环境以及相关的工具链。

可以查看对应rustc以及cargo的版本:

1
2
$ rustc --version
rustc 1.53.0 (53cb7b09b 2021-06-17)
1
2
$ cargo --version
cargo 1.53.0 (4369396ce 2021-04-27)

简单的创建一个rust语言版的Hello World进行测试:

1
2
3
fn main() {
println!("Hello World!");
}

将其保存为hello.rs

在命令行使用rustc将其编译为可执行文件:

1
$ rustc hello.rs

之后直接执行可执行文件,便可以在终端看到对应的输出了!

1
2
$ ./hello
Hello World!

Bob和Alice被邀请参加一个卡牌游戏。庄家从一组扑克牌(4种花色,A-K)给Bob随机发放5张。Bob可以选择其中4张给Alice看,然后Alice被要求猜测Bob手中剩下的一张牌的花色和点数。

问:

Bob和Alice能否仅仅根据牌的花色和点数设计出一个策略,使得无论Bob拿到的是哪五张牌,Alice都能成功猜测出最后一张牌的花色和点数。

13=23!+113 = 2 * 3! + 1

有人直接给出了这么一个式子,感觉思考思考还是很有意思的。

首先两个重要前提,一个在于Bob可以自由选择翻牌的顺序,另一个就是可以选择让Alice猜哪一张牌。

而确定一张牌需要花色加上点数。

首先是花色,花色由于抽屉原理,一定会有两张相同花色的牌。那么可以将一张牌当作被猜的牌,另一张被第一个翻出,当作花色指示牌。

对于点数而言,剩下三张牌可以考虑预先对于花色和点数的组合大小进行一个定义,那么三张不同的牌一共涉及3!=63!=6种排列方式,而1313张牌A-K排成一个圆周,每一张牌到剩下十二张牌的距离都在66以内(顺时针或逆时针)。于是可以预先定义顺/逆时针,然后以第一张标示牌沿顺/逆时针走kk格。kk为之后三张牌组合出来对应的数字,由于Bob拥有一定的自主选择权,可以通过对调第一张牌和最后一张牌的方式来确保一定是可达的。

此时再回头看最开始的那个式子,只用一个公式描述清楚了整个状态,非常精妙!

涉及时间序列的数据当中常常会碰到需要将其转换成一个个滑动窗口来构造对应训练数据的场景,PyTorch里面提供了torch.Tensor.unfold()方法可以直接完成操作。

接受的三个参数依次如下:

  • dimension (int) – unfold操作所作用的维度
  • size (int) – 滑动窗口的窗口大小
  • step (int) – 滑动窗口的步长

以下为使用的样例:

1
2
3
4
5
6
7
8
9
10
>>> x = torch.arange(1., 8)
>>> x
tensor([ 1., 2., 3., 4., 5., 6., 7.])
>>> x.unfold(0, 2, 1)
tensor([[ 1., 2.],
[ 2., 3.],
[ 3., 4.],
[ 4., 5.],
[ 5., 6.],
[ 6., 7.]])

写在前面

希望在寒假加上开学前两周自学完MIT 6.824课程,这个是MIT分布式系统的博士课程,应该也是分布式系统入门的神课。

采用的材料是2020Spring学期的材料,如果没有弃坑的话,对应的Lab解答都会同步更新到博客里面。

课程主页:http://nil.csail.mit.edu/6.824/2020/schedule.html

个人代码Repo:https://github.com/Phimos/6.824-2020Spring

实现过程

Lab1的主要任务就是通过Golang来实现一个MapReduce的算法,具体的内容可以从Lab1的官方文档中获取。

首先定义任务的类型,具体如下,最关键的就是对应的类型/状态/编号。同时利用MapFileReduceFiles字段来提供对应任务的输入。

1
2
3
4
5
6
7
8
9
10
11
type MapReduceTask struct {
TaskType string // Map / Reduce / Wait
TaskStatus string // Unassigned / Assigned / Finished
TaskNum int

MapFile string // Input of Map task
ReduceFiles []string // Input of Reduce task

NumReduce int
NumMap int
}

之后定义RPC相关的参数和返回值,对于请求有两种,当是finish情况时,需要提供对应的Task字段便于修改Master里面的人物状态。

1
2
3
4
5
6
7
8
9
10
// Args for RPC
type MapReduceArgs struct {
MessageType string // request / finish
Task MapReduceTask
}

// Reply for RPC
type MapReduceReply struct {
Task MapReduceTask
}

对于Master的类型,实际上最关键的只有MapTasksReduceTasks以及mu三项,用来存储所有任务的状态。剩下的字段其实都可以根据任务的信息来进行统计,只是处于方便进行监测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type Master struct {
// Your definitions here.
NumMap int
NumMapFinished int
NumReduce int
NumReduceFinished int
mu sync.Mutex

MapTasks []MapReduceTask
ReduceTasks []MapReduceTask

MapFinish bool
ReduceFinish bool
}

之后就根据Lab文档当中所给的Hints来梳理整个Lab1的内容。

One way to get started is to modify mr/worker.go's Worker() to send an RPC to the master asking for a task. Then modify the master to respond with the file name of an as-yet-unstarted map task. Then modify the worker to read that file and call the application Map function, as in mrsequential.go.

Worker()当中仿照样例里面的内容发送RPC请求,结果分为三类执行对应的MapReduceWait三类任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func Worker(mapf func(string, string) []KeyValue,
reducef func(string, []string) string) {

// Your worker implementation here.
for {
args := MapReduceArgs{MessageType: "request"}
reply := MapReduceReply{}

resp := call("Master.MapReduceHandler", &args, &reply)

if !resp {
break
}

switch reply.Task.TaskType {
case "Map":
mapTask(mapf, reply.Task)
case "Reduce":
reduceTask(reducef, reply.Task)
case "Wait":
waitTask()
}
}
}

对于Map的任务,主体部分直接参考mrsequential.go当中的代码,这里只需要从得到的task里面获取输入,并且修改对应的输出内容即可。

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
func mapTask(mapf func(string, string) []KeyValue, task MapReduceTask) {
filename := task.MapFile

file, err := os.Open(filename)
if err != nil {
log.Fatalf("cannot open %v", filename)
}
content, err := ioutil.ReadAll(file)
if err != nil {
log.Fatalf("cannot read %v", filename)
}
file.Close()

kva := mapf(filename, string(content))

kvaa := make([][]KeyValue, task.NumReduce)
for _, kv := range kva {
idx := ihash(kv.Key) % task.NumReduce
kvaa[idx] = append(kvaa[idx], kv)
}

for i := 0; i < task.NumReduce; i++ {
storeIntermediateFile(kvaa[i], intermediateFilename(task.TaskNum, i))
}

defer finishTask(task)
}

The application Map and Reduce functions are loaded at run-time using the Go plugin package, from files whose names end in .so.

这边的话是通过.so文件来直接获取用于Map和Reduce过程的具体函数,包括最终进行test的脚本文件也是通过加载不同的.so来实现不同的测试效果,例如对crash情况的模拟。以下是worker.go中的对应的内容,直接通过已有的loadPlugin()进行加载就可以了。

1
2
3
4
5
6
7
8
9
10
func main() {
if len(os.Args) != 2 {
fmt.Fprintf(os.Stderr, "Usage: mrworker xxx.so\n")
os.Exit(1)
}

mapf, reducef := loadPlugin(os.Args[1])

mr.Worker(mapf, reducef)
}

If you change anything in the mr/ directory, you will probably have to re-build any MapReduce plugins you use, with something like go build -buildmode=plugin ../mrapps/wc.go

**这里每次都要重新build!**不然直接会出错,一开始没有注意到检查了挺久。

This lab relies on the workers sharing a file system. That’s straightforward when all workers run on the same machine, but would require a global filesystem like GFS if the workers ran on different machines.

由于是在同一台机器上去实现这样一个分布式的MapReduce方法,对文件系统实际上进行了一定程度的简化。

A reasonable naming convention for intermediate files is mr-X-Y, where X is the Map task number, and Y is the reduce task number.

这边利用一个函数来规范化对应N x M个中间文件的命名,具体的命名方式采用如上的mr-X-Y格式。

1
2
3
func intermediateFilename(numMapTask int, numReduceTask int) string {
return fmt.Sprintf("mr-%v-%v", numMapTask, numReduceTask)
}

The worker’s map task code will need a way to store intermediate key/value pairs in files in a way that can be correctly read back during reduce tasks. One possibility is to use Go’s encoding/json package. To write key/value pairs to a JSON file:

1
2
3
enc := json.NewEncoder(file)
for _, kv := ... {
err := enc.Encode(&kv)

and to read such a file back:

1
2
3
4
5
6
7
8
dec := json.NewDecoder(file)
for {
var kv KeyValue
if err := dec.Decode(&kv); err != nil {
break
}
kva = append(kva, kv)
}

正如在上面所提到的,利用encoding/json对于中间结果进行存取,只需要对于以上的代码进行简单修改即可。

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
func storeIntermediateFile(kva []KeyValue, filename string) {
file, err := os.Create(filename)
defer file.Close()

if err != nil {
log.Fatalf("cannot open %v", filename)
}
enc := json.NewEncoder(file)
if err != nil {
log.Fatal("cannot create encoder")
}
for _, kv := range kva {
err := enc.Encode(&kv)
if err != nil {
log.Fatal("cannot encode")
}
}
}

func loadIntermediateFile(filename string) []KeyValue {
var kva []KeyValue
file, err := os.Open(filename)
defer file.Close()

if err != nil {
log.Fatalf("cannot open %v", filename)
}
dec := json.NewDecoder(file)
for {
kv := KeyValue{}
if err := dec.Decode(&kv); err != nil {
break
}
kva = append(kva, kv)
}
return kva
}

The map part of your worker can use the ihash(key) function (in worker.go) to pick the reduce task for a given key.

这是mapTask()当中对应的代码部分,在下面的第5行可以看到,通过ihash(key) % nReduce来得到对应的中间输出文件,进行中间结果的划分。

1
2
3
4
5
6
7
8
9
10
11
kva := mapf(filename, string(content))

kvaa := make([][]KeyValue, task.NumReduce)
for _, kv := range kva {
idx := ihash(kv.Key) % task.NumReduce
kvaa[idx] = append(kvaa[idx], kv)
}

for i := 0; i < task.NumReduce; i++ {
storeIntermediateFile(kvaa[i], intermediateFilename(task.TaskNum, i))
}

You can steal some code from mrsequential.go for reading Map input files, for sorting intermedate key/value pairs between the Map and Reduce, and for storing Reduce output in files.

读书人的事情,能够叫做偷吗

既然说了让抄,那就直接从mrsequential.go里面抄就好了,对应的输入输出需要进行修改,主体部分直接粘贴即可。

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
func reduceTask(reducef func(string, []string) string, task MapReduceTask) {
var intermediate []KeyValue
for _, filename := range task.ReduceFiles {
intermediate = append(intermediate, loadIntermediateFile(filename)...)
}
sort.Sort(ByKey(intermediate))
oname := fmt.Sprintf("mr-out-%v", task.TaskNum)
ofile, _ := os.Create(oname)

//
// call Reduce on each distinct key in intermediate[],
// and print the result to mr-out-0.
//
i := 0
for i < len(intermediate) {
j := i + 1
for j < len(intermediate) && intermediate[j].Key == intermediate[i].Key {
j++
}
values := []string{}
for k := i; k < j; k++ {
values = append(values, intermediate[k].Value)
}
output := reducef(intermediate[i].Key, values)

// this is the correct format for each line of Reduce output.
fmt.Fprintf(ofile, "%v %v\n", intermediate[i].Key, output)

i = j
}

ofile.Close()

defer finishTask(task)
}

The master, as an RPC server, will be concurrent; don’t forget to lock shared data.

这里需要上锁的是Master,防止多个Worker进行同时的修改,我这里采用了一个非常暴力的大锁,在MapReduceHandler()的最开始对Master上锁,然后利用defer在函数退出之后进行锁的释放,保证每次只有一个MapReduceHandler()对Master当中的结构进行修改,确保对并发可以正确处理。

1
2
3
4
5
6
// Your code here -- RPC handlers for the worker to call.
func (m *Master) MapReduceHandler(args *MapReduceArgs, reply *MapReduceReply) error {
m.mu.Lock()
defer m.mu.Unlock()
...
}

Use Go’s race detector, with go build -race and go run -race. test-mr.sh has a comment that shows you how to enable the race detector for the tests.

这边是课上所提到的检验race的方法,go语言可以通过对于内存进行监控的情况来查看是否有race发生,但是不会被执行的代码当中的race错误是不会被分析出来的,因为go语言并没有对race进行一个静态的分析。

Workers will sometimes need to wait, e.g. reduces can’t start until the last map has finished. One possibility is for workers to periodically ask the master for work, sleeping with time.Sleep() between each request. Another possibility is for the relevant RPC handler in the master to have a loop that waits, either with time.Sleep() or sync.Cond. Go runs the handler for each RPC in its own thread, so the fact that one handler is waiting won’t prevent the master from processing other RPCs.

暂时还没有新的Task分配的状况,会在Map的任务已经全部分配下去但是还没有全部完成的情况出现。这个时候Master给Worker一个Wait的指令,通过time.Sleep()等待之后再次发送一个申请新任务的RPC请求。

1
2
3
func waitTask() {
time.Sleep(time.Second)
}

The master can’t reliably distinguish between crashed workers, workers that are alive but have stalled for some reason, and workers that are executing but too slowly to be useful. The best you can do is have the master wait for some amount of time, and then give up and re-issue the task to a different worker. For this lab, have the master wait for ten seconds; after that the master should assume the worker has died (of course, it might not have).

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
if args.MessageType == "request" {
if !m.MapFinish {
for index, task := range m.MapTasks {
if task.TaskStatus == "Unassigned" {
m.MapTasks[index].TaskStatus = "Assigned"
reply.Task = m.MapTasks[index]
go m.checkTimeout("Map", index, 10)
return nil
}
}
reply.Task.TaskType = "Wait"
return nil
} else if !m.ReduceFinish {
for index, task := range m.ReduceTasks {
if task.TaskStatus == "Unassigned" {
m.ReduceTasks[index].TaskStatus = "Assigned"
reply.Task = m.ReduceTasks[index]
go m.checkTimeout("Reduce", index, 10)
return nil
}
}
reply.Task.TaskType = "Wait"
return nil
} else {
return nil
}
}

具体的checkTimeout()实现如下,就是进行一定时间的Sleep,之后检查任务是否完成,如果仍然没有完成处于Assigned状态的话,说明对应的Worker可能已经crash了。于是将其标为Unassigned状态,在之后进行重分配,保证MapReduce流程可以继续运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (m *Master) checkTimeout(taskType string, num int, timeout int) {
time.Sleep(time.Second * time.Duration(timeout))
m.mu.Lock()
defer m.mu.Unlock()
if taskType == "Map" {
if m.MapTasks[num].TaskStatus == "Assigned" {
m.MapTasks[num].TaskStatus = "Unassigned"
}
} else {
if m.ReduceTasks[num].TaskStatus == "Assigned" {
m.ReduceTasks[num].TaskStatus = "Unassigned"
}
}
}

To test crash recovery, you can use the mrapps/crash.go application plugin. It randomly exits in the Map and Reduce functions.

Test的最后一个部分就是crash test,会使用crash.so文件,事实上,在上面利用一个go routine取检查超时,如果一个worker在工作过程中crash了,那么就无法在最后返回个master一个Finish的RPC。所以利用以上的超时检查机制,是可以简单的对于Lab当中的crash进行正确重分配任务,保证MapReduce流程正常进行。

To ensure that nobody observes partially written files in the presence of crashes, the MapReduce paper mentions the trick of using a temporary file and atomically renaming it once it is completely written. You can use ioutil.TempFile to create a temporary file and os.Rename to atomically rename it.

这边只需要修改对应的输出为TempFile -> Rename的流程就可以,这里就不进行修改了。

test-mr.sh runs all the processes in the sub-directory mr-tmp, so if something goes wrong and you want to look at intermediate or output files, look there.

执行sh test-mr.sh的结果如下所示,可以发现对于Lab1的所有测试都完全通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
*** Starting wc test.
2021/02/03 16:24:03 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- wc test: PASS
*** Starting indexer test.
2021/02/03 16:24:09 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- indexer test: PASS
*** Starting map parallelism test.
2021/02/03 16:24:12 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- map parallelism test: PASS
*** Starting reduce parallelism test.
2021/02/03 16:24:20 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- reduce parallelism test: PASS
*** Starting crash test.
2021/02/03 16:24:28 rpc.Register: method "Done" has 1 input parameters; needs exactly three
--- crash test: PASS
*** PASSED ALL TESTS

体验

  • Golang上手的感觉还行,感觉和C语言差别不大,有C语言的基础熟悉一下语言特性应该就可以上手。
  • 难度一般,可能是Lab1的缘故,总体实现上困难不是很大。
  • 从文档和代码上看,整个Lab的结构上感觉没有6.828课程的巧妙,但是已经非常完备了,远超国内学校课程作业的实用程度。

2020

有所得

有所失

面试完全没有提到跟简历有关的内容,基本就是问智力题,感觉答得非常一般。

最终面试结果为未通过。

  1. (博弈论)ABC三家公司,在0-100的101个整数点上都存在住户,按照ABC的顺序每个人依次选择1-100当中的一个位置作为公司的办公地点,住户会选择离他最近的公司。为了最大化收益(最大化到自己公司的用户数量),A的最优选择是什么?

就是一个博弈论的问题,应该算Best Response逐层上推就好了,当时面试只讲了思路,没有算出来。

  1. NN个序列,每个序列有3个数字,任意两组之间的correlation都小于0.7,问NN可能的最大取值是多少。

将其转变成一个三维的单位球,问求表面能够取多少向量,两两之间夹角的余弦值小于0.7。可以通过用正三角形的构造方法,来利用立体角构造上界。但并不知道怎么计算准确值,当时面试官说可以计算出准确的结果。

  1. 一个没有记忆功能科学计算器,加减乘除和数字键都坏了,可以采用类似三角函数,取倒数,对数,开方,阶乘等操作。最开始只有一个0,如何得到任意整数?如何得到任意有理数?

本质是利用直角边为n\sqrt{n}11的直角三角形。

首先通过取cos\cos得到11,然后依次采用arctan\arctancos\cos,取倒数,平方,就可以得到22。开方之后再次通过以上流程就可以得到33,依次类推可以得到任意整数。

对于任意有理数,实际上要可以得到任意的mn\frac{m}{n},由上面的流程,我们可以在知道rr的情况下,得到r+1r+1,同时可以得到任意的1n\frac{1}{n}

那么对于任意的mn\frac{m}{n},总是用大的减去小的,就可以最终化成一个1k\frac{1}{k}的形式,这个是可以得到的,之后再反复利用倒数和+1+1的操作反推回去,就可以得到任意有理数了。

  1. 笔试当中提到的,最奇怪的交易股票的策略。

CQ资产的笔试题目,笔试时间为40分钟,题量为9道。总体感觉笔试难度适中,时间有一点紧。由于笔试题目本身为英文,这里不做额外的翻译,解答为笔者所做,可能存在错误。

个人笔试结果为通过。

  1. Given the following function definition: (4 min, score = 3)

    1
    2
    3
    4
    5
    Define f(x): 
    result = 1
    For i from 1 to x (inclusively):
    result = result + i
    return result

    How many additions will take place while evaluating f(f(f(3)))?

Solution:

f(x)=1+(1++x)=1+x(1+x)2=x2+x+22\begin{aligned} f(x) &= 1 + ( 1+ \ldots+x) \\ &=1 + \frac{x(1+x)}{2} \\ &= \frac{x^2 + x + 2}{2} \end{aligned}

Total additions:3+f(3)+f(f(3))=3+7+29=393+f(3) + f(f(3)) = 3+7+29=39.

  1. A stock’s price fluctuates every day by going up exactly 5% or going down exactly 5%. Assume that each direction is equally likely. Assume zero trading cost, zero interest rate, and no dividends and splits. What strategy is most likely to be profitable after 100 days?
    (3 min, score = 3)

    A. Buy or sell will produce same profitable

    B. Cannot know / no strategy can be profitable

    C. Buy the stock

    D. Sell the stock

Solution:

D

  1. Below is a list of asymptotic complexities of 8 functions, each with length N input:

    1. O(N^3)

    2. O(Log(N))

    3. O(Sqrt(N))

    4. O(N * log(N))

    5. O(2^N)

    6. O(N^N)

    7. O(N!)

    8. O(Log(Log(N)))

    Please sort the functions by order of growth, with slower growing functions first. (your answer shall be a sequence of letters, for example “BACDFHGE􏰀”)
    (4 min, score = 3)

Solution:

HBDCAEGF

  1. What is the maximum possible variance of a random variable taking values in the interval [0, 10]?
    (2 min, score = 2)

Solution:

Half is 00, half is 1010.

Var(x)=E[XE(X)]2=52=25Var(x) = E[X-E(X)]^2 = 5^2 = 25

  1. How many integers nn such that nnn^n is a perfect square are there in range [100: 400]?
    (5 min, score = 4)

Solution:

If nn is even, n=2kn = 2k, then nn=n2k=nk\sqrt{n^n} = \sqrt{n^{2k}} = n^k, so it’s a perfect square.

If nn is odd, n=2k+1n = 2k+1, then nn=n2k+1=nkn\sqrt{n^n} = \sqrt{n^{2k+1}} = n^k\sqrt{n}, it’s a perfect square if and only if nn is a perfect square.

We have:

102=100202=40010^2 = 100 \qquad 20^2 = 400

So there are 5 odds that meet the condition, 112,132,,19211^2,13^2,\ldots,19^2.

Totally, 151+5=156151 + 5 = 156 integers.

  1. Assume there are three random variables X,Y,ZX, Y, Z. All pairwise correlations are equal: corr(x,y)=corr(y,z)=corr(x,z)=rcorr (x,y)=corr(y,z)=corr(x,z) = r. What is the range of possible values of rr? (list a range, like [0.3:0.7][-0.3:0.7], for example)
    (6 min, score = 12)

Solution:

1rrr1rrr1=1r2+r(r2r)+r(r2r)=2r33r2+1=(r1)2(2r+1)0\begin{aligned} \left|\begin{array}{cccc} 1 & r & r \\ r & 1 & r\\ r & r & 1 \end{array}\right| &= 1 -r^2 + r(r^2-r) + r(r^2 - r) \\ &= 2r^3 - 3r^2 + 1 \\ &= (r - 1)^2 (2r+1)\ge 0 \end{aligned}

So the range of possible values of rr is [1/2,1][-1/2, 1].

  1. Assume there are three random variables X,Y,ZX, Y, Z. We would like to use one number to describe their relations, just like the pairwise correlation of 2 variables corr(x,y)corr(x,y). We need the number to be normalized. Please list the possible mathematical formulas to calculate such number, the more the better.
    (6 min, score = 12)

Solution:

corr(x,y)+corr(y,z)+corr(x,z)3\frac{corr(x,y) + corr(y, z) + corr(x, z)}{3}

  1. Triangle ABC has sides of length 45, 60 and 75. A point XX is placed randomly and uniformly inside the triangle. What is the expected value of the sum of perpendicular distance from point X to this triangle’s three sides?
    (9 min, score = 10)

Solution:

452+602=75245^2 + 60^2 = 75^2

It’s easy to know, triangle ABC is a right triangle.

E[l]=1516040(123x)/4(x+y+123x4y5)dydx=1516040(123x)/4(125+2x5+y5)dydx=151604(12+2x5123x4+110(123x4)2)dx=151604(310(242xx2)+110916(168x+x2))dx=151604(81102120x39160x2)dx=1516(81104212042239160433)=151/618.8=47\begin{aligned} E[l]&=15 * \frac{1}{6}\int_0^4\int_0^{(12-3x)/4} \left(x+y+\frac{12-3x-4y}{5}\right) dydx \\ &= 15 * \frac{1}{6}\int_0^4\int_0^{(12-3x)/4} \left(\frac{12}{5}+\frac{2x}{5}+\frac{y}{5}\right) dydx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{12+2x}{5} \frac{12-3x}{4}+\frac{1}{10}(\frac{12-3x}{4})^2\right)dx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{3}{10}(24-2x-x^2)+\frac{1}{10}\frac{9}{16}(16-8x+x^2)\right)dx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{81}{10} - \frac{21}{20}x -\frac{39}{160}x^2 \right)dx \\ &= 15 * \frac{1}{6}\left(\frac{81}{10} * 4 - \frac{21}{20}*\frac{4^2}{2} -\frac{39}{160}*\frac{4^3}{3}\right) \\ &= 15 * 1/6 * 18.8 \\ &= 47 \end{aligned}

  1. Please list one of your most “strange” or “crazy” idea to predict stock’s return. You can assume you have all available public data and strong computing power. The answer shall be as “strange” as possible.
    (6 min, score = 10)

Solution:

Use the stock code to select stocks. If the stock code is a prime number, buy it and hold. The strategy is pretty strange because there should be no useful information in the stock code.

这是一篇模型压缩领域的综述,主要从参数剪枝和量化(Parameter pruning and quantization),低秩分解(Low-rank factorization),转移/紧致卷积滤波器(Transferred/compact convolutional filters)和知识蒸馏(Knowledge distillation)四个方面来对于已有的模型压缩方法进行综述。这篇文章发表的时间点为2017年,可能对于较新的成果涉及并不是那么广泛,但是对于模型压缩加速领域的一个初步了解而言感觉还是可以的。

四个方向的总体概览如下所示:

image-20200828211417546

参数剪枝和量化(Parameter pruning and quantization)

量化与二值化(Quantization and Binarization)

网络量化是通过用来表示权重的bits数目来将原网络进行压缩的,比如可以采用16-bit浮点或者是8-bit整数来表示权重,极限情况下可以采用1-bit的二进制权重神经网络。

同时也有一种方法是通过权重共享来实现模型的压缩,可以认为是通过Hash方法将所有近似的权重对应于一个Hash值,即使得相同的权重只被存放一次。这里通过哈夫曼编码来减少存放索引所需要的空间,从而可以通过索引去读取对应的内容。

流程如下所示:

image-20200828154712428

他实际上在利用Code Book量化之后会对共享的权重进行重训,来得到更好的效果。最后得到的就是权重的Code Book,每个权重存放的是对应的索引而不是权值。

(好奇.jpg,离散值的梯度反传等等怎么搞?找到了个知乎链接,有空看看,估摸着是不一定会看了)

缺点:

  • 二进制网络的精度降低非常严重。
  • 当前的二进制方案基于简单的矩阵估计,忽略了二进制在精度损失方面的效果。

网络剪枝(Network Purning)

网络剪枝和共享已经被用于减少网络复杂性和处理过拟合任务。一个早些的剪枝方法是有偏的权重衰减。最优脑损害(The Optimal Brain Damage)和最优脑外科医生(the Optimal Brain Surgeon)方法基于损失函数Hessian矩阵来减少连接层的参数,这些工作期望能够比基于大小的剪枝方法(比如权重衰减)有更高的准确率。

网络剪枝的最近一个方向是剪枝掉预训练模型当中的冗余权重,通过data-free的方式来去除掉冗余的神经元和连接。

同时也有一个方向是训练带有稀疏性约束的CNN网络。在最优化问题当中,稀疏性约束通常就是l0l_0l1l_1正则化。

缺点:

  • 利用l1l_1或者是l2l_2正则化通常需要更多的迭代来收敛
  • 所有的剪枝条件都一定程度上需要人工来设置网络层的敏感性
  • 网络剪枝通常能够降低模型大小但是没有办法提升效率

构造结构化矩阵(Designing Structural Matrix)

结构化矩阵的方式从我的理解来看,实际上就是通过更少的参数来表示全连接层的那个大矩阵,从而降低需要的参数量。由于有的结构化方法可以通过特性进行高效的矩阵-向量乘法,所以不仅可以降低内存的消耗,同时可以加速模型的训练和推断。

(好奇.jpg x 2,卷积实际上应该也是一种结构化矩阵,这玩意能不能在受限情况下进行搜索?)

一种方法就是通过循环投影(circulant projections),通过向量r=(r0,r1,,rd1)\mathbf{r}=(r_0,r_1,\ldots,r_{d-1}),一个循环矩阵RRd×d\mathbf{R}\in \mathbf{R}^{d\times d}可以如下定义:

R=circ(r):=[r0rd1r2r1r1r0rd1r2r1r0rd2rd1rd1rd2r1r0]\mathbf{R}=\text{circ}(\mathbf{r}):=\left[\begin{array}{ccccc} r_{0} & r_{d-1} & \ldots & r_{2} & r_{1} \\ r_{1} & r_{0} & r_{d-1} & & r_{2} \\ \vdots & r_{1} & r_{0} & \ddots & \vdots \\ r_{d-2} & & \ddots & \ddots & r_{d-1} \\ r_{d-1} & r_{d-2} & \ldots & r_{1} & r_{0} \end{array}\right]

这使得内存消耗从O(d2)O(d^2)变成了O(d)O(d),同时循环矩阵也可以利用快速傅立叶变换(FFT)来加速计算过程。提供一个dd维的向量,通过上述矩阵的计算时间复杂度为O(dlogd)O(d\log d)

缺点:

  • 结构化约束会使得模型有偏,损害模型的性能(我的角度来看就是做了不该做的假设)

  • 很难找到合适的结构化矩阵,当前也缺乏理论指导

低秩分解(Low-rank factorization)

卷积操作占据了深度CNNs模型中的最大计算篇幅,因此减少卷积层能够提升压缩率同时也能加快运算速度。

对于卷积核,它可以被认为一个4D张量。基于张量分解的想法驱使我们本能的认为4D张量的冗余性去除会有一个显著提升,这是一个特殊的方式去移除冗余性。注意到全连接层,它能够被视为一个2D矩阵并且低秩也能有所帮助。

很长时间以来,人们使用低秩滤波器去加速卷积,例如,高维DCT(discrete cosine transform,)和小波系统(wavelet systems)各自使用张量积去构造从一维DCT和小波。

低秩估计是逐层而做的。一层的参数在低质估计后固定下来,而上面的层是微调基于一个重构误差准则。这些是典型的用于压缩2D卷积滤波器的低秩估计方法。根据这个方向,Canonical Polyadic(CP)分解是一个用于核张量的方法。人们使用非线性的最小二乘去计算CP分解。然而,找到最好的低秩估计在CP分解中式一个病态问题,并且最好的rankKrank-K(K是秩的值)估计可能是不存在的。

正如前面所提,全连接层可以看成是2D矩阵,因此上述的方法(指低秩估计的方法)也能够应用到这儿(指全连接层的分解)。也有工作应用截断奇异值分解去分解全连接层用于设计紧凑的多任务深度学习框架。

缺点:

  • 低秩方法涉及到计算代价昂贵的分解操作,执行起来并不容易。
  • 由于不同层有着不同的信息,当前的低秩估计方法是逐层的,因此不能执行全局的参数压缩。
  • 比较原始模型, 分解需要额外的再训练去实现收敛。

转移/紧致卷积滤波器(Transferred/compact convolutional filters)

CNNs 是参数有效的对于转换的不变性,对于输入图片表示的不变性,而这对于训练深度模型而不导致过拟合是重要的。尽管目前还缺失强理论证明,但是大量的经验事实支持平移不变性和权重共享对于好的预测性能是重要的。 使用转移卷积滤波器去压缩CNN模型的想法受到研究工作启发,它引入了等价理论。让xx是一个输入,Φ()\Phi(\cdot)是一个网络层和T()\mathcal{T}(\cdot)是一个转换矩阵。等价性的概念如下所定义:

T(Φ(x))=Φ(Tx)\mathcal{T}^\prime(\Phi(x)) = \Phi(\mathcal{T}x)

表明转换了T()\mathcal{T}(\cdot) 的输入 xx 然后传递它到层次Φ()\Phi(\cdot)的网络(即得到Tx\mathcal{T}x后再用网络作用)应该有同样的结果在第一次用网络映射xx然后再转换表示(即先得到Φ(x)\Phi(x),再用T\mathcal{T}作用)。注意:T()\mathcal{T}^\prime(\cdot)T()\mathcal{T}(\cdot)不是必须相同的。根据这个理论,应用转换层或者滤波器Φ()\Phi(\cdot)去压缩整个网络模型是合理的。从经验观察,深度CNNs同样受益于使用大的卷积滤波器通过应用确定的转换T()\mathcal{T}(\cdot)到一个小的基础偏置滤波器的集合,由于它扮演了一个模型的正则化。

在这个方向,有许多最近的研究工作去建立一个由基础滤波集合构建的卷积层。(就是从不同的角度定义函数 T()\mathcal{T}(\cdot)

缺点:

  • 这些方法能够对于宽度(扁平)的框架(比如VGGNet)能够实现竞争性的性能,但是对于深度的网络(比如GoogleNet,ResNet)效果就不是很好。
  • 指导学习的转移假设条件有时太强了,这使得结构对于某些情形是不稳定的。

知识蒸馏(Knowledge Distillation)

知识蒸馏的基本想法就是将深度大模型中蒸馏知识到一个浅层的网络当中。压缩的网络会尝试学习深层复杂网络的这样一个映射。通常的方法就是通过学习softmax之后的分布来讲大模型的知识蒸馏到小模型当中。当然也有一些工作来尝试学习高层隐层当中的表征,或者是feature maps来进行知识蒸馏,以获得相对于最终的分布更多的信息。通常而言大模型和压缩模型的容量结构相差比较大,假设其中间结果有着相似效果是一个过强的约束。

缺点:

  • 知识蒸馏的方法可以显著降低运算量,但是只能够被用在softmax loss的任务上。
  • 只能够从头开始训练,不能够从已有的模型权重当中进行抽取。
  • 效果相对于其他方法而言也并不够好。

评测指标与数据集

数据集

数据集主要为主流的图像相关任务数据集,对应的Baseline模型为主流的CV经典模型,如ResNet,VGG nets等。

评测指标

MM为模型,aa为模型所含有的参数数量,ss为模型的运行时间,大部分工作是采用的平均每epoch的训练时间,但是实际上测试时间也是可以的。利用MM^*的星号上标来表示压缩后模型的对应指标,通常采用的评价指标有以下几种:

  • 压缩比率(compression rate)

    α(M,M)=aa\alpha(M, M^*) = \frac{a}{a^*}

  • 索引空间节省量(index space saving)

    β(M,M)=aaa\beta(M, M^*) = \frac{a - a^*}{a^*}

  • 加速比率(speedup rate)

    δ(M,M)=ss\delta(M,M^*) = \frac{s}{s^*}

通常而言压缩比和加速比是高度相关的,因为越小的模型通常跑的越快。事实上在不同的任务当中这可能和不同的层类型是相关的。大多是任务的运算主要集中在全连接层,但是对图像分类任务而言,绝大多数的运算主要集中在卷积层,因为一开始的图像面积比较大,卷积层运算非常耗时间。所以具体的压缩和加速方法需要对应于不同的应用着重关注不同类型的网络层。