大家好! 昨天我与一位朋友聊天, 他正在准备编程面试, 并试图学习一些算法基础知识.
我们聊到了二次时间 quadratic-time 与线性时间 linear-time 算法的话题, 我认为在这里写这篇文章会很有趣, 因为避免二次时间算法不仅在面试中很重要 -- 有时在现实生活中了解一下也是很好的! 后面我会快速解释一下什么是 "二次时间算法" :)
以下是我们将要讨论的 3 件事:
二次时间函数比线性时间函数慢得非常非常多
有时可以通过使用 hashmap 把二次算法变成线性算法
这是因为 hashmap 查找非常快(即时查询!)
我会尽量避免使用数学术语, 重点关注真实的代码示例以及它们到底有多快 / 多慢.
目标问题: 取两个列表的交集
我们来讨论一个简单的面试式问题: 获取 2 个数字列表的交集. 例如, intersect([1,2,3], [2,4,5]) 应该返回 [2].
这个问题也是有些现实应用的 -- 你可以假设有一个真实程序, 其需求正是取两个 ID 列表的交集.
"显而易见" 的解决方案:
我们来写一些获取 2 个列表交集的代码. 下面是一个实现此需求的程序, 命名为 quadratic.py.
- import sys
- # 实际运行的代码
- def intersection(list1, list2):
- result = []
- for x in list1:
- for y in list2:
- if x == y:
- result.append(y)
- return result
- # 一些样板, 便于我们从命令行运行程序, 处理不同大小的列表
- def run(n):
- # 定义两个有 n+1 个元素的列表
- list1 = list(range(3, n)) + [2]
- list2 = list(range(n+1, 2*n)) + [2]
- # 取其交集并输出结果
- print(list(intersection(list1, list2)))
- # 使用第一个命令行参数作为输入, 运行程序
- run(int(sys.argv[1]))
程序名为 quadratic.py(LCTT 译注:"quadratic" 意为 "二次方的")的原因是: 如果 list1 和 list2 的大小为 n, 那么内层循环 (if x == y) 会运行 n^2 次. 在数学中, 像 x^2 这样的函数就称为 "二次" 函数.
quadratic.py 有多慢?
用一些不同长度的列表来运行这个程序, 两个列表的交集总是相同的:[2].
- $ time python3 quadratic.py 10
- [2]
- real 0m0.037s
- $ time python3 quadratic.py 100
- [2]
- real 0m0.053s
- $ time python3 quadratic.py 1000
- [2]
- real 0m0.051s
- $ time python3 quadratic.py 10000 # 10,000
- [2]
- real 0m1.661s
到目前为止, 一切都还不错 -- 程序仍然只花费不到 2 秒的时间.
然后运行该程序处理两个包含 100,000 个元素的列表, 我不得不等待了很长时间. 结果如下:
- $ time python3 quadratic.py 100000 # 100,000
- [2]
- real 2m41.059s
这可以说相当慢了! 总共花费了 160 秒, 几乎是在 10,000 个元素上运行时 (1.6 秒) 的 100 倍. 所以我们可以看到, 在某个点之后, 每次我们将列表扩大 10 倍, 程序运行的时间就会增加大约 100 倍.
我没有尝试在 1,000,000 个元素上运行这个程序, 因为我知道它会花费又 100 倍的时间 -- 可能大约需要 3 个小时. 我没时间这样做!
你现在大概明白了为什么二次时间算法会成为一个问题 -- 即使是这个非常简单的程序也会很快变得非常缓慢.
快速版: linear.py
好, 接下来我们编写一个快速版的程序. 我先给你看看程序的样子, 然后再分析.
- import sys
- # 实际执行的算法
- def intersection(list1, list2):
- set1 = set(list1) # this is a hash set
- result = []
- for y in list2:
- if y in set1:
- result.append(y)
- return result
- # 一些样板, 便于我们从命令行运行程序, 处理不同大小的列表
- def run(n):
- # 定义两个有 n+1 个元素的列表
- list1 = range(3, n) + [2]
- list2 = range(n+1, 2*n) + [2]
- # 输出交集结果
- print(intersection(list1, list2))
- run(int(sys.argv[1]))
- (这不是最惯用的 Python 使用方式, 但我想在尽量避免使用太多 Python 思想的前提下编写代码, 以便不了解 Python 的人能够更容易理解)
这里我们做了两件与慢速版程序不同的事:
将 list1 转换成名为 set1 的 set 集合
只使用一个 for 循环而不是两个
看看 linear.py 程序有多快
在讨论 为什么 这个程序快之前, 我们先在一些大型列表上运行该程序, 以此证明它确实是很快的. 此处演示该程序依次在大小为 10 到 10,000,000 的列表上运行的过程.(请记住, 我们上一个的程序在 100,000 个元素上运行时开始变得非常非常慢)
- $ time python3 linear.py 100
- [2]
- real 0m0.056s
- $ time python3 linear.py 1000
- [2]
- real 0m0.036s
- $ time python3 linear.py 10000 # 10,000
- [2]
- real 0m0.028s
- $ time python3 linear.py 100000 # 100,000
- [2]
- real 0m0.048s <-- quadratic.py took 2 minutes in this case! we're doing it in 0.04 seconds now!!! so fast!
- $ time python3 linear.py 1000000 # 1,000,000
- [2]
- real 0m0.178s
- $ time python3 linear.py 10000000 # 10,000,000
- [2]
- real 0m1.560s
在极大型列表上运行 linear.py
如果我们试着在一个非常非常大的列表 (100 亿 / 10,000,000,000 个元素) 上运行它, 那么实际上会遇到另一个问题: 它足够 快 了(该列表仅比花费 4.2 秒的列表大 100 倍, 因此我们大概应该能在不超过 420 秒的时间内完成), 但我的计算机没有足够的内存来存储列表的所有元素, 因此程序在运行结束之前崩溃了.
- $ time python3 linear.py 10000000000
- Traceback (most recent call last):
- File "/home/bork/work/homepage/linear.py", line 18, in <module>
- run(int(sys.argv[1]))
- File "/home/bork/work/homepage/linear.py", line 13, in run
- list1 = [1] * n + [2]
- MemoryError
- real 0m0.090s
- user 0m0.034s
- sys 0m0.018s
不过本文不讨论内存使用, 所以我们可以忽略这个问题.
那么, 为什么 linear.py 很快呢?
现在我将试着解释为什么 linear.py 很快.
再看一下我们的代码:
- def intersection(list1, list2):
- set1 = set(list1) # this is a hash set
- result = []
- for y in list2:
- if y in set1:
- result.append(y)
- return result
假设 list1 和 list2 都是大约 10,000,000 个不同元素的列表, 这样的元素数量可以说是很大了!
那么为什么它还能够运行得如此之快呢? 因为 hashmap!!!
hashmap 查找是即时的("常数级时间")
我们看一下快速版程序中的 if 语句:
- if y in set1:
- result.append(y)
你可能会认为如果 set1 包含 1000 万个元素, 那么这个查找 --if y in set1 会比 set1 包含 1000 个元素时慢. 但事实并非如此! 无论 set1 有多大, 所需时间基本是相同的(超级快).
这是因为 set1 是一个哈希集合, 它是一种只有键没有值的 hashmap(hashtable)结构.
我不准备在本文中解释 为什么 hashmap 查找是即时的, 但是神奇的 Vaidehi Joshi 的 https://medium.com/basecs 系列中有关于 hash table 和 hash 函数 的解释, 其中讨论了 hashmap 即时查找的原因.
不经意的二次方: 现实中的二次算法!
二次时间算法真的很慢, 我们看到的的这个问题实际上在现实中也会遇到 --Nelson Elhage 有一个很棒的博客, 名为 不经意的二次方 https://accidentallyquadratic.tumblr.com/ , 其中有关于不经意以二次时间算法运行代码导致性能问题的故事.
二次时间算法可能会 "偷袭" 你
关于二次时间算法的奇怪之处在于, 当你在少量元素 (如 1000) 上运行它们时, 它看起来并没有那么糟糕! 没那么慢! 但是如果你给它 1,000,000 个元素, 它真的会花费几个小时去运行.
所以我认为它还是值得深入了解的, 这样你就可以避免无意中使用二次时间算法, 特别是当有一种简单的方法来编写线性时间算法 (例如使用 hashmap) 时.
总是让我感到一丝神奇的 hashmap
hashmap 当然不是魔法(你可以学习一下为什么 hashmap 查找是即时的! 真的很酷!), 但它总是让人 感觉 有点神奇, 每次我在程序中使用 hashmap 来加速, 都会使我感到开心 :)
来源: http://developer.51cto.com/art/202109/682394.htm