浅谈慢速二次算法与快速哈希图

大家好！昨天和一个准备编程面试的朋友聊天，想学习一些算法基础知识。我们谈到了二次时间与线性时间算法的主题，我认为在这里写下它们会很有趣，因为避免二次时间算法不仅在面试中很重要——有时在现实生活中也很重要！稍后我将快速解释什么是“二次时间算法”:)这里有3件事我们将讨论：二次时间函数比线性时间函数慢很多，有时可以通过使用hashmap转a来解决二次算法转换为线性算法，因为hashmap查找非常快（即时查找！）我将尽量避免使用数学术语，并专注于真实的代码示例以及它们到底有多快/慢。目标问题：求两个列表的交集让我们讨论一个简单的面试题：求两个数字列表的交集。例如，intersect([1,2,3],[2,4,5])应该返回[2]。这个问题也有点现实——你可以想象一个真实的程序，它的要求是取两个ID列表的交集。“显而易见”的解决方案：让我们编写一些代码来获取2个列表的交集。下面是实现此要求的程序，名为quadratic.py。importsys#实际运行代码defintersection(list1,list2):result=[]forxinlist1:foryinlist2:ifx==y:result.append(y)returnresult#一些模板方便我们从命令行运行程序和进程列表ofdifferentsizesdefrun(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]))程序名为二次的。py（LCTT译注：“quadratic”的意思是“quadratic”）是：如果list1和list2的大小为n，那么内层循环（如果x==y）将运行n^2次。在数学中，像x^2这样的函数被称为“二次”函数。quadratic.py有多慢？使用多个不同长度的列表运行这个程序，两个列表的交集总是相同的：[2]。到目前为止一切顺利-该程序仍然需要不到2秒。然后在两个100,000个元素的列表上运行程序，我不得不等待很长时间。结果如下：$timepython3quadratic.py100000#100,000[2]real2m41.059s这太慢了！总共花费了160秒，比在10,000个元素（1.6秒）上运行时快了近100倍。所以我们可以看到，在某个点之后，每将列表扩展10倍，程序的运行时间就会增加大约100倍。我没有尝试在1,000,000个元素上运行它，因为我知道它会再花100倍的时间——可能大约3个小时。我没时间做那个！您现在可能明白为什么二次时间算法会成为一个问题——即使是这个非常简单的程序也会很快变得非常慢。快速版：linear.py好了，我们来写一个快速版的程序。我会先给你看这个程序长什么样子，然后再分析它。importsys#实际执行的算法defintersection(list1,list2):set1=set(list1)#thisisahashsetresult=[]foryinlist2:ifyinset1:result.append(y)returnresult#一些模板方便我们在命令行运行程序和handledifferentsizesThelistdefrun(n):#定义两个有n+1个元素的listlist1=range(3,n)+[2]list2=range(n+1,2*n)+[2]#输出交集resultprint(intersection(list1,list2))run(int(sys.argv[1]))（这不是最地道的Python使用方式，但我想写代码时尽量不用太多Python思维这样（对于不懂Python的人来说更容易理解）在这里我们做了两件与程序的慢版本不同的事情：将list1转换成一个名为set1的集合只使用一个for循环而不是两个看linear.pyprogramhasHowFast在讨论这个程序为什么快之前，我们先通过在一些大的列表上运行这个程序来证明它是快的。下面是程序运行sequ的演示最终在10到10,000,000的列表中。（请记住，我们上一个程序在100,000个元素时开始变得非常非常慢）$timepython3linear.py100[2]real0m0.056s$timepython3linear.py1000[2]real0m0.036s$timepython3linear.py10000#10,000[2]real0m0.028s$timepython3linear.py100000#100,000[2]real0m0.048s<--quadratic.pytook2minutesinthiscase！我们在0.04secondsnow!!!sofast!$timepython3linear.py1000000#1,000,000[2]real0m0$timepython378spy10000000#10,000m[real],000srunning.py在非常大的列表上如果我们尝试在非常非常大的列表（100亿/10,000,000,000个元素）上运行它，我们实际上还有另一个问题：它足够快（列表只比花费4.2的列表大100倍）秒，所以我们应该可以在不超过420秒内完成），但是我的计算机没有足够的内存来存储列表的所有元素，所以程序在运行结束之前就崩溃了。$timepython3linear.py10000000000Traceback(mostrecentcallast):File"/home/bork/work/homepage/linear.py",line18,inrun(int(sys.argv[1]))File"/home/bork/work/homepage/linear.py",line13,inrunlist1=[1]*n+[2]MemoryErrorreal0m0.090suser0m0.034ssys0m0.018s但是本文不讨论内存使用，所以我们可以忽略这个问题。那么，为什么linear.py很快？现在我将尝试解释为什么linear.py很快。再看我们的代码：defintersection(list1,list2):set1=set(list1)#thisisahashsetresult=[]foryinlist2:ifyinset1:result.append(y)returnresult假设list1和list2都是大约10,000,000个不同元素的列表，这个元素的数量可以说是非常多了！那它为什么能跑得这么快呢？因为hashmap!!!hashmap查找是即时的（“恒定时间”）让我们看一下快速版本程序中的if语句：ifyinset1:result.append(y)你可能会认为如果set1包含1000万个元素，那么这个lookup——ifyinset1将比set1包含1000个元素慢。但事实并非如此！无论set1有多大，所需时间基本相同（超快）。这是因为set1是一个hashset，它是一个只有key没有value的hashmap（哈希表）结构。我不打算在本文中解释为什么hashmap查找是即时的，但在令人惊叹的VaidehiJoshi的basecs系列中有一个关于哈希表和哈希函数的解释，该系列讨论了为什么hashmap查找是即时的。RandomQuadratics：现实中的二次算法！二次时间算法真的很慢，我们看到的问题实际上发生在现实生活中——NelsonElhage有一个很棒的博客，叫做ForAccidentallyQuadratic，有关于在二次时间算法中无意中运行代码导致性能问题的故事。二次时间算法可能会“偷偷摸摸”你二次时间算法的奇怪之处在于，当你在少量元素（如1000）上运行它们时，它看起来并不那么糟糕！没那么慢！但是如果你给它1,000,000个元素，它实际上需要几个小时才能运行。所以我认为它仍然值得深入了解，这样你就可以避免无意中使用二次时间算法，尤其是当有一种简单的方法来编写线性时间算法时（例如使用哈希图）。Hashmap总是让我觉得有点神奇。当然这不是魔术（你可以了解为什么hashmap查找是即时的！真的很酷！），但总感觉有点神奇，每次我在程序中使用hashmap来加速时，都会让我开心:)