数据结构、算法的组合
算法是个抽象，底层可以由不同的数据结构实现。在学习算法的时候，我们往往要针对某个算法进行训练，因而一般都是学习的是比较纯粹的某种数据结构实现的算法。例如说实现抽象数据结构（ADT）堆栈或者队列，底层可以由数组或者链表实现。
但是，你可知真实的算法世界是复杂的，学习了纯化的数据结构和算法后，我们需要去真实的商业级语言库、代码库中去看看算法实现，此时很自然会发现面目全非，除了底层是纯化的数据结构和算法的影子这个本质不会变，真实世界的算法都是量体裁衣，经过组合或者优化了的。
组合是面向对象的一个原则，这个原则在算法世界中也有广泛应用，我们就以一些实例看一下数据结构组合完成新数据结构和新算法、算法组合完成新算法。
数据结构组合成新数据结构
第一个例子就是LinkedHashMap，如下图：
image.png
先不看红线，这是一个散列表，当hash冲突时，采用链表挂在散列节点下。在散列表基础上，增加了一个基础数据结构，链表，标红的就是链表。这个组合数据结构有什么用处呢？
基本的散列表操作不会变，但是遍历数据时，链表就派上用场了，因为链表是按照插入顺序构造的，所以可以按照插入顺序遍历散列表数据。
数据结构组合成新算法
最小栈问题
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
这个题目，我们就使用了两个栈进行组合，一个是常规的栈，另外一个栈只存储最小值。处理过程如下：
stack minStack
入栈 5 ， 5 大于 minStack 栈顶，不处理
| | | |
| 5 | | |
|_3_| |_3_|
stack minStack
入栈 2 ，此时右边的 minStack 栈顶就保存了当前最小值 2
| 2 | | |
| 5 | | 2 |
|_3_| |_3_|
stack minStack
出栈 2，此时右边的 minStack 栈顶就保存了当前最小值 3
| | | |
| 5 | | |
|_3_| |_3_|
stack minStack
出栈 5，右边 minStack 不处理
| | | |
| | | |
|_3_| |_3_|
stack minStack
出栈 3
| | | |
| | | |
|_ _| |_ _|
stack minStack
如下是go代码实现
type Node struct {
Val int
Prev *Node
Next *Node
}
func NewNode(x int) *Node {
return &Node{x, nil, nil}
}
type Stack struct {
Bottom *Node
TopNode *Node
}
func NewStack() Stack {
node := NewNode(0)
return Stack{node, node}
}
func (s *Stack)IsEmpty() bool {
return s.Bottom == s.TopNode
}
func (s *Stack)Top() int {
if s.IsEmpty() {
panic("stack is empty")
} else {
return s.TopNode.Val
}
}
func (s *Stack)Push(x int) {
node := NewNode(x)
node.Prev = s.TopNode
s.TopNode.Next = node
s.TopNode = node
}
func (s *Stack)Pop() {
if s.IsEmpty() {
panic("stack is empty")
} else {
prev := s.TopNode.Prev
prev.Next = nil
s.TopNode = prev
}
}
type MinStack struct {
Data Stack
Min Stack
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{NewStack(), NewStack()}
}
func (this *MinStack) Push(x int) {
this.Data.Push(x)
if this.Min.IsEmpty() || this.Min.Top() >= x {
this.Min.Push(x)
}
}
func (this *MinStack) Pop() {
x := this.Data.Top()
this.Data.Pop()
if x == this.Min.Top() {
this.Min.Pop()
}
}
func (this *MinStack) Top() int {
return this.Data.Top()
}
func (this *MinStack) GetMin() int {
return this.Min.Top()
}
关键点在于最小栈的入栈和出栈的条件。
两个栈组合形成新的算法的例子还有较多。
算法组合成新算法
排序算法我们很熟悉，基本算法按时间复杂度分：
- O(n^2) 插入排序、冒泡排序、选择排序
- O(nlgn) 快速排序、归并排序
- O(n) 桶排序、基数排序、计数排序
真实算法世界中Arrays.Sort()是怎样排序的呢？资料百度可查，使用了TimSort，具体原理可以查阅资料。这个算法就典型的是插入排序和归并排序的组合，组合的依据也就是复杂度。插入排序虽然复杂度高，但在小数据量的时候，是快于归并排序的。
小结
学习了纯化的数据结构和算法后，我们必须将目光投入到真实的算法世界。组合只是纯化的数据结构和算法为原料，构造了新的原料；我们还可以观察到纯化数据结构和算法和锁结合，形成支持并发的数据结构和算法；继续观察，有redis上为了高效率，量体裁衣，构造了自己的字符串、压缩列表等各种数据结构。
从观察到的东西来看，设计上的用到的理念，算法中通用。和编码设计对比，总结一下就是，纯化的数据结构和算法，要滚瓜乱熟，然后要通过实战经验积累真实世界的算法。
