为什么Python dict在查找/更新值时比set更有效？

Question

在解决leetcode 3sum问题时，我提交了以下代码：

class Solution1:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        res = set()
        nums.sort()
        for firstEle in range(len(nums)-2):
            if firstEle > 0 and nums[firstEle] == nums[firstEle - 1]:
                continue
            target = 0 - nums[firstEle]
            dic = {}
            for j in range(firstEle+ 1,len(nums)):
                if target - nums[j] in dic:
                    res.add((nums[firstEle], target - nums[j], nums[j]))
                else:
                    dic[nums[j]] = j
        return list(map(list, res))

运行时间约为844毫秒

我将dict替换为set，并修改代码如下：

class Solution2:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        res = set()
        nums.sort()
        for firstEle in range(len(nums)-2):
            if firstEle > 0 and nums[firstEle] == nums[firstEle - 1]:
                continue
            target = 0 - nums[firstEle]
            mem = set()
            for j in range(firstEle+ 1,len(nums)):
                if target - nums[j] in mem:
                    res.add((nums[firstEle], target - nums[j], nums[j]))
                else:
                    mem.add(nums[j])
        return list(map(list, res))

然后得到了大约1044毫秒的运行时间

为什么数据结构会降低效率？你知道吗

更新时间：

我在笔记本电脑上测试了代码：

import timeit
s1 = Solution1()
s2 = Solution2()

print("dict:", timeit.timeit(lambda: s1.threeSum([-1, 0, 1, 2, -1, -4]), number=100000))

print("set:", timeit.timeit(lambda: s2.threeSum([-1, 0, 1, 2, -1, -4]), number=100000))

得到了结果：

dict: 0.671448961016722
set: 0.7314219229156151

环境：

MacBook Pro（视网膜，13英寸，2015年初）

CPU:2.7 GHz英特尔酷睿i5

内存：8 GB 1867 MHz DDR3

Python版本：3.6

似乎set还是比较慢。你知道吗

Answer 1

检查以下链接：

PythonWiki : TimeComplexity

time-complexity-of-python-set-operations

time-complexity-of-accessing-a-python-dict

set和dict的时间复杂度都是O（1）。你知道吗