本文除了注明由 AI 生成的内容以外均为纯手工写作，不含 AI 成分请放心食用。
0. 前言（废话）
我的上一篇公开博文发表于 Mar 10, 2022 至今已经超过一年，这段时间发生了不少事情：
从本博客创建之初的 COVID-19 已经告一段落，紧接着的是以 GPT-3.5 AI 模型的 “涌现” 为代表的革命性突破，2023 年我们迎来了 AGI 元年。
我在上一篇文章中讲到我将 “have a complete removal for the usage of Chinese from my daily work and study activities”，然而这件事情在 AGI 元年的今天来看简直就是一种毫无必要的行为了。
在这里我引用一下 Yachen Liu 的观点：
大家觉得 ChatGPT 会革了语言教育产业的命，我觉得要再想大一点，要不了多久学习外语都不再是必要的了，科幻电影中那种准确度极高的自动翻译设备已经离我们非常近（大概5年?）。
这之后，学习外语将变为类似学一门乐器的个人爱好或专业特长，大量非英语母语学生的精力将从学习英语中解放出来。
一切都将迎来巨变，在这个值得纪念的人类倒数几个高光时刻，我重新捡回了博文写作，讲讲近期我对当前这些准 AGI 实践和感想。本篇作为第一期，先来讲讲如何跟 AI 一起从头设计一个简单的算法（采用 Go 语言实现）。
1. 需求分析
在某个低时延实时数据流处理系统（后面简称系统）中，我们需要从上游接收多组实时数据流，由于上游采用了 UDP 数据包在互联网传输并且没有设计可靠性保证机制，数据完整性完全靠多组数据流冗余和重复发送来实现，系统在对数据流进行合并之后需要去重，所以本次的算法需要实现一个低时延的实时数据流去重。
说到去重，最容易想到的算法便是 hash set，将 id 做为 key 值，但这个方法问题很大：尽管从时间复杂度来看是 O(1) 的，满足我们的低时延需求，但是从空间复杂度来看是 O(n) 的，最终可能会被数据集挤爆内存。即便没有挤爆，我们也不希望在这个环节消耗过多的内存，因为数据存储等工作将在另外的流程中实现。总之我们希望空间复杂度也尽量逼近 O(1)。
再看看要处理的数据流的一些具体特征：
- 上游在传入数据至系统的时候会呈现局部的重复和乱序，但最终的整体数据集的 id 是整数连续且单调递增的。
- 数据流并非 7 * 24 小时连续，id 会每天重新从 1 开始增长。
总结下来就是: 算法需要在一组局部重复和乱序但数据集整体是整数连续且每日重置的整数数据流中完成时间复杂度近乎 O(1)、空间复杂度近乎 O(1) 的去重操作。
2. 数据结构设计
我们在需求分析中可以了解到数据集本身是整数连续的，那么在记录已经收到的数据的方式上可以考虑使用区间存储以压缩不必要的空间占用，例如我们定义一个数据结构 Interval 如下：
type Interval struct {
start int
end int
}
这个结构表示了一个 [start, end] 区间，表示在这个区间范围内的整数都已经收到过，如果再次收到则算为重复。
我们在需求分析中还可以了解到数据集本身是单调递增的，只不过在流式传输的途中会有局部的重复和乱序，那么我们可以考虑使用链表将 Interval 串起来，这个时候数据结构变成这样：
type Interval struct {
start int
end int
next *Interval
}
type IntervalSet struct {
head *Interval
}
Interval 中多了一个 *Interval 类型的 next 值，用以指向链表的下一个节点，而 IntervalSet 则表示区间集合链表这个对象，其中 head 指向链表的头部节点。
3. 算法设计
经过上面两步分析，我们的算法可以总结为是一种以链表连接的整数区间集合算法，这个时候可以请出 chatGPT 来帮我们进行算法代码的生成了。
以下是我和 chatGPT 的对话：
我：
请用Go做一个链表实现的区间集合，只需要实现一个操作：InsertOrContains 输入一个int返回是否存在该元素，如果不存在则插入至集合，并自动合并相邻区间
chatGPT：
以下是用Go语言实现的链表实现的区间集合，只包含InsertOrContains操作：
type Node struct {
Start int
End int
Next *Node
}
type IntervalSet struct {
Head *Node
}
func (is *IntervalSet) InsertOrContains(val int) bool {
if is.Head == nil {
is.Head = &Node{Start: val, End: val}
return false
}
var prev *Node
curr := is.Head
for curr != nil && curr.End < val {
prev = curr
curr = curr.Next
}
if curr != nil && curr.Start <= val && curr.End >= val {
return true
}
if curr == nil || curr.Start > val {
if prev != nil && prev.End == val-1 {
prev.End = val
if curr != nil && curr.Start == val+1 {
prev.End = curr.End
prev.Next = curr.Next
}
} else if curr != nil && curr.Start == val+1 {
curr.Start = val
} else {
node := &Node{Start: val, End: val}
node.Next = curr
if prev != nil && prev.End == val-1 {
prev.End = val
node.Next = curr
} else if prev != nil {
prev.Next = node
} else {
is.Head = node
}
}
return false
}
return false
}
该实现中，Node代表一个区间，包含了该区间的起始值和结束值，以及下一个Node的指针。IntervalSet代表整个区间集合，包含了链表的头指针。
InsertOrContains函数接受一个整数作为输入，并返回一个布尔值，表示该整数是否存在于集合中。如果该整数不存在于集合中，则将其插入到集合中，并自动合并相邻区间。具体地，InsertOrContains函数会遍历链表，找到第一个起始值大于等于输入值的区间，然后根据输入值和该区间的起始值和结束值的关系，进行不同的操作，如新增节点、合并区间等等。最后返回表示该整数是否存在于集合中的布尔值。
看起来 chatGPT 似乎是很好地理解了我的需求，那么他给出的算法是否完备呢？我是不会去检查他写的代码的，让他给出测试用例。
我：
请给出测试用例
chatGPT:
以下是一些针对IntervalSet的测试用例，涵盖了不同的情况：
func TestIntervalSet_InsertOrContains(t *testing.T) {
is := IntervalSet{}
// Test case 1: Insert a new value to an empty set.
if is.InsertOrContains(3) != false {
t.Errorf("Expected false, but got true")
}
if is.Head == nil || is.Head.Start != 3 || is.Head.End != 3 {
t.Errorf("Expected head to be a node with start=3 and end=3, but got %v", is.Head)
}
// Test case 2: Insert a value before the head.
if is.InsertOrContains(1) != false {
t.Errorf("Expected false, but got true")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 3 {
t.Errorf("Expected head to be a node with start=1 and end=3, but got %v", is.Head)
}
// Test case 3: Insert a value after the head.
if is.InsertOrContains(5) != false {
t.Errorf("Expected false, but got true")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 3 || is.Head.Next.Start != 5 || is.Head.Next.End != 5 {
t.Errorf("Expected head to be a node with start=1 and end=3, and next node with start=5 and end=5, but got %v", is.Head)
}
// Test case 4: Insert a value in the middle of two nodes, merge the nodes.
if is.InsertOrContains(4) != false {
t.Errorf("Expected false, but got true")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 5 || is.Head.Next != nil {
t.Errorf("Expected head to be a node with start=1 and end=5, and next node to be nil, but got %v", is.Head)
}
// Test case 5: Insert a value at the beginning of an existing node.
if is.InsertOrContains(1) != true {
t.Errorf("Expected true, but got false")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 5 || is.Head.Next != nil {
t.Errorf("Expected head to be a node with start=1 and end=5, and next node to be nil, but got %v", is.Head)
}
// Test case 6: Insert a value at the end of an existing node.
if is.InsertOrContains(5) != true {
t.Errorf("Expected true, but got false")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 5 || is.Head.Next != nil {
t.Errorf("Expected head to be a node with start=1 and end=5, and next node to be nil, but got %v", is.Head)
}
// Test case 7: Insert a value that forms a new node with an existing node.
if is.InsertOrContains(6) != false {
t.Errorf("Expected false, but got true")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 6 || is.Head.Next != nil {
t.Errorf("Expected head to be a node with start=1 and end=6, and next node to be nil, but got %v", is.Head)
}
// Test case 8: Insert a value that merges two existing nodes.
if is.InsertOrContains(2) != true {
t.Errorf("Expected true, but got false")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 6 || is.Head.Next != nil {
t.Errorf("Expected head to be a node with start=1 and end=6, and next node to be nil, but got %v", is.Head)
}
// Test case 9: Insert a value that is already in the set.
if is.InsertOrContains(3) != true {
t.Errorf("Expected true, but got false")
}
if is.Head == nil || is.Head.Start != 1 || is.Head.End != 6 || is.Head.Next != nil {
t.Errorf("Expected head to be a node with start=1 and end=6, and next node to be nil, but got %v", is.Head)
}
}
这些测试用例覆盖了集合为空、插入到头部、插入到尾部、插入到中间、合并节点等不同的情况。在每个测试用例中，我们都检查了插入后集合的头节点是否正确，并检查了`InsertOrContains`方法的返回值是否正确。
看起来还是很合理的，那么给他跑一遍测试看看。很快嗷，测试用例返回了n个错误：
=== RUN TestIntervalSet_InsertOrContains
main_test.go:21: Expected head to be a node with start=1 and end=3, but got &{1 1 0xc0000b60a8}
main_test.go:29: Expected head to be a node with start=1 and end=3, and next node with start=5 and end=5, but got &{1 1 0xc0000b60a8}
main_test.go:37: Expected head to be a node with start=1 and end=5, and next node to be nil, but got &{1 1 0xc0000b60a8}
main_test.go:45: Expected head to be a node with start=1 and end=5, and next node to be nil, but got &{1 1 0xc0000b60a8}
main_test.go:53: Expected head to be a node with start=1 and end=5, and next node to be nil, but got &{1 1 0xc0000b60a8}
main_test.go:61: Expected head to be a node with start=1 and end=6, and next node to be nil, but got &{1 1 0xc0000b60a8}
main_test.go:65: Expected true, but got false
--- FAIL: TestIntervalSet_InsertOrContains (0.00s)
FAIL
Process finished with the exit code 1
我又跟 ChatGPT 对话了几轮，跑完测试把结果丢给他他就继续改进，然后我又做了一轮泛型化，最终得到了一个比较完善的代码：
package main
type Integer interface {
int | int32 | int64
}
type Interval[T Integer] struct {
start T
end T
next *Interval[T]
}
type IntervalSet[T Integer] struct {
head *Interval[T]
}
func (s *IntervalSet[T]) ContainsOrInsert(val T) bool {
if s.head == nil {
s.head = &Interval[T]{start: val, end: val}
return false
}
if val < s.head.start {
s.head = &Interval[T]{start: val, end: val, next: s.head}
s.merge()
return false
}
cur := s.head
for cur != nil {
if val >= cur.start && val <= cur.end {
return true
}
if cur.next != nil && val > cur.end && val < cur.next.start {
newInterval := &Interval[T]{start: val, end: val, next: cur.next}
cur.next = newInterval
s.merge()
return false
}
if cur.next == nil && val > cur.end {
cur.next = &Interval[T]{start: val, end: val}
s.merge()
return false
}
cur = cur.next
}
return false
}
func (s *IntervalSet[T]) merge() {
cur := s.head
for cur != nil && cur.next != nil {
if cur.end+1 >= cur.next.start {
if cur.end < cur.next.end {
cur.end = cur.next.end
}
cur.next = cur.next.next
} else {
cur = cur.next
}
}
}
最终得到了一个完备的，可用的算法。我也给他进行了压力测试，在符合预设的场景下，此算法是高效的，基本达到了我想要的效果。
4. 结论 & 感想
从上面的尝试来看，ChatGPT 的代码能力还是比较有限的，逻辑严密程度一般，但是语言的理解能力还不错。好消息是他可以配合我们进行几轮迭代，到最后是能够得到一份足够完备的、能用的东西。
如果把所有的信息看作是全集 A，我们想要的东西就是 A 的子集 R，我们给 ChatGPT 输入的东西就是刻画 R 的条件。因为 ChatGPT 拥有自然语言的理解能力，我们可以用自然语言的形式把条件表达出来，语文能力越好，就越能表达的清楚，从而让 ChatGPT 给出越接近 R 的回答。如果一轮对话不能表达明白那就继续补充，如果写代码就可以以“测试-改进”这种循环来进行反复迭代直至命中我们需要的东西。
尽管本次实践只是利用 ChatGPT 做了一个相当简单的算法，但是已经完全可以看到随着 GPT 模型的迭代，他的能力还会继续上升，最终在一些更复杂的实践中也迟早会派得上用场。
人类会被取代吗？我认为不会，计算机发明以来，人类已经相当程度地解放了大脑，人们可以从事一些更高维度的工作而不是当个人肉计算器。如今喷涌而出的 AGI 只不过是更加深入地解放了大脑，我们必须承认一件事情：人脑的优势一直都不是这些具体的、细节的、低维的工作。在不远的未来，人类彻底抛开那些不擅长的工作之后，必将迎来一个全新的黄金时代。当然，也有可能是倒数第几个黄金时代。
我倒不认为人类会被所谓的强人工智能毁灭，毕竟这种事情过于经典，我们有各种各样的科幻名著已经把这件事情都快讲成烂梗了。没有什么东西是永垂不朽的，人类终将迎来自己的落日，但我唯一相信的一点是：原因一定不是我们现在能够想到的任何一种，它会是以一种黑天鹅的形式出现，将这片严重偏离均值的地方拉回到该有的样子。