好，接下来我们编写一个快速版的程序。我先给你看看程序的样子，然后再分析。
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
在极大型列表上运行 linear.py
如果我们试着在一个非常非常大的列表（100 亿 / 10,000,000,000 个元素）上运行它，那么实际上会遇到另一个问题：它足够 快了（该列表仅比花费 4.2 秒的列表大 100 倍，因此我们大概应该能在不超过 420 秒的时间内完成），但我的计算机没有足够的内存来存储列表的所有元素，因此程序在运行结束之前崩溃了。
$ time python3 linear.py 10000000000Traceback (most recent call last): File "/home/bork/work/homepage/linear.py", line 18, in
不过本文不讨论内存使用，所以我们可以忽略这个问题。
那么，为什么 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有多大，所需时间基本是相同的（超级快）。