Python 性能优化｜元素极少时 list 和 set 的查找速度_list查找复杂度

结论：

• 当集合中元素为整数时：若元素数量小于等于 2，则 list 的查找性能略优于在 set；若元素数量大于 2 时，则 set 的查找性能显著优于 list。
• 当集合中元素为字符串时：无论元素数量是多少，set 的查找性能略优于在 list。

建议：无论元素数量和元素类型，如需进行查找，直接使用 set 即可。

---

分析过程如下：

因为在 Python 中 list 的底层数据结构是数组，查找一个元素的时间复杂度是 $O(N)$，set 的底层数据结构是哈希表，查找一个元素的时间复杂度是 $O(1)$，所以如果 list 和 set 中元素较多，那么在 list 中查找一个元素的速度一定比在 set 中查找一个元素慢。

但是，在 set 中查找一个元素，需要先计算哈希值再在哈希表中查找，其时间复杂度的系数可能更大。因此，怀疑当元素极少时，是否在 list 中的查找速度比 set 更快的情况？

验证 1：整数元素的查找性能

for n in range(1, 11):
    t1 = timeit.timeit(
        f"{n} in ss",
        setup="ss = {i for i in range(%d)}" % n,
        number=10000000
    )
    t2 = timeit.timeit(
        "\n".join([f"{i} in ss" for i in range(n)]),
        setup="ss = {i for i in range(%d)}" % n,
        number=10000000
    )
    t2 /= n

    t3 = timeit.timeit(
        "\n".join([f"{i} in ss" for i in range(n)]),
        setup="ss = [i for i in range(%d)]" % n,
        number=10000000
    )

    t4 = timeit.timeit(
        "\n".join([f"{i} in ss" for i in range(n)]),
        setup="ss = [i for i in range(%d)]" % n,
        number=10000000
    )
    t3 /= n
    t4 /= n

    print(n, ":", round(t1, 4), round(t3, 4), round(t2, 4), round(t4, 4))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1 : 0.2725 0.3951 0.3137 0.2326
2 : 0.2625 0.2518 0.2677 0.2461
3 : 0.2592 0.3511 0.2173 0.3298
4 : 0.2861 0.3939 0.2901 0.383
5 : 0.2776 0.4827 0.2333 0.485
6 : 0.2977 0.5183 0.229 0.5241
7 : 0.2866 0.5703 0.2257 0.5755
8 : 0.3617 0.671 0.2335 0.8581
9 : 0.3613 0.7754 0.2474 0.7343
10 : 0.2869 0.8404 0.2251 0.8088
1
2
3
4
5
6
7
8
9
10

其中 t1 为在 set 中查找不存在元素的时间，t2 为在 list 中查找不存在元素的时间，t3 为在 set 中查找存在元素的时间期望，t4 为在 list 中查找存在元素的时间期望。

可以看到，当元素数量小于等于 2 时，list 的查找性能略优于在 set，当元素数量大于 2 时，set 的查找性能显著优于 list。

对于整数来说，在 Python 中其哈希值就是它本身，因此在使用 set 时不需要额外计算哈希值；整数是否相等的判断的直接比较即可，因此在使用 list 时也不需要额外判断是否相等。

验证 2：字符串元素的查找性能

for n in range(1, 11):
    t1 = timeit.timeit(
        f"'{n}' in ss",
        setup="ss = {str(i) for i in range(%d)}" % n,
        number=10000000
    )
    t2 = timeit.timeit(
        "\n".join([f"'{i}' in ss" for i in range(n)]),
        setup="ss = {str(i) for i in range(%d)}" % n,
        number=10000000
    )
    t2 /= n

    t3 = timeit.timeit(
        "\n".join([f"'{i}' in ss" for i in range(n)]),
        setup="ss = [str(i) for i in range(%d)]" % n,
        number=10000000
    )

    t4 = timeit.timeit(
        "\n".join([f"'{i}' in ss" for i in range(n)]),
        setup="ss = [str(i) for i in range(%d)]" % n,
        number=10000000
    )
    t3 /= n
    t4 /= n

    print(n, ":", round(t1, 4), round(t3, 4), round(t2, 4), round(t4, 4))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1 : 0.2795 0.4101 0.3468 0.4128
2 : 0.2799 0.4645 0.3163 0.441
3 : 0.3148 0.5627 0.3365 0.5785
4 : 0.2907 0.6019 0.2929 0.6104
5 : 0.263 0.7906 0.3018 0.9251
6 : 0.2917 0.8355 0.3358 0.8554
7 : 0.296 0.9797 0.3165 0.9614
8 : 0.327 1.0284 0.3417 1.0674
9 : 0.286 1.1635 0.3045 1.1854
10 : 0.292 1.2718 0.3046 1.2978
1
2
3
4
5
6
7
8
9
10

其中 t1 为在 set 中查找不存在元素的时间，t2 为在 list 中查找不存在元素的时间，t3 为在 set 中查找存在元素的时间期望，t4 为在 list 中查找存在元素的时间期望。

可以看到，无论元素数量是多少，set 的查找性能略优于在 list。

对于字符串来说，在使用 set 时需要额外计算哈希值；字符串是否相等的判断也相对复杂，在使用 list 时也需要额外的判断。

---

以上验证在 Python 3.9 的环境下执行。