我正在处理一个子程序,我需要处理矩阵的每一行,并找出当前行中包含的其他行。有关行何时包含另一行的说明,请考虑如下的3x3矩阵:
[[1, 0, 1],
[0, 1, 0],
[1, 0, 0]]
这里第1行包含第3行,因为第1行中的每个元素都大于或等于第3行,但第1行不包含第2行。
我提出了以下解决方案,但由于for循环(矩阵大约为6000x6000大小),它非常慢。
for i in range(no_of_rows):
# Here Adj is the 2D matrix
contains = np.argwhere(np.all(Adj[i] >= Adj, axis = 1))
能不能让我知道是否可以更有效地做到这一点?
由于矩阵的大小以及问题的要求,我认为迭代是不可避免的。你不能利用广播,因为它会爆炸你的内存,所以你需要逐行操作现有的数组。你可以使用numba
和njit
来加速这一过程,而不是纯粹的python方法。
import numpy as np
from numba import njit
@njit
def zero_out_contained_rows(a):
"""
Finds rows where all of the elements are
equal or smaller than all corresponding
elements of anothe row, and sets all
values in the row to zero
Parameters
----------
a: ndarray
The array to modify
Returns
-------
The modified array
Examples
--------
>>> zero_out_contained_rows(np.array([[1, 0, 1], [0, 1, 0], [1, 0, 0]]))
array([[1, 0, 1],
[0, 1, 0],
[0, 0, 0]])
"""
x, y = a.shape
contained = np.zeros(x, dtype=np.bool_)
for i in range(x):
for j in range(x):
if i != j and not contained[j]:
equal = True
for k in range(y):
if a[i, k] < a[j, k]:
equal = False
break
contained[j] = equal
a[contained] = 0
return a
这保持了在另一行中是否使用行的运行记录。这可以防止在通过0
最终消除其他行中包含的行之前通过短路进行许多不必要的比较。
与使用迭代的初始尝试相比,这是一个速度提升,并且还处理零行为正确的行。
a = np.random.randint(0, 2, (6000, 6000))
%timeit zero_out_contained_rows(a)
1.19 s ± 1.87 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
一旦你的尝试结束,我会更新时间(目前约为10分钟)。
如果你有矩阵6000x6000比你需要(6000 * 6000 - 6000)/ 2 = 17997000计算。
您可以尝试使用生成器作为矩阵的顶部三角形,而不是使用np.triu_indices - 它应该减少内存消耗。试试这个,也许会有所帮助..
def indxs(lst):
for i1, el1 in enumerate(lst):
for el2 in lst[i1:][1:]:
yield (el1, el2)