Exc*_*ior 4 python optimization performance dictionary
我不清楚字典查找的幕后发生了什么.密钥大小是否与该密钥的查找速度有关？
当前字典键在10-20长,字母数字之间.
我需要每分钟进行数百次查找.
如果我用1到4位数字的较小密钥ID替换那些,我会获得更快的查找时间吗？这意味着我需要在字典中包含的每个项目中添加另一个值.整体而言,字典会更大.
此外,我需要更改程序以查找ID,然后获取与ID关联的URL.
我是否可能只是为程序增加复杂性而没什么好处？
字典是哈希表,因此查找键包括:
通常情况下,这是摊销的固定时间,你不关心任何事情.有两个潜在的问题,但它们并不经常出现.
散列密钥占用密钥长度的线性时间.例如,对于大字符串,这可能是个问题.但是,如果你看看源代码,最重要的类型,包括[ str/ unicode](https://hg.python.org/cpython/file/default/Objects/unicodeobject.c,你会发现它们缓存第一次使用哈希.所以,除非你输入(或随机创建,或者其他什么)一串字符串来查找一次然后丢弃,否则这在大多数现实生活中都不太可能成为问题.
最重要的是,20个字符真的很短; 你可能每秒可以做数百万次这样的哈希,而不是数百次.
通过在我的计算机上进行快速测试,散列20个随机字母需要973ns,散列4位数字需要94ns,并且散列我已经散列的值需要77ns.是的,那是纳秒.
同时,"用结果索引表格"有点作弊.如果两个不同的键散列到同一个索引会发生什么？然后"比较查找的密钥"将失败,并且...接下来会发生什么？CPython的实现使用探测器.精确的算法在源代码中得到了很好的解释.但是你会注意到,鉴于真正的病态数据,你最终可能会对每个元素进行线性搜索.这是永远不会出现的 - 除非有人可以通过明确制作病理数据来攻击您的程序,在这种情况下它肯定会出现.
从20个字符的字符串切换到4位数字也无济于事.如果我正在通过词典冲突来制作你的系统的DoS键,我不关心你的实际键是什么样的,只是他们哈希的东西.
更一般地说,过早优化是万恶之源.这有时候被错误地引用来夸大这一点; Knuth认为最重要的事情是找到优化很重要的3%的情况,而不是优化总是浪费时间.但无论哪种方式,重点是:如果你事先不知道你的程序在哪里太慢(如果你认为你提前知道,你通常是错的......),对它进行分析,然后找到你所在的部分获得最大的收益.优化代码的任意一段可能根本没有可衡量的影响.