Xu an's Web
0%

Grokking Algorithms

发表于 更新于 分类于 Valine：
学习记录

快速排序

基本思想：将数组分解直至满足基线条件，使用递归调用排序

快速排序 
1
2
3
4
5
6
7
8
def quicksort(array):
	if len(array) < 2:
		return array
	else:
		pivot = array[0]
		less = [i for i in array[1:] if i <= pivot] #由所有小于基准值的元素组成
		greater = [i for i in array[1:] if i > pivot]
		return quicksort(less) + [pivot] + quicksort(greater)

散列表（哈希表）

散列函数可以“将输入映射到数字”。

应用案例

  • 用于“大海捞针”式的寻找。例如在访问网站时，计算机需要将网页地址转换为IP地址，即将网址映射到IP地址。该过程被称为DNS解析，可以应用哈希表实现。
  • 防止重复。利用哈希表映射寻找表内内容是否出现了重复。
哈希表(避免重复） 
1
2
3
4
5
6
7
8
9
10
11
12
voted = {}

def check_voter(name):
    if voted.get(name):
        print("kick them out!")
    else:
        voted[name] = True
        print("let them vote!")

check_voter("tom")
check_voter("mike")
check_voter("tom")
  • 将散列表用于缓存。例如cache存储，内存，外存和页表。
哈希表（缓存） 
1
2
3
4
5
6
7
8
9
cache = {}

def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data

冲突的解决和哈希表的性能

哈希表的平均性能为O(1)，单数冲突的产生会导致哈希表的性能在最糟糕的情况下都为O(n)，即比很多线性表都要慢，因此需要避免冲突。一般解决办法式有较低的填装因子和良好的散列函数。

填装因子

当填装因子大于0.7，就需要调整列表的长度。

良好的散列函数

良好的散列函数让数组中的值呈均匀分布。

广度优先搜索

图

图可以用于模拟不同的东西是如何相连的。

算法实现

首先创建一个队列，用于搜索每一个节点的相连节点。即由队列组成一个拓扑图，由此出发进行搜索。

图 
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
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = {}
graph["peggy"] = {}
graph["thom"] = {}
graph["jonny"] = {}#生成一个图

from collections import deque#建立队列用于搜索

def search(name):
    search_queue = deque()
    search_queue += graph[name]#放入搜索队列
    searched = []#已搜索过的元素，避免循环搜索
    while search_queue:#如果搜索队列不为空
        person = search_queue.popleft()#从队列中弹出搜索项
        if person not in searched:
            if person_is_seller(person):
                print(person + "is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False
    
def person_is_seller(name):
    return name[-1] == 'm'

search("you")

狄克斯特拉算法

狄克斯特拉算法用于寻找加权图中的最短路径，但只适用于有向无环图和正权重。

算法核心思想在于寻找最便宜的节点，检查他们的邻居，检查是否有前往他们的更短路径，如果有就更新其开销，重复这个过程直到遍历所有节点，最后计算最终路径。

在计算过程中需要不断根据最短路径更新权重哈希表和父节点哈希表中的信息。

狄克斯特拉算法实现 
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
#狄克斯特拉算法
graph = {}
graph["satrt"] = {}
graph["satrt"]["a"] = 6
graph["satrt"]["b"] = 2#建立起点的两个邻居及其权重

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}#完成图中其他节点的建立

#创建哈希表存储初始计算结点的开销
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

#创建哈希表存储初始计算的父节点
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

#建立数组用于存放已经搜索过的节点
processed = []

#算法
def find_lowest_cost_node(costs):#寻找最便宜的点
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost  = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


node = find_lowest_cost_node(costs)
while node is not None:#遍历所有节点
    cost = costs[node]
    neighbors = graph[node]#得到当前节点邻居的哈希表
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:#如果当前节点前往该邻居更近
            costs[n] = new_cost#就更新节点的开销
            parents[n] = node#并将邻居的父节点设为当前的节点
    processed.append(node)
    node = find_lowest_cost_node(costs)

贪婪算法

每步都采取最优的做法，即每步都选择局部最优解，最终得到的就是全局最优解。

集合覆盖问题

假设有一个广播节目，要让全美50个州的听众都听得到，但因为每一个广播台播出都需要费用，故要选择在尽可能少的广播台播出。

贪婪算法（集合覆盖问题） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca","az"])

stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv" , "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()

while states_needed:
    best_station = None
    states_covered = set()
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station#求需要和已覆盖的交集
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered

    final_stations.add(best_station)
    states_needed -= states_covered

print(final_stations)

NP完全问题

“以难解著称的问题”

  • 元素较少时运行速度很快，但随着元素的增加运行速度变得非常慢
  • 涉及所有组合的问题
  • 不能将问题分为小问题，必须考虑各种可能的情况
  • 如果问题涉及序列且难以解决
  • 如果问题涉及集合
  • 如果问题可以转化为集合覆盖或者旅行商问题

则可能是NP完全问题。

动态规划

如何设计出动态规划解决方案？

  • 每种动态规划解决方案都涉及网格
  • 单元格中的值通常就是你要优化的值
  • 每个单元格都是一个子问题，因此你应考虑如何将问题分成子问题。

_没有放诸四海而皆准的动态规划算法。

K最近邻算法（KNN）

可以用作制作推荐系统。如果需要量度两个用户的相似度，还可以使用余弦相似度。

使用KNN时挑选合适的特征至关重要。

  • 和内容紧密相关的特征
  • 不偏不倚的特征

KNN可以用于机器学习来创建推荐系统或识别系统。通过大量的数字图像提取特征来建立KNN算法的参考库，例如谷歌使用的OCR（光学字符识别），垃圾邮件过滤器（使用朴素贝叶斯分类器）等。

将深入的方向

  • B树，红黑树，堆，伸展树
  • 反向索引
  • 傅里叶变换
  • Diffie-Hellman算法
  • 所有的图算法都可以用线性规划实现。
  • Simplex算法。