在刷题的时候,经常碰到需要生成非常大的邻接矩阵,往往我们都是用 list 存储,但是我在最近刷题的过程中就遇上了TLE的情况,原因就是生成邻接矩阵时间太花时间了。
先说结论:[ ]* n 比 [ for i in range(n) ]列表生成式的速度快,差不多快3倍多
尽量使用邻接表代替邻接矩阵。比如在leetcode 1786这道题中,使用了邻接矩阵,直接超时;把邻接矩阵去除之后,直接双百。
import time
t1 = time.clock()
z = [[0]*20000 for i in range(20000)]
print(time.clock()-t1)
#6.8233608
t2 =time.clock()
z = [[0]*20000]*20000
print(time.clock()-t2)
#1.9150372
|