题目具体可以看 这里
简单概括描述就是：
给定一些整数输入 seeds，并且给出一些 mapping (list list (dst, src, length))，如果 seed 落在 [src, src + length] 这个区间里面，就 map 成 (dst + seed - src)。求经过多次 mapping 之后，seeds 当中的最小值。
暴力 with F#
看到题目很直观的一个想法就是对于输入的每个 seed 都扫一遍所有的 mapping，得到一个最终的 seed，并从中求最小值。part1 很轻松就过掉，但是到了 part2 的时候，每两个 seed 表示输入的是 [seed1, seed1 + seed2] 区间内的所有 seeds，加起来超过 198 亿个 seeds。
最开始直接用 F# 写了一个暴力法模拟，但是跑了一段时间后可能因为数量太多直接给我中断了。于是手动把输入分成了两半，然后跑两次，一次大概要跑 8 分钟，不过能跑到正确的答案。
既然这么耗时，第一时间想到的就是用多线程并行来跑。在 F# 当中，可以很简单地通过 async block + Async.Parallel 实现并行计算，看起来能跑满七八个核。
1
2
3
4
5
6
7
8
9
10
11
12
13
| seeds
|> Seq.map (fun (a, b) ->
async {
let allSeeds =
[| for i in a .. (a + b - (int64 1)) do
yield i |]
return maps |> Array.fold (fun seeds map -> seed2Map seeds map) allSeeds |> Seq.min
})
|> Async.Parallel
|> Async.RunSynchronously
|> Array.min
|
在 F# 当中使用多线程跑，5 分钟多点就能跑完。
既然跑得慢，那么切换到一个跑得更快的语言，用 Rust 来写，应该能提升不少。
暴力 with Rust
先用 Rust 写了个逻辑一样的暴力模拟，基本上就是把 F# 写的逻辑搬了过来，4 分钟左右能跑完。这个速度比我在 F# 用多线程来跑还快！Rust 的性能果然名不虚传。
然后继续用多线程的方法又写了一版，每两个 seed 作为一组，开一个线程来逐个 seed 处理。然后一分钟左右就能跑完，确实快，Rust 实在是太强辣。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| let mut handlers = vec![];
for (start, cnt) in seeds {
let maps_clone = maps.clone();
let handler = thread::spawn(move || {
(start..start + cnt)
.map(|seed| {
maps_clone
.iter()
.fold(seed, |seed, map| seed_2_map(seed, &map))
})
.min()
.unwrap()
});
handlers.push(handler);
}
handlers
.into_iter()
.map(|handler| handler.join().unwrap())
.min()
.unwrap()
|
真正的解法
之前暴力的解法是逐个 seed 做多次 mapping 得到结果再找最小值，但是这个数量太多，需要跑的次数太多。但实际也不需要每个 seed 做 mapping，完全可以根据区间来做 mapping.
对于一个 seeds 的区间 range，经过一轮 mapping 后，
- 如果跟其中的一个 map 有交集，可以取这个交集出来做 mapping
- 交集部分两个端点进行 mapping 可以得到新 range
- 非交集部分取出来得到新 range，继续和其他的 map 进行处理
- 如果都没有交集，那么直接进入下一轮 mapping
具体代码如下
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
| #[derive(Copy, Clone)]
struct Range {
start: u64,
end: u64,
}
impl Range {
fn new(start: u64, end: u64) -> Range {
Range { start, end }
}
fn is_empty(&self) -> bool {
self.start >= self.end
}
fn intersect(&self, other: Range) -> Range {
Range {
start: self.start.max(other.start),
end: self.end.min(other.end),
}
}
fn difference(&self, other: Range) -> (Range, Range) {
let left_diff = Range::new(self.start, self.end.min(other.start));
let right_diff = Range::new(self.start.max(other.end), self.end);
(left_diff, right_diff)
}
}
let mut ranges = seeds;
for map in maps {
let mut mapped_ranges = vec![];
while let Some(range) = ranges.pop() {
let mut has_intersect = false;
for (target, source, len) in map.iter() {
let mapped_range = Range {
start: *source,
end: *source + len,
};
let intersection = range.intersect(mapped_range);
if intersection.is_empty() {
continue;
}
has_intersect = true;
mapped_ranges.push(Range {
start: intersection.start - *source + *target,
end: intersection.end - *source + *target,
});
let (left_diff, right_diff) = range.difference(mapped_range);
if !left_diff.is_empty() {
ranges.push(left_diff);
}
if !right_diff.is_empty() {
ranges.push(right_diff);
}
break;
}
if !has_intersect {
mapped_ranges.push(range);
}
}
ranges = mapped_ranges;
}
ranges.iter().map(|range| range.start).min().unwrap()
|
切换到这个解法后，直接 0.05s 秒了！
一个小问题：对于这种需要三个嵌套循环的代码逻辑，如果转成使用函数式编程的思路，比如用 F# 来实现，该怎么办呢？具体请看下回分解。