python - 使嵌套循环运行得更快，例如通过 Python 中的矢量化

问题描述

我有一个ids代表间隔的 2 * N 整数数组，其中 N 约为一百万。看起来像这样

 0 2 1 ...
 3 4 3 ...

数组中的整数可以是 0、1、...、M-1，其中 M <= 2N - 1。（详细说明：如果 M = 2N，则整数跨越所有 2N 整数；如果 M < 2N，则有一些整数具有相同的值。）

我需要从计算一种逆映射ids。我所说的“逆映射”是将ids间隔视为间隔并从它们的内部点与它们的索引捕获关系。

直觉直觉上，

 0 2 1 
 3 4 3

可以看作

0 -> 0, 1, 2
1 -> 2, 3
2 -> 1, 2

我的问题排除了右侧端点。“逆”地图将是

0 -> 0
1 -> 0, 2
2 -> 0, 1, 2
3 -> 1

代码我有一段 Python 代码试图在inv 下面的字典中计算逆映射：

  for i in range(ids.shape[1]):
    for j in range(ids[0][i], ids[1][i]):
        inv[j].append(i)

其中 eachinv[j]是一个类似数组的数据，在嵌套循环之前初始化为空。目前我使用python的内置数组来初始化它。

  for i in range(M):  inv[i]=array.array('I')

问题上面的嵌套循环就像一团糟。在我的问题设置中（在图像处理中），我的第一个循环有一百万次迭代；第二个大约 3000 次迭代。它不仅占用大量内存（因为inv它很大），而且速度也很慢。我想在这个问题上关注速度。如何加速上面的这个嵌套循环，例如使用矢量化？

标签： pythonperformancevectorization

解决方案

您可以尝试以下选项，其中，您的外部循环隐藏在 numpy 的 C 语言实现中apply_along_axis()。不确定性能优势，只有相当规模的测试才能说明（尤其是在将列表转换为 numpy 数组时涉及一些初始开销）：

import numpy as np
import array

ids = [[0,2,1],[3,4,3]]
ids_arr = np.array(ids)   # Convert to numpy array. Expensive operation?

range_index = 0   # Initialize. To be bumped up by each invocation of my_func()

inv = {}
for i in range(np.max(ids_arr)):
    inv[i] = array.array('I')

def my_func(my_slice):
    global range_index
    for i in range(my_slice[0], my_slice[1]):
        inv[i].append(range_index)
    range_index += 1

np.apply_along_axis (my_func,0,ids_arr)
print (inv)

输出：

{0: 数组('I', [0]), 1: 数组('I', [0, 2]), 2: 数组('I', [0, 1, 2]), 3: 数组( '我', [1])}

编辑：

我觉得在这里使用字典可能不是一个好主意。我怀疑在这种特殊情况下，字典索引实际上可能比numpy数组索引慢。使用以下几行来创建和初始化inv为numpyPython 数组的数组。其余代码可以保持原样：

inv_len = np.max(ids_arr)
inv = np.empty(shape=(inv_len,), dtype=array.array)
for i in range(inv_len):
    inv[i] = array.array('I')

（注意：这假设您的应用程序没有在dict上执行特定的操作inv，例如inv.items()or inv.keys()。但是，如果是这种情况，您可能需要一个额外的步骤来将 numpy 数组转换为 a dict）

python - 使嵌套循环运行得更快，例如通过 Python 中的矢量化

问题描述

解决方案

推荐阅读