求数组的算术平均,但参数是一个数组,怎么高效实现?

[dwjgwsm]

import numpy as np

a=np.arange(10)

print(a)

b=np.array([2,4,3,5,2,1,4,5,3,2])

c=MA(a,b)

要求输出:
[nan nan 1.  nan 3.5 5.  4.5 5.  7.  8.5]

也就是说,数组每个点的算术平均所使用的参数都可能是不同的.我现在用的办法是 map,速度很慢,想破脑袋也想不到更好的办法,不知道有没有什么高效的实现办法?

[jmc891205]

算术平均不是求和除以个数吗？
你这个结果是什么 看不懂

[vegito2002]

看不懂问题

[ericls]

我估计 MA 是 moving average 吧…… ？？

[noe132]

看不懂问题+1

[wizardforcel]

MA ？？ np.convolve 了解一下。。

[kysida]

试试 numpy.mean()???

[RecursiveG]

楼主的表达能力堪忧啊。
我估计楼主是想要实现 `c[i]=avg(a[i-b[i]+1:i+1]) if i-b[i]+1>=0 else NaN`
不担心数字太小的话可以先算 a 的前缀和。

[RecursiveG]

更正：不担心数字太大的话可以先算 a 的前缀和

[Kirscheis]

论 dp 在计算机编程中的经典应用

[dwjgwsm]

抱歉,是我大意了,我以为都能看懂呢,MA 是我自己写的移动平均函数,用的 map 遍历.我想来想去觉得想找更好算法这个问题无解. 卷积,我也想过,问题是每个元素的权重都不同吧. 我没有信心了,想弃楼了

[dwjgwsm]

@kysida map(fun,a,b)的 fun 里面就是用的 np.mean 返回.

[dwjgwsm]

@jmc891205 比如最后一个 8.5=(a[8]+a[9])/b[9]

[Kirscheis]

我靠，出去玩了一天你这个帖子竟然还没有人给实现。。。看来你的表达 v 友估计都没看懂
这就是 dp 的例题啊老哥

首先假设你的 a，b 长度都是 n。如果不是，rightpad b。O(1)
在 a 后面 append INFINITY，然后把 a 变成循环数组，并且以下所说的数组都是循环数组。O(1)
b 实际上是区间集，把它转换成左右指标的集 c。O(n)
d = sorted(c)。O(nlogn)
初始化二维 array dp[2n][2n]。O(1)
//求 dp，O(n)
for i in range(len(c)):
dp [ d[i] ] [ d[i+1] ] = sum( a [d[i], d[i+1]] )
最后，把区间碎片的和拼接成所需的和，存进 e。worst case O(n)
ans = e ./ b，./是 element-wise division。O(n)
最后检查 ans，把所有 INFINITY 替换成 NaN。O(n)

总复杂度 O(nlogn)，和排序差不多

[dwjgwsm]

@Kirscheis 对的,a b 数组长度相等, 我再描述一下吧,我们计算平均值,都有个参数 n:n 个数字的平均值, 在这里,数组 b=np.array([2,4,3,5,2,1,4,5,3,2])的每个元素都是对应位置的 n ,比如返回数组是 result_arr,则:

result_arr[9]=(a[8]+a[9])/b[9] #b[9]==2,所以是 2 个元素的平均值
result_arr[8]=(a[6]+a[7]+a[8])/b[8] #b[8]==3,所以是 3 个元素的平均值

不过大哥,你说的我表示完全看不懂啊. 你说"这是 dp 的例题",出自哪里啊?

[jmc891205]

@dwjgwsm 懂你的题目了
一种做法是可以先用数组 a 构建一棵线段树 然后遍历 b 去线段树上查询你需要的区间的和

[aijam]

quick and dirty: [np.mean(a[i - size + 1: i+1]) if i - size + 1 >= 0 else np.NaN for i, size in enumerate(b)]

[dwjgwsm]

@aijam 我就是这么做的,不过我是用 map 一个子函数来实现的,子函数做了一点参数检查

[dwjgwsm]

@jmc891205 我觉得恐怕不行,线段树的每个数组起始点和结束点不同.

[wingkou]

@dwjgwsm 前缀和很好啊，像 @RecursiveG 所说。线段树也行啊 像 @jmc891205，跟起始终止没关系吧？

[Kirscheis]

@dwjgwsm 晕了，不知道你有没有算法背景，我上面讲的都是一些很简单的概念啊。。建议你再去随便找本算法书看看 dynamic programming 的章节。。
我再倒着给你讲一遍好了

你要的最后的结果是一个列表，而你的 b 列表里的元素实际上就是除因子，所以这个问题本质是求 a 列表中一些不同长度和起始点的区间的和。你的 b 列表给出了这些区间的起始范围，所以可以转化成坐标对的形式。直接对这些坐标排序，实际上是裂解了你要求的那些区间

举例，比如你想求一个列表在这些区间的和：(2, 10), (5, 7), (3, 16), (8, 23)
对坐标排序给出 ((2,3,5,7,8,10,16,23))
依次求出上面这些小区间的局部和，并且存在一个表格里，那么将来要用的时候就不用反复求和了。这一步操作只需要线性时间
那么就有 sum(2, 10) = sum(2, 3)+ sum(3, 5)+ sum(5, 7)+ sum(7, 8) + sum(8, 10)
其它区间类似
最后把这些区间和的每一项除以 b 列表的对应元素 (element-wise division)，就是你要的那些平均值了，这一步也是线性时间的
以上这些算法我设计的时候都考虑了并行优化，也就是说它们都是可以直接 GPU/FPGA 加速的。如果你的数据集真的很大，这个算法的耗时和快排是基本一样的

这样讲你能明白吗。。再不明白我就没办法了😂

至于为什么要在 a 后面 append 一个 INFINITY，再把 a 变成循环数组，这是因为你的区间有可能会 index out of range，这样干了之后任何 index out of range 的区间的局部和都是 INFINITY，求平均之后还是 INFINITY。因此，你最后检查一遍结果，如果发现 INFINITY，就知道这个元素对应的区间 index out of range 了，于是就把它换成 NaN。这是一个设计算法的时候常用的技巧，在具体实现的时候，把 INFINITY 设置成一个很大的常数，比如在 64 位机上 0xEFFFFFFFFFFFFFFF，规定这个数附近的数都是 INFINITY 就可以了