python - 相对于原点累积滑动窗口
问题描述
A
我有一个形状的数组,(3,3)
它可以被认为是形状为 的未知数组的滑动窗口视图(5,)
。我想用 shape 计算数组的倒数(5,)
。这个的伴随操作将是求和。我的意思是,我想将每个对应窗口中的值与数组中的相关位置累积起来,形状为(5,)
. 当然,我对这个反函数的预期输出和输入A
是不相关的,只是普通的数组。我有两个例子,希望能更好地解释这一点。
A = np.array([[0, 0, 1],
[0, 0, 1],
[0, 0, 1]], dtype=np.float32)
我期望这个输出:
np.array([0, 0, 1, 1, 1])
另一个例子:
A = np.array([[1, 2, 3],
[2, 3, 4],
[3, 4, 5]], dtype=np.float32)
我期望这个输出:
np.array([1, 2+2, 3+3+3, 4+4, 5]) = np.array([1, 4, 9, 8, 5])
我的解决方案很慢(结果存储在out
)
out = np.zeros(5, dtype=np.float32)
windows = np.lib.stride_tricks.as_strided(out, shape=(3,3), strides=(4,4))
for i in np.ndindex(windows.shape):
windows[i] += A[i]
写入跨步视图感觉有点 hacky,我相信有更好的解决方案。
有没有办法以向量化的方式编写这个,没有for循环?(也适用于多个维度)
编辑
就更高维度的泛化而言,我有一些情况是从图像(二维数组)中获取窗口,而不是像上面的示例那样从一维数组中获取。对于 2d 情况,A
例如可以是大小为 的窗口3
。这意味着从具有形状的图像(输出)中(4,4)
,窗口A
将具有形状(2,2,3,3)
。
A = np.array([[[[0, 0, 0],
[0, 1, 0],
[0, 0, 0]],
[[0, 0, 0],
[1, 0, 0],
[0, 0, 0]]],
[[[0, 1, 0],
[0, 0, 0],
[0, 0, 0]],
[[1, 0, 0],
[0, 0, 0],
[0, 0, 0]]]], dtype=np.float32)
使用 Pablo 给出的解决方案,我收到以下错误
value array of shape (2,2,3,3) could not be broadcast to indexing result of shape (2,2)
使用我的跨步解决方案的略微修改版本:
def inverse_sliding_windows(A, window_sz, image_sz):
out = np.zeros(image_sz, dtype=np.float32)
windows = np.lib.stride_tricks.sliding_window_view(out, window_sz, writeable=True)
for i in np.ndindex(windows.shape):
windows[i] += A[i]
window_sz = (3,3)
image_sz = (4,4)
inverse_sliding_windows(A, window_sz, image_sz)
输出:
array([[0., 0., 0., 0.],
[0., 4., 0., 0.],
[0., 0., 0., 0.],
[0., 0., 0., 0.]], dtype=float32)
为了澄清,窗口大小和输出形状是预先知道的,请参阅inverse_sliding_windows
。
解决方案
正如我在评论中提到的,矢量化解决方案并不总能保证更好的运行时间。如果您的矩阵很大,您可能更喜欢更有效的方法。矩阵旋转缓慢的原因有几个(尽管很直观),请参阅评论。
性能对比:
Solution: Wall time: 61.6 ms
Rotation: Wall time: 3.32 s
代码(在 jupyter notebook 中测试)
import numpy as np
def rotate45_and_sum(A):
n = len(A)
x, y = np.meshgrid(np.arange(n), np.arange(n)) # at least doubled the running time
xn, yn = x + y, n - x + y - 1 # generating xn and yn at least doubled the running time
M = np.zeros((2*n -1, 2*n -1)) # at least slows down running time by a factor of 4
M[xn,yn] = A[x,y] # very inefficient indexing strategy
return M.sum(1)
def solution(A):
n = A.shape[0]
retval = np.zeros(2*n-1)
for i in range(n):
retval[i:(i+n)] += A[i, :]
return retval
A = np.random.randn(10000, 10000)
%time solution(A)
%time rotate45_and_sum(A)
在多维情况下:
def solution(A):
h,w,x,y = A.shape # change here
retval = np.zeros((2*x-w,2*y-h)) # change here
indices = np.ndindex(w, h) # change here
for index in indices:
slices = tuple()
for i in range(len(index)):
slices = slices + (slice(index[i], index[i]+x),) # I assume x = y = ..., you need to change here also if the assumption is not correct
retval[slices] += A[index] # slices is roughly equal `i:(i+x), j:(j+y)` in your code
return retval
实际上我不知道如何根据您的描述计算尺寸(或形状):(。但我认为它可以概括。这个想法是随手构建slices
。所以你需要指定哪些尺寸对应h, w
,对应于x, y
. 我认为做到这一点并不难。
关于https://stackoverflow.com/a/67341994/14923227
def fast(A):
n = A.shape[0]
retval = np.zeros(2*n-1)
for i in range(n):
retval[i:(i+n)] += A[i, :]
print(retval.sum())
return retval
##########################
import threading
class sumThread(threading.Thread):
def __init__(self, A, mat, threadID, ngroups, size):
threading.Thread.__init__(self)
self.threadID = threadID
self.size = size
self.ngroups = ngroups
self.mat = mat
self.A = A
def run(self):
begin = (self.size + self.ngroups) // self.ngroups * self.threadID
end = min(self.size, (self.size+self.ngroups)//self.ngroups*(self.threadID+1))
for i in range(begin, end):
self.mat[self.threadID, i:(i+self.size)] += self.A[i, :]
def faster(A):
num_threads = max(1, A.shape[0] // 4000)
mat = np.zeros((num_threads, 2*A.shape[0]-1))
threads = []
for i in range(num_threads):
t = sumThread(A, mat, i, num_threads, A.shape[0])
t.start()
threads.append(t)
# Wait for all threads to complete
for t in threads:
t.join()
return np.sum(mat, axis=0)
大型阵列的性能:
A = np.random.randn(20000,20000)
%timeit fast(A) # 263 ms ± 5.21 ms per loop
%timeit faster(A) # 155 ms ± 3.14 ms per loop
for
将循环并行化很简单fast
。但fast
实际上是最高效的缓存(即使对于 GPU 缓存和内存库),因此是计算它的最快方法。理想情况下,您可以使用 CUDA/OpenCL 并行化代码,因为 GPU 中有更多内核。如果你做得正确,运行时间将减少到log(original_fast_time)
base k
,这k
是你拥有的核心数量。
但是,该函数中只有少量计算。因此,内存和 GRAM 之间的数据传输可能占主导地位。(我没有测试过)
推荐阅读
- javascript - 如何使用 jquery 切换具有垂直文本和内容的垂直选项卡
- asp.net-core - NuGet.targets 错误:'.',十六进制值 0x00,升级到 .Net Core 2.1.1 后是无效字符
- javascript - 在我的数组显示中删除 NaN
- google-drive-api - 谷歌驱动器中的文件夹为空,已删除的文件未显示在垃圾箱中
- android - 为什么 ConstraintLayout 1.1.0 layout_constraintWidth_percent 和 layout_constraintDimensionRatio 不能一起工作?
- python - 如何将彩色颗粒图像转换为黑白 (0,1) 以使晶界保持可识别
- c# - 使用 AutoMapper 将 id 列表转换为 Object
- javascript - 用户脚本跨域请求失败
- oauth-2.0 - 使用 Auth0 的身份验证过程将用户从我们的应用程序转移到另一个位置
- c# - 如何从 TranslateZoomRotateBehavior 禁用旋转手势