学习python的小伙伴都知道python语法简单，学习起来上手快。但是代码的运行效率一直让人诟病。确实，在一些场景中，python代码的运行效率确实没有C++或者C效率高。但是在一些场景下，我们也可以通过一些优化来提升运行效率。下面我们从一道算法题入手带着大家剖析一下。
题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标，如果有多组，只返回一组即可。这道题非常简单，是Leecode刷题网站的第1题。下面我们按步骤来解析优化。
1. 方法1：最简单的想法，for循环暴力解决：
最简单粗暴的方法，即从列表的第一个数开始，依次与后面的数相加看看是否等于目标值。如果不满足，在取第二个数，并与它后面的数相加直至将所有的数遍历一遍，代码如下：
def find_pairs(target, nums_list):
"""
:para:target, int, the required target of 2 nums in the nums_list
:para:nums_list, a list of int nums
:return: the 2 nums index in the list, which sum is target value.
"""
for i in range(len(nums_list)):
for j in range(i + 1, len(nums_list)):
if nums_list[i] + nums_list[j] == target:
print(f'For target: {target}, index is: {i}, {j} , value is {nums_list[i]}, {nums_list[j]}')
return i, j
return None # 如果循环结束还没有符合的输出None
我们用两个测试案例检验一下
target1,nums_list1 = 14, [3,6,9,1,4,5] # 正常案例， 输出index 2,5
target2,nums_list2 = 20, [3,6,9,1,4,5] # 没有合适的数值，输出None
result1 = find_pairs(target1, nums_list1)
result2 = find_pairs(target2, nums_list2)
print('******* Following is the result ******')
print(result1)
print(result2)
>>>For target: 14, index is: 2, 5 , value is 9, 5
******* Following is the result ******
(2, 5)
None
上面的方法使用了两重循环，其效率非常低。可以稍微换位思考一下，我们使用target依次减去列表中元素获得一个差值，在判断该差值是否在列表剩下的元素中同样可以解决问题，这样我们只使用一个循环就可以完成。
2. 方法二：改进版，查找列表中是否存在target减去当前值的差
代码如下：
def find_pairs_v2(target, nums_list):
"""
:para:target, int, the required target of 2 nums in the nums_list
:para:nums_list, a list of int nums
:return: the 2 nums index in the list, which sum is target value.
"""
for i in range(len(nums_list)):
a = target - nums_list[i]
if a in nums_list[i+1:]:
j = nums_list.index(a)
print(f'For target: {target}, index is: {i}, {j} , value is {nums_list[i]}, {nums_list[j]}')
return i, j
return None
下面使用两个测试案例对两个方法的运行时间进行比较，看看效率是否有提升
先确保两个方法都的行为一致，即输出同样的结果：
# 使用同一个测试用例， 首先确保两个方法的行为一致，输出的结果相同
target,nums_list = 50, [3,6,9,1,4,5,14,20,30]
result1 = find_pairs(target, nums_list)
result2 = find_pairs_v2(target, nums_list)
print(f"result from 2-for-loop is: {result1}")
print(f"result from improved one for loop is: {result2}")
>>>result from 2-for-loop is: (7, 8)
result from improved one for loop is: (7, 8)
上面的案例中，将target设置成50，强制程序走到最后一个循环，对比最差情况下的时间效率。下面使用%timeit魔法命令测试运行时间。该魔法命令的详细用法可以参考：N多Notebook技巧让你的Jupyter notebook起飞 - 简书 (jianshu.com)
注意: 以下该魔法命令的演示是在Notebook中完成的。为了让程序运行过程中不在输出print语句，需要把上面方法定义中的print语句注释掉。
%timeit find_pairs(target, nums_list)
>>>10.2 µs ± 3.26 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit find_pairs_v2(target, nums_list)
>>>4.62 µs ± 1.12 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
可以看到改成一个for循环后运行时间减少了一倍左右，这个随着列表元素的增多效果更加明显。
3. 进一步提升
上面的方法二在判断一个元素是否在列表中的时候，实际上内部仍然是通过遍历列表来完成的。在比较极端的情况下时间复杂度仍然为O(n)。那么有没有方法改进呢？有的，在Python查找元素，相对于列表，字典是一种更加高效的数据结构。字典的键是有可哈希的数据构成，查找字典中的键以及通过这个键取值的时间复杂度均为O(1)。所以，思路来了，我们将列表转换为字典，使用字典的键作为列表中的元素，值为该元素在列表中的index。查找命中该键后直接输出该键对应的值即可，代码如下：
def find_pairs_v3(target, nums_list):
temp_map = dict()
for i, num in enumerate(nums_list):
if target - num in temp_map:
j = temp_map[target - num]
print(f'For target: {target}, index is: {i}, {j} , value is {nums_list[i]}, {nums_list[j]}')
return [temp_map[target - num], i]
temp_map[nums_list[i]] = i
return None
同样的，我们使用和上面同一个用例测试一下：
print(target, nums_list)
find_pairs_v3(target, nums_list)
>>>50 [3, 6, 9, 1, 4, 5, 14, 20, 30]
For target: 50, index is: 8, 7 , value is 30, 20
下面使用同一个案例测试V2和V3版本的运行时间，看看是不是改成字典后效率有所提升：
%timeit find_pairs_v3(target, nums_list)
>>>2.68 µs ± 4.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
效率有所提升，但是不明显。将时间复杂度从O(n)降低到O(1)，这个是数量级方面的提升。猜测可能是因为列表的长度不够，我们将列表长度增加再来尝试一下。
上面代码中，在列表的末尾插入两个元素100,200，在将target设置成300，强制让程序走到最后一个循环测试最差的情况。
可以看到将列表的长度增加到900后，运行时间有了数量级的提升，但这个还不够。这样的差异对于O(n)和O(1)仍然不够可观。其中的原因，猜测可能是Python内部对于这种int型的数据有相应的优化。如果我们将需要查找的元素改为字符串再来对比一下列表和字典元素查找的效率。
4. 使用字符串测试列表和字典的查找时间效率
首先我们定义一个方法可以生成任意长度的字符串列表name_list，并规定name_list中字符串元素的长度。代码如下：
# 首先定义一个方法产生长度为n的列表，列表中每个元素包含m的字符（大写或者小写）
import string
import random
def gen_name_list(list_len, name_len):
name_list = []
while len(name_list) < list_len:
name = ''.join(random.sample(string.ascii_letters, name_len))
if name not in name_list:
name_list.append(name)
return name_list
# test
gen_name_list(5, 6) # 测试：生成一个包含5个元素的列表，每个元素长度6
>>> ['LCBmZR', 'vrFypk', 'GCTdMh', 'eOMqHc', 'dHVxDA']
好了，有个这个方法后， 我们先用这个方法生成一个包含1000个元素的字符串列表，每个字符串包含8个元素，同时，将列表的中间元素和最后一个元素取出备用。另外再将这个列表转成字典：
result_list = gen_name_list(1000, 8)
print(result_list[:5])
mid_str, last_str = result_list [500], result_list[-1]
print(mid_str, last_str)
result_dict = {k:v for v,k in enumerate(result_list)} # 将列表转换成字典，键为元素，值为该元素在列表中的index
print(result_dict[mid_str], result_dict[last_str])
>>>['rGvpIBET', 'igwoZJKC', 'faEXAzTl', 'xIwibYGK', 'DqUClGkZ']
FOosAXyl bWryJKuB
500 999
下面我们只测试列表和字典的查找效率，查找的代码如下：
def find_key_list(key, list):
if key in list:
return key
else:
return None
def find_key_dict(key, dict):
if key in dict:
return key
else:
return None
测试前，使用测试案例确保两个方法的行为一致：
r1_list = find_key_list(mid_str, result_list)
r2_list = find_key_list(last_str, result_list)
r1_dict = find_key_dict(mid_str, result_dict)
r2_dict = find_key_dict(last_str, result_dict)
print(r1_list, r2_list)
print(r1_dict, r2_dict)
>>>FOosAXyl bWryJKuB
FOosAXyl bWryJKuB
运行时间统计，仍然使用%timeit魔法方法，结果如下图：
OK， 这个效果就比较明显了。而且从上面的结果中，也可以验证我们的结论：
- 列表查找时本质上仍然是采用循环来遍历。我们从查找中间元素和队列末尾元素的用时也能看出来，随着该元素越靠后，用时越长。上面的结果中，中间元素用时11.5us, 而队尾元素用时16.8us, 差异明显
- 而对于字典来说，第一，其查找效率相对于列表有个质的提升。而且，因为其时间复杂度为O(1), 其查找的时间与元素的位置无关。上面的结果中，中间元素用时192ns， 队尾元素用时198ns, 几乎没有差别
注意：以上测试结果和测试平台软硬件均有关，不同的配置结果可能会有差异
好了，以上就是本次分享案例的所有内容。从这个案例中我们可以深刻的领会到在列表中查找一个元素的时间复杂度为O(n), 而在字典中获取一个键的时间复杂度为O(1)。同时在解析过程带着大家领略一下Python中列表和字典的一些小技巧，例如将一个列表转成字典，随机生成一个固定长度的字符串等等，希望大家看完有所收获。如果对你有所帮忙，还希望点个赞+一键3连！感谢！
