python 效能提升的幾種方法

關於python 性能提升的一些方案。

一、函數呼叫最佳化（空間跨度，避免存取記憶體）

 程式的最佳化核心點在於盡量減少操作跨度，包括程式碼執行時間上的跨度以及記憶體中空間跨度。

1.大數據求和，使用sum

a = range(100000)
%timeit -n 10 sum(a)
10 loops, best of 3: 3.15 ms per loop
%%timeit
  ...: s = 0
  ...: for i in a:
  ...:  s += i
  ...:
100 loops, best of 3: 6.93 ms per loop

2.小數據求和，避免使用sum

%timeit -n 1000 s = a + b + c + d + e + f + g + h + i + j + k # 数据量较小时直接累加更快
1000 loops, best of 3: 571 ns per loop
%timeit -n 1000 s = sum([a,b,c,d,e,f,g,h,i,j,k]) # 小数据量调用 sum 函数，空间效率降低
1000 loops, best of 3: 669 ns per loop

結論：大數據求和sum效率高，小數據求和直接累加效率高。

二、for循環最佳化之取元素（使用堆疊或暫存器，避免存取記憶體）

for lst in [(1, 2, 3), (4, 5, 6)]: # lst 索引需要额外开销
  pass

　應盡量避免使用索引。

for a, b, c in [(1, 2, 3), (4, 5, 6)]: # better
  pass

相當於給每一個元素直接賦值。

def force():
 lst = range(4)
 for a1 in [1, 2]:
   for a2 in lst:
     for a3 in lst:
       for b1 in lst:
         for b2 in lst:
           for b3 in lst:
             for c1 in lst:
               for c2 in lst:
                 for c3 in lst:
                   for d1 in lst:
                     yield (a1, a2, a3, b1, b2, b3, c1, c2, c3, d1)
                      
%%timeit -n 10
for t in force():
  sum([t[0], t[1], t[2], t[3], t[4], t[5], t[6], t[7], t[8], t[9]])
10 loops, best of 3: 465 ms per loop
%%timeit -n 10
for a1, a2, a3, b1, b2, b3, c1, c2, c3, d1 in force():
  sum([a1, a2, a3, b1, b2, b3, c1, c2, c3, d1])
10 loops, best of 3: 360 ms per loop

三、生成器最佳化（查表代替運算）

def force(start, end): # 用于密码暴力破解程序
  for i in range(start, end):
    now = i
    sublst = []
    for j in range(10):
      sublst.append(i % 10) # 除法运算开销较大，比乘法大
      i //= 10
    sublst.reverse()
    yield(tuple(sublst), now)

def force(): # better
 lst = range(5)
 for a1 in [1]:
   for a2 in lst:
     for a3 in lst:
       for b1 in lst:
         for b2 in lst:
           for b3 in lst:
             for c1 in lst:
               for c2 in lst:
                 for c3 in lst:
                   for d1 in lst:
                     yield (a1, a2, a3, b1, b2, b3, c1, c2, c3, d1)
　　

r0 = [1, 2] # 可读性与灵活性
r1 = range(10)
r2 = r3 = r4 = r5 = r6 = r7 = r8 = r9 = r1
force = ((a0, a1, a2, a3, a4, a5, a6, a7, a8, a9)
      for a0 in r0 for a1 in r1 for a2 in r2 for a3 in r3 for a4 in r4
      for a5 in r5 for a6 in r6 for a7 in r7 for a8 in r8 for a9 in r9)

 四、冪運算最佳化（pow（x，y，z））　

def isprime(n):
  if n & 1 == 0:
    return False
  k, q = find_kq(n)
  a = randint(1, n - 1)
  if pow(a, q, n) == 1: # 比使用 a ** q % n 运算优化数倍
    return True
  for j in range(k):
    if pow(a, pow(2, j) * q, n) == n - 1: # a **((2 ** j) * q) % n
      return True
  return False

 結論：pow（x,y,z）優於x**y%z.

 五、除法運算最佳化

In [1]: from random import getrandbits
 
In [2]: x = getrandbits(4096)
 
In [3]: y = getrandbits(2048)
 
In [4]: %timeit -n 10000 q, r = divmod(x, y)
10000 loops, best of 3: 10.7 us per loop
 
In [5]: %timeit -n 10000 q, r = x//y, x % y
10000 loops, best of 3: 21.2 us per loop

 結論：divmod優於//和%。

 六、最佳化演算法時間複雜度　　

演算法的時間複雜度對程式的執行效率影響最大，在python中可以選擇適當的資料結構來最佳化時間複雜度，如list和set找出某一個元素的時間複雜度分別是O(n)和O( 1)。不同場景有不同的最佳化方式，總的來說，一般有分治，分支定界、貪心動態規劃等思想。

七、合理使用copy和deepcopy　　

對於dict和list等資料結構的對象，直接賦值使用的是引用的方式。而有些情況下需要複製整個對象，這時可以使用copy包裡的copy和deepcopy，這兩個函數的不同之處在於deepcopy是遞歸複製的。效率不同：

In [23]: import copy
In [24]: %timeit -n 10 copy.copy(a)
10 loops, best of 3: 606 ns per loop
In [25]: %timeit -n 10 copy.deepcopy(a)
10 loops, best of 3: 1.17 us per loop

 timeit後面的-n表示運行的次數，後兩行對應的是兩個timeit的輸出，下同。由此可見後者慢一個數量級。

 關於copy的例子：

>>> lists = [[]] * 3
>>> lists
[[], [], []]
>>> lists[0].append(3)
>>> lists
[[3], [3], [3]]

 發生的事情是這樣的，[[]]是包含一個空列表的只有一個元素的列表，所以[[]] * 3的所有三個元素都是（指向）這個空列表。修改lists的任何元素都修改這個清單。修改效率高。

 八、使用dict或set找出元素

python 字典和集合都是使用hash表來實作（類似c++標準函式庫unordered_map），而找出元素的時間複雜度是O(1)。

In [1]: r = range(10**7)
In [2]: s = set(r) # 占用 588MB 内存
In [3]: d = dict((i, 1) for i in r) # 占用 716MB 内存
In [4]: %timeit -n 10000 (10**7) - 1 in r
10000 loops, best of 3: 291 ns per loop
In [5]: %timeit -n 10000 (10**7) - 1 in s
10000 loops, best of 3: 121 ns per loop
In [6]: %timeit -n 10000 (10**7) - 1 in d
10000 loops, best of 3: 111 ns per loop

結論：set 的記憶體佔用量最小，dict運行時間最短。

九、合理使用（generator）和yield（節省記憶體）

In [1]: %timeit -n 10 a = (i for i in range(10**7)) # 生成器通常遍历更高效
10 loops, best of 3: 933 ns per loop
In [2]: %timeit -n 10 a = [i for i in range(10**7)]
10 loops, best of 3: 916 ms per loop
In [1]: %timeit -n 10 for x in (i for i in range(10**7)): pass
10 loops, best of 3: 749 ms per loop
In [2]: %timeit -n 10 for x in [i for i in range(10**7)]: pass
10 loops, best of 3: 1.05 s per loop

結論：盡量使用生成器去遍歷。

以上就是對python 性能提升的一些方案，後續繼續補充，需要的可以看下。