加速 Python for 迴圈

2024-06-06碼農

點選上方 " Python人工智慧技術 " 關註，星標或者置頂

22點24分準時推播，第一時間送達

後台回復「 大禮包 」，送你特別福利

編輯：樂樂 | 來自： deephub

正文

大家好，我是Python人工智慧技術

在本文中，我將介紹一些簡單的方法，可以將Python for迴圈的速度提高1.3到900倍。

Python內建的一個常用功能是timeit模組。下面幾節中我們將使用它來度量迴圈的當前效能和改進後的效能。

對於每種方法，我們透過執行測試來建立基線，該測試包括在10次測試執行中執行被測函式100K次(迴圈)，然後計算每個迴圈的平均時間(以納秒為單位，ns)。

幾個簡單方法

1、列表推導式

# Baseline version (Inefficient way) # Calculating the power of numbers # Without using List Comprehension def test_01_v0(numbers): output = [] for n in numbers: output.append(n ** 2.5) return output # Improved version # (Using List Comprehension) def test_01_v1(numbers): output = [n ** 2.5 for n in numbers] return output

結果如下：

# Summary Of Test Results Baseline: 32.158 ns per loop Improved: 16.040 ns per loop % Improvement: 50.1 % Speedup: 2.00x

可以看到使用列表推導式可以得到2倍速的提高

2、在外部計算長度

如果需要依靠列表的長度進行叠代，請在for迴圈之外進行計算。

# Baseline version (Inefficient way) # (Length calculation inside for loop) def test_02_v0(numbers): output_list = [] for i in range(len(numbers)): output_list.append(i * 2) return output_list # Improved version # (Length calculation outside for loop) def test_02_v1(numbers): my_list_length = len(numbers) output_list = [] for i in range(my_list_length): output_list.append(i * 2) return output_list

透過將列表長度計算移出for迴圈，加速1.6倍，這個方法可能很少有人知道吧。

# Summary Of Test Results Baseline: 112.135 ns per loop Improved: 68.304 ns per loop % Improvement: 39.1 % Speedup: 1.64x

3、使用Set

在使用for迴圈進行比較的情況下使用set。

# Use for loops for nested lookups def test_03_v0(list_1, list_2): # Baseline version (Inefficient way) # (nested lookups using for loop) common_items = [] for item in list_1: if item in list_2: common_items.append(item) return common_items def test_03_v1(list_1, list_2): # Improved version # (sets to replace nested lookups) s_1 = set(list_1) s_2 = set(list_2) output_list = [] common_items = s_1.interp(s_2) return common_items

在使用巢狀for迴圈進行比較的情況下，使用set加速498x

# Summary Of Test Results Baseline: 9047.078 ns per loop Improved: 18.161 ns per loop % Improvement: 99.8 % Speedup: 498.17x

4、跳過不相關的叠代

避免冗余計算，即跳過不相關的叠代。

# Example of inefficient code used to find # the first even square in a list of numbers def function_do_something(numbers): for n in numbers: square = n * n if square % 2 == 0: return square return None # No even square found # Example of improved code that # finds result without redundant computations def function_do_something_v1(numbers): even_numbers = [i for n in numbers if n%2==0] for n in even_numbers: square = n * n return square return None # No even square found

這個方法要在設計for迴圈內容的時候進行程式碼設計，具體能提升多少可能根據實際情況不同：

# Summary Of Test Results Baseline: 16.912 ns per loop Improved: 8.697 ns per loop % Improvement: 48.6 % Speedup: 1.94x

5、程式碼合並

在某些情況下，直接將簡單函式的程式碼合並到迴圈中可以提高程式碼的緊湊性和執行速度。

# Example of inefficient code # Loop that calls the is_prime function n times. def is_prime(n): if n <= 1: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True def test_05_v0(n): # Baseline version (Inefficient way) # (calls the is_prime function n times) count = 0 for i in range(2, n + 1): if is_prime(i): count += 1 return count def test_05_v1(n): # Improved version # (inlines the logic of the is_prime function) count = 0 for i in range(2, n + 1): if i <= 1: continue for j in range(2, int(i**0.5) + 1): if i % j == 0: break else: count += 1 return count

這樣也可以提高1.3倍

# Summary Of Test Results Baseline: 1271.188 ns per loop Improved: 939.603 ns per loop % Improvement: 26.1 % Speedup: 1.35x

這是為什麽呢？

呼叫函式涉及開銷，例如在堆疊上推入和彈出變量、函式尋找和參數傳遞。當一個簡單的函式在迴圈中被重復呼叫時，函式呼叫的開銷會增加並影響效能。所以將函式的程式碼直接行內到迴圈中可以消除這種開銷，從而可能顯著提高速度。

⚠️但是這裏需要註意，平衡程式碼可讀性和函式呼叫的頻率是一個要考慮的問題。

一些小技巧

6 .避免重復

考慮避免重復計算，其中一些計算可能是多余的，並且會減慢程式碼的速度。相反，在適用的情況下考慮預計算。

def test_07_v0(n): # Example of inefficient code # Repetitive calculation within nested loop result = 0 for i in range(n): for j in range(n): result += i * j return result def test_07_v1(n): # Example of improved code # Utilize precomputed values to help speedup pv = [[i * j for j in range(n)] for i in range(n)] result = 0 for i in range(n): result += sum(pv[i][:i+1]) return result

結果如下

# Summary Of Test Results Baseline: 139.146 ns per loop Improved: 92.325 ns per loop % Improvement: 33.6 % Speedup: 1.51x

7、使用Generators

生成器支持延遲求值，也就是說，只有當你向它請求下一個值時，裏面的運算式才會被求值，動態處理數據有助於減少記憶體使用並提高效能。尤其是大型數據集中

def test_08_v0(n): # Baseline version (Inefficient way) # (Inefficiently calculates the nth Fibonacci # number using a list) if n <= 1: return n f_list = [0, 1] for i in range(2, n + 1): f_list.append(f_list[i - 1] + f_list[i - 2]) return f_list[n] def test_08_v1(n): # Improved version # (Efficiently calculates the nth Fibonacci # number using a generator) a, b = 0, 1 for _ in range(n): yield a a, b = b, a + b

可以看到提升很明顯:

# Summary Of Test Results Baseline: 0.083 ns per loop Improved: 0.004 ns per loop % Improvement: 95.5 % Speedup: 22.06x

8、map()函式

使用Python內建的map()函式。它允許在不使用顯式for迴圈的情況下處理和轉換可叠代物件中的所有項。

def some_function_X(x): # This would normally be a function containing application logic # which required it to be made into a separate function # (for the purpose of this test, just calculate and return the square) return x**2 def test_09_v0(numbers): # Baseline version (Inefficient way) output = [] for i in numbers: output.append(some_function_X(i)) return output def test_09_v1(numbers): # Improved version # (Using Python's built-in map() function) output = map(some_function_X, numbers) return output

使用Python內建的map()函式代替顯式的for迴圈加速了970x。

# Summary Of Test Results Baseline: 4.402 ns per loop Improved: 0.005 ns per loop % Improvement: 99.9 % Speedup: 970.69x

這是為什麽呢？

map()函式是用C語言編寫的，並且經過了高度最佳化，因此它的內部隱含迴圈比常規的Python for迴圈要高效得多。因此速度加快了，或者可以說Python還是太慢，哈。

9、使用Memoization

記憶最佳化演算法的思想是緩存(或「記憶」)昂貴的函式呼叫的結果，並在出現相同的輸入時返回它們。它可以減少冗余計算，加快程式速度。

首先是低效的版本。

# Example of inefficient code def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 return fibonacci(n - 1) + fibonacci(n-2) def test_10_v0(list_of_numbers): output = [] for i in numbers: output.append(fibonacci(i)) return output

然後我們使用Python的內建functools的lru_cache函式。

# Example of efficient code # Using Python's functools' lru_cache function import functools @functools.lru_cache() def fibonacci_v2(n): if n == 0: return 0 elif n == 1: return 1 return fibonacci_v2(n - 1) + fibonacci_v2(n-2) def _test_10_v1(numbers): output = [] for i in numbers: output.append(fibonacci_v2(i)) return output

結果如下：

# Summary Of Test Results Baseline: 63.664 ns per loop Improved: 1.104 ns per loop % Improvement: 98.3 % Speedup: 57.69x

使用Python的內建functools的lru_cache函式使用Memoization加速57x。

lru_cache函式是如何實作的?

「LRU」是「Least Recently Used」的縮寫。lru_cache是一個裝飾器，可以套用於函式以啟用memoization。它將最近函式呼叫的結果儲存在緩存中，當再次出現相同的輸入時，可以提供緩存的結果，從而節省了計算時間。lru_cache函式，當作為裝飾器套用時，允許一個可選的maxsize參數，maxsize參數決定了緩存的最大大小(即，它為多少個不同的輸入值儲存結果)。如果maxsize參數設定為None，則禁用LRU特性，緩存可以不受約束地增長，這會消耗很多的記憶體。這是最簡單的空間換時間的最佳化方法。

10、向量化

import numpy as np def test_11_v0(n): # Baseline version # (Inefficient way of summing numbers in a range) output = 0 for i in range(0, n): output = output + i return output def test_11_v1(n): # Improved version # (# Efficient way of summing numbers in a range) output = np.sum(np.arange(n)) return output

向量化一般用於機器學習的數據處理庫numpy和pandas

# Summary Of Test Results Baseline: 32.936 ns per loop Improved: 1.171 ns per loop % Improvement: 96.4 % Speedup: 28.13x

11、避免建立中間列表

使用filterfalse可以避免建立中間列表。它有助於使用更少的記憶體。

def test_12_v0(numbers): # Baseline version (Inefficient way) filtered_data = [] for i in numbers: filtered_data.extend(list( filter(lambda x: x % 5 == 0, range(1, i**2)))) return filtered_data

使用Python的內建itertools的filterfalse函式實作相同功能的改進版本。

from itertools import filterfalse def test_12_v1(numbers): # Improved version # (using filterfalse) filtered_data = [] for i in numbers: filtered_data.extend(list( filterfalse(lambda x: x % 5 != 0, range(1, i**2)))) return filtered_data

這個方法根據用例的不同，執行速度可能沒有顯著提高，但透過避免建立中間列表可以降低記憶體使用。我們這裏獲得了131倍的提高

# Summary Of Test Results Baseline: 333167.790 ns per loop Improved: 2541.850 ns per loop % Improvement: 99.2 % Speedup: 131.07x

12、高效連線字串

任何使用+操作符的字串連線操作都會很慢，並且會消耗更多記憶體。使用join代替。

def test_13_v0(l_strings): # Baseline version (Inefficient way) # (concatenation using the += operator) output = "" for a_str in l_strings: output += a_str return output def test_13_v1(numbers): # Improved version # (using join) output_list = [] for a_str in l_strings: output_list.append(a_str) return"".join(output_list)

該測試需要一種簡單的方法來生成一個較大的字串列表，所以寫了一個簡單的輔助函式來生成執行測試所需的字串列表。

from faker import Faker def generate_fake_names(count : int=10000): # Helper function used to generate a # large-ish list of names fake = Faker() output_list = [] for _ in range(count): output_list.append(fake.name()) return output_list l_strings = generate_fake_names(count=50000)

結果如下：

# Summary Of Test Results Baseline: 32.423 ns per loop Improved: 21.051 ns per loop % Improvement: 35.1 % Speedup: 1.54x

使用連線函式而不是使用+運算子加速1.5倍。為什麽連線函式更快?

使用+操作符的字串連線操作的時間復雜度為O(n²)，而使用join函式的字串連線操作的時間復雜度為O(n)。