Zhouyao's Blog

Do Something Big With Us

python 的 dict真的不会随着key的增加而变慢吗?

CC BY SA  4.0

文章来源:知乎

廖雪峰python教程上看到:
和list比较,dict有以下几个特点:
查找和插入的速度极快,不会随着key的增加而变慢;
需要占用大量的内存,内存浪费多。


你问的问题其实很有价值。这是很多初学数据结构的人的困扰,因为它没逻辑。凭什么我多大的数据量,访问速度都是一样的?这根本不符合常理。

很多人会告诉你,这是Hash Table,而Hash Table的访问速度是O(1)的,而对于你来说,这就和没说一样。这个答案既不算精确,也没能回答你的问题。

首先如果你真的想搞清楚这个问题的来龙去脉,你需要搞懂Hash Table到底是什么东西。Hash Table首先默认了一件事情,在电脑中,读取或者写入一个已知地址的内存需要的最大时间是固定的,和有可能写入内存的长度无关的。

举个例子,你在家有一个柜子,柜子上有一堆抽屉,你把这些抽屉分别编号为1-10。这时候我和你说,找10号抽屉,你可以立刻找到10号。我说找6号,你可以立刻找到6号。现在你的柜子扩大了,抽屉有100个,我说找56号,你还是可以立刻找到56号。你柜子又大了,变成了1000个抽屉,我说找729号,你依然可以立刻找到729号。

对于人类来说,这是不可能的。随着抽屉数量的增加,我们找对应抽屉的速度会下降。但是对于现在的计算机来说,这个假设是成立的。这是你要理解的第一点计算机和人类的不同。无论有多少抽屉,只要你说找这个号码的抽屉,不管是第一个,最后一个,还是中间任何抽屉,计算机的反应速度都一样。

好,现在假设我们有1000个抽屉,我们有4份文件。每一份文件有一个唯一且不重复的文件编码,这个编码是8位码,比如01303457。我们需要把这四份文件保存到抽屉里,并且希望下次有人来要这些文件的时候,我们可以立刻找到。

我们可以把这四份文件都放到第一个抽屉,然后人来的时候把四个文件找出来,逐一对比文件编码。这是一种线性数据结构,他的搜索速度和文件的数量是线性关系。我们有100份文件,速度大概是10份的10倍。我们管他叫O(N)。我们可以按照文件编码先把文件排序,然后都放第一个抽屉里。这样搜的时候,我们可以利用二分法来找文件。这时候我们的速度提高到了log(N)。随着文件的增加,我们的搜索时间还是在增加,但是增加的缓慢了。

然而还有一个方法。我们可以看文件的尾号,把他们放进和尾号对应的抽屉里。比如01303457号文件,我们就给他放到457号抽屉。我们可以想象,在文件比较少的时候,我们的每个抽屉很可能只有一份文件。这时候有个人来说我要01303457号文件,我们就可以直接去457号抽屉给她拿。由于我们找一个抽屉的速度时固定的,所以随着文件的增加,我们搜索文件的时间是没有增加的。

下面才是重点,也是两种逻辑产生冲突的地方。如果文件多了,肯定会有抽屉不止两个文件。最理想的情况下,在有1001份文件的时候,也会有一个抽屉有两份文件。而最差的情况,所有的文件尾号都一样,那我们不是回到了第一种方法么?

没错!你想的是完全正确的。相信自己的判断。

很多课在入门数据结构的时候会尽量回避这个地方,或者一笔带过,留下莫名其妙的学生们,背下来Hash Table的access是O(1)。而事实上这里的O(1)是有很多先决条件的。

第一,这是一个平均值,不是最差值。在Worst case下,Hash Table的access时间并非O(1),是会随着数据的增长而增长的。也就是说,我们常理上看,虽然有着每一份来的文件编号尾号都一样的可能性,但是平均上说,他们应该是分的比较开的。而如何把文件尽量分散地对应到相应的抽屉,也是一个学问,这里不赘言(思考一下如果按照常规的文件编号方法,顺序编号,用尾数和用开头的三位会有什么不同?)。

第二,你抽屉的数量要远大于文件的数量。如果你只有10个抽屉,有100份文件,那当然会随着文件数量的增加,找文件的速度变慢。对于Hash Table也是一个道理,你准备好的内存需要远大于实际使用的内存。如果你准备迎接100个数据,你可能就要准备400个以上的空位。随着数据量的增加,为了保证你的读写速度还在O(1),你的内存开销也会变大。换言之,一个理想Hash Table的读写速度确实是O(1),但是占用内存是无限大(因此理想Hash Table不存在)。

回到你的问题,在我们正常写程序的时候,所用到的数据量都不算太大(相对于可支配内存),所以我们可以把dict看作一个理想Hash Table。这时候随着key的增加,它确实不会变慢(占用内存变多)。但是到了极端情况,当你的key非常非常非常多的时候(这时候要看他Hash Table的具体实现),他的速度是有可能随着key的增加而减慢的。

发布于 2017-07-06

著作权归作者所有


你问的问题其实很有价值。这是很多初学数据结构的人的困扰,因为它没逻辑。凭什么我多大的数据量,访问速度都是一样的?这根本不符合常理。

很多人会告诉你,这是Hash Table,而Hash Table的访问速度是O(1)的,而对于你来说,这就和没说一样。这个答案既不算精确,也没能回答你的问题。

首先如果你真的想搞清楚这个问题的来龙去脉,你需要搞懂Hash Table到底是什么东西。Hash Table首先默认了一件事情,在电脑中,读取或者写入一个已知地址的内存需要的最大时间是固定的,和有可能写入内存的长度无关的。

举个例子,你在家有一个柜子,柜子上有一堆抽屉,你把这些抽屉分别编号为1-10。这时候我和你说,找10号抽屉,你可以立刻找到10号。我说找6号,你可以立刻找到6号。现在你的柜子扩大了,抽屉有100个,我说找56号,你还是可以立刻找到56号。你柜子又大了,变成了1000个抽屉,我说找729号,你依然可以立刻找到729号。

对于人类来说,这是不可能的。随着抽屉数量的增加,我们找对应抽屉的速度会下降。但是对于现在的计算机来说,这个假设是成立的。这是你要理解的第一点计算机和人类的不同。无论有多少抽屉,只要你说找这个号码的抽屉,不管是第一个,最后一个,还是中间任何抽屉,计算机的反应速度都一样。

好,现在假设我们有1000个抽屉,我们有4份文件。每一份文件有一个唯一且不重复的文件编码,这个编码是8位码,比如01303457。我们需要把这四份文件保存到抽屉里,并且希望下次有人来要这些文件的时候,我们可以立刻找到。

我们可以把这四份文件都放到第一个抽屉,然后人来的时候把四个文件找出来,逐一对比文件编码。这是一种线性数据结构,他的搜索速度和文件的数量是线性关系。我们有100份文件,速度大概是10份的10倍。我们管他叫O(N)。我们可以按照文件编码先把文件排序,然后都放第一个抽屉里。这样搜的时候,我们可以利用二分法来找文件。这时候我们的速度提高到了log(N)。随着文件的增加,我们的搜索时间还是在增加,但是增加的缓慢了。

然而还有一个方法。我们可以看文件的尾号,把他们放进和尾号对应的抽屉里。比如01303457号文件,我们就给他放到457号抽屉。我们可以想象,在文件比较少的时候,我们的每个抽屉很可能只有一份文件。这时候有个人来说我要01303457号文件,我们就可以直接去457号抽屉给她拿。由于我们找一个抽屉的速度时固定的,所以随着文件的增加,我们搜索文件的时间是没有增加的。

下面才是重点,也是两种逻辑产生冲突的地方。如果文件多了,肯定会有抽屉不止两个文件。最理想的情况下,在有1001份文件的时候,也会有一个抽屉有两份文件。而最差的情况,所有的文件尾号都一样,那我们不是回到了第一种方法么?

没错!你想的是完全正确的。相信自己的判断。

很多课在入门数据结构的时候会尽量回避这个地方,或者一笔带过,留下莫名其妙的学生们,背下来Hash Table的access是O(1)。而事实上这里的O(1)是有很多先决条件的。

第一,这是一个平均值,不是最差值。在Worst case下,Hash Table的access时间并非O(1),是会随着数据的增长而增长的。也就是说,我们常理上看,虽然有着每一份来的文件编号尾号都一样的可能性,但是平均上说,他们应该是分的比较开的。而如何把文件尽量分散地对应到相应的抽屉,也是一个学问,这里不赘言(思考一下如果按照常规的文件编号方法,顺序编号,用尾数和用开头的三位会有什么不同?)。

第二,你抽屉的数量要远大于文件的数量。如果你只有10个抽屉,有100份文件,那当然会随着文件数量的增加,找文件的速度变慢。对于Hash Table也是一个道理,你准备好的内存需要远大于实际使用的内存。如果你准备迎接100个数据,你可能就要准备400个以上的空位。随着数据量的增加,为了保证你的读写速度还在O(1),你的内存开销也会变大。换言之,一个理想Hash Table的读写速度确实是O(1),但是占用内存是无限大(因此理想Hash Table不存在)。

回到你的问题,在我们正常写程序的时候,所用到的数据量都不算太大(相对于可支配内存),所以我们可以把dict看作一个理想Hash Table。这时候随着key的增加,它确实不会变慢(占用内存变多)。但是到了极端情况,当你的key非常非常非常多的时候(这时候要看他Hash Table的具体实现),他的速度是有可能随着key的增加而减慢的。

发布于 2017-07-06

著作权归作者所有


其实字典这个东西,你就用现实中查字典去类比就能理解了。比如delicious,先找d开头的单词,在d开头的单词里面找第二个字母为e的单词,再在所有前两个字母为de的单词里面找第三个字母为l的单词。如此反复,直到找到位置。字典的key经过hash以后,会得到一串很长的类似于a1f3cb42edf97 这样的hash值。Python首先去找第一个字母为a的所有值,再找在第一个字母为a的情况下的第二个为1的所有值,就跟查字典一样。而所有这些key的hash的位数是固定的,假设是32位,那么不论是任何key,Python都只需要找32次就能找到。所以查找的时间是固定的。

作者:匿名用户
链接:https://www.zhihu.com/question/62050494/answer/194602324
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

+ 65 = 73