python中 in 在 list 和 dict 中查找效率-不要用 in 列表 !

坑爹的知识点！
我一直用in list，程序运行一直超时，前前后后检查代码好几遍，发现除了遍历这里不一样，其余都一样，百度一查才知道 in list 的效率比 in dict 的效率低很多！！

切记：能用in dic.keys() 就不要用 in list

import time

query_lst = [-60000,-6000,-600,-60,-6,0,6,60,600,6000,60000]

lst = []
dic = { 
   }

for i in range(10000000):
    lst.append(i)
    dic[i] = 1
start = time.time()
for v in query_lst:
    if v in lst:
        continue
end1 = time.time()

for v in query_lst:
    if v in dic:
        continue

end2 = time.time()

for v in query_lst:
    if v in dic.keys():
        continue

end3 = time.time()

print (end1-start)
print (end2-end1)
print(end3-end2)

输出为：

0.7265586853027344
0.0
0.0

可以看出，in list 速度比 in dic 慢很多

总结

list的查找效率远远低于dict的效率，原因如下：

python中list对象的存储结构采用的是顺序存储，因此其查询复杂度为O(n), 而dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)。

编程题目：

给定长度为N的整数数组，以及M个互不相同的整数，请找出包含这M个整数的最短子数组。例如：给定数组[4 2 1 3]，包含数字集{2, 3}的最短子数组是[2 1 3]，包含数字集{1, 3}的最短子数组是[1 3]。

输入描述:
第一行一个正整数T（T<=10），表示T个测试样例；对于每个测试样例，输入正整数N（N<=100,000），表示数组长度；接下来输入N个正整数，所有整数都>=0且<=1,000,000,000；输入正整数M（M<=N），表示M个互不相同的整数；接下来输入M个整数，表示要查询的整数，已保证互不相同。有部分测试样例满足N<=1,000。

输出描述:
输出T行，每行一个正整数，表示最短子数组的长度。如果不存在，输出0

示例1

输入
1
4
4 2 1 3
2
2 3

输出
3
下面是我做题过程中，发现以上问题的题目：
使用 in list 一直说超时：代码中是 in nums

while True:
    try:
        T = int(input())
        for t in range(T):
            n = int(input())
            arrs = [int(item) for item in input().strip().split()]
            m = int(input())
            nums = [int(item) for item in input().strip().split()]
            need_dic = { 
   }
            for i in range(m):
                need_dic[nums[i]] = 1
            l = r = 0
            dic = { 
   }
            count = 0
            ans = n
            while r < n:
                char = arrs[r]
                if char in nums:
                    dic[char] = dic.get(char,0) + 1
                    if dic[char] == need_dic[char]:
                        count += 1

                while count == m:
                    ans = min(ans, r - l + 1)
                    print(ans,r,l)
                    if arrs[l] in nums:
                        dic[arrs[l]] -= 1
                        if dic[arrs[l]] < 1:
                            count -= 1
                    l += 1
                r += 1
            print(ans) if ans != n else 0
    except:
        break

修改之后 in dic.keys()成功提交：

while True:
    try:
        T = int(input())
        for t in range(T):
            n = int(input())
            arrs = [int(item) for item in input().strip().split()]
            m = int(input())
            nums = [int(item) for item in input().strip().split()]
            need_dic = { 
   }
            for i in range(m):
                need_dic[nums[i]] = 1
            l = r = 0
            dic = { 
   }
            count = 0
            ans = n + 1
            while r < n:
                char = arrs[r]
                if char in need_dic.keys():
                    dic[char] = dic.get(char,0) + 1
                    if dic[char] == need_dic[char]:
                        count += 1
                while count == m:
                    ans = min(ans, r - l + 1)
                    if arrs[l] in need_dic.keys():
                        dic[arrs[l]] -= 1
                        if dic[arrs[l]] < 1:
                            count -= 1
                    l += 1
                r += 1
            if ans != n+1:
                print(ans)
            else:
                print(0)
            #print(ans if ans != n + 1 else 0)
    except:
        break