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

Question

我有一个 2 * N 整数数组 ids 表示间隔，其中 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)

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

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

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

Answer 1

避免for循环，只是一个pandas样本

import numpy as np
import pandas as pd

df = pd.DataFrame({
    "A": np.random.randint(0, 100, 100000),
    "B": np.random.randint(0, 100, 100000)
})

df.groupby("B")["A"].agg(list)

Answer 2

您可以尝试以下选项，其中，您的外循环隐藏在 numpy 的 C-language 实现 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: array('I', [0]), 1: array('I', [0, 2]), 2: array('I', [0, 1, 2]), 3: array('I', [1])}

编辑：

我觉得在这里使用字典可能不是一个好主意。我怀疑在这个特定的上下文中，dictionary-indexing 实际上可能比 numpy 数组索引慢。使用以下行创建 inv 并将其初始化为 Python 数组的 numpy 数组。其余代码可以保持as-is:

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')

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

Answer 3

由于N的阶数很大，我想出了一个看似实用的方法；如果有任何缺陷，请告诉我。

对于ith区间为[x,y]，存储为[x,y,i]。根据开始和结束时间对数组进行排序。这应该花费 O(NlogN) 时间。
创建频率数组freq[2*N+1]。对于每个间隔，使用 range update in O(1) per update 的概念更新频率。生成频率在 O(N) 中完成。
根据您的数据确定一个阈值。根据该值，可以将元素指定为稀疏或频繁。对于稀疏元素，什么也不做。仅对于频繁元素，存储它们出现的间隔。
查找时，如果有频繁出现的元素，可以直接访问pre-computed列表。如果元素是稀疏元素，则可以在 O(logN) 时间内搜索间隔，因为间隔已排序并且在步骤 1 中附加了索引。

这对我来说似乎是一种实用的方法，其余取决于您的使用情况。比如每个查询所需的分摊时间复杂度等等。

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

Making the nested loop run faster, e.g. by vectorization in Python

python

performance

vectorization

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

Making the nested loop run faster, e.g. by vectorization in Python

python

performance

vectorization

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