字典的高效键

Question

我是第一次在这里发帖，希望提供足够的细节。我想知道在Python中选择关键字是否会影响字典的效率。一些我正在考虑的比较如下：

• 数字与字符串（例如，my_dict[20]是否比my_dict['twenty']更快）
• 字符串的长度（例如，my_dict['a']是否比my_dict['abcdefg']更快）
• 混合使用键类型，例如使用数字，字符串和/或元组（例如，my_dict = {0: 'zero', 2: 'two'} 是否比 {0：'zero'，'two'：2} 更快）

我在谷歌搜索中没有找到这个主题，所以想着这里是否有人知道。

- ThatNewGuy

---

为了查找，使用整数哈希值。这使得该类型对性能影响非常小。 - Klaus D.

哈希对于几乎所有类型都非常快速。差异将非常小。我不会担心它。 - Patrick Haugh

请参考这个非常相似的SO问题（虽然不确定你的是否完全重复）。 - benvc

Answer 1

首先，我建议您了解Python内置字典是如何实现的。

现在，让我们做一个小的随机实验来证明这个理论（至少部分地）：

import timeit
import string
import random
import time


def random_str(N):
    return ''.join(
        random.choice(string.ascii_uppercase + string.digits) for _ in range(N)
    )


def experiment1(dct, keys):
    s = time.time()
    {dct[k] for k in keys}
    return time.time() - s


if __name__ == "__main__":
    N = 10000
    K = 200
    S = 50000
    dct1 = {random_str(K): None for k in range(N)}
    dct2 = {i: None for i in range(N)}
    keys1 = list(dct1.keys())
    keys2 = list(dct2.keys())

    samples1 = []
    samples2 = []
    for i in range(S):
        samples1.append(experiment1(dct1, keys1))
        samples2.append(experiment1(dct2, keys2))

    print(sum(samples1), sum(samples2))

    # print(
    #     timeit.timeit('{dct1[k] for k in keys1}', setup='from __main__ import dct1, keys1')
    # )

    # print(
    #     timeit.timeit('{dct2[k] for k in keys2}', setup='from __main__ import dct2, keys2')
    # )

我在我的电脑上使用不同的采样大小得到了以下结果:

• N=10000, K=200, S=100 => 0.08300423622131348 0.07200479507446289
• N=10000, K=200, S=1000 => 0.885051965713501 0.7120392322540283
• N=10000, K=200, S=10000 => 8.88549256324768 7.005417346954346
• N=10000, K=200, S=50000 => 43.57453536987305 34.82594871520996

所以你可以看到，无论你是使用大型随机字符串查找字典还是整数，在性能方面基本相同。唯一需要考虑的“真正”区别可能是两个字典的内存消耗。当将大型字典从磁盘中导出/导入时可能会有影响，这种情况下，拥有紧凑形式的数据结构可能值得一试，这样在缓存/读取它们时就可以节省几秒钟的时间。

NS：如果有人能够解释为什么我在使用timeit（被注释掉的部分）时会得到非常高的时间，请告诉我……我用了一些实验常数，结果得到了非常高的值……这就是为什么我把它注释掉了。如果您知道原因，请添加评论;D

- BPL

Answer 2

我也不知道答案，但测试起来很容易。

from timeit import default_timer as timer
import string

#Create a few dictionaries, all the values are None
nums = range(1,27)
dict_numbers = dict.fromkeys(nums)

letters = string.ascii_lowercase
dict_singleLetter = dict.fromkeys(letters)

long_names = []
for letter in letters:
    long_names.append(''.join([letter, letters]))
dict_longNames = dict.fromkeys(long_names)

#Function to time thousands of runs to average out discrepancies
def testSpeed(dictionary, keys):
    x = None
    start = timer()
    for _ in range(1,100000):
        for i in keys:
            x = dictionary[i]
    end = timer()

    return str(end - start)

#Time the different dictionaries
print("Number took " + testSpeed(dict_numbers, nums) + " seconds")
print("Single letters took " + testSpeed(dict_singleLetter, letters) + " seconds")
print("Long keys took " + testSpeed(dict_longNames, long_names) + " seconds")

所有这些字典的长度都相同，并且每个键都包含相同的值。当我运行时，具有长键的字典实际上总是最快的，尽管可能只快了5％。这可能可以解释其他我不知道的小差异。数字和单个字母的速度非常接近，但数字通常比单个字母稍微快一点。希望这回答了您的问题，而且这段代码应该很容易扩展以测试混合情况，但我现在没有时间。

- Gunnar