python 双层嵌套循环

477 字

2 分钟

python 双层嵌套循环

2023-07-26

编程

Python

前言#

分析 python 中如何设置双层嵌套循环效率最高：

数组的遍历方式
内外层循环数

实验#

案例1 内外层循环数量相同，比较数组遍历方式的效率#

内层对列遍历，外层对行遍历，平均用时 15.16065s

1
mat = np.zeros((10000, 10000))
2
for h in range(height):
3
    for w in range(width):
4
        a = mat[h, w]

内层对行遍历，外层对列遍历，平均用时 16.26099

1
mat = np.zeros((10000, 10000))
2
for w in range(width):
3
    for h in range(height):
4
        a = mat[h, w]

案例2 循环总数量相同，内外层循环数量不同#

内存循环数量比外层循环数量多，平均用时 282.56361s

1
for _ in range(10):
2
    for _ in range(10000000):
3
        a = 0
4
        for _ in range(10):
5
            a = a + 1.1
6
            a = a * 1.1
7
            a = 0

外层循环数量比内存循环数量多，平均用时 282.43570

1
for _ in range(10000000):
2
    for _ in range(10):
3
        a = 0
4
        for _ in range(10):
5
            a = a + 1.1
6
            a = a * 1.1
7
            a = 0

结论#

相同任务下，按行遍历比按列遍历更快：连续内存的调度相比非连续内存更快
相同任务下，内外层循环数量差别很小：Cache 的命中率

完整代码#

1
import time
2
import numpy as np
3

4
times = [[], []]
5
for _ in range(10):
6
    time.sleep(1)
7
    mat = np.zeros((10000, 10000))
8
    height, width = mat.shape
9
    begin_time = time.time()
10
    for h in range(height):
11
        for w in range(width):
12
            a = mat[h, w]
13
    cost_time1 = time.time() - begin_time
14

15
    time.sleep(1)
16
    mat = np.zeros((10000, 10000))
17
    height, width = mat.shape
18
    begin_time = time.time()
19
    for w in range(width):
20
        for h in range(height):
21
            a = mat[h, w]
22
    cost_time2 = time.time() - begin_time
23

24
    times[0].append(cost_time1)
25
    times[1].append(cost_time2)
26

27
print(f"按行遍历 {np.average(times[0]):.5f}s")
28
print(f"按列遍历 {np.average(times[1]):.5f}s")
29

30
times = [[], []]
31
for _ in range(10):
32
    time.sleep(1)
33
    a = 0
34
    begin_time = time.time()
35
    for _ in range(10):
36
        for _ in range(10000000):
37
            a = 0
38
            for _ in range(10):
39
                a = a + 1.1
40
                a = a * 1.1
41
                a = 0
42
    cost_time1 = time.time() - begin_time
43

44
    time.sleep(1)
45
    begin_time = time.time()
46
    for _ in range(10):
47
        for _ in range(10000000):
48
            a = 0
49
            for _ in range(10):
50
                a = a + 1.1
51
                a = a * 1.1
52
                a = 0
53
    cost_time2 = time.time() - begin_time
54

55
    times[0].append(cost_time1)
56
    times[1].append(cost_time2)
57

58
print(f"内循环多 {np.average(times[0]):.5f}s")
59
print(f"外循环多 {np.average(times[1]):.5f}s")